Постановка задачи:
Учитывая заранее известный набор целых чисел, генерирует код , чтобы проверить, есть ли в наборе одно целое число. Доменом функции тестирования являются целые числа в некотором последовательном диапазоне.
В настоящее время ничего конкретно не известно о диапазоне или наборе, подлежащем тестированию. Диапазон может быть небольшим или огромным (но решение может отклонить проблемы, которые слишком велики, но более высокие пределы лучше). Может случиться так, что очень мало значений в допустимом диапазоне находятся в наборе или большинство из них или что-то среднее. Набор может быть равномерно распределен или сгруппирован. Могут быть большие разделы только содержащих / не содержащихся значений, или может быть по меньшей мере несколько значений каждого типа в большинстве рядов. (вроде как предположение, сделанное для элементов, которые должны быть отсортированы при анализе алгоритмов сортировки)
Целью является процедура генерации эффективного кода для запуска теста.
Частичные решения, которые приходят на ум, включают
- Идеальная хеш-функция (дорого для больших наборов)
- диапазон испытаний:
foreach(b in ranges) if(b.l <= v && v <= b.h) return true;
- деревья / индексы (в некоторых случаях дороже, чем другие)
- поиск таблицы (дорого для больших наборов)
- инверсия любого из этих (кодос Джейсон S )
Кажется, что идеальное решение могло бы выбрать, какой вариант лучше, или, если ни один из них не работает хорошо, использовать дерево, чтобы разбить весь диапазон на разделы, а затем переключиться на другие варианты для подразделов, которые лучше подходят им.
Темы, которые могут быть полезны, включают:
Примечание: это не домашняя работа. если он был выпущен как домашнее задание ниже докторского уровня, проф должен быть застрелен пистолетом Нерфа (если вы этого не получите, перечитайте проблему, это очень нетривиально)
Примечание: это проблема, которая возникла у меня несколько дней подряд, и я ломал голову над этим время от времени. Я не имею прямого использования для этого, но думал, что это будет крутой проблемой для атаки. Причина, по которой я хочу сгенерировать код, заключается в том, что сгенерированный код будет не медленнее, чем обычный код (в случае необходимости он может быть тем же самым), и может быть быстрее в некоторых / многих случаях.
Я публикую этот вопрос столько же, чтобы прояснить свои мысли, как и все остальное. Если я смогу найти какие-либо разумные или интересные решения, я планирую реализовать их как шаблонную метапрограмму (другая причина для сгенерированного кода)
некоторые люди отметили, что проблема очень общая. В этом суть. Я надеюсь создать систему, которая будет работать в очень общей области: наборы целых чисел в некотором диапазоне.