logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

Jakie algorytmy sortowania plików: jednofazowe, dwufazowe, polifazowe?

And! 15 Paź 2004 19:04 5844 14
REKLAMA
  • #1 914869
    And!
    Admin grupy Projektowanie
    Posty: 9058
    Pomógł: 175
    Ocena: 783
    Szukam info o algorytmach sortowania plików:

    -proste jednofazowe
    -proste dwufazowe

    -naturalne jednofazowe
    -naturalne dwufazowe

    -polifazowe

    Problem w tym że nazwy algorytmów któe otrzymałem nie są zbyt popularne i mam problem ze znalezieniem algorytmów.

    Chyba dla utrudnienia zamiast np. mergsort dostałem jakieś dziwne nazwy.

    Zamykam. - arnoldziq
  • REKLAMA
  • #2 915070
    Xitami
    Poziom 29  
    Posty: 1130
    Pomógł: 118
    Ocena: 31
    mam książkę "Software Tools in Pascal" by Brian W. Kernighan (był chyba jeszcze jakiś współautor) kupiłem w antykwariacie już bez dyskietki, skaner mi zdechł, ale kiedyś widziałem gdzieś w sieci komplet źródeł z tej książki, mam polskie wydanie "Narzędzia programistyczne w języku pascal"
    oczywiście w księgarniach jest "The art of computer programming" papcia Knutha (drożyzna)
    a słyszałeś o tacces'ie? b-tree, nie są to drzewa binarne, nie pamiętam już anatomii ;) był chyba też plik indeksu, stała (>4 bajty) wielkość rekordu
    szukaj hasła EXTERNAL SORTING (sortowanie zewnętrzne)
    na mojego czuja, z tych nazw które podałeś nie wiele wyniknie
  • REKLAMA
  • #5 915244
    And!
    Admin grupy Projektowanie
    Posty: 9058
    Pomógł: 175
    Ocena: 783
    Chodziło mi o sortowanie plików.

    A szczególnie o ew nazwy zamienne do tych które podałem gdyż nie mogę znaleźć żdnych sensownych informacji.
  • REKLAMA
  • #6 915310
    Xitami
    Poziom 29  
    Posty: 1130
    Pomógł: 118
    Ocena: 31
    nic poza "external" nie przychodzi mi do głowy, szukasz terii czy walczysz z czymś konkretnym?
  • #8 915421
    Xitami
    Poziom 29  
    Posty: 1130
    Pomógł: 118
    Ocena: 31
    proste jednofazowe czyli jakikolwiek algorytm (no teraz niech ktoś powie że bąbelki są dobre) i zamias indeksowania tablicy indeksowanie pliku?

    dwufazowe? hm, może tak:
    1 tworzymy indeks (jak? może drzewo?)
    2 przepisujemy oryginalny plik już w dobrej kolejności
  • #9 915544
    And!
    Admin grupy Projektowanie
    Posty: 9058
    Pomógł: 175
    Ocena: 783
    Owszem to dość optymalne.

    Tyle że z tego co wiem te algorytmy sortowania zewnętrznego
    (te o które pytam)
    zakładają sekwencyjny a nie indeksowy (swobodny) dostęp do pliku.

    W dodatku jest tam pojęcie ilości taśm które nie bardzo rozumiem.
    (z kilku plików naraz ? )
  • REKLAMA
  • #11 915920
    And!
    Admin grupy Projektowanie
    Posty: 9058
    Pomógł: 175
    Ocena: 783
    No cóż dlatego sekwencyjny bo takie mam zadanie do zrealizowania.
    Ma być to program bardziej dydaktyczny niż użytkowy (porównanie złożoności w/w algorytmów).
  • #12 915975
    Xitami
    Poziom 29  
    Posty: 1130
    Pomógł: 118
    Ocena: 31
    ostatni etap, scalanie pośrednich plików to będzie chyba MERGE SORT
  • #13 916836
    And!
    Admin grupy Projektowanie
    Posty: 9058
    Pomógł: 175
    Ocena: 783
    Tak do tego już doszedłem że sortowanie proste to MergeSort.

    Teraz się zastanawiam nad różnicą w jedno i dwu fazowym oraz w ilości taśm (chyba chodzi o ilość plików na które jest dzielony plik główny)
  • #14 916907
    Xitami
    Poziom 29  
    Posty: 1130
    Pomógł: 118
    Ocena: 31
    jednofazowe i pliki tylko sekwencyjne? jeśli danych jest więcej niż pamięci operacyjnej to nie mam pomysłu.

    ilość pomocniczych plików to niby (ilość danych)/(wielkość pamięcio oper.), ale ładniej by było przyjąć jakąś małą liczbę, więc scalania nie wykonamy raz na koniec, ale za każdym razem kiedy ilość pośrednich plików osiągnie określoną liczbę.

    porównanie złożoności? czyli w zasadzie nie trzeba by pisać programu tylko porachować trochę ołówkiem na papierze, choć nie - trzeba by zmierzyć czasy: odczytu, zapisu, sortowania w pamięci. uwzględnić kiedy dane losowe, wstępnie posortowane w oczekiwanym porządku, kiedy w odwrotnym.
    a do pomiarów z zegarkiem w ręku to trzeba pamiętać o wielkości buforów dyskowych (przy małym pliku wszystko może odbyć sięw RAM i pomiar o niczym nie powie), przydał by się osobny dysk (lub choć partycja). defragmentacja też wpłynie na czas wykonania
  • #15 917026
    jiwaniuk
    Poziom 31  
    Posty: 1393
    Pomógł: 142
    Ocena: 145
    Cała teoria o którą pytasz (łącznie z algorytmami napisanymi w Pascalu) opisana jest w książce "Algorytmy+Struktury danych=Programy autorstwa Niklausa Wirtha na stronach 99 do 129.

    Pozdrawiam wszystkich

    jjanek

Podsumowanie tematu

✨ Dyskusja dotyczy algorytmów sortowania plików zewnętrznych, w szczególności prostych jednofazowych, dwufazowych, naturalnych oraz polifazowych. Wskazano, że popularne nazwy tych algorytmów mogą różnić się od tych podanych przez pytającego, a kluczowym terminem jest "external sorting" (sortowanie zewnętrzne). Algorytmy te operują na danych większych niż pamięć operacyjna i często zakładają sekwencyjny dostęp do plików, co historycznie wiązało się z użyciem taśm magnetycznych. W implementacji dydaktycznej ważne jest zrozumienie różnic między sortowaniem jednofazowym a dwufazowym, gdzie dwufazowe może polegać na tworzeniu indeksu i scalaniu plików. Ilość taśm (plików pomocniczych) wpływa na sposób dzielenia i scalania danych. W praktyce scalanie pośrednich plików realizowane jest metodą Merge Sort. Wskazano również na potrzebę uwzględnienia parametrów takich jak rozmiar buforów, rodzaj danych (losowe, wstępnie posortowane) oraz wpływ defragmentacji na pomiary czasu sortowania. Polecono literaturę: "Algorytmy+Struktury danych=Programy" Niklausa Wirtha oraz "Software Tools in Pascal" Briana W. Kernighana, a także materiały dydaktyczne polskich uczelni wyższych.
Wygenerowane przez model językowy.
REKLAMA