goto - с любимыми не расставайтесь, или break не тащит

[alexs]

Модераторы - уберите тему во флуд.

[sign]

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

За плечами и Фортран, и ПЛ-1, и бейсик с ихними goto
Но вот что б так!!!

[iskander]

Модераторы - уберите тему во флуд.

+1
Говнокодить можно с лёгкостью на любом языке, хоть с GOTO, хоть без оного.
Имхо бывают вещи и похуже, например вот это.
Что по мнению знатоков не так с этой сортировкой и можно ли это исправить? Варианты ответа:

• Нельзя.
• Заменить Inc на +1.
• Отключить оптимизацию.
• Добавить парочку GOTO.
• Сделать скриншот.
• Что-то иное(что именно?).

PS. runewalsh прошу не беспокоиться.

[Seenkao]

Имхо бывают вещи и похуже, например вот это.
Что по мнению знатоков не так с этой сортировкой и можно ли это исправить? Варианты ответа:

я бы до такого не додумался...
Я не знаток, но по моему и проще и нагляднее пройтись пузырьковой сортировкой. А такой код, я бы вообще не предлагал ни кому.

Добавлено спустя 3 минуты 6 секунд:

За плечами и Фортран, и ПЛ-1, и бейсик с ихними goto

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

[iskander]

я бы до такого не додумался.

Кто бы сомневался. Но она действительно в некоторых случаях не намного быстрее пузырька.

[Seenkao]

iskander, не уверен вообще, что быстрее. А если пузырёк немного оптимизировать, то уж точно не быстрее.
... хотя ... опять от умельца зависит. )))

[iskander]

iskander, не уверен вообще, что быстрее. А если пузырёк немного оптимизировать, то уж точно не быстрее.
... хотя ... опять от умельца зависит. )))

Не уверен - не обгоняй.

[Seenkao]

Код: Выделить всё

var
  massive: array[0..100] of integer;    // можно не определённый массив
procedure Sort;
var
  i, n: integer;
begin
  i := length(massive);
  dec(i);
  while i > 0 do
  begin
    if massiv[i] > massiv[i + 1] then
    begin
      n := massive[i];
      massive[i] := massive[i + 1];
      massive[i + 1] := n;
    end;
    dec(i);
  end;
end;


самый простой пузырёк.
Оптимизация: сначала считываем N из массива и начинаем прогонять оп массиву, не перебрасывая, пока не попадётся элемент больше. Сдвигаем весь массив ниже и меняем N на значение в массиве, продолжаем ход. Нужна дополнительные переменные для учёта смещения по массиву и указанию "места остановки" (где брали последний элемент).

Дальнейшая оптимизация зависит от того какие величины используются в массиве. Если целые, то можно прогонять по несколько чисел сразу, если они последовательны друг за другом (имеет смысл, если в массиве большое количество элементов).

Одна из оптимизаций - прогон нескольких элементов, но здесь надо подходить аккуратно и хорошенько всё просчитывать, потому что можем спокойно всё запороть.

P.S. какой ерундой я страдаю...

[iskander]

P.S. какой ерундой я страдаю...

¯\_(ツ)_/¯

[runewalsh]

runewalsh прошу не беспокоиться

Почему? :D

Моя велосипедная сортировка выглядит следующим образом. Правда, она не через стирание типа и не через дженерики, а через псевдо-темплейты {$define} + {$include} — мне так больше нравится, можно тонко всё настроить.

Код: Выделить всё

class procedure classname.QSort(p: pElem; count, reasonable: SizeUint
   {$ifdef allow_mt}; parallel: pParallelQSort {$endif} {$ifdef param}; const param: ParamType {$endif});
var
   L, R: SizeUint;
   t, avg: SwapTemp;
