Когда карта становится лучше, чем два вектора?

Question

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

Насколько великадолжен ли пул объектов (ключей) быть для того, чтобы карта начала работать лучше, чем два вектора?

Редактировать: более обобщенная версия вопроса: насколько большим должен быть пул объектов, чтобы бинарный поиск работал лучше, чем линейныйпоиск?

Я использую строки в качестве ключей, а значения являются указателями, но мой конкретный вариант использования, вероятно, не должен иметь значения.Мне более любопытно понять, как правильно использовать эти два инструмента.

Answer 1

Если вы простите мое изречение, большинство ответов звучат для меня как различные способы сказать: «Я не знаю», фактически не признавая, что они не знают.Хотя я в целом согласен с советом, который они дали, похоже, что никто из них не пытался напрямую ответить на вопрос, который вы задали: что такое точка безубыточности.Я тоже не знал.Это одна из тех вещей, которые все мы знаем основы: для достаточно маленькой коллекции линейный поиск, вероятно, будет быстрее, а для достаточно большой коллекции, бинарный поиск, несомненно, будет быстрее.У меня, однако, никогда не было особых причин что-либо исследовать относительно того, какой будет точка безубыточности.Однако ваш вопрос вызвал у меня любопытство, поэтому я решил написать немного кода, чтобы получить хоть какую-то идею.

Этот код определенно является очень быстрым взломом (много дублирования, тольков настоящее время поддерживает один тип ключа и т. д.), но, по крайней мере, он может дать некоторое представление о том, чего ожидать:

#include <set>
#include <vector>
#include <string>
#include <time.h>
#include <iostream>
#include <algorithm>

int main() {   

    static const int reps = 100000;

    std::vector<int> data_vector;
    std::set<int> data_set;
    std::vector<int> search_keys;

    for (int size=10; size<100; size += 10) {
        data_vector.clear();
        data_set.clear();
        search_keys.clear();

        int num_keys = size / 10;   
        for (int i=0; i<size; i++) {
            int key = rand();

            if (i % num_keys == 0)
                search_keys.push_back(key);

            data_set.insert(key);
            data_vector.push_back(key);
        }

        // Search for a few keys that probably aren't present.
        for (int i=0; i<10; i++)
            search_keys.push_back(rand());

        long total_linear =0, total_binary = 0;

        clock_t start_linear = clock();
        for (int k=0; k<reps; k++) {
            for (int j=0; j<search_keys.size(); j++) {
                std::vector<int>::iterator pos = std::find(data_vector.begin(), data_vector.end(), search_keys[j]);
                if (pos != data_vector.end())
                    total_linear += *pos;
            }
        }
        clock_t stop_linear = clock();                      

        clock_t start_binary = clock();
        for (int k=0; k<reps; k++) {
            for (int j=0; j<search_keys.size(); j++) {
                std::set<int>::iterator pos = data_set.find(search_keys[j]);
                if (pos != data_set.end())
                    total_binary += *pos;
            }
        }
        clock_t stop_binary = clock();

        std::cout << "\nignore: " << total_linear << " ignore also: " << total_binary << "\n";

        std::cout << "For size = " << size << "\n";
        std::cout << "\tLinear search time = " << stop_linear - start_linear << "\n";
        std::cout << "\tBinary search time = " << stop_binary - start_binary << "\n";
    }
    return 0;
}

Вот результаты, которые я запускаю на своей машине:

ignore: 669830816 ignore also: 669830816
For size = 10
        Linear search time = 37
        Binary search time = 45

ignore: 966398112 ignore also: 966398112
For size = 20
        Linear search time = 60
        Binary search time = 47

ignore: 389263520 ignore also: 389263520
For size = 30
        Linear search time = 83
        Binary search time = 63

ignore: -1561901888 ignore also: -1561901888
For size = 40
        Linear search time = 106
        Binary search time = 65

ignore: -1741869184 ignore also: -1741869184
For size = 50
        Linear search time = 127
        Binary search time = 69

ignore: 1130798112 ignore also: 1130798112
For size = 60
        Linear search time = 155
        Binary search time = 75

ignore: -1949669184 ignore also: -1949669184
For size = 70
        Linear search time = 173
        Binary search time = 83

ignore: -1991069184 ignore also: -1991069184
For size = 80
        Linear search time = 195
        Binary search time = 90

ignore: 1750998112 ignore also: 1750998112
For size = 90
        Linear search time = 217
        Binary search time = 79

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

Редактировать: я бы отметилдля записи, которую я не вижу причины, что код, использующий два вектора (или вектор пар), не может быть таким же чистым, как код, использующий набор или карту.Очевидно, что вы захотите поместить код для него в небольшой собственный класс, но я не вижу никакой причины, по которой он не может представить точно тот же интерфейс для внешнего мира, что mapделает.На самом деле, я бы, вероятно, просто назвал это «tiny_map» (или что-то в этом порядке).

Одна из базовых точек ОО-программирования (и в некоторой степени это относится и к универсальному программированию).) состоит в том, чтобы отделить интерфейс от реализации. В данном случае вы говорите только о деталях реализации, которые вообще не должны влиять на интерфейс. На самом деле, если бы я писал стандартную библиотеку, я бы соблазнился включитьэто как «оптимизация малой карты», аналогичная обычной оптимизации малой строки. По сути, просто выделите массив из 10 (или около того) объектов value_type непосредственно в самом объекте карты и используйте их, когда / если карта малазатем переместите данные в дерево, если оно станет достаточно большим, чтобы оправдать его. Единственный реальный вопрос - достаточно ли часто люди используют крошечные карты, чтобы оправдать работу.

Answer 2

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

Answer 3

Карта никогда не будет равна отсортированной скорости векторного поиска, поскольку векторная память лучше упакована, а доступ к памяти более простой.

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

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

Если вы действительно обнаруживаете, что измеряете и хотите действительно выжать производительность из варианта использования, то вам, вероятно, нужна более специализированная структура данных. Посмотрите B-Trees.