информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 ФБР нашла русский след в атаках... 
 Массовый взлом SharePoint 
 Microsoft Authenticator прекращает... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Сортировка 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
Написано что установка может повлиять на скорость обращения к файлу так ли это?
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2025 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach