GoldenLine
Zaloguj się
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

Czesc,

jak w temacie, mecze sie troche ze znalezieniem implementacji BTree

- nie musi byc thread safe, wszystko bede robil za pomoca LinkekTransferQueue i niemutowalnymi obiektami polecen
- musi byc opcja re-sortowania, ale po kuczy (tzn zmieni sie klucz, nie bede nawet usuwal/dodawal wartosci).
- najlepiej implementacja java.util.NavigableMap<K,V>

TreeMap mi nie pasuje bo nie jest re-sortowalny, tak wiec za kazda zmiana musialbym go przebudowywac, co jest mniej niz optymalne - mowie tu o tablicach wielkosci 100 tys obiektow.
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: Zna ktos jakas dobra implementacje BTree?

A po co Ci re-sortowanie?

Nie wystarczy Collections.sort( kolekcjaObiektowZDrzewa, nowyKOmparator() ) ?
Link do wypowiedziLink
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

Bo jak mam resortowac 1-kilkaset tysiecy obiektow, za kazda zmiana 1 z nich, wydaje mi sie to zbedne.
Link do wypowiedziLink

konto usunięte

Temat: Zna ktos jakas dobra implementacje BTree?

Piotr J.:
Bo jak mam resortowac 1-kilkaset tysiecy obiektow, za kazda zmiana 1 z nich, wydaje mi sie to zbedne.

Co masz na myśli pisząc "resortowanie" ?
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: Zna ktos jakas dobra implementacje BTree?

No ale nie sortujesz elementów dla sportu. Co robisz z posortowtanymi obiektami? :)

Czy zawsze chcesz sortować po tym samym parametrze? Czy w grę wchodzą (raz sortuję po X, innym razem po Y, a jeszcze innym razem po kodzie pocztowym).

Ogólnie potrzebujesz struktury danych, która :
- przechowuje kolekcję obiektów (dajmy na to N obiektów)
- nie usuwasz obiektów ze struktury
- operacje dodaj / znajdź mają mieć złożoność np. O(1), O(logN) ?
- operacja "re-sortowanie" ma mieć złożoność O(???) ?

Można myśleć o jakimś tworze, który będzie przechowywał dane na wiele sposobów, np. hasz mapa + kolejki priorytetowe.

Ale trzeba dokładnie określić znaczenie operacji dla takiej struktury danych i ich oczekiwaną złożoność czasową.
Link do wypowiedziLink
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

Dzieki za odp.

Masz racje, powinienem wytlumaczyc co potrzebuje przechowac, a z tego wyniknie w jakiej strukturze danych. Pewnie tez przekombinowuje i nie skumalem, a TreeMap z lekkim dodatkiem w postaci pamietania indeksow mi wystarczy.

W TreeMap bedzie O(logN) dla wszystkich operacji, chodz nie moglem znalezc info co do subMap() i higherKey()

Mam obiekt, ktory ma parametry:

- paramA
- paramB
- paramC

Algortym za kazdym razem pobieral bedzie posortowane obiekty wg najmniejszego indeksu mapy. Czyli jak zrobilbym group by paramA, to bedzie szukal encji z konkretnym wynikiem (lub najblizszym mozliwym do podanego).

1) paramA i paramB zmienia sie bardzo rzadko - moge wiec zawsze budowac cos od zera. Jestem tez w stanie poswieci wiecej pamieci, aby miec szybszy dostep do danych, tym bardziej, ze bedzie bardzo czesty.

2) paramC zmienia sie za kazdym zapytaniem do API, czyli robie put(K, V), a kolejna operacja bezdie potrzebowala juz posortowanej (rowniez wg indeksow) tablicy, bo bedzie potrzebowac najnizszy index.

Zastanawiam sie co jest lepsze do tych indeksow:

- Czy trzymac kazdy index w oddzielnej strukturze, czyli mamy 0-index, 1-index itd...
w zasadzie Set<Map<Short, ? extends Object>> i wykonywac 2 operacja za kazda zmiana indeksu, ale za to zwracac juz praktycznie posortowane+podzielone (tu wchodzi to, jakie bigO ma subMap i higherKey)

- Czy trzymac w 1 strukturze i za kazdym razem szukac submapy, ktora mnie interesuje

