Самый эффективный алгоритм для определения истинности X из N входов

Ответ 1

О сложности проблемы
Поскольку запрашивается точный счет (в отличие от того, чтобы спросить, включено ли хотя бы х входов), проблема очень четко O(n):

• нужно посещать каждый отдельный вход и
• работа для каждого входа не зависит от n (в то время как работа для данного входа может меняться в зависимости от конкретного значения входа, объем работы [для этого входа] не меняется, если количество входов изменено.)

Мы можем, конечно, реализовать субоптимальные алгоритмы, которые, например, [излишне] будут посещать все другие входы, поскольку каждый вход обрабатывается, делая его реализацией O (n ^ 2), но это, конечно, глупо.

При этом утверждается, что вопросы, вероятно, касаются... трюки, которые ускорили бы реализацию
Следует отметить, что, хотя такие трюки могут существовать, сложность алгоритма/задачи остается упрямо в O (n).

Trick 1: Лучшее хранилище для входов
К сожалению, вопрос указывает, что входные данные поступают из именованных переменных и что стоимость для любого преобразования ввода [для обеспечения более быстрого подсчета] должна быть принята во внимание для оценки общей производительности алгоритма. Хотя это в конечном счете зависит от основного языка, времени выполнения и т.д., Необходимость учета стоимости конверсии очень вероятно осуждает любой алгоритм, основанный на альтернативном хранении, который будет медленнее, чем решения, которые сохраняют входы как есть.

Trick 2: короткое замыкание оценки
Идея состоит в том, чтобы вернуть false как можно скорее (или вскоре после) как либо

• количество запущенных входов, большее, чем X, (или, если мы подсчитываем количество отключенных входов, когда этот счетчик превышает (n - X))
• количество входов, оставшихся до тестирования, плюс счетчик запусков включенных входов меньше X. (или что-то подобное в случае подсчета выходов).

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

Trick 3: использовать обратную логику: подсчитайте количество отключенных входов, а не они. (или считать оба).
Стоимость/преимущества этого подхода зависят как от количества входных данных для теста (X вопроса), так и от статистики, которую мы можем иметь о входе (это число на входе в данный момент относительно равномерно или мы имеем тенденцию иметь только несколько входов (или выключен)).

Решение предложенное Крисом Ачесоном, является базой для использования как Trick 2, так и Trick 3. Предполагая, что мы можем сделать несколько предположений о распределении входных данных, дополнительные улучшения производительности для этой базовой линии будут приводиться в движение такими "приоритетами": некоторые быстрые эвристики, сделанные до подсчета входов сами по себе, определяли бы, какое состояние мы должны считать (включенным или выключенным или обоими), что ограничивает нас должен тестировать и т.д. и переходить к соответствующим "версиям" алгоритма.

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

О наилучшей/сложной "сложности" этих оптимизированных алгоритмов
Предполагая, что

• количество входов, которые включены в данный момент времени, равномерно распределено
• все входы имеют 50% -ное изменение в течение определенного времени
• X выбирается случайным образом между 1 и n

Комбинация трюков # 2 и # 3 может быть O(X/2) в среднем (мне нужно сделать математику, но это кажется правильным). Однако я думаю, что разумнее говорить в терминах number of operations относительно X и/или n, а не злоупотреблять O-нотацией...
Предполагая, что все операции примерно несут ту же стоимость

• Инициализировать счетчик или переменную
• Проверьте вход или переменную
• сложение или вычитание
• и т.д.

Легче и точнее вычислить общее количество операций, необходимых для выполнения данного алгоритма, и, следовательно, использовать такие подсчеты для различных лучших/худших/средних случаев, чтобы помочь решить конкретные алгоритмы.
Чтобы проиллюстрировать это, наивная реализация, которая просто систематически учитывала бы все входные данные и только сравнивала счетчик в конце, была бы сложна O (n) и полна во всех случаях примерно в 1 + 2 * n + 1 операциях. Такой алгоритм может оказаться общим, лучше, чем алгоритм fancier, который, будучи, например, O (X), O ((X + n)/2) и O (n) в лучших, средних и худших случаях, соответственно, вполне могут использовать операции X * 3, (X + n) * 1.5 и n * 3 в этих же случаях.

Ответ 2

Эта версия будет эффективной для значений X, близких к нулю или N:

true_counter = 0
false_counter = 0
max_false = N - X

if(input 1)
   true_counter++
   if(counter >= X)
      return true
else
   false_counter++
   if(false_counter > max_false)
      return false

// and so on

Ответ 3

Подсчет истин - это самый быстрый способ. Ваш собственный счетчик позволит больше, чем X, быть правдой, но вопрос подразумевает, что вы хотели получить конкретное значение - не большое дело, но если вы хотите не менее 10 (но больше - все в порядке), вы можете проверить счетчик после каждого приращения счетчик и прервать раньше.

В другой заметке, если флаги упакованы в слово, есть более быстрые способы подсчета 1. В конце концов, подсчет 1 - это путь. BTW в C False равен нулю, а True - 1, поэтому вы можете буквально добавить их вместе, чтобы считать Trues.

Ответ 4

В языках программирования, где логические значения - это просто signed char со значением 1 или 0, мы могли бы просто сделать это:

if (input1 + input2 + input3 + input4 + ... + inputX > n)

Ответ 5

Не может быть сублинейного алгоритма для общего случая: вы должны смотреть на каждый вход. Так что подсчет просто отлично.

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

Кроме того, это действительно сводится к соответствующим структурам данных. Вы спросили о битполях: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Ответ 6

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

Если у вас было N входов в цифровую схему (или процессор ячеек), вы можете подсчитать их в O (log n) раз, рекурсивно добавляя пары и распространяя результат:

[1, 1, 0, 1, 1, 1, 0, 1] -> [(1+1), (0+1), (1+1), (0+1)] -> [(2+1), (2+1)] -> [(3+3)]

Это дает нам N дополнений, но они распараллеливаются в поколение log (2, N) (если у вас достаточно процессоров/сумматоров для одновременного выполнения операций N/2).

Существуют вариации в этом алгоритме, чтобы воспользоваться требованием проблемы с порогом, но в основном они не будут стоить, если ожидается, что порог будет очень низким (например, 10 из 14000 входов).

Ответ 7

import Data.List (foldl')
main :: IO ()
xoutofn :: Num a => (a1 -> Bool) -> [a1] -> a
xoutofn pred ns = foldl' test 0 (map pred ns) where 
                    test x (True)  = x+1
                    test x (False) = x

main = print $ xoutofn predicate [1 .. 1000] where
    predicate x = x > 500

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

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

$ time ./xoutofn
500

real    0m0.003s
user    0m0.000s
sys     0m0.000s