Sortowanie plików Mariusz: Sortowanie plików Na wikipedii podali że najlepiej nadaje się do tego sortowanie przez scalanie lub jakaś hybryda z wczytywaniem fragmentów pliku do pamięci, sortowanie w pamięci ulubionym algorytmem (tutaj chcałbym zauważyć że quicksort is not always so quick) a następnie z scalaniem fragmentów Przypuśćmy że chcemy posortować linie w pliku przez scalanie Ograniczeniem jest to że nie znamy liczby linii w pliku (przeczytanie pliku aby poznać liczbę linii nie jest rozwiązaniem bo może nie zmieścić się w zakresie typu int )

TC: "przeczytanie pliku aby poznać liczbę linii nie jest rozwiązaniem" słyszałeś o tablicach?

Mariusz: 1. Tablica nie jest przystosowana do dostępu sekwencyjnego 2. Co gdy zawartość pliku nie zmieści się w pamięci ?

jc: @Mariusz. Tak, jak piszesz, stosujesz sortowanie przez łączenie. Fragmenty, które mieszczą się w pamięci sortujesz dowolną metodą, a potem już sortujesz przez łączenie.

Mariusz: Problem w tym że idee znam ale z napisaniem w miarę zrozumiałego pseudokodu na podstawie którego można łatwo zapisać kod źródłowy w ulubionym języku programowania to już gorzej Dla sortowania tablic taki pseudokod mają np w Algorithms unlocked

jc: @Mariusz Pomyś, że masz dużo małych posortowanych fragmentów. Sklejasz po dwa, potem po dwa, ..., aż zostanie jeden fragment. Problemem jest sklejanie. Pomyśl, że masz dwa stosy kartek z numerami. Bierzesz kartkę z mniejszą liczbą i odkładasz na trzeci stos, itd. Ale to przecież jest opisane w dziesiątkach miejsc ...

Mariusz: Chwalisz się że byłeś nauczycielem a nie potrafisz nawet dobrze opisać algorytmu to samo było np z rozkładem Jordana "Ale to przecież jest opisane w dziesiątkach miejsc ..." tak jedynie Wirth o tym trochę pisze ale w przeciwieństwie do Cormena trudniej napisać kod na podstawie tego co napisał U Diksa jest o tym tylko kilka zdań Większość w tym Cormen ogranicza się jednak do sortowania tablic

g: Najprościej było by każdą wczytaną linię wstawiać od razu w dobre miejsce listy. Miejsce wstawienia najszybciej znajdziemy podziałem binarnym.

