Как я могу проверить Вес Hamming, не преобразовывая в двоичный файл?
count () выдаст предупреждение, если NULL из PHP 7.2. Есть ли лучший способ исправить это, чем добавить другое условие?
ДА
Решение состоит в том, чтобы аргумент был массивом:
[114 ] Это работает на PHP 5 и 7, все версии до 7.2.4 протестированы. Нет записей в журнале ошибок, где найдено.if (count((array)$this->implements) > 0)
5 ответов
IMO, хорошим подходом было бы используйте справочную таблицу - создайте словарь, который преобразует байты в число единиц (вы можете использовать опубликованный вами код для его генерации, его нужно будет запустить только один раз), а затем используйте что-то вроде этого:
def number_of_ones(n):
sum = 0
while n != 0:
sum += lookup_table[n & 0xff]
n >>= 8
return sum
Я считаю это довольно хороший компромисс между пространством и временем выполнения.
Вы не можете сделать это менее сложным в вычислительном отношении. Это будет O (n) количество бит, или, как показал ответ с трюком &, O (n) количество бит, установленное в 1; но если все числа, которые вы используете, не являются частным случаем, последнее должно быть в среднем n / 2, так что оба этих числа O (n) одинаковы.
И уловка с таблицей поиска, конечно же, на самом деле ничего не делает для вычислительной сложности; это просто плата за время пространством, но без изменения лежащей в основе экономики, которая состоит в том, что вы должны как-то исследовать каждый бит один раз как-то , и нет никакого способа обойти это. Вы не можете, по логике, ответить на вопрос о битах в числе, не проверив каждую из них.
Итак, я полагаю, что я ' m немного небрежно, так как многие из этих примеров на самом деле O (n ^ 2), поскольку в Python вам нужно проверять все число сразу, поэтому с длинным целым числом Python, скажем, 100 байт, a + или & или операция / будет просматривать каждый байт хотя бы один раз, и это будет происходить снова и снова, пока число не уменьшится до нуля (в схемах, описанных выше), так что это, опять же, действительно операции O (n ^ 2). Я не уверен, что Python разрешит здесь истинное решение O (n).
В любом случае: если вы действительно спрашивали о вычислительной сложности, что конкретно означает анализ большого O, это ваш ответ. : -)
или операция / будет просматривать каждый байт хотя бы один раз, и это будет происходить снова и снова, пока число не уменьшится до нуля (в схемах, описанных выше), так что это, опять же, действительно операции O (n ^ 2). Я не уверен, что Python разрешит здесь истинное решение O (n).В любом случае: если вы действительно спрашивали о вычислительной сложности, что конкретно означает анализ большого O, это ваш ответ. : -)
или операция / будет просматривать каждый байт хотя бы один раз, и это будет происходить снова и снова, пока число не уменьшится до нуля (в схемах, описанных выше), так что это, опять же, действительно операции O (n ^ 2). Я не уверен, что Python разрешит здесь истинное решение O (n).В любом случае: если вы действительно спрашивали о вычислительной сложности, что конкретно означает анализ большого O, это ваш ответ. : -)
Я не программист на Python, но, надеюсь, этого будет достаточно для вас.
c = 0
while n:
c += 1
n &= n - 1
return c
Хотя это немного непонятно, его основным преимуществом является скорость и простота. Цикл while повторяется только один раз для каждого бита, установленного в 1 в n.
Если вы хотите сделать это в одной строке, вы можете использовать:
sum( [x&(1<<i)>0 for i in range(32)] )
Если вас действительно беспокоит скорость, запрограммируйте ее на C (см. этот вопрос , чтобы узнать, как), и взаимодействуйте с реализацией C, используя что-то вроде ctypes .