A
не більше
Size: a a a
2020 July 21
RN
поетому вектор будет быстрее
YS
воно мені дасть приріст швидкості в 200 разів
Так нормально
RN
а сет замедлит
RN
ну как хочешь, чево я вообще лезу
AN
Один контейнер, чтобы управлять всеми.
A
поетому вектор будет быстрее
що швидше, 1000000/200==5000(вектор), чи лн(1000000)==20(сет)?
RN
що швидше, 1000000/200==5000(вектор), чи лн(1000000)==20(сет)?
не понял что тут написано
YS
YS
На cppreference тоже писали, что в std::unordered_set поиск константный
YS
Только как они это реализовали
RN
так это ж хеш таблица
RN
через хеш
A
не понял что тут написано
ну, я ж отримую за рахунок кешу приріст швидкості не більше ніж в 200 разів. Відповідно якщо в мене 1 000 000 елементів, то в гіршому випадку пошук елемента буде за лінію / 200(ну або в сеті треба *200, але я пояснюю свій приклад), що рівне 5000
В сеті доступ до елементів за логарифм без оптимізацій через кеш, тобтом лн(1 000 000)==20
В сеті доступ до елементів за логарифм без оптимізацій через кеш, тобтом лн(1 000 000)==20
YS
так это ж хеш таблица
Выходит тогда его лучше использовать
YS
unordered set
.
RN
ну, я ж отримую за рахунок кешу приріст швидкості не більше ніж в 200 разів. Відповідно якщо в мене 1 000 000 елементів, то в гіршому випадку пошук елемента буде за лінію / 200(ну або в сеті треба *200, але я пояснюю свій приклад), що рівне 5000
В сеті доступ до елементів за логарифм без оптимізацій через кеш, тобтом лн(1 000 000)==20
В сеті доступ до елементів за логарифм без оптимізацій через кеш, тобтом лн(1 000 000)==20
не понимаю что ты считаешь
ты думаешь что можешь вот так просто взять и посчитать на бумажке какое будет время?
там же куча оптимизаций внутри и все на то чтоб линейно с памятью работать быстрее
ты думаешь что можешь вот так просто взять и посчитать на бумажке какое будет время?
там же куча оптимизаций внутри и все на то чтоб линейно с памятью работать быстрее
RN
пока ты будешь ждать загрузку кеша для сета, для вектора эти загрузки скорее всего будут нивелированы спекулятивным исполнением
RN
можешь сделать тест если тебе не все равно конечно
A
не понимаю что ты считаешь
ты думаешь что можешь вот так просто взять и посчитать на бумажке какое будет время?
там же куча оптимизаций внутри и все на то чтоб линейно с памятью работать быстрее
ты думаешь что можешь вот так просто взять и посчитать на бумажке какое будет время?
там же куча оптимизаций внутри и все на то чтоб линейно с памятью работать быстрее
та ну не може воно так добре оптимізувати, щоб при числах > 10**5 лінія обганяла логарифм