Эффективная реализация гистограммы с использованием хеш-функции

Question

Существует ли более эффективный подход к вычислению гистограммы, чем двоичный поиск для распределения нелинейных бинов?

На самом деле меня интересует только бит алгоритма, который соответствует ключу (значению) в bin (передаточная функция?), Т.е. для группы значений с плавающей запятой. Я просто хочу знать соответствующий индекс bin для каждого значения.

Я знаю, что для линейного распределения бинов вы можете получить O (1), разделив значение на ширину ячейки, а для не линейных бинов двоичный поиск вы получите O (logN). В моей текущей реализации используется двоичный поиск по неравным ширинам бункера.

В духе повышения эффективности мне было любопытно, можно ли использовать хеш-функцию для сопоставления значения с соответствующим бункером и достижения сложности времени O (1), когда у вас есть ящики с неравной шириной?

Answer 1

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

Альтернативой является создание массива P с записями, которые индексируются в таблицу B пределов бинов.Учитывая некоторое значение x, мы находим бит j, принадлежащий (или иногда близлежащему ящику) через j = P[⌊x·r⌋], где r - это отношение, которое зависит от размера P и максимального значения в B. Эффективность этого подхода зависит от значений в B и размеру P.

Поведение функций, таких как P[⌊x·r⌋], можно увидеть с помощью кода python, показанного ниже. (Метод примерно одинаковый на любом языке программирования. Однако ниже приведены советы для Python-to.) Предположим, что код хранится в файле histobins.py и загружается в интерпретатор ipython с помощью команды import histobins as hb. Затем команда, как hb.betterparts(27, 99, 9, 80,155) производит выходной сигнал, как

At 80 parts, steps = 20 = 7+13 
At 81 parts, steps = 16 = 7+9 
At 86 parts, steps = 14 = 6+8 
At 97 parts, steps = 13 = 12+1 
At 108 parts, steps = 12 = 3+9 
At 109 parts, steps = 12 = 8+4 
At 118 parts, steps = 12 = 6+6 
At 119 parts, steps = 10 = 7+3 
At 122 parts, steps = 10 = 3+7 
At 141 parts, steps = 10 = 5+5 
At 142 parts, steps = 10 = 4+6 
At 143 parts, steps = 9 = 7+2 

эти параметры, чтобы установить betterparts nbins=27, topsize=99, seed=9, plo=80, phi=155, который создает тестовый набор из 27 бункеров для значений от 0 до 99, со случайной затравки 9, и размера P от 80 до 155- 1. Число «шагов» - это количество раз, когда два цикла в тестовых частях() работают во время теста с 10 * nbins значениями от 0 до topsize. Например: «В 143 частях, этапы = 9 = 7 + 2» означает, что, когда размер P равен 143, из 270 испытаний, 261 раз P[⌊x·r⌋] произвел правильный индекс сразу; В 7 раз индекс должен был быть уменьшен, и в два раза он должен был быть увеличен.

Общая идея метода заключается в том, чтобы избавиться от пространства на время. Другим компромиссом является время подготовки и время работы. Если вы собираетесь делать миллиарды поисков, стоит потратить несколько тысяч проб, чтобы найти хорошее значение | P |, размер P. Если вы собираетесь делать всего несколько миллионов поисков, это может быть лучше просто выбрать некоторое большое значение | P | и работать с ним, или, возможно, просто запускать более качественные компоненты в узком диапазоне. Вместо того, чтобы делать 75 тестов, как указано выше, если мы начнем с более больших | P | меньшее количество тестов может дать достаточно хороший результат. Например, 10 тестов через «hb.betterparts (27, 99, 9, 190200)» производит

At 190 parts, steps = 11 = 5+6 
At 191 parts, steps = 5 = 3+2 
At 196 parts, steps = 5 = 4+1 

Пока P вписывается в некоторый уровень кэша (наряду с другими соответствующими данными), что делает | P | больше ускорит доступ. Итак, делая | P | насколько это практично, это хорошая идея. Как | P | становится больше, разница в производительности между одним значением | P | и следующий становится все меньше и меньше. Ограничивающие факторы на скорости затем включают время для умножения и время для установки в цикле. Одним из подходов для более быстрого умножения может быть выбор мощности 2 в качестве множителя; вычислить | P | соответствовать; затем использовать сдвиги или добавлять к экспонентам вместо умножения. Один из подходов к сокращению времени при создании циклов заключается в том, чтобы переместить оператор if bins[bin] <= x < bins[bin+1]: (или его эквивалент C, см. Ниже) перед инструкциями while и делать только в том случае, если инструкция if терпит неудачу.

Код Python показан ниже.Обратите внимание, в переводе с Python на C,
• # начинает комментарий
• def начинает функцию
• заявление как ntest, right, wrong, x = 10*nbins, 0, 0, 0 присваивает значения соответствующих идентификаторов
• заявление как return (ntest, right, wrong, stepdown, stepup) возвращает кортеж из 5 значений, которые вызывающий абонент может назначить кортеж или соответствующие идентификаторы
• сферы действия def, while, или if заканчивается с линией не отступом дальше, чем def, while, или if
• bins = [0] инициализирует список (выдвижная индексируемая массив) со значением 0 в качестве начального входа
• bins.append(t) добавляет значение Т в конце списка bins
• for i,j in enumerate(p): запускает цикл по элементам Iterable р (в данном случае, р представляет собой список), в результате чего индекс i и соответствующие записи j == p[i] доступные внутри цикл
• range(nparts) обозначает список значений 0, 1, ... nparts-1
• range(plo, phi) стендов для списка значений пнули, PLO + 1, ... фи-1
• if bins[bin] <= x < bins[bin+1] средства if ((bins[bin] <= x) && (x < bins[bin+1]))
• int(round(x*float(nparts)/topsize))) фактически завершает x·r вместо вычислений ⌊x·r⌋ как рекламируется выше

