ru.algorithms

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

 Hi!
 
 > У него на "хеш-функцию" сильное ограничение, для возрастающей
 > последовательности на входе она выдает возрастающую последовательность на
 > выходе. Шансов что "повезет" почти не остается. Для примера попробу
 > построить такую ф-цию для последовательности
 > X[1] = 0
 > X[i+1]= (X[i]-A)/1000 + A
 > Где А заранее не известно.
 > Построй, тебе почти известна последовательность, после этого можешь
 > продолжать чтение :)
 
 А ты попробуй ту же последовательность своим хэшем попробовать. :) Там даже
 double разрядности хватит только элементов на пять, 1000 ~= 2^10,
 разрядность мантиссы 2^52 кажется. А дальше пойдут одинаковые значения,
 естественно с одинаковыми хэшами. А для очень многих последовательностей
 вполне подойдет "порядок concat часть мантиссы" в качестве упорядоченного
 хэша, то есть старшие биты бинарного представления для интела. Естественно
 это не для всех случаев. Дак и qsort не для всех случаев, он в некоторых
 случаях O(N*N/2) может дать вместо O(N*logN). И "случайный" хэш может как
 угодно сыграть.
 Bye.
 --- ifmail v.2.15dev4
  * Origin: Demos online service (2:5020/400)
 
 

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