#list #stl #multimap
#Список #stl #multimap
Вопрос:
Мы использовали multimap<int,string> для хранения нескольких сотен тысяч элементов (> 300K), когда поняли, что нам нужно добавить больше данных для анализа. Итак, мы создали класс, который содержал несколько элементов и необходимые переопределенные операторы для stl, и использовали multimap<ourStruct,String> . Это сработало нормально и не заняло намного больше времени, чем раньше (с некоторыми тестовыми данными), когда мы поняли, что stl <список> будет работать просто отлично, при условии, что мы отсортировали его после завершения добавления всех элементов. К нашему удивлению, мы обнаружили, что добавление всех элементов в multimap по-прежнему значительно превосходит общее время добавления всех элементов в список, а затем сортировки.
Это не имеет смысла для нас, EE типов, поскольку, по нашему мнению, каждая вставка в multimap должна была бы проходить по списку, а затем прикреплять его к концу, где, как и в случае со списком, мы бы просто добавили в конец (через push back), тогда, надеюсь, сортировка не заняла бы столько времени.
Еще один факт: мы сначала провели сравнительный тест без сортировки списка и были в восторге, увидев значительное увеличение скорости использования списка. Затем мы добавили сортировку и были немного ошеломлены…
Кто-нибудь из гуру CS хочет поучаствовать?
Ответ №1:
std::multimap использует сбалансированное дерево1, поэтому оно не пересекает весь список при вставке элемента. Количество элементов, пройденных для вставки, приблизительно равно логарифму по основанию 2 от количества элементов в коллекции.
Исходя из того, что вы сказали, вашим лучшим выбором, вероятно, было бы поместить ваши данные в вектор, а затем отсортировать.
1 Технически стандарт напрямую не требует сбалансированного дерева, но он требует способности перемещаться в отсортированном порядке и логарифмической сложности для вставок и удалений в худшем случае, и я не знаю многих других структур данных, которые могут соответствовать этому требованию.
Комментарии:
1. Я неправильно указал. Мы понимаем, что это не пересекает все дерево, только те ветви, которые должны быть (эта штука logN). Мы также тестировали vector, и это было еще медленнее, особенно на этапе добавления. Это то, что привело нас к списку…
Ответ №2:
Удалена ссылка на хэш .. Сбалансированное дерево — вот почему требуется только n2 обхода.