Weryfikacja powtarzalności

Przyjmijmy że posiadamy plik dyskowy X.txt. Jest to plik tekstowy z podziałem na wiersze; jego długość znacznie przekracza ilość dostępnej pamięci operacyjnej. Problem jest następujący: nasz program musi przeczytać cały ten plik (powiedzmy milion linii ;/) wiersz po wierszu i zapisać te linie do pliku Y.txt w taki sposob, aby unikalna linijka pojawila sie tylko raz. Innymi slowy: jeżeli wczytana linijka to XXX i jeszcze taka nie wystąpiła, to zapisać XXX do Y.txt; jeżeli natomiast linijka XXX już została raz zapisana do pliku, to należy ją zostawić w spokoju i iść dalej.

Problem jest tutaj z tą pamięcią... Zakładamy, że plik jest naprawdę duuuży i nie starczy nam RAMu żeby np. wpisywać linijki do tablicy albo listy ;/? Czy ktoś zna może rozwiązanie tego problemu np. w postaci jakiegoś sensownego algorytmu?

Bardzo dziękuję za pomoc i pozdrawiam,
Bulbin

Może by spróbować tak:

Załóżmy plik XXX.txt rozmiaru 1GB, RAMu do dyspozycji aplikacji np.: 20MB.
Plik XXX.txt -> YYY.txt

powtarzając
bierzesz kolejną linię z pliku XXX
póki nie znaleziono końca pliku lub ciągu
ładujesz do RAMU z pliku YYY linie do np.: 16MB
przeszukujesz linia po linii
jeśli znaleziono już taką linię, to przechodzisz do poczatku algorytmu, sprawdzając kolejną linię XXX
trafiłeś na koniec pliku - linii w nim nie ma - dopisz i przejedź do poczatku algorytmu, sprawdzając kolejną linię

Pseudokod:

poki (nie EOF(XXX.txt)) rob
{
  linia = pobierzKolejnaLinie(XXX.txt);
  poki (nie EOF(YYY.txt)) rob
  {
    linie = pobierzKolejneMax16MB(YYY.txt);
    jeśli (liniaZnalezionaWLiniach(linia, linie)) wtedy przerwijIPrzejdzDoKolejnegoWykonaniaGlownejPetli;
  }
  dopiszLinie(YYY.txt, linia);
}

Mhm, to już jest jakieś rozwiązanie :-). Szkoda tylko, że trzeba się będzie bawić w cochwilowe otwieranie i zamykanie plików. No i jeszcze ten czas wykonania... Ale jak na razie to jedyna propozycja więc trzeba się z nią zgodzić ;-). Czekam na jakieś alternatywne rozwiązania ;-).

teoretycznie mozna najpierw posortowac plik wejsciowy i pozniej tylko:

if(linia == poprzednia_linia)

//EDIT: Sebo, napisalaes to samo co ja czy ja nie rozumiem twego postu?
//złoZonosc, RZedu

Jeśli będziesz robił w ten sposób to wyjdzie złorzoność żedu O(n!)[!!!]

Najefektywniejszym sposobem jest posortowanie pliku wejściowego (złożoność sortowania O(n*log(n)) ) pousuwanie powtarzających się linijek ( O(n) ) i mamy gotowy plik yyy.txt

Jeśli plik yyy.txt ma zawierać linijki z xxx.txt w takiej samej kolejności jak tam wysstępowały to należy je ponumerować przed ich sortowaniem i potem posortować według tych numerków.

Złożoność takiego algorytmu będzie O(n*log(n)) i stawiam [browar] jeśli ktoś zaproponuje szybszy sposób

Tak sobie przeglądałem i wpadłem na taki pomysł, który z pewnością wymaga dopracowania, ale może do czegoś się przydać
Co wy na to, aby z każdej linijki zrobić skrót (może być suma), następnie skróty posegregować (tak jak pisaliście powyżej) i dopiero gdy dwa skróty będą takie same sprawdzać czy odpowiadające im linijki również są takie same? Przy założeniu że skróty zmieszczą się w pamięci, myślę że byłoby to szybsze niż segregowanie wszystkich linii z pliku. (Oczywiście zależy to od stosunku prędkości odczytu z dysku do prędkości obliczeń ;) ) Jeżeli się mylę - poprawcie mnie
Pozdrawiam
V-tec