def makebins(nbins, topsize): 
    bins, t = [0], 0 
    for i in range(nbins): 
     t += random.random() 
     bins.append(t) 
    for i in range(nbins+1): 
     bins[i] *= topsize/t 
    bins.append(topsize+1) 
    return bins 
#________________________________________________________________ 
def showbins(bins): 
    print ''.join('{:6.2f} '.format(x) for x in bins) 
def showparts(nbins, bins, topsize, nparts, p): 
    ratio = float(topsize)/nparts 
    for i,j in enumerate(p): 
     print '{:3d}. {:3d} {:6.2f} {:7.2f} '.format(i, j, bins[j], i*ratio) 
    print 'nbins: {} topsize: {} nparts: {} ratio: {}'.format(nbins, topsize, nparts, ratio) 
    print 'p = ', p 
    print 'bins = ', 
    showbins(bins) 
#________________________________________________________________ 

def testparts(nbins, topsize, nparts, seed): 
    # Make bins and make lookup table p 
    import random 
    if seed > 0: random.seed(seed) 
    bins = makebins(nbins,topsize) 
    ratio, j, p = float(topsize)/nparts, 0, range(nparts) 
    for i in range(nparts): 
     while j<nbins and i*ratio >= bins[j+1]: 
      j += 1 
     p[i] = j 
    p.append(j) 
    #showparts(nbins, bins, topsize, nparts, p) 

    # Count # of hits and steps with avg. of 10 items per bin 
    ntest, right, wrong, x = 10*nbins, 0, 0, 0 
    delta, stepdown, stepup = topsize/float(ntest), 0, 0 
    for i in range(ntest): 
     bin = p[min(nparts, max(0, int(round(x*float(nparts)/topsize))))] 

     while bin < nbins and x >= bins[bin+1]: 
      bin += 1; stepup += 1 
     while bin > 0 and x < bins[bin]: 
      bin -= 1; stepdown += 1 
     if bins[bin] <= x < bins[bin+1]: # Test if bin is correct 
      right += 1 
     else: 
      wrong += 1 
      print 'Wrong bin {} {:7.3f} at x={:7.3f} Too {}'.format(bin, bins[bin], x, 'high' if bins[bin] > x else 'low') 
     x += delta 
    return (ntest, right, wrong, stepdown, stepup) 
#________________________________________________________________ 

def betterparts(nbins, topsize, seed, plo, phi): 
    beststep = 1e9 
    for parts in range(plo, phi): 
     ntest, right, wrong, stepdown, stepup = testparts(nbins, topsize, parts, seed) 
     if wrong: print 'Error with ', parts, ' parts' 
     steps = stepdown + stepup 
     if steps <= beststep: 
      beststep = steps 
      print 'At {:3d} parts, steps = {:d} = {:d}+{:d}'.format(parts, steps, stepdown, stepup) 
#________________________________________________________________ 

Answer 2

Зависит от реализации хэширования и типа данных, с которыми вы работаете. Для более мелких наборов данных более простой алгоритм, такой как бинарный поиск, может превзойти постоянный поиск, если накладные расходы хэширования в среднем превышают. Обычная реализация хэширования состоит из массива связанных списков и хеширующей функции, которая отображает строку в индекс в массиве связанных списков. Здесь называется фактор нагрузки, который представляет собой количество элементов в хэш-карте/длине массива связанных списков. Таким образом, для коэффициентов нагрузки < 1 вы достигнете постоянного поиска в лучшем случае, потому что ни один связанный список не будет содержать более одного элемента (лучший случай).

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

Answer 3

В некоторых простых случаях вы можете получить O (1).

Пусть ваши значения 8-бит, от 0 до 255.

Если вы разбили их в 8 закромах размеров 2, 2, 4, 8, 16, 32, 64, 128, то бункер диапазоны значений будут: 0-1, 2-3, 4-7, 8-15, 16-31, 32-63, 64-127, 128-255.

В бинарном этих диапазонах выглядеть следующим образом:

0000000x (bin 0) 
0000001x 
000001xx 
00001xxx 
0001xxxx 
001xxxxx 
01xxxxxx 
1xxxxxxx (bin 7) 

Так что, если вы можете быстро (в O (1)) подсчитать, сколько наиболее значимые нулевые бит Есть в значении, вы можете получить номер ячейки от него.

В этом конкретном случае вы можете предварительно вычислить таблицу поиска из 256 элементов, содержащую номер ячейки и найти соответствующий бит для значения, это всего лишь один просмотр таблицы.

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

Если вы должны были использовать ячейки размером 2, вы можете повторно использовать эту таблицу поиска для 16-битных значений. И вам понадобятся два подхода. Вы можете расширить его до еще более высоких значений.

Answer 4

Interpolation search является вашим другом. Это своего рода оптимистический, интеллектуальный двоичный поиск, где он догадывается, где бункер должен основываться на линейном предположении о распределении входных данных, а не просто разбивать пространство поиска пополам на каждом шаге. Это будет O (1), если линейное предположение верно, но все же работает (хотя и медленнее), когда предположение не является. В той степени, в которой его прогнозы точны, поиск выполняется быстро.