На самом деле это комментарий к тесту производительности, опубликованному 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 );

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

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

В CELT ( http://celt-codec.org ) внеофисный CLZ, который мы используем для компиляторов без 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.

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

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

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.

У меня также есть индекс поиска lucene, который используется несколькими клиентами, я решаю эту проблему, делая «Службу поиска Lucene» отдельной веб-службой, работающей в собственном домене приложений. Поскольку оба клиента попали в одну веб-службу для поиска или обновления индекса, я могу сделать его защищенным от потоков с блокировками на индексаторах Lucene.

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

Чтобы получить возможность использовать новый индекс, я создаю его на стороне, а затем предлагаю службе Search Index поменяться местами для использования нового индекса путем безопасного удаления любых индексаторов в текущем индексе и переименования каталогов, Например,

• Index.Current > Index.Old
• Index.New > Index.Current

Я думаю, что необходимо включить проверку выполнения контракта в параметрах настройки проекта (должна быть панель «Code Contracts»...)

Для получения дополнительной информации см. пользовательскую документацию (раздел 6).

Похоже, диапазон известен. Давайте предположим, что он поднимается до 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.

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

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

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

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

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

Вы можете сделать это за время 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

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