Mariusz: Algorytm rozdzielania serii początkowych (1) Wczytaj pierwsze elementy z pliku źródłowego do tablicy, utwórz kopiec i ustaw licznik serii. Jeżeli rozmiar pliku jest niewiększy od rozmiaru kopca przejdź do kroku (3). (2) Dopóki nie wyczerpiesz pliku źródłowego, wykonuj: (2.1) Zapisz do pliku wyjściowego najmniejszy element z korzenia dolnego kopca (2.2) Odczytaj kolejny element z pliku źródłowego; jeżeli ten element należy do bieżącej serii, umieść go w korzeniu dolnego kopca i odtwórz dolny kopiec, w przeciwnym przypadku: (2.3) Jeżeli kolejny element odczytany z pliku źródłowego należy do nowej serii, wtedy umieść ostatni element kopca w korzeniu dolnego kopca, zmniejsz rozmiar dolnego kopca o 1 i umieść w korzeniu górnego kopca (poprzedni koniec dolnego kopca) odczytany element: (2.3.1) jeżeli korzeń górnego kopca znajduje się w pierwszej połowie całej tablicy, odtwórz górny kopiec; (2.3.2) jeżeli opróżnisz dolny kopiec, zwiększ liczbę serii o 1; kopiec górny wypełnia całą tablicę; (3) Dopóki tablica nie jest wyczerpana, wykonuj: (3.1) Zapisz w pliku element z korzenia dolnego kopca, przestaw element z końca kopca na początek, zmniejsz rozmiar dolnego kopca o 1 i odtwórz dolny kopiec; (3.2) Jeśli istnieje górny kopiec, przestaw ostatni element w górnym kopcu na jego korzeń (pozycja zwolniona przez ostatni element dolnego kopca) i zmniejsz o 1 indeksy górny i dolny górnego kopca − jeżeli indeks korzenia górnego kopca znajduje w pierwszej połowie całej tablicy, odtwórz górny kopiec; (4) Jeśli wyczerpano dolny kopiec, a istnieje górny kopiec, należy opróżnić go zwiększając liczbę serii o 1, jeśli chociaż raz nastąpiła zmiana serii (wykonanie kroku 2.3) . Algorytm sortowania polifazowego (1) Dopóki nie wyczerpiesz pliku źródłowego lub rozłożysz serie na n−1 plikach wyjściowych zgodnie z wymaganiami 1−go poziomu, wykonuj, co następuje: (1.1) Wyznacz na 1−ym poziomie kolejny aktywny plik wyjściowy zgodnie z planowaną liczbą serii idealnych czyli liczb Fibonacciego rzędu n−2 (1.2) Weź z pliku źródłowego po 1 serii i umieść na wyznaczonym pliku wyjściowym; (2) Dopóki nie wyczerpiesz pliku źródłowego, wykonuj, co następuje: (2.1) Wyznacz na wybranym poziomie aktywny plik wyjściowy zgodnie z planowaną liczbą serii idealnych czyli liczb Fibonacciego rzędu n−2. Jeśli osiągnięto idealną liczbę serii w tym pliku, przejdź do kroku (2.3) (2.2) Umieść na wyznaczonym pliku wyjściowym kolejną serię. Jeśli należy ona do serii umieszczonej jako ostatnia w pliku, umieść w nim następną serię i przejdź do kroku (2.1) lub zwiększ liczbę fikcyjnych serii tego pliku, jeżeli został wyczerpany plik źródłowy i przejdź do kroku (3). (2.3) Wybierz wyższy poziom rozkładania serii zgodnie z ciągiem Fibonacciego rzędu n−2, wyznacz idealną oraz fikcyjną liczbę serii dla każdego z n−1 plików wyjściowych; (3) Ustaw n − 1 plików wejściowych; (4) Dopóki nie połączysz elementów z wszystkich serii w jedną serię, czyli nie osiągniesz poziomu 0, wykonuj: (4.1) Ustaw n − ty plik wyjściowy i wyznacz najmniejszą liczbę serii na danym poziomie {idealna liczba serii w pliku n−1}; (4.2) Dopóki nie wyczerpiesz wyznaczonej idealnej liczby serii, które należy połączyć na danym poziomie, wykonuj: (4.2.1) wyznacz aktywne pliki wejściowe nie posiadające serii fikcyjnych; (4.2.2) jeśli istnieją serie fikcyjne dla wszystkich plików wejściowych, to połącz po 1 serii z każdego pliku w jedną serię fikcyjną na pliku wyjściowym, w przeciwnym przypadku wykonaj: (4.2.3) połącz po 1 serii fikcyjnej z każdego z nieaktywnych plików wejściowych, jeśli istnieją, oraz dopóki nie wyczerpiesz jednej serii rzeczywistej na każdym z aktywnych plików wejściowych, wykonuj: (4.2.2.1) weź po jednej serii o tym samym numerze z każdego aktywnego pliku wejściowego; (4.2.2.2) połącz te serie w jedną i umieść ją w pliku wyjściowym; (4.2.2.3) eliminuj pliki z wyczerpaną serią lub wyczerpane; (4.2.4) zmniejsz liczbę serii idealnych łączonych na danym poziomie; (4.3) Zamień pliki, plik wyjściowy staje się plikiem wejściowym o numerze1; (4.4) Zmniejsz poziom oraz wyznacz serie idealne oraz fikcyjne Znalazłem takie coś tylko jak na podstawie powyższego opisu algorytmu napisać kod

Mariusz: g tutaj chodzi o możliwość sortowania także plików które nie zmieszczą się w pamięci RAM

Dziadek Mróz: Każdy plik ma nagłówek, wczytaj nagłówek do struktury i wtedy sobie sortuj tablicę struktur

Mariusz: Bardziej mi chodzi o realizację algorytmu z 29 stycznia 11:02 bo tak jak już wcześniej pisałem chodzi mi o możliwość sortowania plików które nie zmieszczą się w RAM

Dziadek Mróz: Sortowanie linii w pliku tekstowym? #include <iostream> #include <fstream> #include <vector> #include <algorithm> int main(int argc, char **argv) { std::vector<std::string> vec; std::ifstream ifs; ifs.open("plik.txt"); if (ifs) { while (!ifs.eof()) { std::string linia; std::getline(ifs, linia); vec.push_back(linia); } std::sort(vec.begin(), vec.end()); for (std::vector<std::string>::iterator it = vec.begin(); it != vec.end(); it++) { std::cout << *it << std::endl; } } else { perror("plik.txt"); } }

Mariusz: To co da się wczytać do pamięci to ja sobie posortuje kopcem w przypadku tablicy albo scalaniem w przypadku nieco bardziej rozbudowanego stosu Chodzi o przypadek gdy pamięci RAM jest zbyt mało aby posortować linie w pliku

Mariusz: Tutaj chodzi o sortowanie przez scalanie scalanie proste (nie jestem pewien czy można by było przystosować do tego iteracyjny algorytm sortowania tablic przez scalanie ) Idea jest taka że przed iteracjami mamy pojedyncze linie w pliku posortowane Po pierwszej iteracji ciągi składające się z dwóch linii są posortowane Po drugiej iteracji ciągi składające się z czterech linii są posortowane itd Wprowadzenie liczników do tego algorytmu ograniczyłoby jego możliwości w pewnym momencie moglibyśmy przekroczyć zakres typu int scalanie naturalne wykorzystuje to że już na starcie plik może zawierać ciągi posortowane zawierające więcej niż jedną linię (Gdzieś w sieci jest do tego kod źródłowy) Jest jeszcze wielokierunkowe scalanie wyważone scalanie wielofazowe którego opis dałem 29 sty 11:02