jen bych ke kolegovi dodal, ze to zavisi na skrytych konstantach, resp. poctu tech zaznamu ... :-).
-Vity Dne 21. červenec 2009 14:08 Ondra Medek <[email protected]> napsal(a): > No pokud byste mel klasicky List nebo Set, tak nejlepsi je obe mnoziny > seradit - slozitost O(n log n) a pak je projit jednim pruchodem O(n), > tj. celkem O(n + n log n) = O(n log n). Pokud se A a B nemeni prilis, > tak byste mohl vyuzit SortedSet nebo SortedMap, abyste to nemusel po > kazde zmene znovu radit, pak by vas algorimus mel O(n) slozitost, ale > zase insert/delete v seznamech by neco zabral. > > Ale vase reseni take neni spatne, za predpokladu, ze se prvky v Map > dobre hashuji, tj. slozitost se pristupu se blizi O(1) a tedy cely > prubeh vaseho algoritmu je pak blizko k O(n). > > Jak vidite, pokud si stim chcete hrat, tak si to musite vyzkouset a > zmerit cas :-)) > > O. > > 2009/7/21 Michal Nikodím <[email protected]>: >> Mam dve mnoziny A a B. Mnozina A je 100% prvku a v mnozine B je n prvku. >> Potrebuju projit mnozinu A a ke kazdemu prvku mnoziny A dohledat >> odpovidajici prvek mnoziny B. >> >> Mnoziny jsou plne v moji rezii. Muze to byt List, Map, dle libosti. Prvky >> mnozin jsou tez plne v moji rezii a tak jak to mam ted ma kazdy prvek >> unikatni atribut ID (Long) a equals a hashcode je napsan pro tento atribut. >> Mnozina B je celkem casto prenactena a ja potrebuju po prenacteni proparovat >> s mnozinou A. >> >> Vysledkem je mnozina C kde prvkem je objekt ktery obsahuje instanci z >> mnoziny A a spravnou instanci z mnoziny B (nebo null). >> >> Jak tohle delat co nejefektivneji ? >> >> Osobne to resim tak, ze mam mnozinu B jako Map<Long, Prvek> pricemz iteruju >> mnozinu A a podle ID z mapy dohledam odpovidajici prvek B. >> Ale moc se i to nezda. >> >> > > > > -- > Ondra Medek >
