Какую структуру данных следует использовать

Question

Я пытаюсь выяснить, какая структура данных используется для этой проблемы. Я реализую хранилище ключей с ключами, которые являются строками. Значения часто добавляются и обычно получаются только 1 или 2 раза. Первоначально я использовал , но я обнаружил, что производительность является неоптимальной, поскольку накладные расходы на добавление ключей и перебалансирование красно-черного дерева затмили уменьшение времени для поиска значения. В настоящее время я использую модифицированный одиночный связанный список. Он использует структуру, содержащую строку c (const char *), длину в байтах и ​​сохраненное значение. Когда я хочу найти значение с помощью ключа, я перебираю список и сравниваю размер ключей, если они совпадают, я использую memcmp, чтобы проверить, идентичны ли строки. Если они идентичны, я возвращаю значение. Я способ мог добиться примерно 10-кратной производительности с помощью этого метода по сравнению с std::map. Тем не менее, мне нужно сделать это примерно в 2 раза. Может ли кто-нибудь рекомендовать лучший тип структуры данных для этой проблемы?

Answer 1

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

В качестве комментария к одному из других вопросов вы указываете, что ключи должны быть скопированы в 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. Если вы получите библиотеку, которая уже реализует ее, или вы готовы потратить время, необходимое для этого, trie, вероятно, станет одним из самых быстрых контейнеров для этого типа поиска, поскольку он преобразует переменную «размер» из числа элементов к длине строк.

Answer 2

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

Answer 3

std::vector должен быть быстрее итерации по сравнению с связанным списком и быстрее на push_back(), так как большую часть времени не требуется выделение памяти.

Answer 4

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