GoldenLine
Zaloguj się
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Witam,
mam ciekawy problem do rozgryzienia i chciałbym usłyszeć głosy innych z pomysłami na rozwiązanie.
Mianowicie:

Istnieje struktura (C#) o stałym rozmiarze 24B:

struct ObjInfo
{
Guid ID; [16B]
long SID; [8B]
}

Jest ona wypełniana danymi i zapisywana sekwencyjnie w pliku w postaci binarnej.

Po zapisaniu pewnej ilości N takich struktur na dysku, chcę wyszukać strukturę o pewnym ID w celu odczytania SID.
Zapis oraz dostęp odbywa się poprzez Memory Mapped Files więc fizycznie dane nie znajdują się one w pamięci RAM.

Najprostszy sposób to full scan i porównywanie ID. Jednak przy dużych ilościach odpada. Zakładam, że liczba N jest powyżej 10 000 000.
Jakie macie pomysły na zawężenie obszaru poszukiwań w danym pliku?
Dodam, że te struktury zapisane są w takiej kolejności w jakiej wpadały do pliku.
Link do wypowiedziLink
Jerzy M.

Jerzy M. C#/JavaScript
Developer

Temat: Pomysł na algorytm wyszukiwania

Jeżeli często będziesz potrzebował coś pobrać to warto by posortować tą "tablice" wg. ID.

Nawet jeżeli ID nie są po kolei (tzn. 1,2,3,4) to w posortowanej tablicy znacznie szybciej znajdziesz to czego szukasz.

Troszkę to rozwinę może :-)
Mając rozmiar struktury możesz się poruszać wewnątrz pliku bez jakiś specjalnych trudności. A kierunek wybierać na zasadzie sprawdzenia ID

1 3 6 9 12 20 31 40 41 50

Tak dla przykładu, przesuwasz się na sam środek (wyszukujesz 9) - dostajesz 20, więc jedziemy w lewo (znowu środek) 6 i w prawo 9.

Re down:
A fakt, mój błąd.
-------Jerzy Mieczyński edytował(a) ten post dnia 25.02.10 o godzinie 15:45
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Zgadza się, tylko, że w moim przypadku ID to Guid czyli np. F9168C5E-CEB2-4faa-B6BF-329BF39FA1E4
Generalnie, jest on przechowywany jako 128-bit Integer, więc teoretycznie możliwe jest posortowanie, jednak do tej tablicy będą bardzo często dopisywane nowe struktury. Więc ze względów wydajnościowych każdorazowe sortowanie 10M elementów było by samobójstwem.
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Proponuje zglebic metody wyszukiwania informacji:

http://pl.wikipedia.org/wiki/Systemy_Wyszukiwania_Info...

Nie pamietam juz ktora to metoda byla, ale na pewno znajdziesz metode ktora Ci bedzie pasowala.

A tak na szybko to:

Staralbym sie zgrupowac el w pliki, tak zeby kazdy plik zawieral jakas mozliwa do przejrzenia liczbe elementow (100-1000) no i oczywiscie pozostaje stworzenie/uzycie funkcji skrotu (a'la md5) ktora generowalaby Ci szybko nazwe pliku (pierwsze 5 znakow z guid albo cos podobnego) - nie wiem czy jasno opisalem - jakby co to pytaj :)

ew metoda brutalna, wygeneruj pliki o nazwach ID - tylko nie jestem pewien czy OS to zniesie, zawsze mozesz podzielic na katalogi/podkatalogi/... tak zeby zminimalizowac ilosc wpisow na jednym poziomie (jezeli to stanowi problem)Rafał Ziółkowski edytował(a) ten post dnia 25.02.10 o godzinie 15:59
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Ok, jest to już jakiś trop... problemem może być ilość plików, jako że mamy 16 możliwych znaków (HEX) do tego 5 pierwszych z Guida to daje ~~500k plików, a podejrzewam, że istnieje bardzo małe prawdopodobieństwo, że będzie dużo trafień wewnątrz 1 pliku... ale to trzeba by sprawdzić :)

