Sortowanie bardzo dużych plików tekstowych

[Paweł Włodarski]

cześć,

Problem jest taki, że trzeba posortować w sposób nie do końca alfabetyczny (czyli swoim komparatorem) pliki tekstowe, które nie mieszczą się w pamięci.

Są już na to gotowe algorytmy :

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

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

I nawet jakieś biblioteczki w Javie ale nie mogę znaleźć w necie żadnych relacji jak te biblioteczki radzą sobie na produkcji.

I tutaj moje pytanie : czy ktoś z was miał podobny problem i może polecić konkretne rozwiązanie, które nie popsuło mu produkcyjnej aplikacji?

dzięki

[Grzegorz Borkowski]

Ciekawy problem, niestety nie miałem do czynienia w czymś takim. Ale myślę że jak to potestujesz na przykładowych wielkich plikach, i będzie działać, to czemu na produkcji miałoby nie działać?

--
Otrzymujesz tę wiadomość, ponieważ subskrybujesz grupę dyskusyjną Google o nazwie „Łódź Java User Group (Łódź JUG)”.
 
Odwiedź tę grupę na http://groups.google.com/group/lodz-jug?hl=pl
 
 

[peper]

Jak duże są te pliki? Może jednak da się je upchnąć w jakiś rozproszony Redis, Elastic Search, Riak albo MongoDB? 

Jak często musisz przeprowadzać to sortowanie? Raz, raz dziennie, raz na minutę?

[Paweł Włodarski]

On Wednesday, October 31, 2012 8:45:16 PM UTC+1, Grzegorz Borkowski wrote:

Ciekawy problem, niestety nie miałem do czynienia w czymś takim. Ale myślę że jak to potestujesz na przykładowych wielkich plikach, i będzie działać, to czemu na produkcji miałoby nie działać?

Wiesz Grzesiek jak to jest : rozum podpowiada, że takie testy wystarczą a serce mówi, że i tak coś się zjebie :)

[Paweł Włodarski]

On Thursday, November 1, 2012 1:15:30 PM UTC+1, Piotr Gwiazda wrote:

Jak duże są te pliki? Może jednak da się je upchnąć w jakiś rozproszony Redis, Elastic Search, Riak albo MongoDB? 

Jak często musisz przeprowadzać to sortowanie? Raz, raz dziennie, raz na minutę?

Cześć

 

Pliki mają do 500MB ale w jednej chwili sortowanych ich może być wiele. Częstotliwość tej operacji będzie się zmieniać wraz z upodobaniami klientów aplikacji.

Osobiście wydaje mi się, używanie do tego dodatkowych magazynów danych wprowadza niepotrzebną komplikację jakkolwiek dzięki za odpowiedź.

pzdr

[Piotr Gwiazda]

W najgorszym wypadku będziesz musiał porównać n plików, które będą się różniły dopiero znakiem na 500-tnym megabajcie. Coś mi mówi, że system plików może odmówić robienia tego wydajnie.

Może być tak, że będziesz miał otwarte kilkadziesiąt (kilkaset) plików na raz i będziesz porównywał strumienie znak po znaku szukając pierwszego różniącego się znaku. W sumie nie musisz do tego trzymać wszystkiego w pamięci.

[Grzegorz Duda]

Pawel,

Bez bardziej dokladnego opisania problemu moze byc ciezko znalezc rozwiazanie. Od razu zaznacze, ze nie mialem takiego problemu, ale warto poglowkowac. Moze jednak ktos bedzie mial lepsze i sprawdzone rozwiazanie.

Nie wiem jak sa implementowane te biblioteki do merge sorta, ale wyobrazam sobie, ze gdzies bedzie bardzo duzo odczytow pliku i tez nieco zapisu, a wiec troche bedzie to trwalo, bo jak pewnie wiesz wszlekie operacje na plikach, a zwlaszcza zapis, sa bardzo kosztowne. Z tego co rozumiem po mailach, to maja to byc operacje live, tzn. klient czeka na wyniki.

Co jest w tych plikach tekstowych, tzn. co zawiera i jak duzy jest taki jeden element do posortowania? Jesli dane sa duze, to czy jestes w stanie napisac jakas sprytna funkcje hashujaca, ktorej wynik jest sporo mniejszy od pierwotnych danych, ale zachowuje kolejnosc. Tzn. jak masz X > Y, to hash(X) > hash(Y), Wtedy moglbys np. stworzyc jakas strukture danych w pamieci, ktora bys sortowal "normalnym" algorytmem. Ta struktura zawieralaby hash(X) i pozycje, gdzie znajduje sie X w  pliku. W ten sposob po posortowaniu tej struktury mialbys szybki dostep do oryginalnych danych i uniknalbys drogich i ryzykowanych przy takich rozmiarach operacji na plikach.

Czy krytyczne jest, zeby dostac wynik calego sortowania na raz, czy mialoby sens gdyby szybciej uzytkownik dostal pierwsze np. 10%, a pozniej dalsze czesci posortowanego pliku? Wtedy moglbys dobrac jakis algorytm, ktory wypluwa strumien

Ja osobiscie staralbym sie byc daleko od I/O na plikach, bo tam zawsze moze byc jakis problem np. brak miejsca na dysku, za malo handli do otworzenia nowego pliku, itp.

