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

[Igors]

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

Ага, в ход пошли автоматы/пулеметы. Не навязываю своего мнения, но Вас определенно "заносит в абстракцию"   Лучше смотреть с точки зрения прикладной задачи. Ну напр чего это Вам так остро нужен поиск по имени (строке)? Не лучше ли работать по ID - тогда можно спрыгнуть на индекс - быстрее любой мапы. Мне кажется Вы уперлись в слишком узкое место - QHash вполне хорош, ну и чего мудрить? Поехали дальше, прикладная задача предоставляет гораздо больший простор для фантазии и той же оптимизации чем абстрактные схемы которые, как правило, хорошо известны, и которые Вы упорно хотите обобщить . Вот примерчик из моей практики http://www.prog.org.ru/index.php?topic=21228.msg145940#msg145940

[alexis031182]

Ага, в ход пошли автоматы/пулеметы. Не навязываю своего мнения, но Вас определенно "заносит в абстракцию"   Лучше смотреть с точки зрения прикладной задачи.

Я бы и не задумывался, если бы не условия вполне себе прикладной задачи.

Ну напр чего это Вам так остро нужен поиск по имени (строке)?

А как иначе, если на входе она и только она?

Не лучше ли работать по ID - тогда можно спрыгнуть на индекс - быстрее любой мапы.

"ID" имеется ввиду тип? Да я во сне уже вижу, как я тип на входе получил и прыгаю от радости. К сожалению, только строка.

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

Ну как чего? Условия задачи говорят о том, что поиск будет выполняться зверски часто. 10000 сетевых запросов в секунду как минимум должно обрабатываться. И получение из фабрики объекта, ассоциированного со строкой, полученной в свою очередь по HTTP-протоколу, есть тот код, который существенно влияет на весь процесс. Другие подзадачи, которые входят в это же, критичное по времени исполнения место, я точно также буду "долбить" до потери пульса (надеюсь, что только своего). Пока же остановился на этой задаче.

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

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

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

Вот примерчик из моей практики http://www.prog.org.ru/index.php?topic=21228.msg145940#msg145940

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

[Igors]

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

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

- получили строку, первый символ напр "а", это число - индекс в таблице. Перешли по этому индексу (без всяких поисков) просто table[int('a')]

- следующий символ напр "b", опять прыгнули по индексу, как бы table[int('a')][int('b')]
...
в итоге извлекли что-то table[int('a')][int('b')][int('c')]. Конечно это будет быстрее любого поиска, но надо как-то намутить все эти таблицы. Это не так сложно как кажется, и памяти они сожрут хоть и прилично но не вагон. Хотите этим заниматься - дело Ваше.

"ID" имеется ввиду тип? Да я во сне уже вижу, как я тип на входе получил и прыгаю от радости. К сожалению, только строка.

ID - просто уникальное число. Ну допустим на входе только строка - но при помещении ее в мапу никто не мешает присвоить ей ID и это ID вернуть, И во всех последующих операциях использовать это число которое есть прямой индекс в массиве(ах).

[alexis031182]

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

- получили строку, первый символ напр "а", это число - индекс в таблице. Перешли по этому индексу (без всяких поисков) просто table[int('a')]

- следующий символ напр "b", опять прыгнули по индексу, как бы table[int('a')][int('b')]
...
в итоге извлекли что-то table[int('a')][int('b')][int('c')].

По сути, я взял идею паттерна композит, который представляет из себя дерево элементов. Просто у меня каждый элемент такого дерева - символ (char). Да, Вы описали похоже.

Конечно это будет быстрее любого поиска, но надо как-то намутить все эти таблицы.

А чего их "мутить"? По моему вполне просто любой длины строка вписывается в такое дерево. "Двигаясь" по его веткам, можно легко восстановить строку. При этом, если символы одинаковы на одном порядковом уровне, то хранятся в контейнере они в единичном экземпляре. Но это само собой понятно.

Это не так сложно как кажется, и памяти они сожрут хоть и прилично но не вагон.

"sizeof(letter)", где letter является элементом контейнера и содержит только char, плюс список указателей на такие же, но дочерние letter'ы. Значение же, которое является искомым, содержится лишь на самом верху в иерархии дерева. Поэтому не такой уж и большой перерасход.

Хотите этим заниматься - дело Ваше.