Co o plików dla każdego ID to myślę że odpada... Dużo szybciej można odczytać np. 100 000 (ok. 100ms) struktur z 1 pliku niż skakać po każdą do innego.Michał Jasiorowski edytował(a) ten post dnia 25.02.10 o godzinie 16:03
Link do wypowiedziLink
Marek Trąba

Marek Trąba projektant,
analityk,
programista

Temat: Pomysł na algorytm wyszukiwania

1. Podział na pliki jest dobrym pomysłem pod warunkiem, że plików nie będzie za dużo - jak sam już wiesz byłoby to nieopłacalne.
2. Sortowanie po kluczu jest oczywiście dobrym pomysłem. Jeśli nie będziesz trzymał wszystkiego w jednym pliku , ale w kilku, to zawsze możesz dopisywać do jednego z nich a sortować w tym czasie pozostałe.
3. Jeśli guid nie pasuje Ci do sortowania przebuduj strukturę na taką z kluczem, któy Ci pasuje i sortuj po tym kluczu.
4. Spróbuj też podejść całkiem odmiennie do problemu. Dlaczego zapis sekwencyjny? Może te dane da się jakoś klasyfikować, wtedy od razu mógłbyś je podzielić na mniejsze kawałki i jakoś poukładać. Może warto dodać jakąś dodatkową daną (czas zapisu, offset od jakiegoś miejsca, punktu, czasu, itp) kosztem niewielkiej nadmiarowości danych.
5. Z jeszcze innej strony. Może da się stworzyć jakąś mapę, wg. której mógłbyś klasyfikować dane i przyspieszyć ich. Nie wiem co za dane zapisujesz, ale czasem wystarcy zwykły układ współrzędnych.

To tak na szybko....
Powodzenia w szukaniu rozwiązania....
Link do wypowiedziLink
Rafał Kiełbus

Rafał Kiełbus #blockchain
developer, #bitcoin
maximalist,
#ethereum mage

Temat: Pomysł na algorytm wyszukiwania

A nie można pakować do bazy na sqlite? Dodawanie pewnie byłoby wolniejsze ale wyszukiwanie w btree to przecież moment. Przy takiej ilości elementów zysk byłby wystarczający?
Może z nudów napiszę generator sidów i policzę przy 10M rekordów co się dzieje ;]
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

SQL'e wszelkiej maści niestety odpadają.
Z (nie)nudów, napisałem test który wyszukuje 21 elementów w 21M. Całość zajmuje nieco poniżej 500MB na dysku. Wyszukiwanie odbywa się pełnym przeglądem ale wielowątkowo. Dało to średni wynik ok 1010ms dla odnalezienia jednej struktury.

Czas jak dla mnie średni, chciałbym uzyskać wynik minimum o połowę lepszy :)Michał Jasiorowski edytował(a) ten post dnia 25.02.10 o godzinie 19:45
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

1.sortuj struktury co jakis czas (optymalizacja)
2.moze warto to zrobic w c++? zstawiam, ze bedzie szybcie.

W algorytmie uwzglednij to ze masz posortowane dane.
Link do wypowiedziLink
Stanisław P.

Stanisław P. Software designer

Temat: Pomysł na algorytm wyszukiwania

Michał Jasiorowski:
SQL'e wszelkiej maści niestety odpadają.
Możesz doprecyzować dlaczego? Jeśli musisz się trzymać formatu z danymi zapisanymi sekwencyjnie, to najwyżej możesz go tylko od czasu do czasu posortować - nic więcej tutaj nie wymyślisz tak naprawdę. Możesz ew. bawić się w indeks zewnętrzny który będzie opisywał w jakim regionie masz jakie wartości, żebyś nie musiał sortować całego pliku po wstawieniu, tylko fragmenty - ale to jest wynajdywanie od nowa koślawej bazy danych.
Jeśli nie musisz (bo pisałeś że podział na pliki to już coś), to czemu nie kv-store? Przecież to jest właśnie to co robią.
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Stanisław Pitucha:wstawieniu, tylko fragmenty - ale to jest wynajdywanie od nowakoślawej bazy danych.

Co do tej koślawej bazy danych, to jesteś blisko:) generalnie ta tablica odwzorowań jest częścią właśnie silnika obiektowej bazy danych. Moja część, czyli skład danych jest częścią w większym projekcie.
Dlatego też nie mogę używać SQL bo to niezgodne z projektem.
kv-store, przyjrzę się, może jakieś ciekawe pomysły będzie można podpatrzeć.