A, powinienem chyba dodac, ze jak juz dostane ta subMap, nie musze tak naprawde miec TreeMap, bo bede przez niego traversowal element po elemencie.Ten post został edytowany przez Autora dnia 10.12.13 o godzinie 13:23
Link do wypowiedziLink
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

Dobra, chyba skumalem, zle przeczytalem (bylo gosc niejasno napisane)

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method.

Ze chodzi o Map.Entry zwracane, a nie o sama mape - stad moje przekonanie, ze nie da sie jej posortowac... ech
Link do wypowiedziLink

konto usunięte

Temat: Zna ktos jakas dobra implementacje BTree?

Piotr J.:
Dobra, chyba skumalem, zle przeczytalem (bylo gosc niejasno napisane)

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method.

Ze chodzi o Map.Entry zwracane, a nie o sama mape - stad moje przekonanie, ze nie da sie jej posortowac... ech

Hm... czy zdajesz sobie sprawę z tego, że BTree to pewna forma organizacji posortowanych elementów ?

Złożoność obliczeniowa zwrócenia elementów BTree w pewnym porządku wynosi O(n).
Link do wypowiedziLink
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

@Jakub

Ja sadzilem raczej, ze O(log(N)+M) gdzie n to ilosc elementow w zbiorze, a M ilosc elementow wyciaganych.
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: Zna ktos jakas dobra implementacje BTree?

@Piotr: pomijając złożoność operacji, to nie lepiej zrobić interfejs do abstrakcyjnej struktury danych z operacjami takie jakie potrzebujesz i zaimplementować go jak najprościej np. z wykorzystaniem drzew ?

W ten sposób zobaczysz czy funkcjonalnie to działa, a wymianę implementacji interfejsu zrobisz wtedy jak będzie taka potrzeba ;-)

Implementacja1 : drzewo
Implementacja2 : podział przestrzeni kluczy na K bucketów, np. po 5k elementów i przerzucanie elementów między bucketami. W obrębie bucketów organizujesz kolekcje jako BTree.

Bucket[0] - drzewo trzymające klucze 0..5000, info o ilości elementów etc.
Bucket[1] - drzewo trzymające klucze 5001..10000
...

Wyciągasz element z bucket[1], aktualizujesz klucz i wstawiasz np, do bucket[5].

Różnica log(100k) vs log(5k) przy dużej ilości operacji może być korzystna.

Możesz też przechowywać listę np. Top10 bucketów, w których są jakieś elementy, tak by szybko wybierać k "topowych".

Jest tu jednak pułapka dotycząca rozkładu danych (po 100k iteracjach może być równomierny rozkład danych w bucketach, ale po 200k może się okazać że 90% elementów jest w bucket8).
Link do wypowiedziLink
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

@P K G

Tak wlasnie zrobilem, aby niepewnosc przerzucic na implementacje.

Dzieki za pomoc Panowie!
Link do wypowiedziLink

konto usunięte

Temat: Zna ktos jakas dobra implementacje BTree?

Piotr J.:
@Jakub

Ja sadzilem raczej, ze O(log(N)+M) gdzie n to ilosc elementow w zbiorze, a M ilosc elementow wyciaganych.

Jeśli "wyciąganie" elementu trwa O(log(n)) to złożoność "wyciągania" M elementów wynosi O(M * log(N)). Jeśli M jest stałą to nie ma żadnego problemu.

Teraz trudna część: jeśli M ~~ N to złożoność wynosi O(N*log(N)), czyli te "posortowane dane" sortujesz sobie na nowo, tyle że wg. innych kryteriów.

"Tak wlasnie zrobilem, aby niepewnosc przerzucic na implementacje. "
"niepewność przerzucic na implementacje", serio ?

Dowiedz się "o co chodzi", zrób testy, upewnij się co do metody a później coś zaimplementuj.Ten post został edytowany przez Autora dnia 11.12.13 o godzinie 20:52
Link do wypowiedziLink
Piotr Jasiulewicz

Piotr Jasiulewicz PHP/Java
professional

Temat: Zna ktos jakas dobra implementacje BTree?

Captain obvious strikes again ;-)

Dzieki.
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Czy ktos potrafi?




Wyślij zaproszenie do
Anuluj