Есть вариант лучше? Или Вы имеете в виду, что не стоит овчинка выделки? Тест показал, что стоит. Даже если бы я выиграл здесь 1 мс, то и тогда стоило бы. Это важно, потому что критично именно в той части задачи, о которой я сказал выше. В любом другом случае я конечно бы озадачился вопросом целесообразности столь длительных потугов на поиск наиболее оптимального решения.

ID - просто уникальное число. Ну допустим на входе только строка - но при помещении ее в мапу никто не мешает присвоить ей ID и это ID вернуть, И во всех последующих операциях использовать это число которое есть прямой индекс в массиве(ах).

Это так, но при условии, что не потребуется снова вычислять ID. А почему его потребуется вычислять? Просто потому, что от сетевого клиента придёт строка, содержащая команду, и из которой и надо будет снова вычислить этот ID. Другими словами, ID, как бы я его не использовал, время жизни его ограничено одним сетевым запросом одного из сетевых клиентов. Новый запрос - новое вычисление ID, хотя по сути, оно практически одно и то же и может иметь лишь значение в пределах известных заранее вариантов (для простоты примера пока исключим возможность отсылки заведомо ложных команд вредителей).

[DmitryM]

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

- получили строку, первый символ напр "а", это число - индекс в таблице. Перешли по этому индексу (без всяких поисков) просто table[int('a')]

- следующий символ напр "b", опять прыгнули по индексу, как бы table[int('a')][int('b')]
...
в итоге извлекли что-то table[int('a')][int('b')][int('c')].

По сути, я взял идею паттерна композит, который представляет из себя дерево элементов. Просто у меня каждый элемент такого дерева - символ (char). Да, Вы описали похоже.

Конечно это будет быстрее любого поиска, но надо как-то намутить все эти таблицы.

А чего их "мутить"? По моему вполне просто любой длины строка вписывается в такое дерево. "Двигаясь" по его веткам, можно легко восстановить строку. При этом, если символы одинаковы на одном порядковом уровне, то хранятся в контейнере они в единичном экземпляре. Но это само собой понятно.

Плохо вечером соображаю, вы тут префиксное дерево изобретаете?

[alexis031182]

Плохо вечером соображаю, вы тут префиксное дерево изобретаете?

Ага Спасибо, теперь буду знать, что это trie (странное написание, если tree - дерево; хотя гугл даёт перевод для trie как "синтаксическое дерево").

[alexis031182]

DmitryM, какой реализацией пользуешься? Можешь порекомендовать? Интересует именно скорость поиска элемента, остальное вторично.

[Igors]

А чего их "мутить"? По моему вполне просто любой длины строка вписывается в такое дерево. "Двигаясь" по его веткам, можно легко восстановить строку.

Разница в том что Вы тратите время на цикл for

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

У человека не знакомого с задачей это вызывает большие сомнения. Что это за обработка если ее время соразмеримо с обращением в хеш по ключу? Не теряется ли больше времени напр на перегонку QString в char *? Или просто на создание QString? Впрочем Вам виднее

[DmitryM]

Разница в том что Вы тратите время на цикл for

В случае с QMap тратиться время на сравнение ключей.
В случае с QHash тратится время на вычисления ключа.

[alexis031182]

Разница в том что Вы тратите время на цикл for

DmitryM привёл ссылку на статью, где перечисляются методы по оптимизации подобных деревьев. Они могут значительно сократить количество итераций в циклах (зависит конечно от содержимого ключей, но в моей задаче это как раз присутствует). Попытаюсь реализовать.

У человека не знакомого с задачей это вызывает большие сомнения. Что это за обработка если ее время соразмеримо с обращением в хеш по ключу?

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

Конечно, если бы это было, например, 100 - 1000 запросов, то намерения мои были бы не оправданы. Но временные потери становятся явно ощутимы при многократном увеличении одновременно поступающих сетевых запросов. Для реализации хотя бы просто поддержки такого количества сетевых соединений (не говоря уже о передачи данных) пришлось отказаться от того же QTcpServer, заменив его epoll'ом (меня, всё же, сервер интересует именно под Linux).

Только не говорите, что я снова ударился в специфику. У меня конкретная задача, и как мне обозначить её условия по другому, то есть не переходя к её специфике, я не представляю.

Не теряется ли больше времени напр на перегонку QString в char *? Или просто на создание QString? Впрочем Вам виднее