begin
   repeat
      if count <= SelectionThreshold then
      begin
         SelectionSort(p, count {$ifdef param}, param {$endif});
         exit;
      end;
      if reasonable = 0 then
      begin
         HeapSort(p, count {$ifdef param}, param {$endif});
         exit;
      end;
      reasonable := reasonable div 2 + reasonable div 4;

      avg := SwapTemp(Median(p, count {$ifdef param}, param {$endif})^);
      R := 0;
      L := count - 1;

      repeat
         while {$define _1 := p[R]} {<} {$define _2 := Elem(avg)} less_ do inc(R);
         while {$define _1 := Elem(avg)} {<} {$define _2 := p[L]} less_ do dec(L);
         if R <= L then
         begin
            t := SwapTemp(p[R]); SwapTemp(p[R]) := SwapTemp(p[L]); SwapTemp(p[L]) := t;
            inc(R);
            dec(L);
         end;
      until R > L;

      // [0 .. L], [R .. count - 1]
      if count - R <= L then
      begin
         if R + 1 < count then
         {$ifdef allow_mt} ParallelQSort.MaybeSpawn {$else} QSort {$endif}
            (p + R, count - R, reasonable {$ifdef allow_mt}, parallel {$endif} {$ifdef param}, param {$endif});
         count := L + 1;
      end else
      begin
         if L > 0 then
         {$ifdef allow_mt} ParallelQSort.MaybeSpawn {$else} QSort {$endif}
            (p, L + 1, reasonable {$ifdef allow_mt}, parallel {$endif} {$ifdef param}, param {$endif});
         p += R;
         count -= R;
      end;
   until false;
end;

Усовершенствования относительно варианта из вики следующие:

— Когда мы получили две половинки по разные стороны от точки разделения и нам нужно рекурсивно их отсортировать, честный рекурсивный вызов идёт по МЕНЬШЕЙ половинке, а большая переиспользует исходный кадр стека. То есть это ручная оптимизация хвостовой рекурсии, ШОБ НАВЕРНЯКА. С другими усовершенствованиями это не особенно нужно, но без них защищает от переполнения стека — глубина рекурсии никогда не превысит log₂count (что имеет теоретический предел bitsizeof(SizeUint) = 32 или 64), а без этого может достичь count — длины сортируемого массива.

— При небольшом количестве элементов (не более SelectionThreshold = 12) выполняется сортировка выбором, т. к. она быстрее на очень маленьких массивах.

— Мы отслеживаем загадочное число reasonable. На 0-м уровне рекурсии reasonable = count, а на каждом следующем оно домножается на 3/4. Если reasonable вдруг достигает 0, вместо продолжения рекурсивной быстрой сортировки мы выполняем (для данного кусочка) пирамидальную. Это защита от худшего случая быстрой сортировки: на плохих данных она может выродиться до O(N²) времени. Пирамидальная сортировка в среднем медленнее быстрой (раза так в 3), но не вырождается плохими данными.

Замечу, что с этим приёмом оптимизация хвостовой рекурсии уже не критична (но всё равно лучше, чем её отсутствие). Я украл его из реализации сортировки в MSVC, см. скриншот (_Ideal — это моё reasonable).


— Т. к. половинки сортируются независимо, сортировку больших массивов (у меня от 16 тысяч элементов) легко распараллелить. У меня параллелится только сортировка половинок, особо одарённые умудряются распараллелить и партишен вокруг среднего элемента, но я так и не разобрался, как это сделать. Оптимизации выше — вопрос жалких десятков процентов, от силы 2 раз, а вот распараллеливание даёт гигантский выигрыш. Но нужен пул потоков; я использовал WinAPI-пул, который TrySubmitThreadpoolCallback, и так и не смог обогнать его вручную созданными потоками по числу ядер процессора.

Untitled-1.png

[iskander]

Почему?

Скажем так, мне бы не хотелось, чтобы кто-нибудь выложил решение раньше, чем выскажутся все заинтересованные знатоки. Один вон уже выложил кривую реализацию BubbleSort.
Имхо реализация AnySort содержит реальную ошибку.

[runewalsh]

Даже две, этот [Word] обрежет (должен обрезать) массивы больше 65 Кб.
Первую тоже нашёл, она известная в контексте подводных камней реализации QSort, да.

[iskander]

Ну постарайтесь не спешить, если можно.
Вместо сортировки выбором чаще применяют сортировку вставкой(у неё сложность O(N) в лучшем случае), а насчет распараллеливания интересно.

[runewalsh]

Вместо сортировки выбором чаще применяют сортировку вставкой

Это не сильно принципиально — она выполняется в листовых вызовах, на массивах из [2; THRESHOLD] (THRESHOLD = 12) элементов.
Но сортировка выбором делает гораздо меньше обменов — максимум N−1 обмен — ценой большего количества сравнений, а обмен дороже сравнения. Поэтому она мне больше нравится.

[iskander]

Ну что сказать, выглядит вполне симпатично. А не пробовали сравнить однопоточную версию с другими реализациями?