Získanie výkonovej súpravy súpravy v Jave
1. Úvod
V tomto výučbe sa budeme zaoberať procesom generovania sady napájania danej sady v prostredí Java.
Ako rýchla pripomienka pre každú sadu veľkostí n, existuje výkonová sada veľkosti 2n. Naučíme sa, ako to získať pomocou rôznych techník.
2. Definícia súpravy napájania
Výkonová sada danej množiny S je množina všetkých podskupín súboru S, počítajúc do toho S sám a prázdna súprava.
Napríklad pre danú množinu:
{"APPLE", "ORANGE", "MANGO"}sada napájania je:
{{}, {"APPLE"}, {"ORANGE"}, {"APPLE", "ORANGE"}, {"MANGO"}, {"APPLE", "MANGO"}, {"ORANGE", "MANGO" }, {„JABLKO“, „ORANŽOVÁ“, „MANGO“}}Pretože sa jedná tiež o množinu podmnožín, poradie jej vnútorných podmnožín nie je dôležité a môžu sa zobrazovať v ľubovoľnom poradí:
{{}, {"MANGO"}, {"ORANGE"}, {"ORANGE", "MANGO"}, {"APPLE"}, {"APPLE", "MANGO"}, {"APPLE", "ORANGE" }, {„JABLKO“, „ORANŽOVÁ“, „MANGO“}}3. Knižnica Guava
Knižnica Google Guava má niekoľko užitočných Nastaviť pomocné programy, ako napríklad súprava napájania. Môžeme ho teda ľahko použiť aj na získanie množiny výkonov danej množiny:
@Test public void givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets () {ImmutableSet set = ImmutableSet.of ("APPLE", "ORANGE", "MANGO"); Nastaviť powerSet = Sady.powerSet (sada); Assertions.assertEquals ((1 << set.size ()), powerSet.size ()); MatcherAssert.assertThat (powerSet, Matchers.containsInAnyOrder (ImmutableSet.of (), ImmutableSet.of ("APPLE"), ImmutableSet.of ("ORANGE"), ImmutableSet.of ("APPLE", "ORANGE"), ImmutableSet.of („MANGO“), ImmutableSet.of („APPLE“, „MANGO“), ImmutableSet.of („ORANGE“, „MANGO“), ImmutableSet.of („APPLE“, „ORANGE“, „MANGO“))) ; } Guava powerSet interne funguje nad Iterátor spôsobom, keď sa požaduje ďalšia podmnožina, sa podmnožina vypočíta a vráti. Takže priestorová zložitosť je znížená na O (n) namiesto O (2n).
Ako to ale Guava dosahuje?
4. Prístup k generovaniu napájacieho súboru
4.1. Algoritmus
Poďme teraz diskutovať o možných krokoch na vytvorenie algoritmu pre túto operáciu.
Sada napájania prázdnej sady je {{}} v ktorom obsahuje iba jednu prázdnu množinu, takže to je náš najjednoduchší prípad.
Za každú sadu S okrem prázdnej množiny najskôr extrahujeme jeden prvok a pomenujeme ho - element. Potom pre ostatné prvky množiny subsetWithoutElement, vypočítame ich výkonovú sadu rekurzívne - a pomenujeme to nejako powerSetSubsetWithoutElement. Potom pridaním extrahovaného element do všetkých sád powerSetSubsetWithoutElement, dostaneme powerSetSubsetWithElement.
Teraz je nastavená sila S je spojenie a powerSetSubsetWithoutElement a a powerSetSubsetWithElement:
Pozrime sa na príklad zásobníka rekurzívnej výkonovej sady pre danú množinu {„APPLE“, „ORANGE“, „MANGO“}.
Na zlepšenie čitateľnosti obrázka používame krátke formy mien: P znamená funkciu nastavenia výkonu a „A“, „O“, „M“ sú krátke formy „APPLE“, „ORANGE“, a „MANGO“, v uvedenom poradí:
4.2. Implementácia
Najprv teda napíšme kód Java na extrakciu jedného prvku a získajme zvyšné podmnožiny:
T prvok = set.iterator (). Next (); Nastaviť podmnožinuWithoutElement = nový HashSet (); pre (T s: set) {if (! s.equals (element)) {subsetWithoutElement.add (s); }}Potom budeme chcieť získať množinu subsetWithoutElement:
Nastaviť powersetSubSetWithoutElement = recursivePowerSet (podmnožinaWithoutElement); Ďalej musíme túto sadu napájania pridať späť do pôvodnej verzie:
Nastaviť powersetSubSetWithElement = nový HashSet (); for (Set subsetWithoutElement: powerSetSubSetWithoutElement) {Set subsetWithElement = new HashSet (subsetWithoutElement); subsetWithElement.add (element); powerSetSubSetWithElement.add (subsetWithElement); } Nakoniec spojenie powerSetSubSetWithoutElement a powerSetSubSetWithElement je výkonová sada danej vstupnej sady:
Nastaviť powerSet = nový HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); Ak spojíme všetky naše útržky kódu, uvidíme náš konečný produkt:
verejná sada recursivePowerSet (Set set) {if (set.isEmpty ()) {Set ret = nový HashSet (); ret.add (sada); návrat ret; } T element = set.iterator (). Next (); Nastaviť subSetWithoutElement = getSubSetWithoutElement (množina, prvok); Nastaviť powerSetSubSetWithoutElement = recursivePowerSet (subSetWithoutElement); Nastaviť powerSetSubSetWithElement = addElementToAll (powerSetSubSetWithoutElement, prvok); Nastaviť powerSet = nový HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); sada spätného napájania; } 4.3. Poznámky k jednotkovým testom
Teraz poďme otestovať. Máme tu niekoľko kritérií na potvrdenie:
- Najskôr skontrolujeme veľkosť sady napájania a musí byť 2n pre množinu veľkostí n.
- Potom sa každý prvok vyskytne iba raz v podmnožine a 2n-1 rôzne podmnožiny.
- Nakoniec sa každá podmnožina musí zobraziť raz.
Ak všetky tieto podmienky pominú, môžeme si byť istí, že naša funkcia funguje. Teraz, keď sme použili Nastaviť, už vieme, že sa to nemôže opakovať. V takom prípade stačí skontrolovať veľkosť sady napájania a počet výskytov každého prvku v podmnožinách.
Na kontrolu veľkosti sady napájania môžeme použiť:
MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ())));A skontrolovať počet výskytov každého prvku:
Počítadlo mapy = nový HashMap (); for (Set subset: powerSet) {for (String name: subset) {int num = counter.getOrDefault (name, 0); counter.put (meno, počet + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ()));Nakoniec, ak môžeme dať všetko dohromady do jedného testu jednotky:
@Test public void givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets () {Set set = RandomSetOfStringGenerator.generateRandomSet (); Nastaviť powerSet = nový PowerSet (). recursivePowerSet (sada); MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ()))); Počítadlo mapy = nový HashMap (); for (Set subset: powerSet) {for (String name: subset) {int num = counter.getOrDefault (name, 0); counter.put (meno, počet + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ())); } 5. Optimalizácia
V tejto časti sa pokúsime minimalizovať priestor a znížiť počet interných operácií, aby sme optimálnym spôsobom vypočítali nastavený výkon.
5.1. Dátová štruktúra
Ako vidíme na danom prístupe, potrebujeme veľa odčítaní pri rekurzívnom volaní, ktoré zaberá veľké množstvo času a pamäte.
Namiesto toho môžeme každú množinu alebo podmnožinu namapovať na iné pojmy, aby sme znížili počet operácií.
Najprv musíme každému objektu v danej množine priradiť zvyšujúce sa číslo začínajúce od 0 S čo znamená, že pracujeme s usporiadaným zoznamom čísel.
Napríklad pre danú množinu {„APPLE“, „ORANGE“, „MANGO“} dostaneme:
„JABLKO“ -> 0
„ORANŽOVÝ“ ->
„MANGO“ -> 2
Takže odteraz namiesto generovania podmnožín súboru S, vygenerujeme ich pre zoradený zoznam [0, 1, 2] a keď je zoradené, môžeme simulovať odčítania pomocou počiatočného indexu.
Napríklad ak je počiatočný index 1, znamená to, že generujeme množinu výkonov [1,2].
Na získanie mapovaného id z objektu a naopak uložíme obe strany mapovania. Na našom príklade uložíme oboje („MANGO“ -> 2) a (2 -> „MANGO“). Pretože mapovanie čísel začalo od nuly, pre reverznú mapu môžeme na získanie príslušného objektu použiť jednoduché pole.
Jednou z možných implementácií tejto funkcie by bolo:
súkromná mapa mapa = nová HashMap (); private List reverseMap = new ArrayList (); private void initializeMap (kolekcia kolekcie) {int mapId = 0; pre (T c: kolekcia) {map.put (c, mapId ++); reverseMap.add (c); }}Teraz, aby sme reprezentovali podmnožiny, existujú dva známe nápady:
- Reprezentácia indexu
- Binárne zastúpenie
5.2. Reprezentácia indexu
Každá podmnožina je reprezentovaná indexom jej hodnôt. Napríklad indexové mapovanie danej množiny {„APPLE“, „ORANGE“, „MANGO“} bolo by:
{{} -> {} [0] -> {"APPLE"} [1] -> {"ORANGE"} [0,1] -> {"APPLE", "ORANGE"} [2] -> {" MANGO "} [0,2] -> {" APPLE "," MANGO "} [1,2] -> {" ORANGE "," MANGO "} [0,1,2] -> {" APPLE "," ORANŽOVÁ "," MANGO "}}Môžeme teda načítať príslušnú množinu z podmnožiny indexov s daným mapovaním:
súkromná sada unMapIndex (sada sady) {Sada ret = nový HashSet (); for (Set s: sets) {HashSet subset = new HashSet (); for (Integer i: s) {subset.add (reverseMap.get (i)); } ret.add (podmnožina); } návrat ret; } 5.3. Binárne zastúpenie
Alebo môžeme každú podmnožinu reprezentovať pomocou binárneho súboru. Ak v tejto podmnožine existuje prvok aktuálnej množiny, jeho príslušná hodnota je 1; inak je 0.
Pre náš ovocný príklad by bola sada výkonu:
{[0,0,0] -> {} [1,0,0] -> {"APPLE"} [0,1,0] -> {"ORANGE"} [1,1,0] -> { „APPLE“, „ORANGE“} [0,0,1] -> {„MANGO“} [1,0,1] -> {„APPLE“, „MANGO“} [0,1,1] -> { „ORANGE“, „MANGO“} [1,1,1] -> {„APPLE“, „ORANGE“, „MANGO“}}Môžeme teda získať príslušnú množinu z binárnej podmnožiny s daným mapovaním:
súkromná sada unMapBinary (zbierka sady) {Sada ret = nový HashSet (); pre (Zoznamy: sady) {podmnožina HashSet = nová HashSet (); for (int i = 0; i <s.size (); i ++) {if (s.get (i)) {subset.add (reverseMap.get (i)); }} ret.add (podmnožina); } návrat ret; }
5.4. Implementácia rekurzívneho algoritmu
V tomto kroku sa pokúsime implementovať predchádzajúci kód pomocou oboch dátových štruktúr.
Predtým, ako zavoláte jednu z týchto funkcií, musíme zavolať initializeMap spôsob získania zoradeného zoznamu. Tiež po vytvorení našej dátovej štruktúry musíme zavolať príslušné unmap funkcia na získanie skutočných objektov:
verejná sada recursivePowerSetIndexRepresentation (sada kolekcií) {initializeMap (sada); Nastaviť powerSetIndices = recursivePowerSetIndexRepresentation (0, set.size ()); návrat unMapIndex (powerSetIndices); } Skúsme teda indexovú reprezentáciu:
súkromná sada recursivePowerSetIndexRepresentation (int idx, int n) {if (idx == n) {Set prázdny = nový HashSet (); empty.add (nový HashSet ()); vrátiť sa prázdny; } Nastav powerSetSubset = recursivePowerSetIndexRepresentation (idx + 1, n); Nastaviť powerSet = nový HashSet (powerSetSubset); for (Set s: powerSetSubset) {HashSet subSetIdxInclusive = new HashSet (s); subSetIdxInclusive.add (idx); powerSet.add (subSetIdxInclusive); } návrat powerSet; } Teraz sa pozrime na binárny prístup:
súkromná sada recursivePowerSetBinaryRepresentation (int idx, int n) {if (idx == n) {Set powerSetOfEmptySet = nový HashSet (); powerSetOfEmptySet.add (Arrays.asList (nový Boolean [n])); návrat powerSetOfEmptySet; } Nastav powerSetSubset = recursivePowerSetBinaryRepresentation (idx + 1, n); Nastaviť powerSet = nový HashSet (); for (List s: powerSetSubset) {List subSetIdxExclusive = new ArrayList (s); subSetIdxExclusive.set (idx, false); powerSet.add (subSetIdxExclusive); Zoznam subSetIdxInclusive = nové ArrayList (y); subSetIdxInclusive.set (idx, true); powerSet.add (subSetIdxInclusive); } návrat powerSet; }
5.5. Iterovať cez [0, 2n)
Teraz existuje pekná optimalizácia, ktorú môžeme urobiť s binárnou reprezentáciou. Ak sa na to pozrieme, môžeme vidieť, že každý riadok je ekvivalentný binárnemu formátu čísla v [0, 2n).
Takže ak budeme iterovať číslami od 0 do 2n, môžeme tento index previesť na binárny a použiť ho na vytvorenie boolovskej reprezentácie každej podmnožiny:
súkromný zoznam iterativePowerSetByLoopOverNumbers (int n) {Zoznam powerSet = new ArrayList (); for (int i = 0; i <(1 << n); i ++) {List subset = new ArrayList (n); pre (int j = 0; j <n; j ++) podmnožina.add ((((1 <0); powerSet.add (podmnožina);} návratová množina energie;}
5.6. Minimálna zmena podmnožín podľa sivého kódu
Teraz, ak definujeme bijektívnu funkciu z binárneho vyjadrenia dĺžky n na číslo v [0, 2n), môžeme generovať podmnožiny v akomkoľvek poradí, ktoré chceme.
Šedý kód je známa funkcia, ktorá sa používa na generovanie binárnych reprezentácií čísel tak, aby sa binárna reprezentácia po sebe idúcich čísel odlišovala iba o jeden bit (dokonca aj rozdiel medzi posledným a prvým číslom je jeden).
Môžeme to teda ešte trochu optimalizovať:
súkromný zoznam iterativePowerSetByLoopOverNumbersWithGrayCodeOrder (int n) {Zoznam powerSet = new ArrayList (); for (int i = 0; i <(1 << n); i ++) {List subset = new ArrayList (n); pre (int j = 0; j > 1); subset.add ((((1 <0);} powerSet.add (subset);} return powerSet;}
6. Lenivé načítanie
Aby sa minimalizovalo využitie priestoru napájaného zdroja, ktorý je O (2n), môžeme využiť Iterátor rozhranie na načítanie každej podmnožiny a tiež každého prvku v každej podmnožine lenivo.
6.1. ListIterator
Po prvé, aby bolo možné iterovať z 0 do 2n, mali by sme mať špeciál Iterátor ktorý sa pohybuje v tomto rozmedzí, ale vopred nespotrebuje celý rozsah.
Na vyriešenie tohto problému použijeme dve premenné; jeden pre veľkosť, ktorá je 2na ďalší pre aktuálny index podmnožiny. Náš hasNext () funkcia to skontroluje pozíciu je menej než veľkosť:
abstraktná trieda ListIterator implementuje Iterator {chránená int pozícia = 0; veľkosť súkromného int; public ListIterator (int size) {this.size = size; } @Override public boolean hasNext () {návratová pozícia <veľkosť; }}A náš Ďalšie() funkcia vráti podmnožinu pre aktuálny pozíciu a zvyšuje hodnotu pozíciu jedným:
@Override public Set next () {návrat novej podmnožiny (mapa, reverseMap, pozícia ++); }6.2. Podmnožina
Aby mal lenivý náklad Podmnožina, definujeme triedu, ktorá sa rozširuje Sada abstraktov, a prepíšeme niektoré z jeho funkcií.
Prepojením všetkých bitov, ktoré sú 1 v prijímaní maska (alebo poloha) z Podmnožina, môžeme implementovať Iterátor a ďalšie metódy v Sada abstraktov.
Napríklad veľkosť () je počet 1s v prijímaní maska:
@Override public int size () {return Integer.bitCount (mask); }A obsahuje () Funkcia je len to, či príslušný bit v maska je 1 alebo nie:
@ Override public boolean obsahuje (@Nullable Object o) {Integer index = map.get (o); návratový index! = null && (maska & (1 << index))! = 0; }Používame inú premennú - zostávajúce množiny bitov - upraviť ho vždy, keď načítame jeho príslušný prvok v podmnožine, na ktorú tento bit zmeníme 0. Potom hasNext () skontroluje, či zostávajúce množiny bitov nie je nula (to znamená, že má najmenej jeden bit s hodnotou 1):
@Override public boolean hasNext () {návrat zostávajúcich SetBits! = 0; }A Ďalšie() používa najviac vpravo 1 v zostávajúce množiny bitov, potom ho prevedie na 0, a tiež vráti príslušný prvok:
@Override public E next () {int index = Integer.numberOfTrailingZeros (remainSetBits); if (index == 32) {hod novy NoSuchElementException (); } zostávajúceBity & = ~ (1 << index); návrat reverseMap.get (index); }6.3. PowerSet
Aby mal lenivý náklad PowerSet triedy, potrebujeme triedu, ktorá sa rozširuje Sada abstraktov
The veľkosť () funkcia je jednoducho 2 k sile veľkosti prístroja:
@Override public int size () {return (1 << this.set.size ()); }Pretože výkonová sada bude obsahovať všetky možné podmnožiny vstupnej sady, tak obsahuje (Objekt o) funkcia kontroluje, či sú všetky prvky objekt o existujú v reverseMap (alebo vo vstupnej sade):
@Override public boolean obsahuje (@Nullable Object obj) {if (obj instanceof Set) {Set set = (Set) obj; návrat reverseMap.containsAll (sada); } return false; }Skontrolovať rovnosť daného Objekt s touto triedou môžeme skontrolovať iba to, či je vstup nastaviť sa rovná danému Objekt:
@Override public boolean equals (@Nullable Object obj) {if (obj instanceof PowerSet) {PowerSet that = (PowerSet) obj; return set.equals (that.set); } return super.equals (obj); }The iterátor () funkcia vracia inštanciu ListIterator ktoré sme už definovali:
@ Override public Iterator iterator () {vrátiť nový ListIterator(this.size ()) {@Override public Set next () {return new Subset (map, reverseMap, position ++); }}; } Knižnica Guava používa tento nápad lenivého načítania a tieto PowerSet a Podmnožina sú ekvivalentné implementácie knižnice Guava.
Ďalšie informácie nájdete v ich zdrojovom kóde a dokumentácii.
Ďalej, ak chceme vykonať paralelnú prevádzku nad podmnožinami v PowerSet, môžeme zavolať Podmnožina pre rôzne hodnoty v a ThreadPool.
7. Zhrnutie
Ak to zhrnieme, najskôr sme študovali, čo je to množina energie. Potom sme ho vygenerovali pomocou knižnice Guava. Potom sme študovali prístup a to, ako by sme ho mali implementovať, a tiež to, ako preň napísať jednotkový test.
Nakoniec sme využili Iterátor rozhranie na optimalizáciu priestoru generovania podmnožín a tiež ich vnútorných prvkov.
Ako vždy je zdrojový kód k dispozícii na GitHub.
