W14 sortowanie plików, bioinformatyka, Semestr 2, metody programowania
[ Pobierz całość w formacie PDF ]
IIUJ Metody Programowania strona: 1 Wykład 14. Sortowanie zewnętrzne (sortowanie plików) Sortowanie zewnętrzne , sortowanie plików (ang. external sort ) – to rodzaj metod sortowania, które są stosowane, kiedy z pewnych względów nie jest możliwe jednoczesne umieszczenie wszystkich elementów zbioru sortowanego w pamięci operacyjnej, przy zachowaniu wymogu sekwencyjnego dostępu do pliku. Zakładamy, że pamięć zewnętrzna jest podzielona na bloki, a każdy blok jest identyfikowany przez swój adres. Plik jest listą n rekordów (o tym samym formacie). Ponadto zakładamy, że każdy plik zajmuje pewną liczbę bloków, a każdy blok mieści k rekordów. Za operację dominującą przyjmujemy przesłanie jednego bloku między pamięcią operacyjną a pamięcią zewnętrzną. W plikach nieuporządkowanych rekordy są ułożone w dowolnej kolejności. Wykonanie operacji search() wymaga n/k przesłań bloków, a wykonanie operacji insert() i delete() potrzebuje 1+n/k przesłań. Podstawową wadą jest w tym przypadku długi czas działania operacji gdyż rekordy: a 1 , . . . , a n pliku są przetwarzane sekwencyjnie , tzn.: - aby odczytać a k należy bezpośrednio przedtem odczytać a 1 , . . . ,a k-1 , - aby zapisać nową wartość a k należy zapisać bezpośrednio przedtem a 1 , . . . , a k-1 . Jedną z najważniejszych metod sortowania plików jest sortowanie przez łączenie. Łączenie (lub scalanie) oznacza wiązanie dwóch (lub więcej) ciągów rekordów uporządkowanych w jeden ciąg uporządkowany. 1. Metoda zrównoważona (von Neumann) p1, p2, p3, p4 – pliki (fizycznie, na ogół, odrębne urządzenia) dane wejściowe: n rekordów o kluczach a 1 , . . . . ,a n , na pliku p4 pamięć RAM mieści m rekordów IIUJ Metody Programowania strona: 2 Krok 1 : (sortowanie wstępne i rozdzielanie). Wczytuj po m kolejnych rekordów do pamięci operacyjnej, sortuj i zapisuj posortowane ciągi długości m na pliki p1 i p2 na przemian. Krok 2: (scalanie i rozdzielanie). Scalaj po jednym posortowanym ciągu z p1 i p2 i zapisuj na przemian na pliki p3 i p4 (długość posortowanych ciągów podwaja się). Iteracja: Powtarzaj krok 2 zamieniając rolami p1 , p2 z p3 , p4 aż do osiągnięcia sytuacji gdy pozostaje jeden plik posortowany zawierający cały ciąg. Algorytm scalania posortowanych ciągów: taki jak dla tablic posortowanych (zamiast dwóch tablic wejściowych są dwa ciągi posortowane: jeden z jednego, drugi z drugiego pliku). Przykład. Po kroku 1 mamy 16 ciągów rosnących długości m rozdzielonych na p1 i p2, przy czym <k> - oznacza k - ty ciąg w kolejności utworzenia: p1: <1> <3> <5> <7> <9> <11> <13> <15> p2: <2> <4> <6> <8> <10> <12> <14> <16> po kroku 2: p3: (<1>*<2>) (<5>*<6>) (<9>*<10>) (<13>*<14>) p4: (<3>*<4>) (<7>*<8>) (<11>*<12>) (<15>*<16>) (<k>*<l>) - oznacza ciąg powstały ze scalenia posortowanych ciągów <k> oraz <l> następna iteracja kroku 2 daje: p1: ((<1>*<2>)*(<3>*<4>)) ( (<9>*<10>)*(<11>*<12>)) p2: ((<5>*<6>)*(<7>*<8>)) ((<13>*<14>)*(<15>*<16>)) (ciągi posortowane są już 4*m – elementowe) IIUJ Metody Programowania strona: 3 następna: p3: (((<1>* <2>)*( <3>* <4>))*(( <5>* <6>)*( <7>* <8>))) p4: (((<9>*<10>)*(<11>*<12>))*((<13>*<14>)*(<15>*<16>))) (po jednym ciągu długości n/2 na każdym pliku) i ostatnia daje cały ciąg posortowany na pliku p1 . Jeśli n nie jest potęgą dwójki to pojawiają się ciągi 'bez pary' – które się przepisuje. Złożoność mierzy się liczbą faz (czyli iteracji kroku 2) - jest ich: log (n/m) odczytów i zapisów rekordów na pliki - w każdej fazie jest n odczytów, n zapisów, oraz nie więcej niż n porównań kluczy, w sumie zatem: ( n log (n/m)) operacji. dodatkowo: sortowanie wstępne fragmentów m-elementowych, zakładając sortowanie szybkie: ( n/m * m log m) = ( n log m) porównań Uwagi. 1. Im większa pamięć RAM (parametr m ) tym szybsze sortowanie 2. Mając 2*k plików, k>2, można wykonywać scalanie równocześnie nie dwóch lecz k ciągów (scalanie k - kierunkowe). Liczba faz maleje do log k (n/m). 3. Jeśli k jest duże to można kolejne elementy przy scalaniu wyłaniać utrzymując kopiec (kolejkę priorytetową) długości k zawierający klucz aktualnie czytany z każdego wejściowego pliku. Wówczas kolejny element zapisywany na wyjście otrzymywany jest w wyniku operacji Extract_min, a "doczytywany" z tego samego pliku wejściowego element na miejsce usuniętego wstawiany jest operacją Insert (można obie operacje połączyć w jedną "Replace_min"). IIUJ Metody Programowania strona: 4 2. Sortowanie wielofazowe (czasami „polifazowe”, pod wpływem ang. polyphase sort ) algorytm wynaleziony przez R. L. Gilstada Dysponując k+1 plikami można rozdzielić początkowe ciągi tak, aby potem we wszystkich etapach móc stosować scalanie k - kierunkowe. Dla k=2 schemat rozdziału ciągów wg wartości liczb Fibonacciego, np. liczba podciągów n/m = 13, rozdzielone na 8 i 5 podciągów: p1: <1> <2> <3> <4> <5> <6> <7> <8> p2: <9> <10> <11> <12> <13> p3: pusty Scalanie podciągów parami, z dwóch niepustych plików na aktualnie pusty plik, aż jeden ze scalanych plików będzie pusty. po fazie 1: p1: <6> <7> <8> p2: pusty p3: (<1>*<9>)( <2>*<10>)( <3>*<11>)( <4>*<12>)( <5>*<13>) po fazie 2: p1: pusty p2: (<6>*<1>*<9>) ( <7>*<2>*<10>) ( <8>*<3>*<11>) p3: (<4>*<12>)( <5>*<13>) po fazie 3: p1: (<4>*<12>*<6>*<1>*<9>) ( <5>*<13>*<7>*<2>*<10>) p2: ( <8>*<3>*<11>) p3: pusty po fazie 4: p1: (<5>*<13>*<7>*<2>*<10>) p2: pusty p3: (<8>*<3>*<11>*<4>*<12>*<6>*<1>*<9>) po fazie 5: p1: pusty p2: (<5>*<13>*<7>*<2>*<10>*<8>*<3>*<11>*<4>*<12>* <6>*<1>*<9>) // cały ciąg p3: pusty Metoda daje się uogólnić na dowolną wartość parametru k . IIUJ Metody Programowania strona: 5 3. B-drzewa 1 B-drzewa są szczególnie użyteczne przy organizacji danych w pamięci zewnętrznej. Pierwszą propozycję zastosowania B-drzew jako struktur danych dla pamięci zewnętrznej przedstawili R. Bayer i E. Mcreight w 1972 roku. Jak wspomniano wcześniej aby zapewnić wydajność operacji dostępu do pamięci zewnętrznej dane są odczytywane i zapisywane blokami (stronami). B-drzewa rzedu m to drzewa, których węzłami są bloki pamięci zewnętrznej zawierające klucze w postaci uporządkowanej oraz odsyłacze, przy czym jeden blok zawiera od m do 2m kluczy (wyjątkiem jest korzeń, który może zawierać od 1 do 2m) i dlatego bloki są zawsze przynajmniej na wpół wypełnione kluczami. Blok posiadający k kluczy zawsze zawiera k+1 wskaźników (potomków - dzieci). Liczba m (np. 1024) jest kluczowa w wydajności B-drzew , ponieważ wysokość drzewa dla ogromnej ilości węzłów liczonej w milionach lub miliardach będzie bardzo mała. Np. dla m=1024 w B- drzewie o wysokości 2 można umieścić około miliona bloków. Definicja B-drzewo rzędu m to drzewo, w którym : - klucze w bloku są uporządkowane niemalejąco, - każdy blok zajmuje pamięć dla 2m kluczy i 2m+1 odsyłaczy, - każdy blok (nie korzeń) zawiera k kluczy, przy czym m ≤ k ≤ 2m . - blok-korzeń zawiera k kluczy, przy czym 1 ≤ k ≤ 2m . - każdy blok-liść o k kluczach ma 0 następników - każdy blok-nie-liść o k kluczach ma k+1 następników - wszystkie bloki-liście są na jednym poziomie. Fakt. Jeśli w bloku są klucze i odsyłacze: NEXT[0] INFO[1] NEXT[1] INFO[2] NEXT[2] … NEXT[k-1 ] INFO[k] NEXT[k+1] to wszystkie klucze poddrzewa wskazywanego przez NEXT[i] mają wartości z przedziału ( INFO[i] , INFO[i+1] ); przy czym INFO[0]= -∞ , INFO[ostatni+1] = +∞ 1 Na podstawie wykładu pana dr Jacka Lembasa „ ASD: B-drzewa” [ Pobierz całość w formacie PDF ] |