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