Pawel
да пофигу какой язык, хоть css
🏁Александр
удачи написать хештаблицу на css
Илья
Artem
🏁Александр
я бы посмотрел даже
Pawel
Artem
окей. С ними скорее всего не прокатит. Но повторюсь оно не везде надо и не все спршивают. Кароч каждый при своем мнении
Pawel
Илья
хотя в мордокнигу я, пока, не собеседовался
Илья
посмотрим, что там :D
Constantine️
🏁Александр
ordered map это шо? что бы порядок ключей при range был всегда одинаковый?
Pawel
я про то, что не везде же валенки сидят ,которым можно "втирать". Иногда это прокатывает, но как правило не комильфо - сразу видно же
Илья
Roman
🏁Александр
в go такое делается с помощью смесь slice (порядок ключей) и map
🏁Александр
насколько я знаю
Pawel
нет, не так
Илья
Pawel
можно так, да
при этом будут другие О сложности на получение списка ключей, чем в stl из C++
Pawel
🏁Александр
подрузомевает?
🏁Александр
это что за постановка такая
Илья
хотя мб я тоже не пройду собеседование :)
Илья
и, кстати, насчет "подразумевает", это, обычно, уточняется до решения задачи
Илья
или, вопросы про сложность задаются после, обычно с вопросом, можно ли улучшить это решение
🏁Александр
🏁Александр
тут опять же надо угадать
Илья
🎉
🏁Александр
переезжают потихоньку вроде
Илья
Илья
тогда получение массива O(1) :)
Pawel
эм, так ты хранишь и массив и мап
ну просто почитатй как устроено красно-чёрное дерево, сразу станет понятно о чём речь и в чём пойнт вопроса про ordered map =)
Илья
Roman
а ну ка поясните зачем ordered map делать на сорт. массиве из ключей и hashmap? просто сортированный массив структур kv по k будет намного быстрее. или речь про ассоциативный массив?
Илья
🏁Александр
map кстати доступ нихрена не O(1)
Roman
так он не на hashmap
🏁Александр
на хабре там вон статью пилили
Roman
в го мапа состоит из букетов (цветов, я понимаю). поэтому нифига не о(1).
Roman
поэтому все зависит от разброса хэша по ключу
Roman
в какой из букетов попадет хэш
Илья
Roman
для интов вроде кучная хэш функция там
Илья
Илья
у hashmap amortized O(1), в го аналогично
Roman
а вот для строковых ключей уже не так тривиально, сам хэш посчитать уже нелинейно
Roman
хотя на поиск - да, amortized
Илья
так, кароч, или давайте бенчмарки, или как известно куда двигайтесь
Илья
https://www.reddit.com/r/compsci/comments/2z74z8/why_is_hashtable_lookup_o1_rather_than_olog_n_or/
Илья
то, что хэшмап так живет, это факт
Pawel
Илья
Roman
Roman
при доступ?
да, промах в отсутствующий букет как отработает? в соседний не лезет? надо уточнить
Roman
это linked list
Илья
Илья
нафиг так жить?
Pawel
Илья
логарифм
так откуда эти условия то? есть ограничения по памяти? хэшмап + массив ключей - доступ o(1), вставка такая же lgN
Daniel
Илья
да, типо treemap компактнее в памяти, но изх условия задачи ничего про деревья не было
Pawel
Илья
"разумеется", "конечно", подразумевается
Roman
У какой проблемы?
там где ты хотел переключаться на lock. просто я в итоге делал либо лок на все, либо COW и лок только на замену значения
Pawel
Daniel
У той, над которой я думал, такое
Взять RLock
Проверить, нужна ли запись
Отпустить RLock
Если запись нужна, то
Взять Lock
Проверить, нужна ли запись
Если запись нужна, то
Записать
Отпустить Lock
Roman