Використання регресійних тестів

Останнє оновлення 2026-06-16 | Редагувати цю сторінку

Приблизний час: 50 хвилин

Огляд

Питання

  • Регресійні тести

Цілі

  • Вміти створювати та запускати тестові файли
  • Зрозуміти, як розбіжності у тестах і зміни у швидкості обчислень можна ідентифікувати та інтерпретувати
  • Зрозуміти, як створювати тести для перевірки рандомізованих алгоритмів
  • Засвоїти концепцію “Спочатку зробіть правильно, а потім швидко”

Код AvgOrdOfGroup дуже простий, і з ним нічого не може піти не так. Аналіз тільки одного елемента групи на кожній ітерації замість створення повного списку її елементів дозволяє уникнути нестачі оперативної пам’яті. Наприклад, виклик AsList(SymmetricGroup(11)) може призвести до перевищення дозволеної пам’яті. Однак, обчислення все одно займає деякий час та для розрахунку середнього порядку елемента SymmetricGroup(11) вже буде потрібно декілька хвилин. Але принаймні ми впевнені, що він працює правильно.

Тепер ми хотіли б написати кращу версію цієї функції, використовуючи деякі теоретичні факти, відомі нам із теорії груп. Ми можемо зберігати avgord.g у репозиторії Git, щоб скасувати зміни, якщо буде потрібно. Також, ми можемо створити нову функцію, щоб зберегти стару версію й порівняти результати обох функцій. Більш того, це можна зробити ще ефективніше, якщо ми використаємо регресійне тестування (regression testing): це термін для тестування на основі повторних запусків раніше перевірених тестів, щоб переконатися, що нові зміни не вплинуть на їх коректність або не погіршать їх роботу.

Спочатку нам треба створити тестовий файл. Тестовий файл виглядає точно так само, як сеанс GAP, тому його легко створити, скопіювавши та вставивши текст з сеансу GAP з усіма запрошеннями, вводами та виводами у текстовий файл. Альтернативно, тестовий файл також можна створити з файлу журналу сеансу GAP, записаного за допомогою LogTo. Під час тестування GAP буде виконувати всі команди з тестового файлу, порівнювати результати з тими, що містяться в тестовому файлі, і повідомляти про будь-які відмінності.

Тестові файли GAP — це просто текстові файли, але загальноприйнятою практикою є зберігати їх із розширенням .tst. Тепер створіть файл avgord.tst у поточному каталозі (для уникнення необхідності вводити повний шлях до файлу) з наступним вмістом:

GAP 

# tests for average order of a group element

# permutation group
gap> S:=SymmetricGroup(9);
Sym( [ 1 .. 9 ] )
gap> AvgOrdOfGroup(S);
3291487/362880

Як ви бачите, тестовий файл може включати коментарі, але є певні правила, що визначають, де ці коментарі можна розміщувати, Дійсно, потрібно мати можливість відрізняти коментарі у тестовому файлі від виводу GAP, який починається з #. Тому рядки на початку тестового файлу, які починаються з #, та один порожній рядок, після якого містяться один або декілька рядків, що починаються з #, вважаються коментарями. Усі інші рядки інтерпретуються як вивід, який GAP друкує у відповідь на введену команду.

Щоб запустити тест, слід використовувати функцію Test, як описано в документації. Наприклад (за умови, що функція AvgOrdOfGroup вже завантажена):

GAP 

Test("avgord.tst");

ВИВІД 

true

У цьому випадку Test не знайшов розбіжностей і повернув true, тому ми робимо висновок, що тест пройдено.

Ми не розглядатимемо написання гарного та комплексного набору тестів, а також не будемо розглядати додаткові параметри функції Test, які дозволяють, наприклад, ігнорувати відмінності у форматуванні виводу або відображати хід виконання тесту, оскільки це можна знайти в документації.

Замість цього додамо більше груп до avgord.tst, щоб продемонструвати, що код також працює з іншими типами груп, і показати різні способи використання команд у тестовому файлі:

GAP 

# tests for average order of a group element

# permutation group
gap> S:=SymmetricGroup(9);
Sym( [ 1 .. 9 ] )
gap> AvgOrdOfGroup(S);
3291487/362880

# pc group
gap> D:=DihedralGroup(512);
<pc group of size 512 with 9 generators>
gap> AvgOrdOfGroup(D);
44203/512
gap> G:=TrivialGroup();; # suppress output
gap> AvgOrdOfGroup(G);
1

# fp group
gap> F:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> G:=F/ParseRelators(GeneratorsOfGroup(F),"a^8=b^2=1, b^-1ab=a^-1");
<fp group on the generators [ a, b ]>
gap> IsFinite(G);
true
gap> AvgOrdOfGroup(G);
59/16

# finite matrix group over integers
gap> AvgOrdOfGroup( Group( [[0,-1],[1,0]] ) );
11/4

# matrix group over a finite field
gap> AvgOrdOfGroup(SL(2,5));
221/40

Тепер перевіримо нову версію тесту та переконаємось, що вона працює:

GAP 

Test("avgord.tst");

ВИВІД 

true

Отже, після цього можна починати роботу над більш ефективною версією. Порядок елемента є інваріантом класу спряженості елементів групи, тому нам потрібно лише знати порядки класів спряженості елементів та їх представників. Наступний код, який ми додаємо до avgord.g, читається без жодних синтаксичних помилок:

GAP 

AvgOrdOfGroup := function(G)
local cc, sum, c;
cc:=ConjugacyClasses(G);
sum:=0;
for c in cc do
  sum := sum + Order( Representative(c) ) * Size(cc);
od;
return sum/Size(G);
end;

але коли ми запускаємо тест, ось сюрприз!

GAP 

Read("avgord.g");
Test("avgord.tst");

ВИВІД 

########> Diff in avgord.tst, line 6:
# Input is:
AvgOrdOfGroup(S);
# Expected output:
3291487/362880
# But found:
11/672
########
########> Diff in avgord.tst, line 12:
# Input is:
AvgOrdOfGroup(D);
# Expected output:
44203/512
# But found:
2862481/512
########
########> Diff in avgord.tst, line 23:
# Input is:
AvgOrdOfGroup(G);
# Expected output:
59/16
# But found:
189/16
########
########> Diff in avgord.tst, line 29:
# Input is:
AvgOrdOfGroup(SL(2,5));
# Expected output:
221/40
# But found:
69/20
########
false

Дійсно, ми допустили помилку (навмисно) і замінили Size(c) на Size(cc). Звісно, правильний варіант має виглядати так:

GAP 

AvgOrdOfGroup := function(G)
local cc, sum, c;
cc:=ConjugacyClasses(G);
sum:=0;
for c in cc do
  sum := sum + Order( Representative(c) ) * Size(c);
od;
return sum/Size(G);
end;

Тепер ми виправимо цю помилку в файлі avgord.g, прочитаємо та протестуємо його знову, щоб перевірити, чи тести виконуються правильно.

GAP 

Read("avgord.g");
Test("avgord.tst");

ВИВІД 

true

Таким чином, підхід “Спочатку зробіть правильно, а потім швидко” допоміг виявити помилку відразу після її появи.

Ключові моменти
  • Файл з тестами легко створити, скопіювавши та вставивши текст з сеансу роботи з GAP.
  • Написання корисного та комплексного набору тестів вимагає певних зусиль.
  • Спочатку зробіть правильно, а потім швидко!