implement testing and benchmarking system about cfpq-on-gpgpu HOT 20 CLOSED

@gsvgit, подскажите, в каком формате хранятся данные? Если правильно понял, то они разбиты на папки по каким-то названиям, а в каждой в Grammars лежат грамматика, а в Matrices лежат графы в формате, как на экзамене.

from cfpq-on-gpgpu.

Все именно так. Надо только проверить, что расширения файлов одинаковые везде. Я только сейчас задумался, что в папке с биологами расширения мог криво приписать.

from cfpq-on-gpgpu.

А что насчёт правильных ответов? Или предпологаем, что алгоритмы работают верно и наше дело только замерить время работы?

from cfpq-on-gpgpu.

Думаю, иметь референсные значения и сравнивать с ними - хорошая мысль. Надо только предусмотреть сценарий, когда их нет. Например, первый раз запускаем и хотим как раз их получить. Но при этом они частично могут быть. Например для маленьких графов получены со стороны

Ну и стук уру здесь надо какую-то. То, что для экзамена сделали, удобно, или надо что-то иное?

from cfpq-on-gpgpu.

В .zip-е, который мы кидали, есть правильные ответы, мы их сперва сверяли по количеству ребер у аксиомы, а затем у всех сошлись с правильными ответами. Для данных с экзамена ответы есть

from cfpq-on-gpgpu.

Для новых данных можно генерировать и проверять другими алгоритмами, что все сходится, предполагая, что большинство не ошибается в нашем случае

from cfpq-on-gpgpu.

Там же был скрипт, который сверяет ответы compare_answers.py и баш-скрипт для всего тестирования, который все запускал, сверял и записывал время и результат в .csv

from cfpq-on-gpgpu.

Ок. Тогда надо аккуратно положить эти данные в репозиторий рядом с графами и уметь поддерживать в актуальном состоянии.

Думаю, что в нашем случае можно считать, что если на графах, для которых есть ответы, все сходится, и для остальных результаты разных алгоритмов совпадают, то они тоже правильные.

Предлагаю в репозитории хранить только результаты для аксиомы. Обычно этого хватает и это самое интересное. Например, как список пар вершин.

from cfpq-on-gpgpu.

Ещё, похоже, данные надо будет держать в архиве. Соответственно, система должна уметь его разжимать. Ну, или git lfs подключать. А то Рустам нагенерировал новых матриц, а там больше 100Мб файлы.

from cfpq-on-gpgpu.

Мне кажется, что lfs чуть лучше, так как архив версонируется никак. А вдруг мы будем референсные значения обновлять и данные добавлять параллельно. Только тогда, верочтно, стоит какое-нибудь расширение для файлов с графами придумать чтобы lfs автоматом отслеживал все файлы с таким расширением.

Что думаете?

from cfpq-on-gpgpu.

Вот что я придумал:
Создаём папку test, в ней ещё 2: validate и measure (можно поди и получше название дать).
В каждой их этих папок храним тесты в таком формате: 1 тест -- 1 папка, её название это что-то вроде id теста, например, biomedical-mesure-primitive. Каждый тест содержит 2 обязательных файла: grammar.txt и graph.txt, а для тестов из validate ещё содержится правильный ответ.

В таком случае под lfs можно просто подвесить папку test, то есть никакие расширения придумывать не надо, а само тестирование происходит так: запускаем умножения на validate, если все ответы совпали, то можно измерять скорость, так как считаем, что алгоритм верен.

from cfpq-on-gpgpu.

Предыдущий способ имеет изъян, что будет

1. много папок;
2. если для каких-то тестов используются общие файлы, то придётся копировать/ставить линки...;

Поэтому есть вот такой вариант, храним данные в одной папке как вздумается (lfs по-прежнему следит за одной папкой, но здесь для удобства ориетирования уже можно расширения добавить). Параллельно с этим поддерживаем какой-то csv файл, где у нас 3-4 колонки с описанием теста: название, относительный путь до графа и грамматики, относительный путь до ответа, если есть.

В таком случае для валидации мы возьмём тесты, на которые есть ответы согласно этой csv, на остальных будем замерять скорость.

from cfpq-on-gpgpu.

Имхо, стоит проверять ответы и на measure.
Чтобы не хранить все ответы для аксиом (может быть тяжело), можно по ответу строить матрицу и проверять ее ключевые числа (кол-во ребер, как раньше) или хэш. Проверить количество ребер совсем ничего не стоит и будет минимальной проверкой хотя бы

from cfpq-on-gpgpu.

Второй вариант, без огромного количества папок мне нравится больше. Впринципе, сейчас уже есть структура, позволяющая как-то навигироватся. У нас вполне может быть так, что есть несколько графов и несколько грамматик и надо запустить каждый с каждым. Так что просто название датасета, а в нем две подпапки с графами и грамматиками. Результаты лучше проверять везде, где они есть. Вероятно, достаточно проверять количество ребер с аксиомой. Это, конечно, слабая проверка, но у нас задача не проверить корректность алгоритма. Полноценные тесты - отдельная задача. Так что можно действительно хранить рядом мапу из грамматики графа нетерминала (на всякий случай, вдруг стартовый не s) и количество единиц в матрице для этого нетерминала. Думаю, что такая мапа должна быть для каждого датасета. В папке с датасетом 2 подпапки и файл с мапой.

from cfpq-on-gpgpu.

Как будет готов lfs -- пинганите, у меня тут ещё данные есть для замеров.

from cfpq-on-gpgpu.

@gsvgit добавил lfs: #18
Мне нравится идея с поддержкой хешей матрицей, выводить хеши для для каждого нетерминала.
Что насчёт csv, будет ли удобно его поддерживать? Для тестирования это точно будет в разы удобнее, в data/info.csv делаем колонки: name, grammar, graph, pairs of hash.

from cfpq-on-gpgpu.

Добавил ещё данных.

Так как добавление новых данных для замеров --- вещь редкая и разовая, то, думаю, csv --- нормальный вариант. Его не надо будет часто изменять.

Хаши -- кол-во ненулевых ячеек? Иначе не очень понятно, как организовать задёшево стабильную хэш-функцию. Ну и опять же, не очень понятно, как вручную проверять корректность референсных результатов. Сейчас у нас просто есть набор результатов из других статей и нашего алгоритма, который отдельно протестирован и мы верим, что эти результаты правильные. И то, они только для аксиомы. Вот добавил я новую пачку данных. Как я должен действовать? Я всё же считаю, что тестирование алгоритма и проверка простых контрольных сумм -- две разные задачи. Но может я всё усложняю)

from cfpq-on-gpgpu.

Для каждой матрицы считаем её хеш: p^j*q^i*a_ij -- расширение полиномиального хеша на матрицу, т.е. считаем полиномиальный хеш каждой строки, а потом полиномиальный хеш строк.
Теперь вместо вывода кучи позиций ненулевых значений будут выводиться хеши каждого нетерминала.
Тогда для проверки правильности достаточно проверить эти хеши, а не сравнивать выводы.
Профит будет на больших тестах, так как получится сказать с достаточной большой вероятностью, что алгоритм отработал правильно. А реализация не отличается, мы запоминаем какие хеши нам выдал алгоритм, который мы считаем правильным, а затем сравниваем с ответом каждой реализацией.

from cfpq-on-gpgpu.

Ок. Давайте так. Но кол-во ненулевых для аксиомы я бы всё равно хранил и выводил. Так как его чачто в статьях приводят. Типа "Всего мы по такому запросу в таком графе нашли столько-то"

from cfpq-on-gpgpu.

#19

from cfpq-on-gpgpu.