ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Val Krigan                           2:5020/400     08 Apr 2003  21:33:26
 To : Ilya Teterin
 Subject : Re: Сортировка
 -------------------------------------------------------------------------------- 
 

 "Ilya Teterin" wrote
 
 >  VK> Если да, то пжалста примерчик для целочисленной ф-ции от real
 
 переменно.
 
 >
 > И она была в исходике... Ты его вообще читал, или только обнаружил
 
 непохожесть
 
 > на свою идею, и сразу закричал "ужас"? :)
 >
 > int hash_func(double arg){
 >         return int((arg-min)/(max-min)*hash_space);
 > }
 >
 > Это - для равномерного распределения, min и max - минимальное и
 
 максимальное
 
 > значение входных данных соответственно. Для другого распределения
 
 оптимальный
 
 > вид функции будет другим. Обо всем этом я уже говорил...
 
 Ага, ну значит это не опечатка, т.е. масштабирование и сдвиг ты назваешь
 хеш-функцией. Можно кого угодно с толку сбить :) Хорошо, это будет работать
 только если данные равномерно распределены в заранее известном диапазоне.
 Иначе надо подбирать другую ф-цию. Пробными сортировками? :)) Обычно данные
 группируются вокруг некоторых значений, в твоем случае у них хороший шанс
 попасть в одну ячейку. Как решение можно уваличить "hash_space", но..
 во-первых ограничения по памяти, во-вторых при распечатка придется пробегать
 по бОльшему числу пустых ячеек, в-третих при инициализации их тоже придется
 обходить все и обнулять... И в-четверты, не факт что после этого значения
 попадут в разные ячейки. Еще есть вариант с автоматическим построением
 "hash_func", для этого придется делать предварительный анализ данных, его
 сложность может оказаться выше предложеных мною способов :))
 
 В качестве упражнения можешь рассмотреть сортировку массива.
     arr[i+1]= arr[i]/1000000
 
 HО(!) не все потеряно, твой способ можно усовершенствовать посторными
 сортировками в ячейках с большим числом данных, твоим же способом. Hачиная с
 какого-то момента он _иногда_ будет неплохо работать. Иногда, потому что не
 в приведенном выше примере.
 --- ifmail v.2.15dev4
  * Origin: Demos online service (2:5020/400)
 
 

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