Содержит тест на постоянный набор
Постановка проблемы:
Учитывая заранее известный набор целых чисел, код генерировать проверяет, есть ли в наборе одно целое число. Область тестовой функции - это целые числа в некотором последовательном диапазоне.
В настоящее время ничего конкретного не известно о диапазоне или наборе для тестирования. Диапазон может быть маленьким или огромным (но решение может отклонить слишком большие проблемы, но более высокие пределы лучше). Может случиться так, что в наборе находится очень мало значений из допустимого диапазона, или большинство из них, или что-то среднее между ними. Набор может быть равномерно распределенным или сгруппированным. Могут быть большие разделы только содержащихся / не содержащихся значений или может быть по крайней мере несколько значений каждого типа в большинстве диапазонов. (что-то вроде предположения об элементах, которые нужно отсортировать при анализе алгоритмов сортировки)
Целью является процедура генерации эффективного кода для запуска теста.
Частичные решения, которые приходят на ум, включают:
- идеальная хеш-функция (дорого для больших наборов)
- дальность испытаний:
foreach(b in ranges) if (b.l <= v && v <= b.h) return true; - деревья / индексы (в некоторых случаях дороже, чем другие)
- поиск по таблице (дорого для больших наборов)
- инверсия любого из них (кодос к Джейсон С)
Кажется, что идеальным решением было бы выбрать, какой вариант лучше всего, а если ни один из них не работает хорошо, использовать дерево, чтобы разбить весь диапазон на разделы, а затем переключиться на другие варианты подразделов, которые им больше подходят.
Темы, которые могут быть полезны, включают:
Примечание: это не домашнее задание. если оно было выдано как домашнее задание ниже докторского уровня, профессора следует застрелить из ружья Нерф (если вы этого не понимаете, перечитайте задачу, это очень нетривиально)
Примечание: это проблема, которая возникала у меня несколько дней назад, и я ломал голову над ней то и дело. У меня нет прямого использования этого, но я подумал, что было бы круто атаковать. Причина, по которой я хочу сгенерировать код, заключается в том, что сгенерированный код будет не медленнее, чем общий код (при необходимости, это может быть то же самое) и может быть быстрее в некоторых / многих случаях.
Я отправляю этот вопрос, чтобы прояснить свои мысли. Если я смогу придумать какие-либо разумные или крутые решения, я планирую реализовать их в виде метапрограммы шаблона (другая причина сгенерированного кода)
некоторые люди отметили, что проблема носит очень общий характер. Вот в чем суть. Я надеюсь создать систему, которая будет работать в очень общей области: наборы целых чисел в некотором диапазоне.
спасибо за разъяснение - теперь вопрос не только смехотворно чрезмерно обобщен (обрабатывать целые числа 100B, обрабатывать целые числа 6), но объяснение снисходительно и оскорбительно. Отличная работа! Получите -1 за усилия и голосование за закрытие как «не настоящий вопрос» (потому что это не настоящая проблема).
@Steven: Я думаю (но не уверен), что вы упускаете использование оскорбительного тега. IIRC это за спам, клеветы, порно и тому подобное.
Какого черта? Это правильный вопрос, охватывающий несколько различных проблемных областей (большие наборы, маленькие наборы и т. д.).
спасибо за переформулировку оскорбительного раздела, оскорбительное голосование удалено (я считаю оскорбление читателя оскорблением / клеветой; давайте будем вежливыми и дружелюбными)
@ [Jason S]: в этом вопросе запрашивается генератор кода для задачи ввода без ограничений; поэтому она неразрешима. Смотрите "ответ"
p.s. Я бы сначала рассмотрел подход, не связанный с созданием кода (общий алгоритм), или, по крайней мере, несколько перекрывающихся алгоритмов, которые обрабатывают разные варианты проблемы. Тогда, если похоже, что генерация кода имеет большую выгоду, используйте ее. (в остальном это кажется большим усилием)
@Steven: Странно, я оставил часть, которая, как я ожидал, будет самой оскорбительной (re: "Nerf gun"). Почему вы считаете оскорбительным сказать кому-то, что он чего-то не понимает?
Почему это не может быть просто цивилизованным обсуждением? Это очень открытая проблема, которая, вероятно, не имеет определенного решения, но OP ищет некоторые идеи о возможных подходах.
Я разочарован, увидев -1 голос, проблема, с которой я столкнулся с ними в таком случае, заключается в том, что они привлекают другие -1 голоса и отталкивают людей, которые в противном случае могли бы внести весомый вклад в вопрос, потому что они видят: «О, это один из тех постов с отрицательными моментами ».
Голос против удален, чтобы отдать должное любезным ответам ОП. Но я тоже не могу проголосовать за него, это просто не проблема. У реальных проблем есть ограничения. [и стрелять в профессоров CS из нерфов не оскорбительно, это обязательно]
Ответы 3
предыдущий вопрос по словарю / проверке орфографии имеет ряд ответов, в которых упоминается Фильтры Блума; может это поможет.
Я думаю, что тестирование больших наборов будет дорогостоящим, несмотря ни на что.
Фильтры Блума - это расширение хеширования. Если я пойду по этому пути, то с таким же успехом я могу сделать минимальный идеальный хеш или что-то подобное. Это хорошая мысль, которая может быть полезна для связанных вопросов.
давайте на мгновение представим, что это реальный вопрос:
- нет ограничений на размер базового набора или входного набора
это делает "проблему" нереальной, недооцененной и неразрешимой в любом практическом смысле.
Если кто-то хочет предложить решение, вот несколько примеров модульного тестирования:
модульный тест 1:
- базовый набор - это все целые числа от -1,000,000,000,000 до +1,000,000,000,000, за исключением 100000000000 случайно удаленных значений
- входной набор - 100000000000 случайно сгенерированных целых чисел в том же диапазоне
модульный тест 2:
- базовый набор - это ряд Фибоначчи
- входной набор - это 1T случайно сгенерированных целых чисел в диапазоне 0..infinity
добавил несколько прагматических заметок, чтобы ответить на ваши вопросы. (даже qsort не сработает, если список настолько велик, что не хватает места в стеке)
Для модульного теста 1 было бы более эффективно обрабатывать дополнение базового набора.
@ [Jason S]: верно, но с учетом описания проблемы («Ничего особенного сейчас не известно о диапазоне или наборе для тестирования») у вас не будет возможности узнать об этом!
Вы бы не знали этого во время разработки, но вы бы знали это во время выполнения, поскольку алгоритм знает фиксированный набор входных данных, которые он дал, и может подсчитывать, чтобы увидеть, является ли набор или его дополнение больше / проще / что бы ни.
Итак, ваше решение представляет собой набор эвристик, предполагающих, в каком частном случае следует применить оптимизацию; можно реализовать в качестве шаблона стратегии для генерации кода, это сработает, но поскольку проблема не решена, у вас будет неограниченный набор возможных эвристик
есть также boost :: dynamic_bitset, не уверен, как он масштабируется во времени или в пространстве относительно распределения исходных чисел. (например, если биты хранятся в кусках 8/16/32/64, то разреженные битовые наборы неэффективны)
или, возможно, веб-страница это (сжатый набор бит) или это (битовый вектор) (я искал в Google "большие разреженные наборы битов" и "сжатые наборы битов")
Интересно. Однако я подозреваю, что сжатый набор битов не настроен для доступа к отдельным битам. Потребуется какая-то система сжатия с произвольным доступом (но, похоже, это активная область исследований и разработок)
Вы хорошо поработали, объяснив проблему, за исключением того, почему вы хотите это сделать и почему необходимо сгенерировать код вместо общего решения. Можете ли вы заполнить эту информацию?