Sortowanie zbioru uporządkowanych ciągów liczb

0

Witam,

Otóż mam takie zagadnienie (związane z poprzednimi na forum). Mam bardzo duży zbiór uporządkowanych ciągów liczb całkowitych postaci

(h,k,l,...)

Takich ciągów mam bardzo dużo (np. 300 tyś.) i potrzebuję je jakoś uporządkować (tak aby było to jakoś rosnąco względem kolejnych liczb itp.). Na początku myślałem, że mogę policzyć coś w stylu "checksum" dla tych refleksów i uporządkować je względem tak policzonej wartości. Zrobiłem to za pomocą algorytmu sortowania przez kopcowanie (heap sort) bo jest bardzo szybki (na tym mi zależy), ale to może nie być w moim przypadku dostatnie ogólne i wynik nie wygląda jakoś przepięknie. Myślałem zatem aby zrobić to za pomocą algorytmu sortowania pozycyjnego (radix sort), ale przyznam, że nie nie mam pojęcia jak zaimplementować istniejące kody (programuję w FORTRANie tylko...) do mojego przypadku.

Z góry dzięki za pomoc z objaśnieniu jak taki ew. algorytm miałby działać.

Radek

0

Ty te ciągi generujesz, czy masz dane?

0

Mam je jako dane. Niektóre mogą się powtarzać więc chcę je pogrupować itp.

0

Jeżeli bardzo nie zależy Ci na czasie porównywania (tzn. może sobie przez parę minut algorytm podziałać), to po prostu zrób dokładną funkcję porównującą, 300 tyś to nie tak dużo, zobacz czy najprostsze rozwiązanie przyniesie dobre wyniki (ja ogólnie przyjmuje zasadę, że jak dość prosty algorytm ma złożoność n log n to zwykle nie ma co komplikować, z drugiej strony głęboko się zastanawiam nad zastosowaniem rozwiązania kwadratowego). Jeżeli jednak potrzebujesz większej szybkości (w końcu robisz w FORTRANIE) to opisz dokładniej swój problem (zawartość ciągów, typy danych, jak te ciągi mają być posortowane).

0

W jakim celu chcesz je sortować? Jeżeli tylko po to, żeby wyrzucić duplikaty to są efektywniejsze metody niż sortowanie.

0

Dzięki za pytania i sugestie. Odpowiadając na pytania. No troszkę mi zależy na szybkości bo powinno to robić kilka sekund a nie minut... Algorytm co robi to kilka-kilkanaście minut to wymyśliłem wcześniej i jest trochę bezsensowny. Najlepiej aby coś miało złożoność typu O(n log n). Struktura danych to po prostu tablica typu n x k gdzie n to liczba wierszy a k to liczba kolumn odpowiadająca liczbie liczb całkowitych w tych ciągach. Czyli obrazowo dla k = 3:

(h1, k1, l1) [ h1 k1 l1 ]
(h2, k2, l2) --> [ h2 k2 l2 ]
(h3, k3, l3) [ h3 k3 l3 ]

Nie chcę natomiast wyrzucać powtarzających się elementów bo są z nimi związane też inne dane (tj. pewne wielkości fizyczne). Chcę te ciągi pogrupować a potem porobić różne statystyki na już ładnie zgrupowanych elementach. A jak mają być posortowane to np. najładniej by jakoś było coś w stylu, że najwolniej zmienia się ostatnia liczba a najszybciej pierwsza w ciągu czy jakoś tak.

Z góry dzięki,

Radek

0

Ogólnie takie moje przemyślenia są takie, że można zrobić (jak ktoś kiedyś mi na forum sugerował) zrobić sortowanie pozycyjne (radix sort) a w obrębie każdej pozycji np. zrobić sortowanie przez scalanie (bo jest szybkie i stabilne). Nawet na stronie tutaj znalazłem jak to zrobić mniej więcej:

Merge Sort

Z tym, że jako, że nie znam w ogóle C++ to nie jestem w stanie tego przetworzyć na kod FORTRANa... Fajne jest to, że jest to wersja nierekurencyjna co ułatwi mi dalszą modyfikacje (a muszę potem takowe wprowadzić aby mi też odpowiednio sortował kilka macierzy razem z tą z ciągami).

Radek

0

Jedno usprawnienie to by było sortowanie indeksów wierszy, a nie wierszy, a po tym ewentualne skopiowanie tablicy. O ile dobrze pamiętam to w Fortranie tablice są ułożone w pamięci kolumnami, a w C wierszami, więc odczytanie i zapisanie wiersza w Fortranie jest zdecydowanie wolniejsze przy dużej ilości kolumn. Moim pomysłem by było spróbowanie użycia jakieś gotowej biblioteki z sortowaniem, może po prostu twoja implementacja jest zbyt wolna, wrzuć kod to w czymś pomożemy.

edit - to wygląda ładnie:

http://fortranwiki.org/fortran/show/qsort_inline
</p>
0

Jeśli potrzebujesz tylko pogrupować elementy to wystarczy stworzyć hash mapę z duplikatami. Czas tworzenia takiej mapy to O(n) tak więc szybciej niż O(nlogn).

1 użytkowników online, w tym zalogowanych: 0, gości: 1