stranger777 Jul 19 2017 at 15:04

K-sort: новый алгоритм, превосходящий пирамидальную при n <= 7 000 000

6 min

14K

Algorithms*

Translation

+19

Comments 18

Centimo Jul 19 2017 at 23:27

Почему-то по графику виден перелом (где K-sort расходится с heap; такое ощущение, что после этой точки рост линейный) — в чём причина?

khoramus Jul 20 2017 at 18:11

Линейный рост для сортировки это очень даже хорошо)

daiver19 Jul 20 2017 at 06:33

Код ну совсем тяжко читать: с отступами непонятно что, зато комментарии вроде «затем установите a[j] = a[p]». Псевдокод чисто на английском все бы поняли, я думаю.

А вообще неясно, почему не сравнивали с классической быстрой сортировкой (или она вообще по умолчанию отстой для маленьких н?). Еще неясно, можно ли её рандомизировать для поддержки ожидаемого времен н лог н или вообще обеспечить гарантированный н лог н? Короче, вроде есть какой-то анализ, а по сути нет.

AleksandrK Jul 20 2017 at 18:11

Действительно, странная логика — быстрая сортировка (quick sort), модификацией которой является представленный алгоритм, имеет временную сложность O(n^2) в худшем случае. Пирамидальная (heap) сортировка в худшем случае O(n*log(n)), да еще и стабильна. Сравнение теплого с мягким.

netch80 Jul 21 2017 at 20:02

> Пирамидальная (heap) сортировка в худшем случае O(n*log(n)), да еще и стабильна.

Если «стабильна» это сохранение порядка равных элементов, то этого свойства как раз у пирамидальной никогда не было.

> быстрая сортировка (quick sort), модификацией которой является представленный алгоритм, имеет временную сложность O(n^2) в худшем случае

Только если её неправильно реализовать. Даже случайный выбор разделяющего элемента асимптотически снижает вероятность такого до нуля. С помощью медианы медиан получается гарантированное O(n log n), причём всё равно дешевле в большинстве окружений, чем пирамидальная.
Если авторы не знают этой возможности гарантировать время для быстрой сортировки, то что они вообще знают, простите?

joossy Jul 21 2017 at 14:55

И вовсе не отстой она для маленьких N. Qsort легко модифицируется заменой рекурсивных вызов алгоритмом сортировки вставками когда N становится «маленьким».

daiver19 Jul 21 2017 at 17:31

Ну правильно, для маленьких н как раз хип сорт и используют, а для совсем маленьких вставки. Так что сравнивать логичнее сразу с пирамидальной. Другое дело, что 7000000 — это далеко е маленько н, и думаю что тот же std::sort и раньше побьет.

stranger777 Jul 21 2017 at 20:08

Поправил. Спасибо. С отступами да, непонятно что… потестирую в черновиках, посмотрю, как ведёт себя source (кстати, тега не было, его добавил либо хабр автоматически, либо какие-то неизвестные корректоры статей).
Ваши вопросы спрошу у автора, если ответит — добавлю ответ и отпишу сюда.

valemak Jul 22 2017 at 18:05

Пытался реализовать этот псевдокод, сортировка не работает.

Также вообще непонятно, по какому принципу работает алгоритм. Псевдокод представляет собой набор бессмысленных инструкций, в статье о принципах сортировки тоже ничего не сказано (кроме беглого упоминания, что это якобы «разновидность quicksort»). Гугл также по поводу «k-sort source» абсолютно ничем не порадовал (кроме ссылки на эту хабрастатью).

Если всё-таки попробуете связаться с авторами и они даже что-то ответят — поинтересуйтесь, пожалуйста, есть ли у них работающий код этой сортировки на любом языке программирования?

VaalKIA Jul 20 2017 at 07:44

Эта версия, называемая нами K-sort, упорядочивает элементы быстрее пирамидальной при значительном размера массива (n <= 7 000 000) для входных данных равномерного распределения

Суть статьи: мы быстрее, на заранее подготовленных данных, а теперь и без вспомогательного массива — хвалите нас!

kovserg Jul 20 2017 at 18:11

Обычно проводят множество экспериментов с разными данными и на разных машинах и потом усредняют и получают данные с доверительными интервалами. У вас на графиках погрешностей что-то не видно.

Современные процессоры не так просты как может показаться: Сache, Branch prediction, AMD SenseMI, ...
Так что в вашем частном случаем может и быстрее. А если еще использовать и возможности современных процессоров то можно сделать еще быстрее. Но на теоретическую асимптотику это не повлияет.