Update:
Od kv-store dotarłem do czegoś, od czego tak naprawdę powinienem zacząć czyli system składowania Google (BigTable). Specyfikacja techniczna ich składu danych, to naprawdę kopalnia pomysłów i wskazówek (szczególnie w kontekście mojego zadania).
Jak tylko będę miał jakieś ciekawe pomysły opracowane na podstawie ich technologii, to na pewno się podzielę :)Michał Jasiorowski edytował(a) ten post dnia 25.02.10 o godzinie 22:35
Link do wypowiedziLink
Stanisław P.

Stanisław P. Software designer

Temat: Pomysł na algorytm wyszukiwania

Michał Jasiorowski:
Co do tej koślawej bazy danych, to jesteś blisko:) generalnie ta tablica odwzorowań jest częścią właśnie silnika obiektowej bazy danych. Moja część, czyli skład danych jest częścią w większym projekcie.
Dlatego też nie mogę używać SQL bo to niezgodne z projektem.
kv-store, przyjrzę się, może jakieś ciekawe pomysły będzie można podpatrzeć.

Zaraz... piszesz od nowa bazę danych i zadajesz tu takie pytania?

Proszę, oszczędź lepiej użytkownikom cierpienia, bo jeśli masz jakikolwiek liniowy zapis w bazie danych, to to jest porażka. Mamy bazy obiektowe takie jak db4o, jak i szybkie tablice k-v takie jak w BDB, TC, QDB, i wiele innych. Jeśli musisz pisać coś swojego, to przynajmniej przeczytaj o btree, radix sorcie i konstrukcji prawdziwych bazy danych. Z aktualnym sposobem to nigdy nie będzie i nie ma prawa być szybkie.
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Zaraz zaraz powoli... bez rozpędu z tym oburzaniem się :)

Wiem, że najprościej jest zastosować w tym wypadku index w postaci drzewa binarnego, wszystko ładnie i szybko będzie działać (sprawdzone).
Moje pytanie dotyczyło jednak czegoś innego. Mianowicie, wszystkie dane są na dysku, nie ma ich fizycznie w pamięci z racji ilości. Z tego samego powodu wygenerowanie indeksu dla tych danych nawet przy ilości np. 5M elementów zabiera bardzo dużo pamięci. Chciałem nawiązać dyskusję żeby określić czy w ogóle możliwe jest efektywne wyszukiwanie elementów bez konieczności tworzenia tak kosztownych struktur w pamięci.

Nie mówię, że docelowo nie zastosuję indeksu, jednak chciałem najpierw sprawdzić tą drogę. Czy jest to w ogóle możliwe.
Link do wypowiedziLink
Stanisław P.

Stanisław P. Software designer

Temat: Pomysł na algorytm wyszukiwania

Michał Jasiorowski:
Moje pytanie dotyczyło jednak czegoś innego. Mianowicie, wszystkie dane są na dysku, nie ma ich fizycznie w pamięci z racji ilości.
Wtedy można używać cachowania z określoną ilością wpisów, albo określonym timeoutem... (memcache to załatwia)
Z tego samego powodu wygenerowanie indeksu dla tych danych nawet przy ilości np. 5M elementów zabiera bardzo dużo pamięci.
Np. w TC jeśli zapiszę 5M elementów GUIDów z kluczem tekstowym to:
- GUIDy: 171MB
- klucze: 32MB
- całość: 231MB
- indeks = plik-reszta == 28MB (czyli 10% całości - przy dłuższych rekordach jest inna proporcja oczywiście)

