Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
 |
Сортировка 13.10.01 23:09 Число просмотров: 913
Автор: NiFi... <NiFiGaSebe!> Статус: Member
|
napishi mne na mafia_zhivet@hotmail.com,
ja tebe programmku prislju, porpobuesh ee.
|
<programming>
|
Сортировка 13.10.01 20:25
Автор: Heromantor Статус: Незарегистрированный пользователь
|
Нужно сортировать большой файл порядка 500Mb-1Gb, файл текстовый причем строки в нем не длинее 50 символов. Т.е строк в нем больше 10 миллионов это точно. Как бы быстро отсортировать его чтобы вемя сортировки превышало время копирования этого файла ну в раза 2-3 не больше. Сейчас делаю так сначала сортирую файл блоками по тыс 10 строк QuicSort`ом, а потом сортирую все блоки слиянием. Еще хотелось бы чтобы программа не зависела от размера файла(ну если только 4Гб) т.е. если размер файла не должен влиять на кол-во требуемой оперативной памяти => не должно быть рекурсии, хешей, индексов.
Что-то я разошелся :), в обсчем я исхожу из того что sort.exe сортирует довольно быстро, один недостаток: больше 50Мб не хочет файл брать.
|
 |
Сортировка 13.10.01 23:09
Автор: NiFi... <NiFiGaSebe!> Статус: Member
|
napishi mne na mafia_zhivet@hotmail.com,
ja tebe programmku prislju, porpobuesh ee.
|
 |
Не mail-ы случайно сортируешь? :) 13.10.01 22:24
Автор: SEH Статус: Незарегистрированный пользователь
|
|
 |  |
И не только их :) 14.10.01 01:33
Автор: Heromantor Статус: Незарегистрированный пользователь
|
|
 |
Сортировка 13.10.01 21:08
Автор: kabanchik Статус: Незарегистрированный пользователь
|
> Нужно сортировать большой файл порядка 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.
|
 |  |
Сортировка 14.10.01 01:48
Автор: Heromantor Статус: Незарегистрированный пользователь
|
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
Написано что установка может повлиять на скорость обращения к файлу так ли это?
|
|
|