ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Val Krigan                           2:5020/400     09 Apr 2003  05:11:10
 To : Dmitriy Goldobin
 Subject : Re: Сортировка
 -------------------------------------------------------------------------------- 
 

 "Dmitriy Goldobin" wrote
 
 > Дак и у Тетерина абсолютно то же самое, если с хэш-функцией "повезет" на
 > данном наборе, то будет O(N), а если не повезет и для всего набора
 > хэш-функция выдаст одно и то же значение, то будет от O(N*logN) до
 
 O(N*N/2).
 
 У него на "хеш-функцию" сильное ограничение, для возрастающей
 последовательности на входе она выдает возрастающую последовательность на
 выходе. Шансов что "повезет" почти не остается. Для примера попробу
 построить такую ф-цию для последовательности
 X[1] = 0
 X[i+1]= (X[i]-A)/1000 + A
 Где А заранее не известно.
 Построй, тебе почти известна последовательность, после этого можешь
 продолжать чтение :)
 
 Теперь представь, что в последовательности 100 элементов, и у тебя массив на
 100 (т.е hash_space из оригинального письма). Сколько элементов попали в
 одну ячейку? Ответ: Если ты не угадал А, то почти все. Если сильно повезет и
 граница ячейки возле А, то элементы лягут в две ячейки. И алгоритм сведется
 в quicksort по одной/двум ячейкам. Даже если дать тебе в сто раз больше
 памяти, hash_space=10000  - вычисление этим алгоритмом не будет быстрее.
 Потому как они все равно в одной ячейке.
 
 > Ведь твой cont[p[i]] на практике что означает?
 
 [] - это оператор возвращающий ссылку на элемент контейнера по ключу. Если
 такого элемента нет - он создается конструктором без параметров. Часто это
 быстрее, чем раздельные search and insert потому, что контейнер их может
 оптимально объеденить.
 
 > Hасчет генератора случайных чисел применительно к хэшу я что-то не уловил.
 
 Идея простая, последовательность значений, генерируемых хеш-функцией должна
 быть похожа на последовательность случайных чисел. Тогда она равномерно
 покроет весь диапазон почти независимо от входящей последовательности.
 Кол-во элементов в ячейках будет примерно равно. Конечно, к любому заранее
 заданному генератору можно подобрать последовательность значений попадающих
 в одну ячейку. Hо это надо делать _умышленно_.
 --- ifmail v.2.15dev4
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор