Когда использовать SortedList <TKey, TValue> по SortedDictionary <TKey, TValue>?
Несколько положительных сторон уже. У меня есть несколько дополнительных комментариев:
-
Принятие мы говорим о библиотеке стандарта C++, "вектор" подразумевает контейнер произвольного доступа, который имеет гарантии C-массива (произвольный доступ, contiguos расположение памяти и т.д.). Если бы Вы сказали, что 'some_container', многие вышеупомянутые ответы были бы более точными (контейнерная независимость и т.д.).
-
Для устранения любых зависимостей от компиляторной оптимизации Вы могли переместить some_vector.size () из цикла в индексируемом коде, как так:
const size_t numElems = some_vector.size(); for (size_t i = 0; i
-
Всегда преинкрементные итераторы и постинкременты обработки как исключительные случаи.
Настолько принимающий и индексируемый std::vector<> как контейнер, нет никакого серьезного основания предпочесть один по другому, последовательно проходя контейнер. Если необходимо часто обращаться к более старым или более новым индексам elemnent, то индексируемая версия является большим количеством appropropriate.
В целом, использование итераторов предпочтено, потому что алгоритмы используют их, и поведением можно управлять (и неявно зарегистрировать) путем изменения типа итератора. Местоположения массива могут использоваться вместо итераторов, но синтаксическое различие перетерпит.
2 ответа
Вот и все. Получение ключей сравнимо, но добавление со словарями происходит намного быстрее.
Я стараюсь использовать SortedList как можно чаще, потому что он позволяет мне перебирать ключи и коллекции значений. Насколько я знаю, это невозможно с SortedDictionary.
Я не уверен в этом, но насколько мне известно, словари хранят данные в древовидных структурах, тогда как List хранит данные в линейных массивах. Это объясняет, почему вставка и удаление словаря выполняется намного быстрее, поскольку требуется перемещать меньше памяти. Это также объясняет, почему вы можете перебирать SortedLists, но не SortedDictionary.
Я не уверен, насколько точна документация MSDN по SortedList и SortedDictionary . Кажется, что оба реализованы с использованием двоичного дерева поиска. Но если SortedList использует двоичное дерево поиска, почему он будет намного медленнее при добавлении, чем SortedDictionary ?
В любом случае, вот некоторые результаты теста производительности.
Каждый тест работает с SortedList / SortedDictionary , содержащим 10 000 ключей int32. Каждый тест повторяется 1000 раз (Release build, Start without Debugging).
Первая группа тестов добавляет ключи в последовательности от 0 до 9 999. Вторая группа тестов добавляет случайные перемешанные ключи от 0 до 9 999 (каждое число добавляется ровно один раз).
***** Tests.PerformanceTests.SortedTest
SortedDictionary Add sorted: 4411 ms
SortedDictionary Get sorted: 2374 ms
SortedList Add sorted: 1422 ms
SortedList Get sorted: 1843 ms
***** Tests.PerformanceTests.UnsortedTest
SortedDictionary Add unsorted: 4640 ms
SortedDictionary Get unsorted: 2903 ms
SortedList Add unsorted: 36559 ms
SortedList Get unsorted: 2243 ms
Как и при любом профилировании, важна относительная производительность, а не реальные цифры.
Как видите, для отсортированных данных отсортированный список работает быстрее, чем SortedDictionary . Для несортированных данных SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
Как видите, для отсортированных данных отсортированный список работает быстрее, чем SortedDictionary . Для несортированных данных SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
Как видите, для отсортированных данных отсортированный список работает быстрее, чем SortedDictionary . Для несортированных данных SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его работу.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
SortedDictionary . Для несортированных данных SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
SortedDictionary . Для несортированных данных SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
SortedList немного быстрее при извлечении, но примерно в 9 раз медленнее при добавлении.
Если оба используют бинарные деревья внутренне, довольно удивительно, что операция добавления для несортированных данных так много медленнее для SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.
SortedList . Возможно, что отсортированный список может одновременно добавлять элементы в отсортированную линейную структуру данных, что замедлит его.
Однако можно ожидать, что использование памяти SortedList будет равно или больше или, по крайней мере, равно SortedDictionary . Но это противоречит тому, что говорится в документации MSDN.