О маразме некоторых преподавателей информатики

СПбГУ. Специальность "Прикладная математика и информатика", 1 курс. Лекции читает некто К. Для пущей определённости могу заметить, что его фамилия и слово "кретин" различаются лишь 2-й и 3-й буквами.

Итак, дело дошло до зачёта. Мне там выпал билетик про каноническую форму перестановок. Программу этот <censored> принял, но его придирки были фееричненькие. Там критиковать их было, наверное, бессмысленно (всё равно такие не лечатся, да и вообще — на зачёте себе дороже), так что раскритикую здесь. В пух и прах.

Итак, как выглядела моя программа? (Перепечатал точь-в-точь, как было на бумажке.)

const N = 100;

type permutation = array[1..N] of 1..N;
     permutationCF = array[1..N] of 1..N; 

procedure to_canonical_form(var p, r: permutation);
var right_bound: 1..N;
    cycle_length: 1..N;
    i,j,link: 1..N;
    visited: array[1..N] of boolean;
begin
    for i := 1 to N do visited[i] := false;
    right_bound := N;
    for i := 1 to N do
        if not visited[i] then
        begin
            visited[i] := true;
            cycle_length := 1;
            link := p[i];
            r[cycle_length] := i;
            while link <> i do
            begin
                inc(cycle_length);
                r[cycle_length] := link;
                visited[link] := true;
                link := p[link];
            end;
            if cycle_length < right_bound then
            begin
                for j := cycle_length downto 1 do
                    r[j + right_bound - cycle_length] := r[j];
                dec(right_bound, cycle_length);
            end;
        end;
end;

Так вот, о придирках.

Первая: "Ну зачем у вас названия переменных такие длинные? Мне же читать неудобно!". Ага, а мне его код читать удобно: месиво из i,j,k,a,f,g,h и ещё чёрт-те чего. Из-за того и лекции его принципиально не посещаю.
А вот на реальный недостаток кода препод внимания почему-то не обратил: мне вот повторение строк внутри и вне цикла глаза режет. Код так и просится быть переписанным через repeat .. until.

Вторая: "А зачем элементам visited присваивать false? Можно же true присвоить, тогда not при проверке не понадобится, и на одну операцию меньше будет!"
Ухахах, оптимизатор недоделанный :-)))))) Даже моих обрывочных знаний ассемблера хватает, чтобы осознавать, что разница получится не больше, чем оная между JE и JNE. (Если же это вдруг не так — IMHO, компилятору место на помойке.) Между прочим, это предположение можно легко проверить, компилируя код FreePascal Compiler-ом с флагом -al.

И, наконец, третья: "Ой, так это получается, вы элементы сперва в начало массива записываете, а потом их ещё раз перемещаете? Можно было без этого обойтись, используя рекурсию."
А смысл-то в этом какой? Уменьшится не только размер кода, но и его понятность. А выигрыша в скорости рекурсия не даст: итерационный вариант здесь работает быстрее, т.к. позволяет компилятору распихать большинство переменных по регистрам процессора. Опять же, можно посмотреть сгенерированный компилятором ассемблерный код.

Чтобы сравнить скорость (не люблю быть голословным), я наколбасил на Ruby генератор перестановок:

File.open('test.dat', 'w+') { |f|
    nums = (1..100).to_a
    500000.times do
       f.puts (nums.shuffle.map &:to_s) . join " "
    end
}

Ещё был вариант с 1000 элементов и 50000 тестов. В обоих случаях разница в скорости составила около 4%. Не в пользу рекурсивного варианта. (Компилировал обе программы с флагом -O3)

Ах да, эталонный Божественный Код Его Величества: (TPE и TPK — его названия типов, которые у меня названы permutation и permutationCF)

procedure CANON(var f: TPE; var g: TPK);
var i,j: 0..N;
    a: array[1..N] of boolean;
  procedure B(k: integer);
  begin a[k] := false;
        if k <> i then
        begin
            B(f[k]);
            g[j] := k; j := j-1;
        end
  end;
begin
    for i := 1 to N do a[i] := true;
    j := N;
    for i := 1 to N do
    if a[i] then
        begin
            B(f[i]);
            g[j] := i; j := j-1
        end
end;