|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Aleh Veraskouski 2:450/42.68 07 Sep 2002 15:47:54
To : Slavik Levchenko
Subject : соpтиpовка стpок в файле
--------------------------------------------------------------------------------
*** В сообщении от <31 авг 2002>, Slavik Levchenko обращается к All:
SL> дyмается создавать хэш-таблицy и соpтиpовать значения таблицы. потом
SL> только пеpеписать стpоки в опpеделенном поpядке. только вот не знаю как
SL> этy таблицy стpоить. по какомy пpинципy стpоятся хэш-таблицы для массивов
SL> символов?
Идея: незачем в хеше юзать всю строку. Можно только несколько первых
символов (если конечно текст достаточно разнообразный), а если с одинаковым
хешем соберется много строчек, то их потом не проблема еще раз отсортировать
(на этом можно потерять скорость). Зато при хорошем тексте получаем сортировку
за 3*N (2*N - чтение N - запись) обращений к диску и за O(n^2) операций в
памяти (худший случай построения бинарного дерева). Где N - размер файла. n -
размер хеш-значения (к примеру, 4 байта). Будет летать.
Замечу, что файл в память полностью считывать не придется никогда.
WBW
Aleh Veraskouski
... PGP key fingerprint = 7AC2 FF30 9AA9 7155 81C5 54FC 0F88 49A6 3B6E 3998
--- GoldED+/W32 1.1.4.5
* Origin: -=- Origami -=- (2:450/42.68)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
