Какой тип контейнера обеспечивает лучшую (среднюю) производительность, чем std :: map?

Question

В следующем примере структура std :: map заполнена 26 значениями из A - Z (для ключа) и 0 - 26 для значения. Время, необходимое (в моей системе) для поиска последней записи (10000000 раз), составляет примерно 250 мс для вектора и 125 мс для карты. (Я скомпилировал, используя режим выпуска, с включенной опцией O3 для g ++ 4.4)

Но если по какой-то странной причине я хотел получить лучшую производительность, чем std :: map, какие структуры данных и функции мне нужно было бы использовать?

Я прошу прощения, если ответ кажется очевидным для вас, но у меня не было большого опыта в критических аспектах программирования на C ++.

#include <ctime>
#include <map>
#include <vector>
#include <iostream>

struct mystruct
{
    char key;
    int value;

    mystruct(char k = 0, int v = 0) : key(k), value(v) { }
};

int find(const std::vector<mystruct>& ref, char key)
{
    for (std::vector<mystruct>::const_iterator i = ref.begin(); i != ref.end(); ++i)
        if (i->key == key) return i->value;

    return -1;
}

int main()
{
    std::map<char, int> mymap;
    std::vector<mystruct> myvec;

    for (int i = 'a'; i < 'a' + 26; ++i)
    {
        mymap[i] = i - 'a';
        myvec.push_back(mystruct(i, i - 'a'));
    }

    int pre = clock();

    for (int i = 0; i < 10000000; ++i)
    {
        find(myvec, 'z');
    }

    std::cout << "linear scan: milli " << clock() - pre << "\n";

    pre = clock();

    for (int i = 0; i < 10000000; ++i)
    {
        mymap['z'];
    }

    std::cout << "map scan: milli " << clock() - pre << "\n";

    return 0;
}

Answer 1

Для вашего примера используйте int value(char x) { return x - 'a'; }

Более обобщенно, поскольку «ключи» являются непрерывными и плотными, используйте массив (или вектор), чтобы гарантировать Θ (1) время доступа.

Если вам не нужно сортировать ключи, используйте unordered_map, что должно обеспечить амортизированное логарифмическое улучшение (т. Е. O (log n) -> O (1)) для большинства операций.

(Иногда, особенно для небольших наборов данных, линейный поиск выполняется быстрее, чем хеш-таблица (unordered_map) / сбалансированные бинарные деревья (карта), потому что в первом алгоритм гораздо проще, что уменьшает скрытую константу в big-O. Профиль, профиль, профиль.)

Answer 2

Если у вас действительно есть значения для всех записей от А до Я, почему бы вам не использовать букву (правильно настроенную) в качестве индекса для вектора?:

std::vector<int> direct_map;
direct_map.resize(26);

for (int i = 'a'; i < 'a' + 26; ++i) 
{
    direct_map[i - 'a']= i - 'a';
}

// ...

int find(const std::vector<int> &direct_map, char key)
{
    int index= key - 'a';
    if (index>=0 && index<direct_map.size())
        return direct_map[index];

    return -1;
}

Answer 3

Для начала вам, вероятно, следует использовать std::map::find, если вы хотите сравнить время поиска; operator[] имеет дополнительные функции сверх обычной находки.

Кроме того, ваш набор данных довольно мал, что означает, что весь вектор легко поместится в кэш процессора; многие современные процессоры оптимизированы для такого рода перебора, так что в итоге вы получите довольно хорошую производительность. Карта, теоретически имеющая лучшую производительность (O (log n), а не O (n)), не может реально использовать ее преимущество меньшего числа сравнений, потому что не так много ключей для сравнения и издержки ее макет данных работает против него.

TBH для таких структур данных так мало, дополнительный выигрыш в производительности от неиспользования вектора часто пренебрежимо мал. «Умнее» структуры данных, такие как std::map, вступают в игру, когда вы имеете дело с большими объемами данных и хорошо распределенным набором данных, которые вы ищете.