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
