Я пытаюсь найти лучшую структуру данных для решения этой проблемы. Я реализую хранилище ключевых значений с ключами, которые являются строками. Значения добавляются часто и обычно просматриваются только 1 или 2 раза. Первоначально я использовал std::map, но обнаружил, что производительность неоптимальна, так как накладные расходы на добавление ключей и перебалансировку красно-черного дерева затмевают уменьшение времени поиска значения. В настоящее время я использую модифицированный односвязный список. Он использует структуру, которая содержит строку c (const char *), длину в байтах и сохраненное значение. Когда я хочу найти значение с помощью ключа, я перебираю список и сравниваю размер ключей, если они совпадают, я использую memcmp, чтобы проверить, идентичны ли строки. Если они идентичны, я возвращаю значение. Я могу добиться примерно в 10 раз большей производительности, используя этот метод по сравнению с std::map. Однако мне нужно сделать его примерно в 2 раза эффективнее. Может ли кто-нибудь порекомендовать лучший тип структуры данных для этой проблемы?
Какую структуру данных следует использовать
Ответы (4)
Трудно найти быстрое решение, не зная реальной проблемы. В частности, насколько велик ваш набор данных, где хранятся настоящие данные (хранятся ли они в контейнере или где-то еще?). Какие еще операции необходимо выполнить с контейнером? Вам нужно удалить элементы из контейнера?
В качестве комментария к одному из других вопросов вы заявляете, что ключи необходимо скопировать в std::unordered_map... если ключи уже хранятся где-то еще, я бы посоветовал вам использовать карту, но не копировать строки. Используйте указатели в качестве ключей и пользовательский компаратор для разыменования и работы с результатом:
// Assuming that the data is stored in std::string somewhere else
struct custom_compare {
bool operator()( std::string* lhs, std::string* rhs ) const {
return lhs!=rhs && (lhs->size() < rhs->size() || lhs->compare( *rhs ) < 0);
}
};
std::map< std::string*, data, custom_compare > mymap;
Сохранение указателей вместо фактических строк избавило бы от копирования. Пользовательский компаратор в основном так же быстр, как тот, который вы реализовали в списке, и дерево будет балансировать содержимое, позволяя выполнять поиск O (log n). В зависимости от размера набора (если элементов много) это будет улучшением по сравнению с линейным поиском, а если размер мал, то линейный поиск будет лучше.
Кроме того, в зависимости от разнообразия данных вы можете следовать линейному поиску, но разделить пространство поиска в зависимости от некоторых критериев, которые быстро вычисляются и в то же время делят множество как можно более равномерно. Например, вы можете использовать линейный поиск, но вместо одного списка сохраните разные списки в зависимости от длины ключа.
Если критерий фактически основан на содержимом строки (буквы, а не размер), то вы приближаетесь к определению дерева. Если у вас есть библиотека, в которой она уже реализована, или вы готовы потратить на это время, то trie, вероятно, будет одним из самых быстрых контейнеров для такого типа поиска, поскольку он преобразует переменную size из числа элементы к длине строк.
std::vector должен выполняться быстрее, чем связанный список, а также быстрее push_back(), так как в большинстве случаев выделение памяти не требуется.
Он у вас есть как один из ваших тегов... почему бы не использовать Trie? Вставки должны быть быстрыми, использование памяти может снизиться из-за перекрытия символов, а поиск должен быть быстрым.
Может быть, какая-то хеш-таблица? Использование хорошего алгоритма хеширования для ваших ключей значительно ускорит время поиска. Ваше время вставки будет немного замедлено, но, надеюсь, не сильно, если ваша хэш-функция хороша.
std::map (rbtree) на std::unordered_map (хэш-таблица) и протестировать. Я был очень доволен производительностью std::unordered_map в моем коде.
- person Blastfurnace; 10.02.2011
