Ответ 1

Короткий ответ

Что касается python:

• самый быстрый метод для всех, чтобы найти показатель 2 ** x, - это поиск в словаре, чьи хэши имеют степень 2 (см. "hashlookup" в коде)
• самый быстрый побитовый метод - это тот, который называется unrolled_bitwise.
• Оба предыдущих метода имеют четко определенные (но расширяемые) верхние пределы. самый быстрый метод без жестко заданных верхних пределов (который масштабируется, поскольку python может обрабатывать числа) является "log_e".

Предварительные примечания

• Все приведенные ниже измерения скорости были получены с помощью timeit.Timer.repeat(testn, cycles), где testn было установлено значение 3, а cycles было автоматически настроено с помощью script для получения времени в диапазоне секунд ( Примечание: была ошибка в этом автоматическом регулировании, который был исправлен 18/02/2010).
• Не все методы могут масштабироваться, поэтому я не тестировал все функции для разных степеней 2
• Мне не удалось заставить некоторые из предложенных методов работать (функция возвращает неверный результат). Мне еще не удалось сделать пошаговый отладочный сеанс: я включил код (прокомментировал) на всякий случай, когда кто-то замечает ошибку путем проверки (или хочет самостоятельно выполнить отладку)

Результаты

FUNC (2 5) **

hashlookup:          0.13s     100%
lookup:              0.15s     109%
stringcount:         0.29s     220%
unrolled_bitwise:    0.36s     272%
log_e:               0.60s     450%
bitcounter:          0.64s     479%
log_2:               0.69s     515%
ilog:                0.81s     609%
bitwise:             1.10s     821%
olgn:                1.42s    1065%

FUNC (2 31) **

hashlookup:          0.11s     100%
unrolled_bitwise:    0.26s     229%
log_e:               0.30s     268%
stringcount:         0.30s     270%
log_2:               0.34s     301%
ilog:                0.41s     363%
bitwise:             0.87s     778%
olgn:                1.02s     912%
bitcounter:          1.42s    1264%

FUNC (2 128) **

hashlookup:     0.01s     100%
stringcount:    0.03s     264%
log_e:          0.04s     315%
log_2:          0.04s     383%
olgn:           0.18s    1585%
bitcounter:     1.41s   12393%

FUNC (2 1024) **

log_e:          0.00s     100%
log_2:          0.01s     118%
stringcount:    0.02s     354%
olgn:           0.03s     707%
bitcounter:     1.73s   37695%

Код

import math, sys

def stringcount(v):
    """mac"""    
    return len(bin(v)) - 3

def log_2(v):
    """mac"""    
    return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999

def log_e(v):
    """bp on mac"""    
    return int(round(math.log(v)/0.69314718055994529, 0))  # 0.69 == log(2)

def bitcounter(v):
    """John Y on mac"""
    r = 0
    while v > 1 :
        v >>= 1
        r += 1
    return r

def olgn(n) :
    """outis"""
    if n < 1:
        return -1
    low = 0
    high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
    while True:
        mid = (low+high)//2
        i = n >> mid
        if i == 1:
            return mid
        if i == 0:
            high = mid-1
        else:
            low = mid+1

def hashlookup(v):
    """mac on brone -- limit: v < 2**131"""
#    def prepareTable(max_log2=130) :
#        hash_table = {}
#        for p in range(1, max_log2) :
#            hash_table[2**p] = p
#        return hash_table

    global hash_table
    return hash_table[v] 

def lookup(v):
    """brone -- limit: v < 2**11"""
#    def prepareTable(max_log2=10) :
#        log2s_table=[0]*((1<<max_log2)+1)
#        for i in range(max_log2+1):
#            log2s_table[1<<i]=i
#        return tuple(log2s_table)

    global log2s_table
    return log2s_table[v]

def bitwise(v):
    """Mark Byers -- limit: v < 2**32"""
    b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000)
    S = (1, 2, 4, 8, 16)
    r = 0
    for i in range(4, -1, -1) :
        if (v & b[i]) :
            v >>= S[i];
            r |= S[i];
    return r

def unrolled_bitwise(v):
    """x4u on Mark Byers -- limit:   v < 2**33"""
    r = 0;
    if v > 0xffff : 
        v >>= 16
        r = 16;
    if v > 0x00ff :
        v >>=  8
        r += 8;
    if v > 0x000f :
        v >>=  4
        r += 4;
    if v > 0x0003 : 
        v >>=  2
        r += 2;
    return r + (v >> 1)

def ilog(v):
    """Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32"""
    ret = 1
    m = (not not v & 0xFFFF0000) << 4;
    v >>= m;
    ret |= m;
    m = (not not v & 0xFF00) << 3;
    v >>= m;
    ret |= m;
    m = (not not v & 0xF0) << 2;
    v >>= m;
    ret |= m;
    m = (not not v & 0xC) << 1;
    v >>= m;
    ret |= m;
    ret += (not not v & 0x2);
    return ret - 1;


# following table is equal to "return hashlookup.prepareTable()" 
hash_table = {...} # numbers have been cut out to avoid cluttering the post

# following table is equal to "return lookup.prepareTable()" - cached for speed
log2s_table = (...) # numbers have been cut out to avoid cluttering the post

Ответ 2

"языковой агностик" и беспокоиться о производительности - это в значительной степени несовместимые понятия.