Regards/Pozdrawiam,
Grzegorz Duda (http://www.dworld.pl/page/show/Grzegorz_Duda/)

33rd Degree conference for Java Masters (http://33degree.org)
Developers World (http://www.dWorld.pl)
JAVA exPress (http://www.javaexpress.pl)

2012/11/1 Paweł Włodarski <pwlo...@gmail.com>

--

[Paweł Włodarski]

On Thursday, November 1, 2012 6:28:52 PM UTC+1, Grzegorz Duda wrote:

Pawel,

Bez bardziej dokladnego opisania problemu moze byc ciezko znalezc rozwiazanie. 

Cześć,

Nie opisywałem dokładnego problemu bo bardziej chciałem się skupić na bibliotekach.

Algorytmy działające na IO wyglądają obiecującą i mają już jakieś tam rzekomo działające implementacje. 

Jednakże w życiu czasem tak bywa, że jakaś młoda gwiazda zaimplementuje bibliotekę i jakoś tam się przypadkowo przedrze tyci tyci - ale zawsze -  wyciek pamięci czy coś podobnego.

Byłem ciekaw waszych doświadczeń z podobnymi problemami jakkolwiek jestem bardzo wdzięczny za ogólne zainteresowanie.

Co do samego problemu to mamy duże pliki tekstowe zawierające kwerendy geograficzne w formacie:

A,B,C,D,F,

A,B,C,D,F,

A,B,C,D,F,

itd...

Dane geograficzne w magazynie są tak porozmieszczane, że wykonanie kwerend będzie wydajniejsze jeśli nie będziemy musieli skakać chaotycznie po całym świecie.

Czyli sortujemy te wszystkie kwerendy tak - najpierw państwo, potem miasto itd - oczywiście dane nie są poukładane w tej kolejności w wierszach dlatego potrzebny jest nasz własny komparator.

i to w zasadzie tyle ;)

dzięki za pomoc

[Piotr Gwiazda]

Nie jestem do końca pewien, czy trzymanie tych kwerend geograficznych, które jak napisałeś mają jakąś konkretną strukturę, w plikach to jest najlepszy pomysł. Bardziej mi to wygląda na strukturę dla jakiegoś magazynu danych typu document store.

[Wojciech Erbetowski]

Sortowanie merge sort czy inne ogólnego zastosowania jest wariactwem, gdy masz tak mocno ograniczoną domeną.

Rozumiem, że spodziewasz się, jak rozłożone są dane w tych plikach średnio?

Nie kapuję do końca tej struktury (może przykładzik prawdziwych danych),

ale sugeruję sortowanie kubełkowe. Będzie skrajnie proste do zaimplementowania i otestowania,

wydajne na poziomie O(n) oraz możesz je stosować na częściach (on-demand a nie upfront) i do tego łatwo utrzymywać,

dla przychodzących nowych danych. No i oczywiście działa pięknie strumieniowo, bez przeciążania pamięci.

Żeby wyjaśnić - lecisz plik po pliku i rozrzucasz dane do kubełków, wg przedziałów wartości.

Powiedzmy mam 2 pliki do posortowania:

a.txt:

Ania

Krysia

Helena

b.txt:

Beata

Matylda

Znając dziedzinę (żeńskie imiona), sprawdzam czętości występowań imion (u Ciebie to by były zagęszczenia lokalizacji)

i dzielę na odpowiednią ilość kubełków (koniecznie, aby liczba kubełków ~ O(n), a w kubełku < K elementow, dla pewnego K.

Powiedzmy u nas to kubełki A-K i N-Z i otrzymujemy pliki:

A-K.txt:

Ania

Krysia

Helena

Beata

N-Z.txt

Matylda

Wtedy sortujesz już pliki rozmiarów <K (łatwo załadować do pamięci i użyć dowolnego zastowoania).

Oczywiście można to zrobić w czasie pierwszego użycia danych.

To wymaga mało kodowania, ale posiedzenia z kartką i ołówkiem, aby poznać dziedzinę i dobrać kubełki.

Jeśli imion miałbym 5GB, to kubełki dzieliłbym np wg prefixu pierwszych 4 znaków:

AAAA.txt.

AAAB.txt 

and so on

Jeśli posortowane dane potrzebne są Ci jako jeden dlugi strumien, nic prostszego:

strumieniujesz: joinIterators(buckets[0].sortedIterator, ..., buckets[N/K].sortedIterator),

gdzie sorted iterator posortuje elementy w kubełku w czasie wyciągania elementów w runtime,

a nie w momencie utworzenia go.

Pozdrawiam,

Wojtek

--

[Paweł Włodarski]

Ok, dzięki za wszystkie odpowiedzi. Widzę, że największy problem z tego typu pytaniami to ile zdradzić szczegółów aby problem był jasny 

ale nie przytłaczający skorych do pomocy użytkowników forum ;)

Pomysłów na rozwiązanie tego problemu mam z tuzin jakkolwiek tutaj chciałem skupić się na znalezieniu gotowej biblioteki do użycia na produkcji.

Jak już wszystko zadziała to podzielę się doświadczeniami. Jeszcze raz dzięki za dyskusję!

pzdr

[Paweł Włodarski]

Jeśli kogoś interesuje jak sprawa sortowania tych plików się rozwiązała to 

statystyki i pomiary (plus trochę filozofii) można znaleźć tutaj : http://pawelwlodarski.blogspot.com/2012/11/sortowanie-duzych-plikow-i-geneza.html

pzdr