GoldenLine
Zaloguj się
Piotr Głudkowski

Piotr Głudkowski Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...

Temat: Pomysł na algorytm wyszukiwania

Piotr, parę postów wyżej autor wątku napisał, że nie może użyć żadnej bazy danych (w tym SQL-owej). Wyjaśnił też, dlaczego.Piotr G. edytował(a) ten post dnia 27.02.10 o godzinie 01:56
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Michał Jasiorowski:
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

Niedawno robiłem coś takiego. Liczba danych szła w GB, ale wystarczyło rozbić to na wielopoziomowe katalogi i wszystko dobrze chodziło. Proces polegał na generowaniu masy plików i późniejszym ich przeglądaniu. Problem polega na tym, że Windows (a być może także Linux) ma ograniczenie wydajnościowe na liczbę plików w jednym katalogu. Dlatego można zrobić coś takiego:

- GUID określa nazwę pliku i katalogu
- bierzesz k pierwszych (lub ostatnich) liter GUID
- generujesz nazwę pliku: GUID(1:k)
- generujesz ścieżkę: GUID(1:1)\GUID(1+1:2)\GUID(2+2:3)
gdzie druga cyfra w nawiasach oznacza długość podłańcucha hex

czyli dla GUID = F9168C5E-CEB2-4faa-B6BF-329BF39FA1E4

nazwa pliku ze ścieżką będzie:

F\91\68C\F9168C5E.dat

A w środku - od 1 do n rekordów.

Technika opisana tutaj:
http://www.linuxjournal.com/article/6932
Link do wypowiedziLink
Michał Jasiorowski

Michał Jasiorowski Inżynier ds.
oprogramowania

Temat: Pomysł na algorytm wyszukiwania

Piotr Likus:
Niedawno robiłem coś takiego. Liczba danych szła w GB, ale wystarczyło rozbić to na wielopoziomowe katalogi i wszystko dobrze chodziło. Proces polegał na generowaniu masy plików i późniejszym ich przeglądaniu.

Też coś takiego kiedyś robiłem, technika dobrze znana przy dużych serwisach internetowych, pozwala na zachowanie wydajności obsługi dużej ilości plików (np. pliki graficzne).
W moim rozwiązaniu przyjęte zostało ograniczenie ilości plików do 255 więc raczej nie będzie problemu z dużą ilością w jednym pliku.

Jeśli chodzi o przeszukiwanie tego pliku, to po kilku próbach zdecydowałem, że jednak wykorzystam strukturę SkipList do indeksowania (głównie z powodu innych modułów które trzeba opracować, a czasu mało). Generalnie wiedziałem, że prawdopodobnie na tym się skończy przygoda z przeszukiwaniem, ale chciałem najpierw trochę pokombinować, a nóż mogło coś z tego ciekawego wyjść :)
Dziękuje wszystkim za mniejszą lub większą pomoc. Jeśli ktoś ma jakieś jeszcze ciekawe sugestie dotyczące tego tematu to z chęcią wysłucham!
Link do wypowiedziLink
Jakub Fila

Jakub Fila Inżynieria / finanse
/ zarządzanie

Temat: Pomysł na algorytm wyszukiwania

Michał - sprawa wg mnie wyjaśniona - grzebiecie coś przy Globusie, który ma własny system przechowywania danych (ach, ta piękna struktura plików). Pewnie w tle jest współbieżność działania części usług systemu.

Odnośnie Twojego pytania - odpowiem wysokopoziomowo:
1. Samosortująca się struktura , ew. posortowana struktura z zapewnieniem odpowiedniego wstawiania elementu
2. Wstępnie spartycjonowanie dancyh na paczki (Twoje Guid'y to string, więc częściowy porządek masz od ręki), przy wyszukiwaniu elementu idziesz najpierw do odpowiedniej paczki.
3. wewnątrz paczki możesz użyć już dowolnej struktury o niskim koszcie - np. B-tree.

Jeśli ma to być zbudowane od zera, polecam przejrzenie książki Cormen, Liserson, Rivest "Wstęp do algorytmów", gdzie znajdziesz porządnie zredagowany rozdział nt. struktur danych, wyszukiwania, sortowania itd.
Link do wypowiedziLink

konto usunięte

Temat: Pomysł na algorytm wyszukiwania

Ja bym chyba polecał ściągnąć implementację B-tree z MS SQLa - dlatego z niego, bo akurat ten algorytm znam i myślę, że wśród .NETowców jest w miarę popularny i można przez DDBC sporo podejrzeć jak to M$ robi. Wymyśl, aby indeks był unikatowy, wąski, rosnący (z GUIDem problem), statyczny, podziel dane na odpowiedniki page'ów, zaimplementuj page splity itd.... kupa roboty.
Link do wypowiedziLink
Rafał Kiełbus

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

Temat: Pomysł na algorytm wyszukiwania

maciek kański:
kupa roboty.
Tak to jest z wymyślaniem koła na nowo ;]
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj