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

[alexis031182]

Добрый день.

Имеется реализация ассоциативного контейнера на базе std::vector<std::pair<Key, Value>>, предложенная Александреску. Условия использования таковы, что скорость изменения контейнера (добавление, удаление элементов) абсолютно не критична. Критична скорость поиска элемента. Также, обязательна поддержка уникальности ключей.

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

А может быть имеются собственные наработки? В таком случае, если позволяется и/или имеется возможность, поделитесь идеей или просто основными моментами реализации.

Спасибо.

З.Ы. На всякий случай во вложении AssocVector

[m_ax]

А чем std::map не устраивает как ассоциативный контейнер?
Скорость поиска там, как Log(n). (n - число элементов)
http://www.cplusplus.com/reference/stl/map/ 

[alexis031182]

AssocVector ищет со скоростью O(n)

[mutineer]

AssocVector ищет со скоростью O(n)

Так это медленнее, чем логарифм. Или скорость критична в том смысле, что чем медленнее, тем лучше?

[Igors]

AssocVector ищет со скоростью O(n)

Нет, там дело сводится к std::lower_bound, а это тот же логарифм.

Вообще логарифм поиска - совсем неплохая скорость. Быстрее хеш (если дать побольше корзин). Но тут выплывает нужно ли последовательное итерирование? Если необходимо четко выдавать элементы по возрастанию - тогда, на мой взгляд, огород себя не оправдывает - проще std::map или std::set.

Однако есть интересный частный случай - можно выдавать "в порядке корзин", напр
bin1 - values 0.0....0.1
bin2 - values 0.1....0.2
и.т.д

Тогда можно сделать и поиск пошустрее и вставка очень быстрая и расход памяти ноль 

[alexis031182]

Так это медленнее, чем логарифм. Или скорость критична в том смысле, что чем медленнее, тем лучше?

Ошибся. O(n) у него скорость изменения, то есть медленнее, нежели чем у map'а.

Нужен быстрый поиск элемента.

Вот нашёл хоть какой-то перевод:

Значительное усовершенствование заключается в следующем: тип std::map изменен и стал более эффективным. Мэтт Остерн (Matt Austern, 2000) выяснил, что стандартные ассоциативные контейнеры имеют более узкую область применения, чем принято думать. В частности, упорядоченный вектор в сочетании с алгоритмами бинарного поиска (например, алгоритмом std::lower_bound) может оказаться намного эффективнее, чем ассоциативный контейнер. Это происходит, когда количество обращений к его элементам намного превышает количество вставок. Итак, следует внимательно изучить ситуации, в которых обычно применяются объекты двойного диспетчера. Чаще всего двойной диспетчер представляет собой структуру, в которую информация редко записывается, но из которой часто считывается. Обычно программа лишь однажды устанавливает обратные вызовы, а затем очень часто использует диспетчер. Это хорошо согласуется с использованием механизма виртуальных функций, который дополняется двойным диспетчером. Решение о том, какие функции являются виртуальными, а какие нет, принимается на этапе компиляции.

На первый взгляд упорядоченный вектор нам совершенно не подходит. Операции вставки и удаления элементов такого вектора выполняются за линейное время, и двойной диспетчер никак не может повлиять на быстродействие этих операций. Зато этот вектор позволяет повысить скорость просмотра элемента примерно в два раза и намного снизить объем рабочего множества. Эти свойства очень полезны для двойной диспетчеризации.

Библиотека Loki предусматривает использование упорядоченных векторов, определяя шаблонный класс Assocvector, который может заменять собой класс std::map (он содержит те же самые функции-члены), реализованный на основе класса std::vector. Класс Assocvector отличается от класса std::map функциями erase (функции Assocvector::erase аннулируют все итераторы внутри объекта). Кроме того, функции-члены insert и erase усложнены (выполняя операции вставки и удаления за линейное, а не постоянное время). Поскольку класс Accosvector совместим с классом std::map, для описания структуры, содержащейся в двойном диспетчере, мы будем также использовать термин ассоциативный массив (тар).

[alexis031182]

Нет, там дело сводится к std::lower_bound, а это тот же логарифм.

Вообще логарифм поиска - совсем неплохая скорость. Быстрее хеш (если дать побольше корзин). Но тут выплывает нужно ли последовательное итерирование? Если необходимо четко выдавать элементы по возрастанию - тогда, на мой взгляд, огород себя не оправдывает - проще std::map или std::set.

Нужен поиск произвольного элемента по ключу для фабрики.

Однако есть интересный частный случай - можно выдавать "в порядке корзин", напр
bin1 - values 0.0....0.1
bin2 - values 0.1....0.2
и.т.д

Тогда можно сделать и поиск пошустрее и вставка очень быстрая и расход памяти ноль 

Здесь можно более понятно? Или быть может есть ссылка на что почитать

[alexis031182]

Здесь можно более понятно? Или быть может есть ссылка на что почитать

Принцип QHash с reserve имеется ввиду?

[alexis031182]

Сделал тест на поиск 100000 элементов в 100000 контейнере, представлявшем в свою очередь три варианта: AssocVector, QHash и std:map. Усреднённый результат нескольких прогонов:

QHash - 30 ms.
AssocVector - 38 ms.
std::map - 48 ms.

[Igors]

Мэтт Остерн правильно пишет, но не все - массив часто требует намного меньше памяти.

Нужен поиск произвольного элемента по ключу для фабрики.

Здесь просто QHash. Пусть ключ - строка, число элементов напр 100. Тогда на поиске (грубо)

- хеш = 1 вычисление хеш-ключа + 1 сравнение
- мап = 6-8 сравнений

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

[alexis031182]

Спасибо. Получается, QHash - лучший вариант пока. Интересно, а если попробовать применить несколько более быстрый алгоритм для вычисления хэша, нежели тот, что использует QHash?.. Я не проводил сравнения ещё, но давно хотелось сравнить его с superfasthash. Вот и повод. Просто помудрить здесь чего-нибудь эксперимента ради...

[Igors]

Спасибо. Получается, QHash - лучший вариант пока. Интересно, а если попробовать применить несколько более быстрый алгоритм для вычисления хэша, нежели тот, что использует QHash?.. Я не проводил сравнения ещё, но давно хотелось сравнить его с superfasthash. Вот и повод. Просто помудрить здесь чего-нибудь эксперимента ради...

Можно, но там много не отбить. QHash сохраняет хеш-ключ для каждого элемента, т.е. считается только подаваемый. Если строки не слишком длинные - игра свеч не стоит.

Не нужно что-то оптимизировать "не будучи вынужденным". Др словами сначала надо иметь работающую конструкцию, и затем уже искать узкие места и улучшать. А иначе "здесь гоняемся за микронами" а в др месте тратим время вагонами 

[alexis031182]

Можно, но там много не отбить. QHash сохраняет хеш-ключ для каждого элемента, т.е. считается только подаваемый. Если строки не слишком длинные - игра свеч не стоит.

Попробовал, так и есть - никакой разницы

Не нужно что-то оптимизировать "не будучи вынужденным". Др словами сначала надо иметь работающую конструкцию, и затем уже искать узкие места и улучшать. А иначе "здесь гоняемся за микронами" а в др месте тратим время вагонами 

У меня в фабрике (пока ещё без пула/кеша) вроде всё на шаблонах, там больше вроде нечему быть затратным, всё в compile-time идёт, окромя конечно операции создания фабрикой запрашиваемого объекта (единственный new). И вот одним узким местом по сути является поиск класса объекта по ключу.

Надо как-то строку умудриться в шаблон прикрутить. То есть превратить её в тип. В Интернете есть примеры, попробую покопаться.

[alexis031182]

Надо как-то строку умудриться в шаблон прикрутить. То есть превратить её в тип. В Интернете есть примеры, попробую покопаться.

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

Попробовал соорудить самопальный контейнер, где ключами выступают исключительно строки (оно мне для фабрики, в принципе, так и надо будет). В рассуждениях исходил из того, что ключи по значениям своим довольно близки. Например: "AWebRequestGet", "AWebRequestPost", и т.п. Подумал, что имеет смысл сравнивать посимвольно, а в контейнере хранить элементы в виде дерева символов. Таким образом, получилось добиться ускорения чуть более 10 мс по сравнению с QHash в том же тесте и с теми же условиями, что написал ранее:

Сделал тест на поиск 100000 элементов в 100000 контейнере, представлявшем в свою очередь три варианта: AssocVector, QHash и std:map. Усреднённый результат нескольких прогонов:

QHash - 30 ms.
AssocVector - 38 ms.
std::map - 48 ms.

Новый контейнер делает за 15-20 мс.

Код во вложении. Не оптимизирован, имеет варнинги, публикую просто для обсуждения идеи.

Пример использования:

Код

C++ (Qt)
#include "acompositecontainer.h"
 
AComposite::Container<QString> container;
container.insert("tra", QString("tra-ta-ta"));
qDebug() << container.value("tra");
 

[alexis031182]

Если я не ошибся, и алгоритм, реализованный этим кодом стоящий, то можно его превратить в настоящий read only контейнер, регистрацию элементов выполнять в compile-time. Для фабрики будет то, что нужно, т.к. классы как правило регистрируются при старте приложения и пользуются в неизменном виде до окончания сессии его работы. Таким образом, получится мгновенная вставка и довольно быстрый lookup. Такая задумка.