[РЕШЕНО] Ассоциативный контейнер для быстрого lookup'а

[alexis031182]

Во я и спрашиваю с каким стандартным QHash Вы сравниваете. Если QHash <const char *, ...>, то он сравнивает адрес строки, что быстрее хотя и не то что нужно.

Стоп. Да, именно с QHash<const char *, ...>. То есть он не вычисляет хэш для "const char *"?! Едрить

Вычисление ключа я бы сделал так

Код

C++ (Qt)
uint32 hash( const char * str )
{
 if (!str) return 0;
 uint32 val = 0;
 char * dst = (char *) &val;
 size_t i = 0;
 while (*str) {
  dst[i] ^= *str;
  ++str;
  i = (i + 1) % sizeof(val); 
 }
 return val;
}

Я код вычисления хэша взял из самого QHash, чтобы уж совсем одинаково было. Так-то да, его хэш не самый быстрый.

[alexis031182]

Вот я и спрашиваю с каким стандартным QHash Вы сравниваете. Если QHash <const char *, ...>, то он сравнивает адрес строки, что быстрее хотя и не то что нужно.
...

А почему "не то что нужно"?

А вообще, сравнение адреса строки вместо хэша - это корректно? Я не пойму, как это так...

[alexis031182]

Смотрю в исходниках QHash функцию value() - та, которая получает значение из контейнера по ключу. Она вызывает findNode(), в которой производится безусловное вычисление хэша ключа. То есть вычисление для const char* в QHash выполняется.

[Igors]

Смотрю в исходниках QHash функцию value() - та, которая получает значение из контейнера по ключу. Она вызывает findNode(), в которой производится безусловное вычисление хэша ключа. То есть вычисление для const char* в QHash выполняется.

Да, так оно просто адрес подставляет как ключ

Код

C++ (Qt)
const char * str = "abcdefghi";
 
QHash <const char *, int> hash;
hash[str] = 1;
 
char buf[256];
strcpy(buf, str);
qDebug() << hash.contains(buf);
 

[alexis031182]

Я просто изучаю исходники QHash и вижу, что там при одном условии может использоваться выравнивание в памяти для Node, где Node - это структура, являющаяся элементом контейнера и содержащая ключ, хэш ключа и значение элемента.

Однако функция выравнивания qMallocAligned() вызывается только если __alignof__(Node) возвратит число, большее 8 байт. Глянув на свой класс Node (он аналогичен), я получил размер в 4 байта. Другими словами, выравнивание в памяти - это не то, что я ищу. Вот ведь вешалка...

Походу я не прав. Для того чтобы определить вызывать qMallocAligned() или qMalloc() в QHash используется конструкция QMAX(sizeof(Node), __alignof__(Node)). А sizeof для моего класса элемента выдаёт 16. А поскольку мой Node аналогичен Node QHash'а, то можно предположить, что выравнивание в памяти элементов в QHash производится.

Очевидно, что сам код вычисления хэша ключа не является той причиной, что приводит к различной скорости lookup'а у моего хэша и QHash, т.к. алгоритм один и тот же. Очевидно, что причиной этому не может являться и структура построения классов обоих видов контейнеров, т.к. она в общем-то одинакова.

Из оставшегося...

Предварительное резервирование элементов: QHash выделяет заведомо больше памяти, чем реально нужно. Влияет ли это как-то на lookup? Вряд ли.

Выравнивание в памяти: а вот здесь наверное может быть. Но как так - тоже непонятно...

Других различий у QHash и приведённого мною кода вроде нет.

[Igors]

Очевидно, что сам код вычисления хэша ключа не является той причиной, что приводит к различной скорости lookup'а у моего хэша и QHash, т.к. алгоритм один и тот же.

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

[alexis031182]

Да, так оно просто адрес подставляет как ключ

Код

C++ (Qt)
const char * str = "abcdefghi";
 
QHash <const char *, int> hash;
hash[str] = 1;
 
char buf[256];
strcpy(buf, str);
qDebug() << hash.contains(buf);
 

Непонятно. Вот QHash:

Код

C++ (Qt)
template <class Key, class T>
Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
{
    return *findNode(akey) != e;
}
 
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
                                                                            uint *ahp) const
{
    Node **node;
    uint h = qHash(akey); //Здесь безусловное вычисление ключа.
    //Но как это согласуется с приведённым Вами кодом?..
    //Тогда бы он "false" не показывал
 
    if (d->numBuckets) {
        node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
        Q_ASSERT(*node == e || (*node)->next);
        while (*node != e && !(*node)->same_key(h, akey))
            node = &(*node)->next;
    } else {
        node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
    }
    if (ahp)
        *ahp = h;
    return node;
}

