Jak posortowac plik o dowolnym formacie majacy np 600MB ?--Ucz się ucz bo......
Na jakiej zasadzie ma przebiegać sortowanie pliku "o dowolnym formacie"? Jak chcesz sortować *.exe??--Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
Vogel napisał:
Na jakiej zasadzie ma przebiegać sortowanie pliku "o dowolnym formacie"? Jak chcesz sortować *.exe??
>
>--
>Vogel [Delphi 6 PE]
>
>Life is just a dream, you know...
>[Cowboy Bebop]
Sortowanie pliku ma przebiegac bajt po bajcie. ( lub znaki, jak kto woli)--Ucz się ucz bo......
sgr napisał:
Sortowanie pliku ma przebiegac bajt po bajcie. ( lub znaki, jak kto woli)
A na co mi EXE posortowany bajt po bajcie? I 600MB = 600 000 000 znaków, co za problem posortować. Wystarczy mi 256 * 32 bajty pamięci do sortowania.--Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
Moze bys sobie pocztal:
http://www.4programmers.net/view.php?id=95
--Pamietaj że święto zmarłych stanie się także twoim świętem.
werw0e napisał:
Moze bys sobie pocztal:
>http://www.4programmers.net/view.php?id=95
Quicksort jest za wolnym algorytmem do sortowania takiej ilości danych(ktoś kiedyś pisał że próbował posortować 3.000.000 elementów i trwało to ponad tydzień, to tu by trwało kilka ładnych lat), to jest algorytm klasy (N log2N), co do normalnych celów jest naprawde wystarczające. A co do twojego problemu, to z tego co rozumiem chcesz je posortować wg kodów ASCII, wtedy wystarczy zadeklarować 256 elementową tablice longint i napisać procedure która sprawdzałaby kod danego znaku i zwiększało odpowiedni element tablicy o jeden, to byłby algorytm klasy (N).--
werw0e napisał:
Moze bys sobie pocztal: http://www.4programmers.net/view.php?id=95
Jeżeli ilość różnych znaków wynosi tylko 256 to po co mam sobie zawracać głowę takim wolnym sortowaniem? Jestem w stanie zrobić to o wiele szybciej.
Kurde, lamer mnie wyprzedził :P
--
Vogel [Delphi 6 PE]
Life is just a dream, you know...
[Cowboy Bebop]
Vogel napisał:
sgr napisał:
>Sortowanie pliku ma przebiegac bajt po bajcie. ( lub znaki, jak kto woli)
>
>A na co mi EXE posortowany bajt po bajcie? I 600MB = 600 000 000 znaków, co za problem posortować. Wystarczy mi 256 * 32 bajty pamięci do sortowania.
I co dalej z tymi 256*32 bajty. A co powiesz gdy zechce sortowac plik np 5GB ?--Ucz się ucz bo......
lamer napisał:
werw0e napisał:
>Moze bys sobie pocztal:
>>http://www.4programmers.net/view.php?id=95
>
>Quicksort jest za wolnym algorytmem do sortowania takiej ilości danych(ktoś kiedyś pisał że próbował posortować 3.000.000 elementów i trwało to ponad tydzień, to tu by trwało kilka ładnych lat), to jest algorytm klasy (N log2N), co do normalnych celów jest naprawde wystarczające. A co do twojego problemu, to z tego co rozumiem chcesz je posortować wg kodów ASCII, wtedy wystarczy zadeklarować 256 elementową tablice longint i napisać procedure która sprawdzałaby kod danego znaku i zwiększało odpowiedni element tablicy o jeden, to byłby algorytm klasy (N).
Jak chcesz sortowac zawartosc pliku przy pomocy 256 elementowej tablicy? Przeciez trzeba posortowac cala zawartosc pliku, pozamieniac bajty miejscami. A co powiesz gdy plik bedzie mial np 3GB ?
--Ucz się ucz bo......
sgr napisał:
>Jak chcesz sortowac zawartosc pliku przy pomocy 256 elementowej tablicy? Przeciez trzeba posortowac cala zawartosc pliku, pozamieniac bajty miejscami. A co powiesz gdy plik bedzie mial np 3GB ?
>
sqr, do programowania myslec trzeba, a nie tylko okienka ukladac.
liczysz ile razy kazdy bajt wystepuje przy pomocy tej tablicy i wychodzi Ci np 0: 2000 razy, 1 :350 razy, 2: 5512 razy itd.
A potem tworzysz plik skladajacy sie kolejno z 2000 bajtow 0, 350 bajtow 1 itd.--Pawel {Delphi 6 Personal}
Po pierwsze: naciśnij F1
pq napisał:
sgr napisał:
>
>>Jak chcesz sortowac zawartosc pliku przy pomocy 256 elementowej tablicy? Przeciez trzeba posortowac cala zawartosc pliku, pozamieniac bajty miejscami. A co powiesz gdy plik bedzie mial np 3GB ?
>>
>
>sqr, do programowania myslec trzeba, a nie tylko okienka ukladac.
>
>liczysz ile razy kazdy bajt wystepuje przy pomocy tej tablicy i wychodzi Ci np 0: 2000 razy, 1 :350 razy, 2: 5512 razy itd.
>
>A potem tworzysz plik skladajacy sie kolejno z 2000 bajtow 0, 350 bajtow 1 itd.
>
>--
>Pawel {Delphi 6 Personal}
>
>Po pierwsze: naciśnij F1
Wiem ze najlepsze sa najprostrze sposoby. Sam bym na to padl. Ale to nie ma byc takie proste. Skomplikumy nieco problem. Zalozmy ze plik sklada sie z rekordow, milionow rekordow ktore nalezy posortowac. I co wtedy ? Odpadaja wszelkie chwyty. I to nie ma byc rozwiazanie z typy 'sztuczka' lub obejscie problemu. To ma byc prawdziwe SORTOWANIE.
>sqr, do programowania myslec trzeba, a nie tylko okienka ukladac.
Programowaniem zajmuje sie juz 5 lat. I wiem ze bez myslenia nie da rady. Ale gdy pytam cie o sortoweanie, to nie wykrecaj sie prostymi metodami. Slyszles kiedys o External sorting ?--Ucz się ucz bo......
sgr napisał:
>Wiem ze najlepsze sa najprostrze sposoby. Sam bym na to padl. Ale to nie ma byc takie proste. Skomplikumy nieco problem. Zalozmy ze plik sklada sie z rekordow, milionow rekordow ktore nalezy posortowac. I co wtedy ? Odpadaja wszelkie chwyty. I to nie ma byc rozwiazanie z typy 'sztuczka' lub obejscie problemu. To ma byc prawdziwe SORTOWANIE.
>
Zdefiniowales problem jako sortowanie bajtow, wiec teraz sie nie dziw ze rozwiazanie nie pasuje do innego problemu. Nie wiem, jaka test Twoim zdaniem definicja prawdziwego SORTOWANIA. Moja: proces, po wykonaniu ktorego dane sa ulozone w zadanej kolejnosci.
>Programowaniem zajmuje sie juz 5 lat. I wiem ze bez myslenia nie da rady. Ale gdy pytam cie o sortoweanie, to nie wykrecaj sie prostymi metodami. Slyszles kiedys o External sorting ?
OK, sorry, nie chialem Cie urazic. Zdziwilo mnie jedynie ze nie zalapales idei. Przynjamniej tak odebralem to co pisales. BTW, to nie ja 'wykrecilem sie prostymi metodami', ten prosty i piekny pomysl pochodzi od lamer'a.
Nie slyszalem... Mozesz mnie oswiecic, jesli zechcesz.
--
Pawel {Delphi 6 Personal}
Po pierwsze: naciśnij F1
pq napisał:
Nie slyszalem... Mozesz mnie oswiecic, jesli zechcesz.
Metody sortowania plików znajdujących się na nośnikach innych niż pamięć. W takich algorytmach mniej istotna jest złożoność algorytmu, a bardziej liczba koniecznych przejść przez plik w celu odczytania. Dzięki temu można w miarę szybko posortować duże ilości danych.
sgr: Wydaje mi się, że w twoim przypadku najlepszym sposobem (ale nie koniecznie najprostszym) byłoby połączenie polyphase merging z metodą radix (przeszukiwanie bitowe zhaszowanych rekordów). Ale głowy nie dam, że to da najlepsze efekty (nawet nie wiem, jak to w praktyce zastosować - to tylko teoria)--Jest jeszcze jeden błąd ... :)
Apel: Piszcie w tematach o jaki język programowania chodzi np. : [Delphi], [C++], itp.
<quote>pq napisał:
Nie slyszalem... Mozesz mnie oswiecic, jesli zechcesz.
Metody sortowania plików znajdujących się na nośnikach innych niż pamięć. W takich algorytmach mniej istotna jest złożoność algorytmu, a bardziej liczba koniecznych przejść przez plik w celu odczytania. Dzięki temu można w miarę szybko posortować duże ilości danych.
sgr: Wydaje mi się, że w twoim przypadku najlepszym sposobem (ale nie koniecznie najprostszym) byłoby połączenie polyphase merging z metodą radix (przeszukiwanie bitowe zhaszowanych rekordów). Ale głowy nie dam, że to da najlepsze efekty (nawet nie wiem, jak to w praktyce zastosować - to tylko teoria)--Jest jeszcze jeden błąd ... :)
Dzieki za pomoc. Juz rozwiazalem problem tego sortowania. Posluzylem sie metoda nieco zblizona do sorotwania przez scalanie. Idea polega na tym, ze plik wejsciowy dzielony jest na 'n' plikow, w ktorych zapisane sa kolejne sekwencje. Nastepnie pliki te scalane sa do 'm' plikow. W wyniku kolejnych scalen i podzialow laczy sie i sortuje kolejne sekwencje az do momentu uzyskania tylko jednej sekwencji o rozmiarze rownym rozmiarowi pliku wejsciowego. Takw bardzo duzym skrocie wyglada ten algorytm, w literaturze anglojezycznej nazywany external sorting.
To się nazywa sortowanie przez zliczanie. :-) Polecam lekturę podstawowych algorytmów. :-)