LINUX.ORG.RU

Тестирующие системы для структур данных и алгоритмов

 , , , ,


0

4

Может кто-нибудь подсказать, есть ли в открытом доступе тестирующие системы к структурам данных и алгоритмам или хотя бы просто тестовые данные?

Язык - с++

Хотелось бы подтянуть структуры разные, например: хеш таблицы, кольцевой буфер, бинарные деревья поиска, алгоритмы: сортировки, обход деревьев и т.д.

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

Сколько не ищу, ничего найти не могу. Есть сайты, в которых предлагается дописать код к уже готовому классу, мол, допишите методы , а потом запустите run и проверьте, но хотелось бы, конечно, просто загружать реализацию куда-нибудь или запускать все на локалке.

Буду благодарен за какие-нибудь советы и помощь по этому вопросу

Ответ на: комментарий от anonymous

Я еще этот сайт находил freecodecamp.org/learn/

Там в самом низу coding interview prep. Но, опять же, хотелось бы целую систему какую-нибудь и желательно на локалке…

Спасибо за ссылки, про leetcode не знал

wh75per ()

Если знаешь, какая сложность по времени / памяти должна быть, просто наваливаешь данных и строишь графики. Для пропущенных случаев прикрути фаззер какой-то, в общем случае - property-based testing, тебе это будет ещё и полезно для того, чтобы научиться выражать свойства алгоритмов в терминах их апи, а не кишок.

cdshines ★★★★ ()

Из вопросов/ответов есть https://github.com/teivah/algodeck, хоть и не в особо удобной форме (более удобную надо покупать или как-то распарсить).

Задачи из соревнований вместе с тестовыми наборами данных есть только в двух местах (год назад других не находил; вроде, даже с какими-то специфичными лицензиями или вовсе без них, их просто не выкладывают):

Оффлайн-аналогов сайтов по типу codility и т.д. по сути нету (только пару огрызков видел, либо же идут онлайн-системы для проведения соревнований). Я себе кое-как навелосипедил, но задач особо не надобавлял. Если есть желание поковырять, могу прилепить лицензию и дать ссылку, оно на C++ с Qt, но сыровато (в частности ищет sqlite-базы в текущем каталоге).

xaizek ★★★★★ ()

тестирующие системы к структурам данных и алгоритмам или хотя бы просто тестовые данные?

Тестовые данные лучше либо самому генерить (и тогда будешь знать метод генерации и потом поймешь, если где-то накосячил именно с тестовыми данными, и не будешь зависеть от всяких хакерсранков). Либо, если генерация очень трудоемкая (типа всяких датасетов для тренировки распознавателей образов), есть уже собранные научным сообществом и общедоступные датасеты, с которыми разные алгоритмы тестируются.

seiken ★★★★★ ()
Ответ на: комментарий от anonymous

Для меня big data в виде xml, … интересны для тестирования производительности алгоритмов.

Хотя конечно big data в виде xml - очень уныло.
Интересны URL с которых можно скачать большие базы /Firebird, …/.

anonymous ()

Хотелось бы подтянуть структуры разные, например: хеш таблицы, кольцевой буфер, бинарные деревья поиска, алгоритмы: сортировки, обход деревьев и т.д.

Можно просто случайно генерировать большое количество элементов и проверять результат а также замерять время. Для указанных структур данных генерация и проверка случайных данных не составляет проблем. Можно ещё добавить тестовые случаи для пустых данных и одного элемента для проверки граничных случаев.

X512 ()
Ответ на: комментарий от X512

Можно просто случайно генерировать большое количество элементов и проверять результат а также замерять время.

Как сказать.
Нагенерили мусора … и какой критерий того, что алгоритм отработал правильно?

anonymous ()
Ответ на: комментарий от X512

Для сортировки можно отсортировать входные данные заведомо рабочим алгоритмом (например из стандартной библиотеки) и сравнить результат.

Это не ответ.
С таким же успехом можно взять первый том «Война и Мир» … - «и сравнить результат.».

anonymous ()

Можно и самому написать, но есть страх не учесть какой-нибудь случай из-за которого можно пропустить ошибку.

Вы бы посмотрели трекер багов любого популярного проекта …

Владимир

anonymous ()
Ответ на: комментарий от vedowi6419

А зачем ему тестирующие алгоритмы для поднятия «уровня»?

ТС пишет

Хотелось бы подтянуть структуры разные, например: хеш таблицы, кольцевой буфер, бинарные деревья поиска, алгоритмы: сортировки, обход деревьев и т.д.

То бишь бери пять чисел и пробуй их готовой функций отсортировать …
Он то что хочет - понять как использовать это API.
Так что пяти чисел достаточно.

anonymous ()
Ответ на: комментарий от anonymous

Нагенерили мусора … и какой критерий того, что алгоритм отработал правильно?

Никакой, естественно. Тестируется не алгоритм, а его реализация.

seiken ★★★★★ ()

Так нет никаких эталонных api и реализаций. Скорость дело такое себе, в той же самой хеш таблице ты можешь реализовать кеширование наиболее часто запрашиваемых данных или просто кеширование, коллизии разруливать просто листами или деревьями или листами и деревьями, а может ещё чем, а может вообще не разруливать хранение указателей, а хранить индексы на другие хештаблицы в которых уже по типам разложены данные.

Хотя можно брать например алгоритм и его популярную реализацию, потом писать своё и просто сравнивать результаты.

Но если где то есть прям то что ты описал… Подпишусь, тоже интересно. Но я очень сомневаюсь что такое существует что-бы прям всё из коробки

LINUX-ORG-RU ★★ ()
Ответ на: комментарий от cdshines

просто наваливаешь данных

Вот тут тоже интересно. Нужно подготовить хорошие данные понятное дело первое это рандом, затем данные в повторяющимися последовательностями через равный/рандомный промежуток, затем рандомные данные с повторяющимися последовательностями через рандомный/постоянный промежуток данных или статичный поток данных с рандомными блоками через рандомные/статичные промежутки и так далее и так далее. Разнообразные алгоритмы учитывающие всё это или нет могут быть интересны в одних случаях и бесполезны в других. Тут тоже надо подойти с умом и растаропностью. Чаще всего проверяют на откровенном рандоме для некого общего случая выдавая среднюю температуру по больнице их которой нихрена не понятно

LINUX-ORG-RU ★★ ()
Ответ на: комментарий от xaizek

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

Благодарю за ссылки, буду смотреть)

Странно, конечно, что нет никаких общих тестов для структур хотя бы. Я понимаю, что реализации могут различаться как и интерфейсы, но все же… Они много где используются, неужели нет какого-нибудь стандарта. В общем отсутсвтие каких-то наборов данных для тестов структур меня удивляет.

wh75per ()
Последнее исправление: wh75per (всего исправлений: 1)