С другой стороны сортировка пирамидой имеет очень простой алгоритм и понятную асимптотику

struct PSort {
	virtual void swp(int i,int j)=0;
	virtual void cmp(int i,int j)=0;
	void  psort(int n) { // O(n*ln(n))
		int i,r,c;
		for(i=n/2;i>=0;i--) { pfix(i,n); }
		for(i=n-1;i>=0;i--) { swp(0,i);pfix(0,i); }
	}
	void pfix(int i,int n) {
		int c,r;
		for(r=i;r*2<n;r=c) {
			c=r*2; if (c<n-1 && cmp(c,c+1)<0) c++;
			if (cmp(r,c)>=0) break; swp(r,c);
		}
	}
};

stranger777 Jul 20 2017 at 19:06

У вас на графиках погрешностей что-то не видно.

Residual error — остаточная ошибка, она же погрешность.
http://normative_reference_dictionary.academic.ru/98777/50.1.040-2002%3A_Статистические_методы._Планирование_экспериментов._Термины_и_определения. Я не переводил термин, полагая его понятным интуитивно.

https://www.amazon.com/Computer-Experiment-Oriented-Algorithmic-Complexity/dp/3838377435 — книга о компьютерных экспериментах из литературы к статье.
Конечно, на низком уровне из-за оптимизаций в кэше может быть много сюрпризов, но во-первых тут уклон в математику именно, а не в особенности работы памяти. То есть на сферическом языке в вакууме (или на языке, в котором нет этих эвристических трюков с процессорами) по статистическим данным закономерность продолжит работать.
И — в конце концов — это научная статья, а не прикладная. Прикладное исследование — отдельная работа и этим будут заниматься уже не доктора, а скорее заинтересованные лица и энтузиасты.

lpn357 Jul 20 2017 at 18:11

Жаль что данный ресурс всё ещё не включён в перечень рецензируемых научных изданий — ВАК.

wataru Jul 21 2017 at 15:59

Оно нигде не включено, потому что оно нерецензируемое.

nickolaym Jul 27 2017 at 13:46

Я конечно извиняюсь, но почему переводчик сумел перевести весь текст статьи, но оставил как есть описание алгоритма на лютом псевдо-коболе?

Почему авторы статьи дали описание на лютом псевдо-коболе — это, как раз, понятно. Это чёртов наукообразный стиль, редакторы журналов от него млеют и тают.

stranger777 Jul 27 2017 at 17:56

Пока комментарий про желательность псевдокода на английском не набрал два плюса, он был на русском. Мнения разделились, как говорится.

nickolaym Jul 27 2017 at 19:09

Понятно :(
Всё-таки, читать код на псевдо-коболе — это одинаковая кровь из глаз, что на русском, что на английском.
Во-первых, он наглухо неотформатирован.
Во-вторых, весёлая смесь из "=", "= =" и "equals to", всяких операций "decrease j by 1" и прочего.

Вот буквальный перевод этой литературы на питон:

def ksort(a, left, right) :
  # Step 1
  key = a[left]
  i = left
  j = right+1
  k = left+1
  p = left+1

  # Step 2
  while j-i < 2 :
    # Step 3
    if key <= a[p] :
      # Step 3.1
      if p != j and j != right+1 :
        a[j] = a[p]
      else if j == right+1 :
        temp = a[p]
        flag = True
      j -= 1
      p = j
    else :
      # Step 3.2
      a[i] = a[p]
      i += 1
      k += 1
      p = k

  # Step 4
  a[i] = key
  if flag :
    a[i+1] = temp

  # Step 5
  if left < i-1 :
    ksort(a, start, i)

  # Step 6
  if left > i+1 :
    ksort(a, i, right)

Если кто возьмётся расставить здесь осмысленные названия переменных, прокомментировать происходящее и выловить ошибки, — человечество только выиграет.

nickolaym Jul 27 2017 at 17:31

Хипсорт вдвое медленнее квиксорта в среднем — потому что сперва за логлинейное время строит пирамиду, а потом за логлинейное время разбирает её. Зато хипсорт в худшем случае логлинейный (в отличие от квадратного квиксорта).
А что же с К-сортом? В начале статьи упоминаются всякие варианты квиксорта, а потом начинаются сравнения с хипсортом.

Если К-сорт в худшем случае квадратный, то и сравнивать его надо было с квиксортом. Разве нет?
Если он в худшем случае логлинейный, то зачем вводные слова про квиксорт?

Show the best of all time