goto - с любимыми не расставайтесь, или break не тащит
Модератор: Модераторы
Seenkao писал(а):Мне надо прыгнуть с кода на код, для проверки работоспособности программы.
За плечами и Фортран, и ПЛ-1, и бейсик с ихними goto
Но вот что б так!!!
alexs писал(а):Модераторы - уберите тему во флуд.
+1
Говнокодить можно с лёгкостью на любом языке, хоть с GOTO, хоть без оного.
Имхо бывают вещи и похуже, например вот это.
Что по мнению знатоков не так с этой сортировкой и можно ли это исправить? Варианты ответа:
- Нельзя.
- Заменить Inc на +1.
- Отключить оптимизацию.
- Добавить парочку GOTO.
- Сделать скриншот.
- Что-то иное(что именно?).
Последний раз редактировалось iskander 30.10.2020 12:08:28, всего редактировалось 1 раз.
я бы до такого не додумался...iskander писал(а):Имхо бывают вещи и похуже, например вот это.
Что по мнению знатоков не так с этой сортировкой и можно ли это исправить? Варианты ответа:
Я не знаток, но по моему и проще и нагляднее пройтись пузырьковой сортировкой. А такой код, я бы вообще не предлагал ни кому.
Добавлено спустя 3 минуты 6 секунд:
ну да, ну да... может голову включим? Или вы каждый раз при проверке пользуетесь другим языком, а потом этот код ещё и на паскаль переделываете? (конечный результат программы должен быть от тестового кода). Или вы не тестируете свой код?sign писал(а):За плечами и Фортран, и ПЛ-1, и бейсик с ихними goto
Seenkao писал(а):я бы до такого не додумался.
Кто бы сомневался. Но она действительно в некоторых случаях не намного быстрее пузырька.
iskander, не уверен вообще, что быстрее. А если пузырёк немного оптимизировать, то уж точно не быстрее.
... хотя ... опять от умельца зависит. )))
... хотя ... опять от умельца зависит. )))
Seenkao писал(а):iskander, не уверен вообще, что быстрее. А если пузырёк немного оптимизировать, то уж точно не быстрее.
... хотя ... опять от умельца зависит. )))
Не уверен - не обгоняй.
Код: Выделить всё
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. какой ерундой я страдаю...
Seenkao писал(а):P.S. какой ерундой я страдаю...
¯\_(ツ)_/¯
iskander писал(а):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, и так и не смог обогнать его вручную созданными потоками по числу ядер процессора.
У вас нет необходимых прав для просмотра вложений в этом сообщении.
runewalsh писал(а):Почему?
Скажем так, мне бы не хотелось, чтобы кто-нибудь выложил решение раньше, чем выскажутся все заинтересованные знатоки. Один вон уже выложил кривую реализацию BubbleSort.
Имхо реализация AnySort содержит реальную ошибку.
Даже две, этот [Word] обрежет (должен обрезать) массивы больше 65 Кб.
Первую тоже нашёл, она известная в контексте подводных камней реализации QSort, да.
Первую тоже нашёл, она известная в контексте подводных камней реализации QSort, да.
Ну постарайтесь не спешить, если можно.
Вместо сортировки выбором чаще применяют сортировку вставкой(у неё сложность O(N) в лучшем случае), а насчет распараллеливания интересно.
Вместо сортировки выбором чаще применяют сортировку вставкой(у неё сложность O(N) в лучшем случае), а насчет распараллеливания интересно.
iskander писал(а):Вместо сортировки выбором чаще применяют сортировку вставкой
Это не сильно принципиально — она выполняется в листовых вызовах, на массивах из [2; THRESHOLD] (THRESHOLD = 12) элементов.
Но сортировка выбором делает гораздо меньше обменов — максимум N−1 обмен — ценой большего количества сравнений, а обмен дороже сравнения. Поэтому она мне больше нравится.
Ну что сказать, выглядит вполне симпатично. А не пробовали сравнить однопоточную версию с другими реализациями?