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

Question

Этот вопрос был вдохновлен ответом, над которым я работал вчера.

Допустим, у нас есть N входных данных, которые оценивают как истинные или ложные, каков наиболее эффективный способ определить, являются ли X из этих входных данных истинными?

Предостережения:

1. Входные данные не находятся в массиве, поэтому, если вы преобразуете их в массив, учтите любые издержкирасходы.
2. Под "наиболее эффективным" я подразумеваю в терминах наилучшего среднего случая (хотя мне бы хотелось также видеть статистику лучших и худших случаев).

---

Здесьдва метода, с которыми я столкнулся вчера.

1) Думайте о переменных как о булевых входах для схемы и уменьшайте их, используя K-карту

Сначала я подумал, что это будет наиболее эффективным способом, потому чтоэто следует за схемотехникой, но у меня определенно были вторые мысли.По мере увеличения количества входов число сравнений возрастает экспоненциально

2 inputs:
   1 of 2: if(1 OR 2)
   2 of 2: if(1 AND 2)

3 inputs:
   1 of 3: if(1 OR 2 OR 3)
   2 of 3: if((1 AND 2) OR (1 AND 3) OR (2 AND 3))
   3 of 3: if(1 AND 2 AND 3)

4 inputs:
   1 of 4: if(1 OR 2 OR 3 OR 4)
   2 of 4: if((1 AND 2) OR (1 AND 3) OR (1 AND 4) OR (2 AND 3) OR (2 AND 4) OR (3 AND 4))
   3 of 4: if((1 AND 2 AND 3) OR (1 AND 2 AND 4) OR (1 AND 3 AND 4) OR (2 AND 3 AND 4))
   4 of 4: if(1 AND 2 AND 3 AND 4)

... etc. ...

В лучшем случае все в порядке (O(1)), но в худшем случае гораздо хуже, чем ...

2) Счетчик и последовательные операторы if

Это выполняется за O(n) время всегда, что нормально, но я надеялся на лучший лучший случай.

counter = 0

if(input 1)
   counter++

if(input 2)
   counter++

if(input 3)
   counter++

... etc. ...

if(counter >= X)
   // true

---

Что может быть более эффективным решением, чем любое из них?

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Инициализация счетчика или переменной
• Проверка ввода или переменной
• сложение или вычитание
• и т. Д.

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

Answer 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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

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

Answer 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 дополнений, но они распараллеливаются в лог (2, N) поколений (при условии, что у вас достаточно процессоров / сумматоров для одновременного выполнения N / 2 операций ...)

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

Answer 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

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

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

$ time ./xoutofn
500

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