N-й символ строки в качестве хеша не подходит? последний?

> бенчмарк пишу

Ну и как, сильно двоичный поиск проиграл хеш-таблице? :)

>У ТС ключей меньше, чем

Угу. У ТС'а множество строк намного меньше множества строк из 3-8 латинских строчных букв. Но как это учесть алгоритмически?

>Как подобрать функцию?

Еще вспомнил одну хеш функцию, на этот раз из «больших» фортов. Формируется она так <длинна строки>+ n первых символов.

> зачем тогда хэш нужен, если тогда достаточно строки хранить в дереве? а тут ведь именно хэш почему-то нужен

Видать задание в курсовике/лабораторке такое. Что ж тут теперь поделать?

Не. Двоичный поиск с переупорядочиванием как минимум быстрее обычного причем даже в ie8 :) https://gist.github.com/865717 если интересно.

У тебя от 3к до 1.5м возможных комбинаций в каждой строке. Ты пытаешься синтезировать хеш с 255 возможными значениями. Коллизия на коллизии и будет.

Может в 8 бит писать тупо порядковый номер строки?

Поиграл немного с gperf, такие результаты на 30 строках:

real    0m0.439s # двоичный поиск с bsearch и strcmp
real    0m0.117s # gperf (lookup-table)
real    0m0.157s # gperf --switch=1 (большой switch)
real    0m0.211s # gperf -l (сравнивает сначала длины строк)

Хитро замаскированное префиксное дерево ) Должно быть небыстро - такую лесенку свитчей не оптимизируешь.

как считал?

(2^6 = 64) > 40

Хэш-таблица обычно обозначает быстрый поиск. А это - последовательный поиск в массиве.

N-й символ строки в качестве хеша не подходит? последний?

В качестве плохого хэша - подходит )

Переупорядочивание влияет на скорость яваскрипта? оО

Лучше всех пока код gperf (2-й вариант):

/* ANSI-C code produced by gperf version 3.0.4 */
/* Command-line: gperf --output-file hash2.c -LANSI-C  */
/* Computed positions: -k'1,$' */

#define TOTAL_KEYWORDS 30
#define MIN_WORD_LENGTH 3
#define MAX_WORD_LENGTH 7
#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 49
/* maximum key range = 47, duplicates = 0 */

inline static unsigned int
hash (register const char *str, register unsigned int len)
{
  static unsigned char asso_values[] =
    {
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50,  0, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
      50, 50, 50, 50, 50, 50, 50, 10, 25,  5,
      10,  0,  0, 15, 50, 18,  5, 50,  0,  5,
       0, 50, 30, 20, 15,  0,  8, 50,  0,  0,
     /* skipped */
    };
  return len + asso_values[(unsigned char)str[len - 1]] + asso_values[(unsigned char)str[0]];
}

const char *
in_word_set (register const char *str, register unsigned int len)
{
  static const char * wordlist[] =
    {
      "", "", "",
      "new",
      "free",
      /* skipped */
    };

  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
    {
      register int key = hash (str, len);

      if (key <= MAX_HASH_VALUE && key >= 0)
        {
          register const char *s = wordlist[key];

          if (*str == *s && !strcmp (str + 1, s + 1))
            return s;
        }
    }
  return 0;
}

ааа, ты про это. я почему-то провел аналогию с массивом из 40 строк, длинна которых не оговорена. а так, да 6 бит на 40 вариаций строк подходит.

> длинна
Ну откуда же вы такие беретесь?

И это безобразие с хэшами работает быстрее, чем несколько сравнений строк в двоичном поиске?

Почти в 4 раза. Но это на моих строках (иногда отличаются только последней буквой) и со стандартным bsearch.

Ну как бы дин. скриптовым языкам низкоуровневые оптимизации тоже не чужды :) Тем более сейчас качественные jit движки.

двоичный поиск с bsearch и strcmp

накуа????

если у вас строка не длиннее 8 символов, обратите её в 8байтовое целое число. strcmp - это довольно медленная функция, мелкие строки проще превращать в число так:

const uint64_t foo(char * text, int len)
{
   uint out=0; 
   while(len--)out=(out<<8)+(*text);
   return out;
}

 
uint64_t array[N]={foo("bar", 3), foo("ololo", 5), ...};
...
ascending_sort(array);
...
int hash(char * text, int len)
{
   int min=0, max=N;
   uint64_t key=foo(text, len);
   while(min<max){
      int i=(max+min)>>1;
      if(array[i]==key)return i;
      if(array[i]>key)max=i; else min=i+1;
   }
   return NOTFOUND;
}

вызов bsearch сам по себе на коротких строках тяжелее сравнения в лоб двух чисел раз в 10. strcmp - в 20-30 раз.

> 1) reordered binary search is better than ordinary in all engines. Cache-misses in js has pronounced effect.

in -> on, has -> have

2) typed array is efficient only on ff4 and only S32, F32 has big fail in random access. I'll investigate varios typed arrays later.

