ru.algorithms

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

 Tue Apr 08 2003 21:33, Val Krigan wrote to Ilya Teterin:
 
  VK> Ага, ну значит это не опечатка, т.е. масштабирование и сдвиг ты назваешь
  VK> хеш-функцией. Можно кого угодно с толку сбить :) Хорошо, это будет
 
 Виноват, лень было другое слово придумывать.
 
  VK> работать только если данные равномерно распределены в заранее известном
  VK> диапазоне.
 
 И опять ты читал невнимательно. Распределение должно быть не _равномерным_, а
 заранее известным, чтобы можно было построить подходящую функцию. При заранее
 известном распределении можно построить функцию, которая на выходе даст
 равномерное распределение. И во многих случаях такая функция может достаточно
 легко вычисляться, чтобы ее использовать на практике.
 
  VK> Иначе надо подбирать другую ф-цию. Пробными сортировками? :)) Обычно
 
 Hазови пару прикладных задач, в которых о распределении входных данных ничего
 неизвестно заранее.
 
  VK> данные группируются вокруг некоторых значений, в твоем случае у них
  VK> хороший шанс попасть в одну ячейку. Как решение можно уваличить
  VK> "hash_space", но..
 
 Да, в специально придуманных мерзких случаях это будет не быстрее qsort ;)
 
  VK> В качестве упражнения можешь рассмотреть сортировку массива.
  VK>     arr[i+1]= arr[i]/1000000
 
 А про функцию взятия лоха ты забыл? :)
 
 hash_func(arg)=loh(1/arg);
 
  VK> HО(!) не все потеряно, твой способ можно усовершенствовать посторными
 
 Если с этого раза объяснение поймешь, то действительно, не все потеряно. Иначе
 - не знаю...
 
 --- ifmail v.2.15dev4
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

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