Большинство современных процессоров имеют инструкцию CLZ, "подсчитывают ведущие нули". В GCC вы можете добраться до него с помощью __builtin_clz (x) (который также дает разумный, если не самый быстрый, код для целей, которые не содержат clz). Обратите внимание, что этот CLZ равен undefined для нуля, поэтому вам понадобится дополнительная ветвь, чтобы поймать этот случай, если это имеет значение в вашем приложении.

В CELT (http://celt-codec.org) нераскрытый CLZ, который мы используем для compliers, не имеющих CLZ, был написан Тимоти Б. Терриберри:

int ilog(uint32 _v){
  int ret;
  int m;
  ret=!!_v;
  m=!!(_v&0xFFFF0000)<<4;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xFF00)<<3;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xF0)<<2;
  _v>>=m;
  ret|=m;
  m=!!(_v&0xC)<<1;
  _v>>=m;
  ret|=m;
  ret+=!!(_v&0x2);
  return ret;
}

(Комментарии показывают, что это было обнаружено быстрее, чем версия ветвления и версия на основе таблицы поиска)

Но если производительность критическая, вы, вероятно, не должны реализовывать эту часть своего кода в python.

Ответ 3

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

Вы можете попробовать this, например:

register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
  if (v & b[i])
  {
    v >>= S[i];
    r |= S[i];
  } 
}

Похоже, что его можно легко преобразовать в Python.

Ответ 4

Вы можете сделать это в O (lg s) для произвольных целых чисел, используя binsearch.

import sys
def floorlg(n):
    if n < 1:
        return -1
    low=0
    high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
    while True:
        mid = (low+high)//2
        i = n >> mid
        if i == 1:
            return mid
        if i == 0:
            high = mid-1
        else:
            low = mid+1

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

Ответ 5

Кажется, что диапазон известен. Предположим, что он поднимается до 1 < 20, только чтобы сделать его более интересным:

max_log2=20

Итак, создайте список, который (по сути) отображает целое число в его логарифм базы 2. Следующее выполнит трюк:

log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
    log2s_table[1<<i]=i

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

Функция для получения логарифма очень проста и может легко быть встроена:

def table(v):
    return log2s_table[v]

Я не могу гарантировать, что тестовый код, который я написал, точно такой же, как тот, который используется для получения примерных таймингов, но это скорее быстрее, чем код stringcount:

stringcount: 0.43 s.
table: 0.16 s.

Поскольку все значения в таблице меньше 256, я задавался вопросом, будет ли использование строки вместо списка быстрее или, может быть, array.array байтов, но не кости:

string: 0.25 s.
arr: 0.21 s.

Использование dict для поиска - это еще одна возможность, использующая способ проверки только двух значений:

log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])

def map(v):
    return log2s_map[v]

Результаты для этого были не такими хорошими, хотя:

map: 0.20 s.

И только для удовольствия можно также использовать метод hex для объектов float, чтобы получить строку, которая включает в себя (как ее последнюю часть) показатель базовой 2 числа. Это немного медленнее для извлечения в целом, но если показатель только когда-либо будет одной цифрой, это можно сделать достаточно просто:

def floathex(v):
    return ord(float(v).hex()[-1])-48

Это чисто развлекательная ценность, хотя она была неконкурентоспособной - хотя, что удивительно, все же быстрее, чем побитовый подход.

Итак, похоже, что использование списка - это путь.

(Этот подход не будет масштабироваться неограниченно, из-за ограниченной памяти, но чтобы компенсировать это, скорость выполнения не будет зависеть от max_log2 или входных значений любым способом, который вы заметите при запуске python. Что касается потребления памяти, если я правильно помню свои внутренние функции python, таблица будет занимать около (1<<max_log2)*4 байтов, потому что содержимое - это все мелкие целые числа, которые интерпретатор будет автоматически запускаться. SO, когда max_log2 равно 20, это около 4 МБ.)

Ответ 6

Это на самом деле комментарий к тесту производительности, опубликованному mac. Я отправляю это как ответ, чтобы иметь правильное форматирование кода и отступы

mac, вы могли бы попробовать развернутую реализацию bitseach, предложенную Марк Байерсом? Возможно, это просто доступ к массиву, который замедляет его. Теоретически этот подход должен быть быстрее других.

Он будет выглядеть примерно так, хотя я не уверен, что форматирование подходит для python, но я думаю, вы можете видеть, что он должен делать.

def bitwise(v):
    r = 0;
    if( v > 0xffff ) : v >>= 16; r = 16;
    if( v > 0x00ff ) : v >>=  8; r += 8;
    if( v > 0x000f ) : v >>=  4; r += 4;
    if( v > 0x0003 ) : v >>=  2; r += 2;
    return r + ( v >> 1 );

Если python разделяет java отсутствие неразделенных целых чисел, это должно быть примерно так:

def bitwise(v):
    r = 0;
    if( v & 0xffff0000 ) : v >>>= 16; r = 16;
    if( v > 0x00ff ) : v >>=  8; r += 8;
    if( v > 0x000f ) : v >>=  4; r += 4;
    if( v > 0x0003 ) : v >>=  2; r += 2;
    return r + ( v >> 1 );

Ответ 7

Поздно к вечеринке, но как насчет int.bit_length(n) - 1? Вы просили прямо, и это кажется самым простым для меня. Реализация CPython выглядит достаточно производительно.

• Справочная документация
• Исходный код CPython