Multimnožina
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

01./**
02. * Multimnozina implementovana pomoci dvojice seznamu
03. * @author Pavel Micka
04. * @param <ENTITY> typovy parametr obsahu
05. */
06.public class Multiset<VALUE> {
07. 
08.    private List<VALUE> values;
09.    private List<Integer> occurences;
10. 
11.    /**
12.     * Konstruktor
13.     * @param initialCapacity kapacita, se kterou je inicializovan podrizeny seznam
14.     */
15.    public Multiset(int initialCapacity) {
16.        values = new ArrayList<VALUE>(initialCapacity);
17.        occurences = new ArrayList<Integer>(initialCapacity);
18.    }
19. 
20.    /**
21.     * Vlozi entitu do multimnoziny
22.     * @param val dana entita
23.     * @return pocet vyskytu entity po jejim pridani
24.     */
25.    public int put(VALUE val) {
26.        int index = values.indexOf(val);
27.        if (index == -1) {
28.            values.add(val);
29.            occurences.add(1);
30.            return 1;
31.        } else {
32.            int currCount = occurences.get(index);
33.            occurences.set(index, currCount + 1);
34.            return currCount + 1;
35.        }
36.    }
37. 
38.    /**
39.     * Vrati nahodne nejaky prvek z mnoziny (a snizi pocet jeho vyskytu o 1)
40.     * @return prvek, @null pokud je mnozina prazdna
41.     */
42.    public VALUE pick() {
43.        if (values.size() == 0) {
44.            return null;
45.        }
46.        if (occurences.get(0) == 1) {
47.            VALUE v = values.remove(0);
48.            occurences.remove(0);
49.            return v;
50.        } else {
51.            VALUE v = values.get(0);
52.            occurences.set(0, occurences.get(0) - 1);
53.            return v;
54.        }
55.    }
56. 
57.    /**
58.     * Odstrani z mnoziny danou entitu (snizi pocet vyskytu o 1)
59.     * @param val entita
60.     * @return pocet vyskytu po odstraneni dane entity
61.     */
62.    public int remove(VALUE e) {
63.        int index = values.indexOf(e);
64.        int curr = occurences.get(index);
65.        if (curr != 1) {
66.            occurences.set(index, curr - 1);
67.            return curr - 1;
68.        } else {
69.            values.remove(index);
70.            occurences.remove(index);
71.            return 0;
72.        }
73.    }
74. 
75.    /**
76.     *
77.     * Dotaz na pritomnost dane entity
78.     * @param val entita
79.     * @return pocet vyskytu dane entity
80.     */
81.    public int contains(VALUE e) {
82.        int index = values.indexOf(e);
83.        if(index == -1) return 0;
84.        return occurences.get(index);
85.    }
86. 
87.    /**
88.     * Dotaz na velikost mnoziny (vcetne multiplicit)
89.     * @return pocet prvku
90.     */
91.    public int size() {
92.        int count = 0;
93.        for(Integer i : occurences){
94.            count += i;
95.        }
96.        return count;
97.    }
98.}

SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz

Hrajte nejlepší hry jako je GoodGame Empire.





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?, Čeká vás pracovní pohovor mimo město? Podívejte se, jak dokonale zvládnout včasný příchod, 5 úžasných technologií ze světa hazardních her, Mirror and access to Mostbet, Svou kancelář můžete mít stále po ruce, Jaké výhody má digitalizovaná firma oproti off-line konkurenci?, Jaký systém vybrat pro snadné řízení výroby?, Nahradí umělá inteligence ajťáky?, Důvody, proč používat SnapTik ke stahování videí TikTok, Dokonalý den na pláži: Co si vzít s sebou, aby byl výlet zábavný a bezpečný?, Jak přežít dlouhý let?, Go pay GoodGame Empire, Blockchain, Rozhovor, Umělá inteligence


Doporučujeme

Internet pro vaši firmu na míru

https://www.algoritmy.net