Тестирование программ. Стресс тесты. Нужна помощь

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Здравствуйте! Появилась следующая проблема. Решаю задачу с e-olimp, и мое решение проходит только первый тест. Подобрать вручную тест, который не пройдет мне не удалось. Тогда я вспомнил про стресс тесты (моя первая попытка), написал лобовое решение, генератор и батник. запустил все это дело и за 2 часа так и не удалось найти тест, на котором программы работают по-разному. Подскажите, пожалуйста, как лучше писать стресс тесты? или может я что-то не так понимаю?

вот ссылки:
задача
лобовое решение
решение с ошибкой
генератор
сам батник:

@ echo off
:1
echo good
gener.exe
brut.exe
2.exe
fc /L output.txt output_brut.txt 
if %errorlevel% == 0 goto 1
echo NeSovpalo
pause

спасибо за помощь

UPD новое лобовое решение + в генераторе изменил количество тесто на 10 000. запустил, жду...

int chek(LL n) { if (n==1) return 0; for (int i=0; (i<cnt&&primes[i]<=n); i++) { if (!(n%primes[i])) { if (n==primes[i]) return 0; while (n%primes[i]==0) n/=primes[i]; if (n!=1) return 0; else return 1; } } return 0; }

long long rdtsc() { long long x; asm("rdtsc" : "=A"(x)); // Выполнить ассемблерную команду rdtsc и сложить результат из регистров EDX:EAX в переменную x return x; } // ... srand(rdtsc());

Комментарии (10)

Написать комментарий?

Nikitosh

11 лет назад, # |

← Rev. 2 →

+19

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

В данной задаче проще было бы просто втупую посчитать количество различных простых делителей для каждого числа из отрезка.

Кроме того, полезно сдавать тупое решение в тестирующую систему и проверять, не получает ли оно Wrong Answer, и только после этого стрессить.

→ Ответить

WasylF

11 лет назад, # ^ |

спасибо, но я что-то не понял, где у меня ошибка. задачу я отсылал http://www.e-olimp.com/solutions/1396123, получил 1 ок, 5 таймлимитов. и проверку вроде делаю, как Вы пишите, для каждого числф из отрезка low high запускаю проверку:

который возвращает 1, если 1 простой делитель, иначе 0.

Буду очень благодарен, если скажите, где именно ошибка)

ztk

+27

На e-olimp'е правильное решение иногда может не заходить

yeputons

Ваш генератор выводит один и тот же тест в течение секунды из-за инициализации от time(). То есть за два часа вы протестировали всего на 7200 случайных тестах. То же самое можно было бы сделать за пару секунд. Правильный метод — инициализироваться либо от /dev/urandom на Linux, либо от более точных источников времени (clock() в их число не входит — он обычно меряет процессорное время текущего процесса, то есть примерно ноль в самом начале). Под виндой можно пробовать GetTickCount() из #include <windows.h>, либо rdtsc:

Проверьте, какие значения выдаёт функция rand(). Вполне может оказаться, что она выдаёт значения от 0 до 65535 (константа называется MAXRAND или как-то так). Правильный вариант:

int randrange(int n) {
  int v = (rand() << 16) ^ rand();
  return abs(v % n);
}

Слишком мало запросов за раз. Всего десять — это же так мало, запуск процесса — это очень и очень дорого. Гораздо лучше, когда решение работает, скажем, секунду, тогда накладные расходы меньше и получается больше тестов в единицу времени.
Попробуйте вместо случайных сгенерировать вообще все маленькие тесты (скажем, до сотни).
Зашлите в систему "тупое" решение и убедитесь, что оно получает TL на каком-нибудь нетривиальном тесте. Если получило WA — всё очень плохо, если получилось TL1 — немного лучше.
Как уже указали, "тупое" решение вообще не должно содержать ни строчки кода из "умного". С нуля и максимально "в лоб", вообще без алгоритмов и оптимизаций, можно и за бесконечную асимптотику.

спасибо, сейчас перепишу. а все пары меньшие 1000 я уже тоже перебрал, но безрезультатно..

Тогда, скорее всего, проблемы с большими тестами. Может быть из-за:

Продолбали где-нибудь long long (скажем, в умножении) или написали вместо него int
Проблемы со считыванием/выводом при использовании C-style: %lld vs %I64d vs C++11 vs Windows XP
Проблем с точностью. Вы используете вещественные числа, а они могут случайно округлиться не в ту сторону (если, скажем, результат или исходный аргумент функции нельзя точно представить). Попробуйте от них избавиться и в "тупом" (в целочисленных задачах идеально, если в тупом решении вообще вещественной арифметики нет), и в "умном" решениях.

andreyv

Сейчас в GCC даже не нужно пользоваться ассемблером:

#include <x86intrin.h>

unsigned long long t = __rdtsc();

CountZero

я думаю, правильнее всего использовать C++11 для генерации случайных чисел:

#include <chrono>
#include <random>
...
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
for (int i = 0; i < 10; ++i) cout << rng() << '\n';

Programist

← Rev. 5 →

У меня немного другое решение: понятно что почти простые числа имеют вид p^k. Например, почти простыми будут 4, 8, 16, 32, 9, 81, … . Сгенерируем все простые число до 10⁶, а потом сгенерируем и отсортируем все почти простые числа (их будет 80070). Ответ ищем бинарним поиском или даже влоб. У меня такое решение прошло за 62мс.

спасибо, за решение. похоже, оно проще моего)) но в данном случае меня больше интересовало, как находить ошибки самостоятельно))

Блог пользователя WasylF