-> F32 fails on random access scenarios, varios -> various

3) great advantage of solid arrays in JSC(safari5). ff4 has this optimization too but it doesnt works. In v8 holed is slightly faster.

great -> The great, arrays -> arrays is, it doesnt works -> it doesn't work

После holed нужно существительное, если holed - это что-то вроде «дырявый/дырочный/с дырками»

Только идиоты оптимизируют что-то без цели и без надобности. Школьник? Или уже первокурсник?

> in -> on
with же

great -> The great, arrays -> arrays is

не согласен

Однако удачно подобранная хеш-функция вообще обойдется без бранчей. А bsearch в свою очередь наверняка сфейлится в предсказателе переходов. Со всеми вытекающими из этого неприятностями на конвейере.

> обойдется без бранчей

И без обращений ко вспомогательным таблицам, естественно.

> > in -> on

with же

Нет, всё-таки on: «The service is running on Linux»

> great -> The great, arrays -> arrays is

не согласен

Приведённые варианты исправляют часть очевидных грамматических ошибок. С точки зрения семантики - да, лучше не стало.

Уже посоветовали пронумеровать.

А вообще интересно рассмотреть гипотетическую задачу.

Допустим, есть 64 коротких строки и есть необратимая хэш-функция на множество 0-63, дающая коллизии. Нельзя ли добавить по ведру какой-то особой «соли» к исходным строкам, чтобы коллизии исчезли и все значения ровнехонько и однозначно уложились в интервал 0-63?

Может, кто шарит в теме - ответит утвердительно или же расскажет, почему такое в принципе не возможно.

int hash(char * text, int len) 
{
   int min=0, max=N, i;
   uint64_t key=foo(text, len);
   while(min<max)
   {
      i=(max+min)>>1;
      if(array[i]==key)break;
      max=array[i]>key ? i:max; 
      min=array[i]>key ? min:i+1;
   }
   return min<max ? i : NOTFOUND;
}

на куче архитектур ветвлений не будет: вместо них будет условный mov.

вообще возможно, но задача NP-полная

Что здесь делает этот бред под названием hash()?

читай кормена на предмет идеального хеширования

>>задача NP-полная

На глазок прикинул?

>>читай кормена на предмет идеального хеширования

Спасибо, я думал, что кто-то это уже сделал до меня.

Если интересно:

real    0m0.480s # bsearch
real    0m0.378s # ручной двоичный поиск
real    0m0.143s # хэш gperf

>Есть строка из 3-8 латинских строчных букв

Правильно ли я понял, что количество комбинаций уже ограничено 26 символами? то есть 5 бит, то есть один байт у тебя уже содержит 1.5 (ну так вот грубо скажем) первых байта.

Один символ можно закодировать 5 битами, да.

это уже кривизна компилятора. cmov всегда быстрее jmp.

посмотрел вывод обждампа - да,cmovов нету даже с -O3. уроды.

gcc вообще кривой код генерирует. жуть какую-то. зачем его так сломали?

У меня cmov на месте:

$ gcc -march=i586 -O2 -S -o bin5.s bin.c
$ gcc -march=i686 -O2 -S -o bin6.s bin.c
$ diff bin?.s
95c95,96
<       testl %eax,%eax
---
>       movl %eax,%edx
>       testl %edx,%edx
101,110c102,108
<       testl %eax,%eax
<       jge .L146
<       incl %ebx
<       movl %ebx,-4(%ebp)
<       jmp .L112
<       .p2align 4,,7
< .L146:
<       movl %ebx,%edi
< .L112:
<       cmpl %edi,-4(%ebp)
---
>       leal 1(%ebx),%eax
>       cmpl $-1,%edx
>       cmovg -4(%ebp),%eax
>       movl %eax,-4(%ebp)
>       testl %edx,%edx
>       cmovge %ebx,%edi
>       cmpl %edi,%eax

у меня не генерирует ни одной. gcc 4.4.3

погуглил, и оказалось что cmov на 4х пнях просто сделан через жопу http://ondioline.org/mail/cmov-a-bad-idea-on-out-of-order-cpus

gcc, впрочем, всё равно генерит жуткий код 1 64битная(key) и 3 32битных(min max i) переменных умещаются в 5 регистров. на кой юх он в память ломится?

>Один символ можно закодировать 5 битами, да.

(извиняюсь, что отвечаю так долго)

Это я к чему клоню всё, что твое сообщение можно сжать до фактических 5 байт (учтем еще, что длина строки может быть переменной, оставшееся добиваем нулями), взяв хотя бы индекс буквы в алфавите. Если ты обрабатываешь свои строки потоком, то уже можешь получить «хэш» из 5 байт (сразу «сжимая» данные налету, отбрасывая лишние биты). Из 5 байт посчитать 1 уже проще. Ну а дальше попробовать тот же CRC поверх прогнать, например. Таким образом, ты уже изменил исходную строку, получив некий хэш, а потом произвел еще одно преобразование.

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