Могу ли я увидеть прирост производительности, используя std :: map вместо вектора & lt; pair & lt; string, string & gt; & GT ;?
В настоящее время у меня есть код, где я использую vector из pair<string,string>, Это используется для хранения некоторых данных из синтаксического анализа XML, и поэтому процесс довольно медленный местами. С точки зрения попытки ускорить весь процесс, я задавался вопросом, будет ли какое-либо преимущество в производительности при переключении с vector<pair<string,string> > в std::map<string,string> ? Я мог бы закодировать его и запустить профилировщик, но я подумал, что увижу, смогу ли я получить ответ, который сначала предполагает некоторый очевидный прирост производительности. Я не обязан выполнять какую-либо сортировку, я просто добавляю элементы в вектор, затем на более поздней стадии выполняю итерацию содержимого и выполняю некоторую обработку — мне не нужно сортировать или что-либо в этом роде. Я предполагаю, что, возможно, я не получу никакого прироста производительности, но я никогда не использовал std::map раньше, так что я не знаю, не спросив и не закодировав все это.
Решение
Нет. Если (как вы говорите) вы просто перебираете коллекцию, вы увидите небольшое (вероятно, не измеримое) представление снижение используя std::map,
Карты предназначены для доступа к значению по его ключу. Если вы никогда этого не сделаете, карта — плохой выбор для контейнера.
Другие решения
Если вы не изменяете свой vector<pair<string,string> > — просто повторяя это снова и снова — вы получите ухудшение производительности, используя map, Это потому что типичный map организован с двоичным деревом объектов, каждый из которых может быть размещен в разных блоках памяти (если вы не пишете собственный распределитель). Плюс каждый узел map управляет указателями на соседние объекты, так что это также время и память. Но поиск по ключу — это операция O (log). С другой стороны, vector хранит данные в одном блоке, поэтому кэш процессора обычно чувствует себя лучше. Поиск по вектору — это на самом деле операция O (N), которая не так хороша, но приемлема. Поиск в отсортированном векторе можно обновить до O (log), используя функции lower_bound и т. Д.
Это зависит от операций, которые вы делаете над этими данными. Если вы делаете много запросов — вероятно, лучше использовать контейнер хеширования, например unordered_map поскольку поиск по ключу в этих контейнерах является операцией O (1). Для повторения, как уже упоминалось, vector быстрее.
Наверное, стоит заменить string в вашем pair, но это сильно зависит от того, что вы там держите и как контейнер доступа.
Ответ зависит от того, что вы делаете с этими структурами данных и каков их размер. Если у вас есть тысячи элементов в вашем std::vector<std::pair<std::stringm std::string> > и вы продолжаете искать first элемент снова и снова, используя std::map<std::string, std::string> может улучшить производительность (вы можете рассмотреть возможность использования std::unordered_map<std::string, std::string> для этого варианта использования, а не). Если ваши векторы относительно малы, и вы не пытаетесь вставлять элементы в середину слишком часто, использование векторов вполне может быть быстрее. Если вы просто перебираете элементы, векторы работают намного быстрее, чем карты: на самом деле итерации не являются их сильной стороной. Карты хороши в поиске вещей, предполагая, что количество элементов не очень мало, потому что в противном случае линейный поиск по вектору все еще быстрее.
Лучший способ определить, на что тратится время, — это профилировать код: часто неясно, где именно тратится время. Часто подозреваемые горячие точки на самом деле не являются проблемными, а в других областях возникают непредвиденные проблемы с производительностью. Например, вы можете передавать свои объекты моей ценности, а не по ссылке в каком-то непонятном месте.
Если ваш шаблон использования таков, что вы выполняете много вставок перед выполнением любых поисков, то вам может быть полезно реализовать «ленивую» карту, в которой элементы сортируются по требованию (то есть, когда вы получаете итератор, выполняете поиск и т. Д.).
Как говорит C ++ std::vector сортировать элементы в линейной памяти, поэтому сначала он выделяет блок памяти с начальной емкостью, а затем, когда вы хотите вставить новый элемент в вектор, он проверит, есть ли у него больше места или нет, и если нет, он выделит новый буфер с большим количеством пробел, скопируйте все элементы в новый буфер и затем удалите исходный буфер и установите его в новый.
Когда вы просто начинаете вставлять элементы в vector и у вас есть много предметов, которые вы страдаете от слишком большого перераспределения, копирования конструкции и вызова деструктора.
Чтобы решить эту проблему, если вы теперь посчитаете входные элементы (не точные, а их обычную длину), вы можете reserve немного памяти для вектора и избежать перераспределения и все.
если у вас нет представления о размере, вы можете использовать такую коллекцию, как std::list Ведьма никогда не перераспределяет свои внутренние предметы.