Нужно сортировать большой файл порядка 500Mb-1Gb, файл текстовый причем строки в нем не длинее 50 символов. Т.е строк в нем больше 10 миллионов это точно. Как бы быстро отсортировать его чтобы вемя сортировки превышало время копирования этого файла ну в раза 2-3 не больше. Сейчас делаю так сначала сортирую файл блоками по тыс 10 строк QuicSort`ом, а потом сортирую все блоки слиянием. Еще хотелось бы чтобы программа не зависела от размера файла(ну если только 4Гб) т.е. если размер файла не должен влиять на кол-во требуемой оперативной памяти => не должно быть рекурсии, хешей, индексов.
Что-то я разошелся :), в обсчем я исхожу из того что sort.exe сортирует довольно быстро, один недостаток: больше 50Мб не хочет файл брать.
Сортировка13.10.01 23:09 Автор: NiFi... <NiFiGaSebe!> Статус: Member
> Нужно сортировать большой файл порядка 500Mb-1Gb, файл > текстовый причем строки в нем не длинее 50 символов. Т.е > строк в нем больше 10 миллионов это точно. Как бы быстро > отсортировать его чтобы вемя сортировки превышало время > копирования этого файла ну в раза 2-3 не больше. Сейчас > делаю так сначала сортирую файл блоками по тыс 10 строк > QuicSort`ом, а потом сортирую все блоки слиянием. Еще > хотелось бы чтобы программа не зависела от размера файла(ну > если только 4Гб) т.е. если размер файла не должен влиять на > кол-во требуемой оперативной памяти => не должно быть > рекурсии, хешей, индексов. A pochemu takoe ogranichenie? Bois'sya perepolnenia stecka???
Nu hesh eshe ponyatno, a recursion & index ???
> Что-то я разошелся :), в обсчем я исхожу из того что > sort.exe сортирует довольно быстро, один недостаток: больше > 50Мб не хочет файл брать.
Ne znaju poka na skol'ko effectivno budet, no vse taki sdelaj chto nit' vrode indexov, t.k. kak ne kruti, vse ravno s chislami delo budesh' imet'.
i soberi otsortirovannoe binarnoe derevo
i obxod dereva budet bystrej.
poka nikakix konkretnyx algoritmov ne prixodit v golovu. eto prosto myslya.
A pochemu takoe ogranichenie? Bois'sya perepolnenia stecka???
Ага очень боюсь :), у меня он и происходит при quicksort рекурсивной.
Nu hesh eshe ponyatno, a recursion & index ???
Ну если предположить что кол-во строк >10 млн то размер индексов будет(при 1 индексе = DWORD) 10млн*4~38Mb!!! Это не есть хорошо, то есть на моей тачке с 64Mb где свободно Phys Mem где то мег 25-30 это и протестить-то не удасться.
> Ne znaju poka na skol'ko effectivno budet, no vse taki > sdelaj chto nit' vrode indexov, t.k. kak ne kruti, vse > ravno s chislami delo budesh' imet'. > i soberi otsortirovannoe binarnoe derevo
> i obxod dereva budet bystrej. > > poka nikakix konkretnyx algoritmov ne prixodit v golovu. > eto prosto myslya.
В общем хрен его знает... Как sort.exe так сортирует?! Хоть она и на асме полностью написана но у меня ф-ция сортировки тоже на нем. И не хрена! Как мне думаеться тот вариант который я использую не такой уж плохой... Но че-то хочеться исчо ускорить процесс :0. Пока время сортировки = 2.5*3 время копирования файла, при размере буфера для индексов и всякой фигни ~5Mb. Но вот еще вспомнил для CreateFile есть флаг:
FILE_FLAG_NO_BUFFERING
FILE_FLAG_RANDOM_ACCESS
Написано что установка может повлиять на скорость обращения к файлу так ли это?
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
