DI
Т.е. в теории лукап по вектору O(1), но на практике это не так
Да, это верно, это именно то, чем я и вооружусь для собесов.
для справки https://clojure.org/reference/data_structures#Vectors
тут никто про O(1) и не говорит
Size: a a a
2021 April 06
IG
Log32 это очень хорошо, рост очень маленький
E
Dmitry Ivanov
А map и set, получается, тоже на деревьях? Мне казалось, что при некоторых условиях можно получить плоскую HashMap и HashSet соответственно.
Еп. Вот возьмем мапы, к примеру:
(defn sorted-map
[...some-code...] (clojure.lang.PersistentTreeMap/create keyvals))) -- т.е. следует из названия, что дерево
public IPersistentMap [...some-code...] -- там увидим, тоже Leafs/Nodes
(defn sorted-map
[...some-code...] (clojure.lang.PersistentTreeMap/create keyvals))) -- т.е. следует из названия, что дерево
public IPersistentMap [...some-code...] -- там увидим, тоже Leafs/Nodes
AC
для справки https://clojure.org/reference/data_structures#Vectors
тут никто про O(1) и не говорит
тут никто про O(1) и не говорит
Ну в теории принято считать что у вектора лукап O(1) и это сравнивают с log32(n) для кложа вектора.
PP
Dmitry Ivanov
Конечно, но асимптотически, логарифм, делённый на константу, остаётся логарифмом для формального анализа сложности.
Для формального да, но это как раз неплохой пример, которым на собесе можно обратить внимание на отношение между формальным и практическим
KC
Ну в теории принято считать что у вектора лукап O(1) и это сравнивают с log32(n) для кложа вектора.
ну мы же про кложурный вектор говорим, а у него реализация с лукап log32n
AC
Dmitry Ivanov
Да, это верно, это именно то, чем я и вооружусь для собесов.
Это хороший источник, я так понял эти статьи - результат научной работы, те на них можно прямо ссылаться
AC
ну мы же про кложурный вектор говорим, а у него реализация с лукап log32n
Мы сравниваем кложурный с другими векторами.
AC
Так просто в вакууме сказать log32 - это ни о чем не говорит.
E
короче разница видна только на громадных векторах. Ну и всегда есть нативные арреи java
Там ниже по тексту статьи, которую @achikin скинул - указывается, что transient на самом деле демонстрирует сходные результаты с ArrayList
AG
Dmitry Ivanov
Это перестановка FAANGM
Мне интересно что в этой перестановке значит буква "М". Я знаю все остальные, а про М не слышал.
PP
Мне интересно что в этой перестановке значит буква "М". Я знаю все остальные, а про М не слышал.
Microsoft?
AG
Ну просто везде аббревиатура фигурирует обычно как FAANG, и Майкрософт туда не причисляли. Наверное что-то поменялось.
DI
Мне интересно что в этой перестановке значит буква "М". Я знаю все остальные, а про М не слышал.
Просто FAGMAN комичнее, потому можно и Майкрософт включить, как Павел заметил.
AG
Ну ясно. Спс
OR
Работать в FAGMAN как-то не хочется.
MD
На посмеяться