DL
Dmitry Ivanov
А где ещё есть работа со сравнимыми условиями?
В смысле заниматься скучным говном?
Size: a a a
2021 April 06
OR
DI
Спасибо!
E
Dmitry Ivanov
vector в Кложе - это ведь дерево?
Если кто-нибудь использовал Кложу для технического собеседования в FAGMAN , как правильно работать со сложностью в задачах с массивами? Правильно ли я понимаю, что доступ к элементу vec - логарифмический?
Если кто-нибудь использовал Кложу для технического собеседования в FAGMAN , как правильно работать со сложностью в задачах с массивами? Правильно ли я понимаю, что доступ к элементу vec - логарифмический?
Persistent data structures все - дерево, но вектор, если сравнивать с ООП реализует семантику LIFO (читать - стэк).
DI
Persistent data structures все - дерево, но вектор, если сравнивать с ООП реализует семантику LIFO (читать - стэк).
А map и set, получается, тоже на деревьях? Мне казалось, что при некоторых условиях можно получить плоскую HashMap и HashSet соответственно.
PP
Dmitry Ivanov
vector в Кложе - это ведь дерево?
Если кто-нибудь использовал Кложу для технического собеседования в FAGMAN , как правильно работать со сложностью в задачах с массивами? Правильно ли я понимаю, что доступ к элементу vec - логарифмический?
Если кто-нибудь использовал Кложу для технического собеседования в FAGMAN , как правильно работать со сложностью в задачах с массивами? Правильно ли я понимаю, что доступ к элементу vec - логарифмический?
Да, но там деревья, если ничего не путаю, по 32 элемента, так что логарифм там по основанию 32, который растёт ну очень небыстро
PP
Dmitry Ivanov
А map и set, получается, тоже на деревьях? Мне казалось, что при некоторых условиях можно получить плоскую HashMap и HashSet соответственно.
Да и да. Достаточно маленькие упаковываются в один массив целиком (хотя они там не хэшсеты/хэшмапы).
DI
Да, но там деревья, если ничего не путаю, по 32 элемента, так что логарифм там по основанию 32, который растёт ну очень небыстро
Конечно, но асимптотически, логарифм, делённый на константу, остаётся логарифмом для формального анализа сложности.
DI
Да и да. Достаточно маленькие упаковываются в один массив целиком (хотя они там не хэшсеты/хэшмапы).
Спасибо. А достаточно маленькие - это, собственно, 32 элемента и меньше?
AC
Dmitry Ivanov
Конечно, но асимптотически, логарифм, делённый на константу, остаётся логарифмом для формального анализа сложности.
AC
Там в следующих статьях есть бенчмарки
PP
Dmitry Ivanov
Спасибо. А достаточно маленькие - это, собственно, 32 элемента и меньше?
DI
AC
Т.е. в теории лукап по вектору O(1), но на практике это не так
IG
короче разница видна только на громадных векторах. Ну и всегда есть нативные арреи java
IG
скажем, если хранить 10М интов, то это лучше нативно делать
AC
короче разница видна только на громадных векторах. Ну и всегда есть нативные арреи java
Тут имхо основная суть в том что нет никакого O(1) на практике и в этом смысле log32(n) уже не так плохо выглядит как по началу кажется