Multimnožina

Multimnožina (multiset, množina s opakováním, bag) je datový typ vycházející z množiny. Multimnožina slouží jako kontejner na entity, jenž negarantuje pořadí uložených prvků, a který může obsahovat jednotlivé prvky (hodnoty) vícekrát.

Implementace

Nejjednodušším způsobem implementace je použít list a zapomenout na pořadí. Tento způsob je ovšem velmi neefektivní z hlediska použité paměti, pokud se prvky často opakují. Druhou možností je využití dvojice seznamů, z nichž ten první obsahuje hodnoty a druhý zaznamenává počty jejich výskytů. Tento postup je efektivnější, ale stále vyžaduje poměrně náročnou operaci průchodu seznamem pro přístup k jednotlivým položkám (asymptotická složitost O(n) ). Z tohoto důvodu se pro efektivní implementaci využívá hashovací tabulka, která umožňuje přístup k položkám s očekávanou konstantní složitostí.

Kód

Java

 /**
  * Multimnozina implementovana pomoci dvojice seznamu
  * @author Pavel Micka
  * @param <ENTITY> typovy parametr obsahu
  */
 public class Multiset<VALUE> {
 
     private List<VALUE> values;
     private List<Integer> occurences;
 
     /**
      * Konstruktor
      * @param initialCapacity kapacita, se kterou je inicializovan podrizeny seznam
      */
     public Multiset(int initialCapacity) {
         values = new ArrayList<VALUE>(initialCapacity);
         occurences = new ArrayList<Integer>(initialCapacity);
     }
 
     /**
      * Vlozi entitu do multimnoziny
      * @param val dana entita
      * @return pocet vyskytu entity po jejim pridani
      */
     public int put(VALUE val) {
         int index = values.indexOf(val);
         if (index == -1) {
             values.add(val);
             occurences.add(1);
             return 1;
         } else {
             int currCount = occurences.get(index);
             occurences.set(index, currCount + 1);
             return currCount + 1;
         }
     }
 
     /**
      * Vrati nahodne nejaky prvek z mnoziny (a snizi pocet jeho vyskytu o 1)
      * @return prvek, @null pokud je mnozina prazdna
      */
     public VALUE pick() {
         if (values.size() == 0) {
             return null;
         }
         if (occurences.get(0) == 1) {
             VALUE v = values.remove(0);
             occurences.remove(0);
             return v;
         } else {
             VALUE v = values.get(0);
             occurences.set(0, occurences.get(0) - 1);
             return v;
         }
     }
 
     /**
      * Odstrani z mnoziny danou entitu (snizi pocet vyskytu o 1)
      * @param val entita
      * @return pocet vyskytu po odstraneni dane entity
      */
     public int remove(VALUE e) {
         int index = values.indexOf(e);
         int curr = occurences.get(index);
         if (curr != 1) {
             occurences.set(index, curr - 1);
             return curr - 1;
         } else {
             values.remove(index);
             occurences.remove(index);
             return 0;
         }
     }
 
     /**
      *
      * Dotaz na pritomnost dane entity
      * @param val entita
      * @return pocet vyskytu dane entity
      */
     public int contains(VALUE e) {
         int index = values.indexOf(e);
         if(index == -1) return 0;
         return occurences.get(index);
     }
 
     /**
      * Dotaz na velikost mnoziny (vcetne multiplicit)
      * @return pocet prvku
      */
     public int size() {
         int count = 0;
         for(Integer i : occurences){
             count += i;
         }
         return count;
     }
 }

Implementace

Kód

Doporučujeme