Sortowanie zbioru uporządkowanych ciągów liczb

Odpowiedz Nowy wątek
2011-08-17 02:04
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

Pozostało 580 znaków

2011-08-17 09:48
0

Ty te ciągi generujesz, czy masz dane?

Pozostało 580 znaków

2011-08-17 11:12
0

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

Pozostało 580 znaków

2011-08-17 20:45
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).

Jeszcze jedno, przy usuwaniu powtarzających się elementów możesz wykorzystać hashowanie, choć szczególnie uważaj przy liczbach rzeczywistych, najlepiej znajdź jakieś informacje na ten temat w google (tzn. hashowanie liczb zmiennoprzecinkowych). - Zjarek 2011-08-17 20:48
Dodatkowo jeżeli sporo ciągów się powtarza, to możesz użyć do sortowania zrównoważonego drzewa (m log n, gdzie n to ilość różnych elementów, a m ogólna ilość elementów), lub może nawet trie, to drugie może być przydatne, gdy ilość różnych możliwych elementów w ciągach jest mała. - Zjarek 2011-08-17 20:56

Pozostało 580 znaków

2011-08-17 22:36
0

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

Pozostało 580 znaków

2011-08-17 23:22
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

edytowany 1x, ostatnio: rkaminski, 2011-08-17 23:23

Pozostało 580 znaków

2011-08-17 23:51
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

o merge sort zapomnij. Złożoność czasowa 2nlogn i jest stabilna, ale złożoność pamięciowa jest ogromna. W dodatku który fortran, bo chyba starsze nie miały dynamicznej alokacji pamięci, a tu jest przydatna. - Koziołek 2011-08-18 09:04
Jest wariant merge sort, który działa w miejscu więc złożoność pamięciowa jest O(1). A poza tym słyszałem że fortran nie wspiera rekurencji. Czy to prawda> - 0x200x20 2011-08-18 10:07
Nowsze wersje wspierają. Starsze niekoniecznie :D - Koziołek 2011-08-18 10:09

Pozostało 580 znaków

2011-08-17 23:51
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>
edytowany 2x, ostatnio: Zjarek, 2011-08-17 23:56

Pozostało 580 znaków

2011-08-18 12:57
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).

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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