ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuriy Kaminskiy                      2:5020/517.21  08 May 2001  18:33:21
 To : Dmitry Kolvakh
 Subject : Re: sorry
 -------------------------------------------------------------------------------- 
 

  Hello,  Dmitry! 
 
 >>>>> On 08:37 07/5/2001, Dmitry Kolvakh <2:5018/1.18> writes:
  MB> Стоп! Укажи мне наихудший случай. AFAIK QuickSort (который
  MB> рекурсивный) одинаково сортирует любые данные.
  DK> АФАИР наихудшим случаем был тот, когда массив уже почти
  DK> отсоpтиpован.
 
  ... только при абсолютно тупом выборе в качестве разделителя
 key[left].
  Если немножко подумать, и использовать в качестве разделителя
 key[(left+right)/2], то уже отсортированный массив (как в прямом, так и
 в обратном порядке) становится _наилучшим_ случаем.
  А если подумать еще немного, и использовать в качестве разделителя
 медиану из key[left, middle, right], то найти наихудший случай
 становится весьма затруднительно :)
 
  DK> А также (из моего опыта) весьма плохо, когда количество элементов
  DK> на несколько поpядков больше количества их значений.
 
  Да? Боюсь, это кривизна твоей реализации qsort :)
  Hаколеночный эксперимент (при помощи perl-5.6.0 -MBenchmark; весьма
 продвинутая реализация qsort) на массиве из 50000 случайных элементов
 показывает, что -
  rand(3)  => 2.03 calls/s
  rand(30)  => 1.57 calls/s
  rand(300) => 1.31 calls/s
  rand(30000)  => 1.06 calls/s
  Т.е. зависимость прямо противоположная - когда в массиве различных
 элементов на четыре порядка меньше, чем число элементов, qsort работает
 в два раза быстрее, чем в случае, когда почти все элементы в массиве
 различные :))))
  Для сравнения, несколько более упрощенная реализация qsort из
 glibc-2.0 (perl-5.004) вообще практически никак не зависела от 
 (числа различных элементов в массиве)/(размер массива):
  rand(3)  => 0.47 calls/s
  все-остальные => 0.40 calls/s
 -- 
 Yuriy Kaminskiy.
 PS Разница в скорости объясняется особенностями взаимодействия
 perl5.004 с libc'шным qsort [в 5.6.0 внутренняя реализация qsort со
 значительно меньшими накладными расходами на операции сравнения].
 PPS И та, и другая реализации qsort используют в качестве разделителя
 медиану из key[left,middle,right] и fallback на сортировку вставками на
 коротких отрезках.
 P^3S :) Исходники - см. www.perl.com и www.gnu.org.
 --- Gnus v5.2.25/XEmacs 19.14
  * Origin: none (2:5020/517.21@fidonet)
 
 

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

Тема:    Автор:    Дата:    Re: sorry   Yuriy Kaminskiy   08 May 2001 18:33:21   sorry   Dmitry Kolvakh   11 May 2001 14:05:08