соpтиpовка стpок в файле

From

Aleh Veraskouski (2:450/42.68)

To

Slavik Levchenko

Date

2002-09-07T15:47:54Z

Area

RU.ALGORITHMS

            Доброго тебе здравия , дорогой /Slavik/ !

*** В сообщении от <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)