[alexis031182]

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

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

[Igors]

Код

C++ (Qt)
    uint h = qHash(akey); //Здесь безусловное вычисление ключа.
    //Но как это согласуется с приведённым Вами кодом?..
    //Тогда бы он "false" не показывал
}

Так адрес buf другой (это содержимое == str). Он просто использует адрес (как void *). Насколько я понимаю Вас это не устроит

[alexis031182]

Так адрес buf другой (это содержимое == str).

Да, я это понимаю.

Он просто использует адрес (как void *).

Хотел найти в коде QHash, как у него это выходит - сравнение по адресу, а не по хэшу, если в исходниках стоит вызов qHash() без всяких условий. Может у меня исходники левые Уже не знаю, что и думать...

Насколько я понимаю Вас это не устроит

А насколько это может быть чревато? Скорость очень заманчива. Самый быстрый алгоритм вычисления хэша не даст такой скорости как простое сравнение адресов. И я собираюсь использовать именно const char* в виде ключей.

[Igors]

Кого-то из нас переклинило на простой вещи 

Хотел найти в коде QHash, как у него это выходит - сравнение по адресу, а не по хэшу, если в исходниках стоит вызов qHash() без всяких условий. Может у меня исходники левые Уже не знаю, что и думать...

Просто идите по шагам (step in) и увидите что он вызывает qHash (просто ф-ция без класса) которая присваивает ключу адрес

А насколько это может быть чревато? Скорость очень заманчива. Самый быстрый алгоритм вычисления хэша не даст такой скорости как простое сравнение адресов. И я собираюсь использовать именно const char* в виде ключей.

Для строки которую надо найти - где же Вы возьмете тот самый адрес что сидит в ключе хеша? У Вас только содержимое, по нему и придется искать

[alexis031182]

Кого-то из нас переклинило на простой вещи  

Просто идите по шагам (step in) и увидите что он вызывает qHash (просто ф-ция без класса) которая присваивает ключу адрес

Да, точно! Не подумал это попробовать

Для строки которую надо найти - где же Вы возьмете тот самый адрес что сидит в ключе хеша? У Вас только содержимое, по нему и придется искать

Другими словами QHash с const char* в фабрике я использовать не могу. Так или иначе потребовалось бы использовать какую-нибудь обёртку, вроде QLatin1String, правильно?

Сейчас попробовал QHash с ключом QLatin1String - кошмар! Более 300 мс.

Спасибо большое, Игорь. Очень помогли разобраться

[alexis031182]

Вычисление ключа я бы сделал так

Код

C++ (Qt)
uint32 hash( const char * str )
{
 if (!str) return 0;
 uint32 val = 0;
 char * dst = (char *) &val;
 size_t i = 0;
 while (*str) {
  dst[i] ^= *str;
  ++str;
  i = (i + 1) % sizeof(val); 
 }
 return val;
}

Интересный вариант. По скорости сравним с murmurhash3 и superfasthash. Отличительная особенность - не требуется вычислять размер строки ключа. superfasthash немного быстрее, но требуется размер (strlen). Даже не знаю, на каком варианте остановиться.

Игорь, подскажите пожалуйста, тестировали ли Вы свой вариант на количество коллизий?

[Igors]

Интересный вариант. По скорости сравним с murmurhash3 и superfasthash. Отличительная особенность - не требуется вычислять размер строки ключа. superfasthash немного быстрее, но требуется размер (strlen). Даже не знаю, на каком варианте остановиться.

Ну да, задумка обойтись без strlen, вероятно то на то и выходит

Коллизии (хеш-ключ одинаков, в корзине 2 или более) не тестировал. Считаю что к ним надо относиться философски - ну будет так будет, в конце-концов "nothing is perfect". Можно и автоподстройку сделать - давать различные  QHash::reserve(N) и считать сколько с одинаковым хеш-ключом. Выполняется 1 раз на старте

[alexis031182]

Ну да, задумка обойтись без strlen, вероятно то на то и выходит

Мне Ваш вариант очень импонирует своей лаконичностью. Кратко, удобно: всё необходимое сразу из строки.

Коллизии (хеш-ключ одинаков, в корзине 2 или более) не тестировал. Считаю что к ним надо относиться философски - ну будет так будет, в конце-концов "nothing is perfect".

Согласен. Они (коллизии) есть у всех без исключения хэшей.

Можно и автоподстройку сделать - давать различные QHash::reserve(N) и считать сколько с одинаковым хеш-ключом. Выполняется 1 раз на старте

Дельно. Спасибо. Впрочем, с моими ключами, известными заранее, коллизий нет.