Security Teams



:::
Страницы: (2) [1] 2  ( Перейти к первому непрочитанному сообщению ) Ответ в темуСоздание новой темыСоздание опроса

> Сортировка очень большего файла
J-MiB
Дата 28.10.2006 - 15:43
Цитировать сообщение
Offline



Junior
*

Профиль
Группа: -users-
Сообщений: 36
Пользователь №: 4443
Регистрация: 7.09.2006



Рейтинг:
(0%) -----


Задача: дан файл очень большего объема. Сотня гигабайт например. Нужно отсортировать строки в нем по алфавиту.
Я вижу примерно такое решение: задать размер временного буфера, считать в него строки из файла сколько влезет, затем создать массив записей (указатель_на_строку)sad.gifразмер_строки/2), отсортировать этот массив по размеру строк, а затем строки определенного размера отсортировать между собой, притом сначал сортировать по самым последним двум байтам, потом по предполседним двум и тк до самого начала.
Само сабой, что будет использоваться метод быстрой сортировки.
Почему сортировка будет производиться по паре байт? Потому что во временном буфере символы \r и \n будут заменяться на \0, который либо будет включатся в строку, если она нечетной длины, либо не будет иначе - таким образом каждую строку можнео представить в виде массива байт, которых, надо отметить, четное количество.
Затем отсортированный буфер будет сброшен во временный файл. Когда исходный файл будет прочтен до конца останется только слить между собой временные файлы.
Вот относительно слияния и будет мой вопрос - в каком формате лучше всего хранить отсортированные строки на диске и как определить количество файлов, которое будем одновременно сливать? И еще вот что - если у кого есть идеи, как оптимизировать саму сортировку - буду рад, если поделитесь.


--------------------
Ты - мимолетное воспоминание, которое сразу забудется.
Ты не существуешь. Ты вобще не появлялся на свет.
Безымянность - твое имя. Молчание - твой родной язык.
Ты больше не чаcть общества. Ты выпадаешь из системы. Ты над ней, вне ее.
Узы порваны. Мы для всех "они". Мы - люди в черном.
PMПисьмо на e-mail пользователю
Top
rmf
Дата 12.03.2007 - 21:06
Цитировать сообщение
Offline



Junior
*

Профиль
Группа: -users-
Сообщений: 14
Пользователь №: 5013
Регистрация: 9.03.2007



Рейтинг:
(0%) -----


А зачем создавать кучу файлов? Отркываешь свой временный файл с параметром на дозапись(>>), и в конец файла пишешь свои данные.
PMПисьмо на e-mail пользователю
Top
mulder
Дата 13.03.2007 - 08:51
Цитировать сообщение
Offline



.:in root we trust:.
*****

Профиль
Группа: -vip-
Сообщений: 1181
Пользователь №: 1151
Регистрация: 9.08.2005



Рейтинг:
(70%) XXXX-


rmf
Еще лутшее создаещ пространство в памяти и в него пишеш данные !
И всю сортировку делаеш в памяти а не на диске
PM
Top
rmf
Дата 13.03.2007 - 11:19
Цитировать сообщение
Offline



Junior
*

Профиль
Группа: -users-
Сообщений: 14
Пользователь №: 5013
Регистрация: 9.03.2007



Рейтинг:
(0%) -----


сотню гигабайт в памяти? ну-ну...
PMПисьмо на e-mail пользователю
Top
Kom@nd'Or
Дата 13.03.2007 - 13:19
Цитировать сообщение
Offline



Expert
******

Профиль
Группа: -editors-
Сообщений: 2078
Пользователь №: 48
Регистрация: 2.03.2005



Рейтинг:
(90%) XXXXX


rmf
вро-де писали-же, что сортировать файл планируют по частям ...

ЗЫЖ а если "сначала проиндексировать файл, и уже потом сортировать согласно сортировки индексов"?

Это сообщение отредактировал Kom@nd'Or - 13.03.2007 - 13:21


--------------------
--
Hайден неизвестный драйвер, воткните какое-нибудь устройство!
---
[b]Во имя процесса-отца, процесса-сына и святаго root"а... Enter! [/b]
PMICQYahoo
Top
drmist
Дата 14.03.2007 - 12:03
Цитировать сообщение
Offline



Professional
*****

Профиль
Группа: -users-
Сообщений: 1165
Пользователь №: 222
Регистрация: 14.04.2005



Рейтинг:
(0%) -----


Зачем изобретать велосипед? Есть же утилита sort (по крайней мере во FreeBSD smile.gif
Но если очень хочется - используйте сортировку слиянием, для сортировке в памяти - Quick Sort.
Сравнивать строки придется, видимо, банальным strcmp, если во время сортировки планируется удалить одинаковые строки - используйте контрольные суммы, лучше самописную на сдвигах и сложении (не забудте протестировать на каком-нибудь словаре, коллизий на сортируемом множестве быть не долджно, или если есть, то минимум), чем crc32, ибо последний довольно не быстрый.


--------------------
Когда нельзя еще больше хочется...
PMСайт пользователя
Top
VZoL
Дата 3.04.2007 - 17:22
Цитировать сообщение
Offline



Идущий
**

Профиль
Группа: -editors-
Сообщений: 79
Пользователь №: 2551
Регистрация: 6.01.2006



Рейтинг:
(50%) XXX--


А что мешает разбить большой файл на нужное количество частей, отсортировать в памяти каждую часть отдельно, и потом опять записать в один большой файл с учетом алфавита. Вот такой алгоритм.


--------------------
#include <beer.h>
PMICQ
Top
19841204
Дата 3.09.2007 - 10:46
Цитировать сообщение




Unregistered












немучайся почетай про MapViewOfFile он может загрузить в память вайл в несколько терабайт это все сделано на уровне ОС
Top
drmist
Дата 3.09.2007 - 16:36
Цитировать сообщение
Offline



Professional
*****

Профиль
Группа: -users-
Сообщений: 1165
Пользователь №: 222
Регистрация: 14.04.2005



Рейтинг:
(0%) -----


19841204
Да, но работает только в винде и не слабо грузит систему.
Кстати, а если я маплю файл в память, разве я могу обработать файл размером несколько терабайт, если размер регистра всего 32 бита?


--------------------
Когда нельзя еще больше хочется...
PMСайт пользователя
Top
19841204
Дата 3.09.2007 - 20:20
Цитировать сообщение




Unregistered












Да, если подгружать по частям

Это сообщение отредактировал drmist - 4.09.2007 - 09:35
Top

Опции темы Страницы: (2) [1] 2  Ответ в темуСоздание новой темыСоздание опроса