Proces wygląda u mnie tak:
1 zabranie paru minimalnych elementów
2 wstawienie elementu(ów)
3 przemapowanie kolekcji, najlepiej flatMapem, z usunięciem niepotrzebnych i uaktualnieniem istniejących (immutable). - być może parokrotnie.
Mam do dyspozycji listę typu immutable, treeset typu immutable i kolejkę priorytetową niestety mutable.
Zastanawiam się czy użyć kolejki priorytetowej, treesetu, czy listy. Pierwszy punkt doradzałby kolejkę, ale ostatni punkt rodzi watpliwości, ponieważ budowa kolejki / treesetu przy przemapowaniu ma większą złożoność: dołączenie elementu O(log(n)) budując od 1 do n ma złożoność O(n log(n!)) o ilę się nie mylę. Z kolejką jest jeszcze ten problem że żeby dostać x najmniejszych elementów trzeba je z-dequeue-ować i potem znowu wstawić, w treesecie nie ma takiego problemu. Jest też możliwość użyć listy, i sortować tylko raz, przed punktem 1. Wtedy dochodzi złożoność sortowania O(n log(n) ale za to potem w 2 O(1) i w 3 O(n).
Co radzicie wybrać?
- Paru czyli ilu? Czy to „paru” zmienia się w czasie?
- Ile razy wykonujesz każdą operację?
- Ile wynosi n?
Mutowalna kolejka na bazie kopca binarnego jest najbardziej przyjazna dla cache. Treeset i lista to masakra. Złożoność to nie wszystko. Przechodzenie listy i drzewa to potencjalnie cache miss przy każdym elemencie. Wstawianie nowego elementu do listy lub drzewa to alokacja, a w przypadku niemutowalnych kolekcji - kilka alokacji. Kiedyś z pewnego głupiego powodu użyłem drzewa jako kolejki priorytetowej i wydajność była ok. 8x gorsza. Drzewo wygrywa tylko jeśli przebujesz szybkiego dostępu do środka, np. do wyszukiwania zakresowego.
@Krolik
Tylko ogolnie staram sie wybierac rozwiazania typu immutable - same elementy sa immutable i podczas iteracji, czesc zostaje zmienionych. A co sadzisz o immutable kolejce priorytetowej?
- Paru czyli ilu? Czy to „paru” zmienia się w czasie?
- paru jest ciezkie do sprecyzowania, zaleznie od uzytkowalnosci i roznych czynnikow nie do przewidzenia na te chwile
- Ile razy wykonujesz każdą operację?
- napisalem logikę i robie jedną iterację (mapowanie, usuwanie niepotrzebnych), potem pobieram kilka najmniejszych elementow, i na końcu dostawiam element i tyle. to się dzieje per request użytkownika (wiele na sekunde)
- Ile wynosi n?
różnie, nie uruchomilem jeszcze testowo systemu i ciezko mi jakies przybliżenie zrobic.
Skoro nie wiesz, jak duże masz dane, to nie da się wyznaczyć najlepszego rozwiązania. Eksperymentuj.