Jeśli już operujesz na 5M elementów, to czy 28MB to dużo? (5.6 bajta na rekord!) Żeby używać indeksów nie musisz też mieć go całego w pamięci. Przy zmapowanym pliku i częsty dostępie, system powinien sam zadbać o czas dostępu.
Chciałem nawiązać dyskusję żeby określić czy w ogóle możliwe jest efektywne wyszukiwanie elementów bez konieczności tworzenia tak kosztownych struktur w pamięci.
Zawsze jest odpowiedni stosunek między czasem a pamięcią ;) Jeśli nie stworzysz kosztownej struktury... wiesz gdzie płacisz.
Nie mówię, że docelowo nie zastosuję indeksu, jednak chciałem najpierw sprawdzić tą drogę. Czy jest to w ogóle możliwe.
Jeśli chcesz operować bez indeksu musisz znać rozkład danych. Wtedy albo masz cały plik działający np. jak kopiec, judy, czy inny bajer albo musisz mieć dane z założenia posortowane, plik musi zachowywać strukturę i sam musisz napisać kompletną obsługę razem z naprawą potencjalnie uszkodzonego pliku (kto używa bazy danych bez takiego narzędzia?)

Zawsze możesz mieć pół na pół i płacić za czas dodawania rekordu. Jeśli nigdy pól nie usuwasz, to możesz założyć, że cały plik dzielisz na N kubełków, posortowanych względem siebie, a wewnątrz kubełka przeszukujesz liniowo... Co dalej wymusza wkładanie i szukanie O(n), tyle że n jest dużo mniejsze.

No i raczej sam nie napiszesz bazy danych która naprawdę dobrze obsługuje SMP. Nie sądzę też, żebyś wymyślił coś lepszego niż Berkeley DB, bo ludzie z oracla (sleepycat właściwie) już myśleli nad tym dobre kilka lat.

Sory, że tak bezpośrednio, ale myślę, że jeśli ktoś nie żyje bazami danych na codzień, nie powinien się zabierać za pisanie własnej - chyba że potrafi dobrze udokumentować co konkretnie zrobi inaczej i dlaczego nie wystarczy napisać patcha do którejś istniejącej bazy.Stanisław Pitucha edytował(a) ten post dnia 26.02.10 o godzinie 00:55
Link do wypowiedziLink
Jakub Gutkowski

Jakub Gutkowski Software
Developer/Architect
Microsoft MVP

Temat: Pomysł na algorytm wyszukiwania

dobra zadam to pytanie gdyz poprostu sie powstrzymac nie moge.

czy jest to zadanie na uczelnie? i prosilbym o szczera odpowiedz.

dzieki,

Gutek
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Jeśli możesz zapanować na procesem zapisu tych danych to już masz problem rozwiązany, nie musisz wtedy sortować to co jakiś czas.
Robisz wtedy jakieś samo sortujące się drzewko (np. AVL) i masz strukturę gotową którą się będzie szybko szukało, dodatkowo przy takim drzewku możesz zachować niektnięty format pliku jeśli jest serializowany binarnie.

Poza tym, z definicji Memory-Mapped-File jest całe w pamięci a jeśli jego rozmiar wykracza po za pamięć fizyczną to wówczas część która się nie mieści ląduję w pamięci wirtualnej (w takim przypadku, jeśli rozmiar w bardzo znacznym stopniu wykracza po za rozmiar pamięci, to jest mały sens używania takiej metody dostępu).

Zastanów się nad tym ile razy szukasz tą strukturę; jeśli to jest częsta operacja to faktycznie stworzenie jakiegoś cache (np. po pierwszym przeszukaniu liniowym od razu w locie sortuj je), niekoniecznie od razu w pamięci tylko najpierw kawałkami na dysk a potem dopiero podmień struktury w pamięci.Karim Agha edytował(a) ten post dnia 26.02.10 o godzinie 06:00
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Jakub Gutkowski:
dobra zadam to pytanie gdyz poprostu sie powstrzymac nie moge.

czy jest to zadanie na uczelnie? i prosilbym o szczera odpowiedz.

dzieki,

Gutek

Bardziej bym obstawiał to, że jest to pytanie rekrutacyjne ;-)
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Jakub Gutkowski:
dobra zadam to pytanie gdyz poprostu sie powstrzymac nie moge.

czy jest to zadanie na uczelnie? i prosilbym o szczera odpowiedz.

