AK
Alex Sandrov
Пару лет назад, не помню на каком компиляторе, тестировал vector, map и unordered_map, результаты сильно отличались
какова была методика?
Size: a a a
2020 August 17
SE
Alex Sandrov
Пару лет назад, не помню на каком компиляторе, тестировал vector, map и unordered_map, результаты сильно отличались
так там не только компилер надо тестить, а еще конкретную реализацию стл
AK
все реализации должны были выдать O(n) пару лет назад
IZ
Ну вот собственно проблема в том, что итерация по нодам разбросанным в памяти на современных процессорах на порядки медленее чем последовательный доступ. Модели считающие асимптотику по количеству операций это не показывают.
А как ты в стандарт языка который работает на разных процессорах разных архитектур запишешь требования к доступу к памяти?
m
А как ты в стандарт языка который работает на разных процессорах разных архитектур запишешь требования к доступу к памяти?
Кроме стандарта существуют практика. Не все вопросы в этой группе посвящены исключительно стандарту.
IZ
Alex Sandrov
Пару лет назад, не помню на каком компиляторе, тестировал vector, map и unordered_map, результаты сильно отличались
Можешь показать результата тестов?
SE
все реализации должны были выдать O(n) пару лет назад
list? где это написано?
m
list? где это написано?
Думаю эта гарантия приходит из свойств forward iterator'а.
АК
Alex Sandrov
К примеру, у меня вирутальная грида, я скроллюсь на 100000-й элемент в гриде, и мне надо быстро получить 100000-й элемент в контейнере
boost::multi_index решит все проблемы
SE
Думаю эта гарантия приходит из свойств forward iterator'а.
🤔std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is usually implemented as a doubly-linked list.
m
🤔std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is usually implemented as a doubly-linked list.
Я говорил об итерации, а не случайном доступе к элементам.
SE
Они и сейчас отличаются по скорости итерации почти в полтора раза. Буквально два месяца назад тестил на MSVC
ох, в ms stl много всякого, они все грозятся выкатить vNext с поломанным Abi, в твиттере один из разрабов плакался как то что чето-то там ускорил с тредами еще в 2016 году, но из за ABI это еще лежит мертвым грузом
SE
мб таки сломают со следующей студией
AK
list? где это написано?
§27.2.1.10
и §27.2.2 (таблица 94): разыменование и инкремент за констаннтное время — требование для всех типов итераторов.
Это 17й стандарт, сорян, 20ого нету у меня ещё
All the categories of iterators require only those functions that are realizable for a given category in constant
time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.
и §27.2.2 (таблица 94): разыменование и инкремент за констаннтное время — требование для всех типов итераторов.
Это 17й стандарт, сорян, 20ого нету у меня ещё
AS
какова была методика?
большой цикл, it++. По теории, в векторе это просто приращение на константу, в мапе - хождение по указателю.
На самом деле, мне больше важен доступ по (порядковому) индексу. Ситуация: скролл виртуальной гриды до 1М записи, vector получает доступ к 1M с begin() за константу, map получает доступ к 1M за O(n), это хоть и очень быстро, но заметно 😐
На самом деле, мне больше важен доступ по (порядковому) индексу. Ситуация: скролл виртуальной гриды до 1М записи, vector получает доступ к 1M с begin() за константу, map получает доступ к 1M за O(n), это хоть и очень быстро, но заметно 😐
P
Чтобы получить и константный доступ по ключу и преимущества локальности при итерировании - это нужно положить хэш таблицу в вектор :) Из очевидных недостатков - вставка/удаление элементов будут дорогими, так что лучше будет сформировать коллекцию как заранее и потом её не модифицировать. Возможно, готовые реализации уже есть, ну или можно свою написать, там не так сложно.
AK
vector получает доступ к 1M с begin() за константуда не, показалось