QString уже ликвидирован во многих частях кода. И будет убран полностью постепенно. На входе из сети я получаю char*. Именно его я называл "строкой".

[Igors]

DmitryM привёл ссылку на статью, где перечисляются методы по оптимизации подобных деревьев. Они могут значительно сократить количество итераций в циклах (зависит конечно от содержимого ключей, но в моей задаче это как раз присутствует). Попытаюсь реализовать.

Ну и реализуйте автоматом (таблицей) если это так критично

пришлось отказаться от того же QTcpServer

Это к слову (оффтоп), но возможно замена QMutex на атомарный лок (а еще лучше tbb::spin_mutex) будет "само то". 

[alexis031182]

Ну и реализуйте автоматом (таблицей) если это так критично

Это какое-то альтернативное дереву решение? Можно подробнее?

Это к слову (оффтоп), но возможно замена QMutex на атомарный лок (а еще лучше tbb::spin_mutex) будет "само то". 

Спасибо. Мне интересна в общем-то любая замена для кьют-классов, если она будет гарантированно быстрее, и конечно, если эта часть кода выполняется в обработчике сетевых запросов. Но так как мне сразу всё не охватить, я разбил оптимизацию на подзадачи. Но всё же к тредам, думаю, вернусь очень скоро.

С dev-решениями от Intel ещё не приходилось работать. Хотел у них для Linux профилировщик бесплатно заполучить, отправил кучу запросов с их сайта, но что-то нет ответа. Помню, когда-то это прокатило, прислали письмо со ссылкой на программу, но не сохранилась её копия. Жаль.

[DmitryM]

Это к слову (оффтоп), но возможно замена QMutex на атомарный лок (а еще лучше tbb::spin_mutex) будет "само то". 

В qmutex_unix.cpp, там

Код

C++ (Qt)
#elif defined(Q_OS_LINUX)
# include <linux/futex.h>
# include <sys/syscall.h>
# include <unistd.h>
# include <QtCore/qelapsedtimer.h>
#endif
 

Так что QMutex в Linux и так быстрый.
Так что

[Igors]

Это какое-то альтернативное дереву решение? Можно подробнее?

Ну то самое что я писал. Напр первый шаг (первый символ строки) - имея на руках все возможные строки Вы знаете диапазон, пусть 'a'..'t'. Делаете таблицу указателей на ноды, для того чтобы прыгать на нужный элемент сразу (без for), индекс получаете просто отняв 'a' (минимальный возможный) от первого символа. Если индекс < 0 или больше размера таблицы или указатель ноль - ну значит такого нет. Потом все то же для второго символа (уже используя данные нода на который перешли). На первый взгляд это ужасно - море таблиц, но на деле число вариантов невелико. 

Спасибо. Мне интересна в общем-то любая замена для кьют-классов, если она будет гарантированно быстрее, и конечно, если эта часть кода выполняется в обработчике сетевых запросов. Но так как мне сразу всё не охватить, я разбил оптимизацию на подзадачи. Но всё же к тредам, думаю, вернусь очень скоро.

Сделайте просто контейнер и читайте/пишите его под защитой QMutex. Или просто читайте - только зациклите защищенное чтение. Сравните время на 1 и напр 4 нитках. Этот тест займет полчаса но, во всяком случае на posix, возможно Вы будете удивлены (не скажу что "приятно удивлены")

[alexis031182]

Ну то самое что я писал. Напр первый шаг (первый символ строки) - имея на руках все возможные строки Вы знаете диапазон, пусть 'a'..'t'. Делаете таблицу указателей на ноды, для того чтобы прыгать на нужный элемент сразу (без for), индекс получаете просто отняв 'a' (минимальный возможный) от первого символа. Если индекс < 0 или больше размера таблицы или указатель ноль - ну значит такого нет. Потом все то же для второго символа (уже используя данные нода на который перешли). На первый взгляд это ужасно - море таблиц, но на деле число вариантов невелико. 

То есть использовать не QList для хранения нодов, а массив, индексами которого будут являться порядковые номера букв? Очень интересно. Спасибо.

Сделайте просто контейнер и читайте/пишите его под защитой QMutex. Или просто читайте - только зациклите защищенное чтение. Сравните время на 1 и напр 4 нитках. Этот тест займет полчаса но, во всяком случае на posix, возможно Вы будете удивлены (не скажу что "приятно удивлены")

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