Sądząc po twojej uczelni, podejrzewam, że wiem czemu pytasz :)
Odpowiedź jest tak, tyle, że nie do końca "na uczelnie" bardziej "w ramach uczelni". Ale to jest nieistotne.
Karim Agha:
Poza tym, z definicji Memory-Mapped-File jest całe w pamięci a
jeśli jego rozmiar wykracza po za pamięć fizyczną to wówczas część
która się nie mieści ląduję w pamięci wirtualnej (w takim
przypadku, jeśli rozmiar w bardzo znacznym stopniu wykracza po za
rozmiar pamięci, to jest mały sens używania takiej metody dostępu).

Nie jest do do końca prawda, nie jest on cały w pamięci operacyjnej (dokładnie fizycznie na kościach RAM). Polega to na zmapowaniu adresacji pamięci na ten plik (tak samo jak plik wymiany) przez fizycznie nie są ładowane dane do RAM (tylko w momencie dostępu do żądanych danych). Dlatego jest bardzo duży sens korzystania z tej metody jeśli plik przekracza rozmiar dostępnej pamięci operacyjnej :)
Stanisław Pitucha:
No i raczej sam nie napiszesz bazy danych która naprawdę dobrze
obsługuje SMP. Nie sądzę też, żebyś wymyślił coś lepszego niż
Berkeley DB, bo ludzie z oracla (sleepycat właściwie) już myśleli
nad tym dobre kilka lat.

Ja nie twierdzę, że moim celem jest stworzenie czegoś lepszego od
komercyjnych baz danych lub czegokolwiek tworzonego przez lata przez dużą ilość osób. Przypomnę, też, że nie robię tego sam.
A cel w jakim to powstaje jest bynajmniej komercyjny. Ale to już jest zbaczanie z tematu pytania, a nie chcę żeby ten temat stał się dyskusją na temat sensowności pisania czegokolwiek. Zapomnijmy o tym, że to baza danych :)Michał Jasiorowski edytował(a) ten post dnia 26.02.10 o godzinie 09:06
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Michał Jasiorowski:
Nie jest do do końca prawda, nie jest on cały w pamięci operacyjnej (dokładnie fizycznie na kościach RAM). Polega to na zmapowaniu adresacji pamięci na ten plik (tak samo jak plik wymiany) przez fizycznie nie są ładowane dane do RAM (tylko w momencie dostępu do żądanych danych). Dlatego jest bardzo duży sens korzystania z tej metody jeśli plik przekracza rozmiar dostępnej pamięci operacyjnej :)

Faktycznie, coś mi się popierdzieliło ;) Masz rację.
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Rafał Ziółkowski:
Proponuje zglebic metody wyszukiwania informacji:

http://pl.wikipedia.org/wiki/Systemy_Wyszukiwania_Info...

Nie pamietam juz ktora to metoda byla, ale na pewno znajdziesz metode ktora Ci bedzie pasowala.

A tak na szybko to:

Staralbym sie zgrupowac el w pliki, tak zeby kazdy plik zawieral jakas mozliwa do przejrzenia liczbe elementow (100-1000) no i oczywiscie pozostaje stworzenie/uzycie funkcji skrotu (a'la md5) ktora generowalaby Ci szybko nazwe pliku (pierwsze 5 znakow z guid albo cos podobnego) - nie wiem czy jasno opisalem - jakby co to pytaj :)

MD5 (i inne skróty) jest tu niepotrzebny.
GUID akurat jest losowy, więc wystarczy wybrać odpowiednią porcję (z początku lub końca) łańcucha żeby mieć skrót.

http://en.wikipedia.org/wiki/GUID

Do autora wątku:
Możesz zastosować coś jak btree. Albo zrobić sobie indeks na bazie SQL z tablicą:
- GUID
- nr rekordu w pliku płaskim z rekordami docelowymi

a potem:
a) odczytać nr rekordu z indeksu
b) odczytać rekord z pliku płaskiego o stałej długości rekordu

Miałoby to sens, gdybyś:
a) chciał mieć rekord dużo większy niż pole opisujące nr rekordu (oszczędność miejsca)
b) chciał odczytywać sekwencyjnie kilka rekordów z rzędu

W innych przypadkach lepiej zastosuj rozwiązanie SQL-only.
Najlepiej zrób tak od razu i sprawdź czy wydajność rzeczywiście jest za mała. A potem można komplikować (tzn. optymalizować).Piotr Likus edytował(a) ten post dnia 26.02.10 o godzinie 09:21
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj