Эй, у меня сейчас есть список созданной мной структуры, я сортирую этот список каждый раз, когда добавляю новый объект, используя метод сортировки std :: list. Я хочу знать, что будет быстрее, используя std :: multimap для этого или std :: list, , так как я повторяю весь список в каждом фрейме (я делаю игру).std :: list или std :: multimap
Я хотел бы услышать ваше мнение, для чего я должен использовать этот инцидент.
std::multimap, вероятно, будет быстрее, так как это O (журнал N) на вставке , тогда как вставка и вид списка - O (n log n).
В зависимости от вашего шаблона использования, возможно, вам будет лучше с отсортированным vector. Если вы вставляете сразу целую кучу предметов, а затем делаете кучу чтений, то есть чтение и запись не чередуются - тогда вы получите лучшую производительность с vector, std::sort и std::binary_search.
+1 для цитирования 'vector' (вы могли бы сказать' deque' тоже, это может оказаться лучше), однако я бы также предложил «multiset» здесь, так как он не кажется парой ключ/значение. –
Даже если вы вставляете несколько элементов, используя std :: vector с std :: sort, вы не получите более высокую производительность, чем std: set или std :: multimap, потому что в сортировке всегда будет O (n log n) (n элементов в списке) и вставка k элементов в набор с n элементами будет иметь O (k log n), что лучше, если k много меньше n. – MKroehnert
@MKroehnert: Вот почему я говорил о неперемещенных чтениях и письмах. То есть K будет значительным по сравнению с N. Также имейте в виду, что «вектор» имеет МНОГОУлучшую локальность ссылки, а также эффективность пространства по сравнению с картами. Все эти дополнительные разыгрывания, которые должны выполняться внутри карты, не рассматриваются в теоретической сложности, но это действительно влияет на реальный код. См. Эффективный STL Скотта Мейерса. Пункт 23: Рассмотрите возможность замены ассоциативных контейнеров отсортированными векторами. –
Возможно, вы захотите использовать алгоритм lower_bound, чтобы найти, куда вставлять в свой список. http://stdcxx.apache.org/doc/stdlibref/lower-bound.html
Edit: В свете замечаний Нила, обратите внимание, что это будет работать с любой последовательности контейнера (вектор, дека и т.д.)
Обратите внимание, что lower_bound будет плохо работать в списках из-за линейного времени поиска. Иначе +1. –
@Billy ONeal: Нет, проверьте ссылку. Это O (log n). Предположительно используется двоичный поиск. –
Это только (log n) с итераторами произвольного доступа. Список содержит только двунаправленные итераторы, делающие его линейным. Это будет логарифмическое число сравнений, но вам все равно необходимо линейно перечеркивать список. –
Вообще говоря, итерация по контейнеру, скорее всего, займет столько же времени, сколько итерация над другой, поэтому, если вы продолжаете добавлять в контейнер и затем итерации по нему, это в основном вопрос выбора контейнера, который позволяет постоянно перераспределить память и быстро вставить то, что вы хотите.
В обоих списках и мультимапах не нужно перераспределять себя просто из добавления элемента (например, вы могли бы получить с помощью вектора), поэтому речь идет прежде всего о том, сколько времени требуется для вставки. Добавление в конец списка будет O (1), в то время как добавление в мультимап будет O (log n). Тем не менее, multimap будет вставлять элементы в отсортированном порядке, а если вы хотите отсортировать список, вам придется либо отсортировать список в O (n log n), либо вставить элемент отсортированным способом с помощью что-то вроде lower_bound, которое будет O (n). В любом случае для использования списка будет намного хуже (в худшем случае).
Как правило, если вы поддерживаете контейнер в отсортированном порядке и постоянно добавляете его, а не создаете его и сортируете его один раз, наборы и карты более эффективны, поскольку они предназначены для сортировки. Конечно, как всегда, если вы действительно заботитесь о производительности, профилирование вашего конкретного приложения и наблюдение за тем, что работает лучше, - это то, что вам нужно делать. Однако в этом случае я бы сказал, что это почти гарантия того, что multimap будет быстрее (особенно если у вас очень много элементов вообще).
Алгоритмически, так же, как и в течение одного и того же цикла, чем в другом контейнере. На практике из-за соображений кэширования структуры массива ('vector' и' deque') намного эффективнее. –
Если вам не нужны пары Key/Value std::set или std::multiset, вероятно, лучше, чем с использованием std::multimap.
Ссылка для std::set: http://www.cplusplus.com/reference/stl/set/
Ссылка для std::multiset: http://www.cplusplus.com/reference/stl/multiset/
Edit: (кажется, это было неясно раньше) Это вообще лучше использовать контейнер, как std::(multi)set или std:(multi)map, чем при использовании std::list и сортировать его каждый раз, когда вставлен элемент, потому что std::list не очень хорошо вставляет элементы в середину контейнера.
Обратите внимание, что для списка вставка один за другим, даже с линейным временем вставки, составляет не менее O (n^2). Вам лучше вставить их все и отсортировать один раз. –
Это неверно, потому что у вас будет n-кратная вставка O (log n), поэтому вы получите O (n log n), который будет таким же, как для сортировки. – MKroehnert
@MKroehnert - списки не позволяют логарифмические вставки. –
Списки являются контейнером последней инстанции - для моих мыслей по этому вопросу см. Http://punchlet.wordpress.com/2009/12/27/letter-the-fourth/ – 2010-04-14 16:53:03
Что еще вы должны делать с этими объекты? Итерации над ним каждый раз? экстракт мин? Это уже узкое место? Насколько велик список? – fabrizioM
Как вы просматриваете предметы в списке, когда хотите их найти? –