NoneStd ::distance медленно и как его улучшить?
std::distance кажется очень медленным У меня есть большая мультикарта и я пытаюсь использовать equal_range найти элемент с общим ключом:
auto range = in_map.equal_range(neuron_with_spikes[i]);
int count = std::distance(range.first, range.second);
std::distance занимает больше времени, чем equal_range, Наивно я предположил бы, что при равном расположении расстояние вычисляется автоматически. На самом деле это два независимых расчета.
Есть ли другой способ получить общее количество элементов equal_range?
2 ответа
std::multimap::equal_range является O(log <size of the container>) а также std::distance является O(linear <size of the range>) а также std::multimap::count это сумма этих двух.
Это вполне разумно, так как карта отсортирована, и вам нужно посетить каждый элемент в диапазоне, чтобы сосчитать их - поэтому, если вы не можете избавиться от этого в своем решении - это выглядит как нормальное поведение для того, что вы пытаетесь сделать.
Нет; можно реализовать конструкцию типа карты std, в которой подсчет расстояния между итераторами равен O(lg n), но карты std не реализуют его. И дооснащать его непросто; написать свой собственный контейнер, вероятно, так же просто.
В такой модифицированной карте сбалансированное двоичное дерево отслеживает общее количество узлов под; это добавляет постоянный коэффициент издержек к мутации дерева и использованию памяти, но не в O-записи.
Самый простой способ, потому что вам нужно только считать, а не расстояние, возможно, заменить вашу мультикарту с картой от ключа к вектору элементов; и вручную управлять вектором элементов. Расстояние равно O(n), но счет становится O(lg n).