Beginners question по коллекциям Java

Распространенный совет — пока ждешь отклика на резюме, выучи что-то. Многие знания породили многие страдания)

Начну с коллекций — тема собеседований, неотъемлемая, обязательная к использованию часть языка. Прочел теорию графов, книгу с драконом, не понял — зачем было деревья реализовывать на java, а не нативно, ну ладно, это идеологически возможно как-то оправдано, но почему хотя-бы не параллельными массивами?

И jvm, как я понял, честно все эти объекты на каждую запись создает... Но ведь скорость и потребление памяти при параллельных массивах уменьшилось бы в разы, а побочным плюсом можно было бы обойти ограничение на int размер, и вообще позволить переопределять метод индексирования (а не только хеш).
Внутренняя реализация не должна большинство беспокоить (только интерфейс), GC отлично справляется с массивами в тех же arrayList-ах, а расчет «не переживет первую сборку» — не согласуется с сохранением в коллекцию. Тогда чем обосновано решение включить, по сути, в ядро языка, заведомо излишне ресурсоемкое решение, при этом призывая использовать его как можно чаще?

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Скажу честно — в Java прикладному программисту это нужно раз в тысячелетие. Работает. Скорость приличная. Просто скажи сколько миллиардов операций тебе нужно — и дай секунду времени. Уверяю, на изучение этих тупорылых тем и на собеседование по ним ты потратишь куда больше времени, чем 1 секунда.

Если бы речь шла о системном программировании. Да пусть даже о написании серьёзного фреймворка. Тогда — да. Но даже тогда эти темы не зубрятся из книги, а познаются в процессе использования.

Привыкни, что ты живёшь в 21 веке. Цена этих операций настолько низкая, что в принципе на Java пишутся серьёзные вещи. Ты просто не застал времени, когда имея на борту 8 мегабайт памяти — это был отличнейший персональный компьютер. Вот тогда и нужна была оптимизация деревьев и прочая туфта.

Надо ли рассказывать, что в большинстве коллекций java элементов совсем не много, ну два десятка от силы. Ну допустим, в стрингах больше — но как раз этот класс неплохо оптимизирован. Все остальные вылизывания красно-чёрных деревьев, сортировки (в том числе ленивой) и прочего счастья — просто бесполезны для малого количества данных.

Основная задача java на сегодня — это банальнейшие операции: УСЛОВНЫЙ ПЕРЕХОД и МАНИПУЛЯЦИЯ ССЫЛКАМИ. Всё. И если сложить весь другой код, который вы написали за жизнь, кроме этих операций, и запустить его пусть даже на локальной 4-ядерной машине столько раз, сколько он за весь свой жизненный цикл отработает — это время можно измерить сутками для самых производительных говнокодеров, и парой часов для серьёзных программистов.

Всё это — бюрократия. И служит единственной цели: чтобы тот, кто не умеет делать — мог опрашивать и ранжировать тех кто умеет. В реальной жизни это приводит к отсеву ≈75% подходящих кандидатов.

С тем же успехом я могу спросить тебя правила правописания из учебника 5-го класса, и ты на них не ответишь. Но это не значит, что ты не можешь пользоваться языком. Если не веришь — скажи, как пишется пол- с существительными. А теперь сравни с правилом, по которому тебя будет оценивать бюрократ. А ведь это одно из самых простых правил, и их сотни.

И да, если ввести собеседование по русскому языку, процент отсева будет тем же: 75% годных. Притом среди неопытных он меньше — они знают больше теории и меньше практики. А среди пятого класса процент прошедших будет самым высоким.

скажи сколько миллиардов операций тебе нужно — и дай секунду времени
Я Java с андроида начал, довольно дохлого смарта, МТК 6573 двухьядерник, для пробы начал делать векторный редактор, был в шоке — за секунду эта дохлятина достает из 4х массивов последовательно порядка 2 млн. интов и укладывает по координатам примитивы в кадровый буффер, итоговый фпс плавненький )
Собственно, отсюда и нетипичный вопрос по коллекциям))
имея на борту 8 мегабайт памяти
512 кб, Поиск-1
Причина № 2 )
Основная задача java на сегодня — это банальнейшие операции: УСЛОВНЫЙ ПЕРЕХОД и МАНИПУЛЯЦИЯ ССЫЛКАМИ
То-то байт-код состоит из if/goto чуть менее, чем наполовину)
столько раз, сколько он за весь свой жизненный цикл отработает — это время можно измерить сутками
На том-же Поиске-1 написал пару говноигрушек (школьнег же) и графический редактор (без мыши, стрелками, шаг менялся нулем). Шах и мат, атеисты(ц) )))
Всё это — бюрократия. И служит единственной цели: чтобы тот, кто не умеет делать — мог опрашивать и ранжировать
Спасибо, теперь я знаю специфику айти-эйчаров)

ЕСЛИ БЫ только эйчаров. К сожалению, некоторые «сэрцыфыцырованные» лиды ничем не лучше. Ну и те кто нанимает эйчаров — ну как можно доверять этим людям, и ни разу не проверить — а чем они собственно занимаются, и делают ли они именно то что нужно.

Спрашивать-то об этом бесполезно. Проверять надо. А это только обратная связь.

Ну, главное, что я выяснил — джавой занимаются люди, в среднем более гибкие и открытые к другой точке зрения, чем корпоративные фин.аналитики) Для меня это был важный социальный эксперимент, навидался в другой сфере)
А эйчары — да, проблема, для них резюме с банками — черная метка, но это в другую тему)

...у меня 1-ядерный китаец читал 250 000/с пар char в секунду с юсб, делал на них ФМ демодуляцию (включая производную арктангенса), строил FFT и выводил эт все в виде спектра на весь экран + звук радио ... и все это работало плавно при условии оптимизации выделения памяти — т.е. все преаллоцировано + циклы со счетчиком (без for (Object i: some) --- такое сразу уваливает все)

Это хороший вопрос по поводу нативности и производительности. С другой стороны, тогда вообще можно предложить все сделать нативно. Не забывайте, с чего начиналась Java — апплеты и т.д., где производительность-то не сильно и не нужна.

Да, но что мешает СЕЙЧАС разработчикам сохранить интерфейс изменив реализацию, ООП же)

а платить за это великолепие вы готовы?
Если да — обратитесь в Oracle )))

ну хоть не купить Oracle предлагаете)))

Если мне память не изменяет, то основе большинства всех коллекций, если всех вообще, лежат более простые структуры, которые, в свою очередь написаны на С, а все эти абстрактные надстройки сделаны для ускорения написания кода. Читай исходники, по ним можно многое понять. Например, конструктор ArrayList’а первое что делает — переводит этот лист в обычный массив. Я уверен что если покопаться в исходниках джавы, окажется что в основе любой мапы лежит обычный двумерный массив (матрица).

Увы, нет — Roman Gorodischer выкладывал ссылку например habrahabr.ru/...mpany/luxoft/blog/256877 , грубо — если в названии array — на массивах, остальные нет. Вот например grepcode.com/...java/util/LinkedList.java

А как тогда реализуются, например, мапы? Каждой конкретной виртуальной машине по своему?
За ссылку на хабр — спасибо.

Каюсь, гибрид, на одномерном массиве ссылок на объект Entry<key,value>. habrahabr.ru/post/128017 Что мешало сделать на двух массивах — теряюсь в догадках, надо покопать байткод, может там привели)

Учитывая что в мапах используются классы обёртки (для принудительного занесения адресов, а не значений), то логично предположить, что адреса заносятся следующим образом [ID, id_type; value_type, adress], где ID — чаще всего хешкод, id_type — класс-обёртка, value_type — класс-обёртка, adress — ссылка на адрес с объектом. Я бы так делал.

в конце статьи — ссылки на исходники (ну и в Эклипсе можно глянуть), весьма понятно написаны, для меня стандартные библиотеки — образец стиля написания... но не логики)))

но не логики
раджу почитати книжку Ніклауса Вірта «структури даних і алгоритми». він там в першій третині книги розповідає про стандартні структури даних. правда, приклади в нього на паскалі на масивах і функціях. в джаві все так само, тільки обернуте в класи. як на мене — все дуже логічно.

Мешала коллизия хэш функции. Что делать, если два объекта имеют одинаковый хэш? Hash map просто добавит в linked list (bucket) ещё одно значение.

Любые инкапсулированые в объектах данные можно вынести в параллельные массивы (вместо баскетов), парсящиеся с любой логикой, читабельность несколько упадет, но производительность вырастет, об этом был мой первоначальный пост

На сколько я понял структуру HashMap, то в Java она представлена как ArrayList с бакетами. Во что оно дальше траслируется — сильно зависит от архитектуры железа. Нужно будет копать исходники hotspot’a.

Даже в массиве, transient Entry[] table, функционал ArrayList-а реализован отдельно и медленнее, созданием нового массива и копированием через итератор в обёртке(!!!). В этом массиве хранятся ссылки на связные списки типа Entry, цитирую из openjdk

275 static int indexFor(int h, int length) {
276 return h & (length-1);
277 }

386 public V put(K key, V value) {
387 if (key == null)
388 return putForNullKey(value);
389 int hash = hash(key.hashCode());
390 int i = indexFor(hash, table.length);
391 for (Entry<k,v> e = table[i]; e != null; e = e.next) {
392 Object k;
393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394 V oldValue = e.value;
395 e.value = value;
396 e.recordAccess(this);
397 return oldValue;
398 }
399 }
400
401 modCount++;
402 addEntry(hash, key, value, i);
403 return null;
404 }

768 void addEntry(int hash, K key, V value, int bucketIndex) {
769 Entry<k,v> e = table[bucketIndex];
770 table[bucketIndex] = new Entry<k,v>(hash, key, value, e);
771 if (size++ >= threshold)
772 resize(2 * table.length);
773 }

grepcode.com/...ect,java.lang.Object,int

На первый взгляд проблем нет, при более-менее равномерном распределении хеш-функции, но копнем поглубже — в конечном итоге под хранение каждого отдельного значения создается отдельный объект — и это отдельный фрейм для GC...

Есть шикарный фреймвор для микробенчмарков в Java — JMH, его как раз запилили и используют люди которые работают над open Jdk.
Прям в проекте уже есть куча примеров тестов. Если так уверен что можно сделать лучше, посмотри, почитай 10-15 минут доку, запили пару тестов и посмотри будет ли твоя имплементация лучше.
Из практики удавалось дело потокобезопасные коллекции, работающие в многопоточной среде намного быстрее jdk-шных, но они заточенные под какой-то специфик кейс.
PS: без реальных микробенчмарков с использованием нормальной JVM это все пустой треп.

хеш мапа в джаві так і зробить. а взагалі, в хеш мапи як в структури даних є 2 різних реалізації. інша почне шукати вільне місце в сусідніх елементах масиву. сумно що тільки мені прикольно не знати

Певен що багатьом прикольніше знати, ніж не знати, якщо я правильно зрозумів суть)
Мені наприклад цікава друга реалізація, вона має міняти хеш-функцію, як я розумію. Де це реалізовано?
В мене подібна проблема — наприклад, кілька років тому дизасемблював ЕБУ свого авто, абсолютно ніхто з друзів мене не підтримував «дурнею займаєшся, ти ж не автомайстер, краще зароби і купи інше» — було вкрай важко пояснити просту річ, що мені справді цікаво, як це працює

що мені справді цікаво, як це працює
И как оно работает?

Вкратце — ЭБУ это не одна микруха (та, которая по k-line шьется) а несколько, со своей логикой и протоколами связи, прошивка написана изначально на чем-то высокоуровневом (возможно, ООП)), в моем случае даже bootloop не по спецификации, ну и дизассемблировать спагетти код, где половина — безусловные дальние переходы (не только и не столько на таблицы, всё так написано) — удовольствие так себе) Что-то понял, но чтобы писать свое — недостаточно)
Если есть конкретные вопросы — задавайте, а так тема для многотомника (еще теория ДВС цепляется))

Вкратце — ЭБУ это не одна микруха (та, которая по k-line шьется) а несколько, со своей логикой и протоколами связи, прошивка написана изначально на чем-то высокоуровневом (возможно, ООП)), в моем случае даже bootloop не по спецификации,
Я просто стебался. ООП там чаще всего нет вообще, голый ассемблер, ибо ценность программы в ECU нулевая — главная ценность табличные данные для разных узлов в разных режимах работы.
Если есть конкретные вопросы — задавайте, а так тема для многотомника (еще теория ДВС цепляется))
Хорошо, конкретный вопрос. Зачем тебе с такими скиллами Java?

1. Не только лишь не все можно сделать через таблицы, а только то, что сервисникам менять доверили — например, таблицы адаптации можно только обнулить. Алгоритм коррекции по лямбда-зонду (а не пара переменных), аварийные режимы, много чего... Ну и, почему мне не могло быть просто интересно? Это НАСТОЛЬКО странно?)
Насчет ассемблера — не уверен, может подскажешь насчет такого в неиспользуемом куске прошивки «STACK:... ... .R...REG:... SP:. CP:.).ENTER — next dump row, A — new adress, ESC — reset ...User Call — .Stack Overflow.Stack Underflow.Proc. Error.NMI...Debugger» ?
Проц если че www.st.com/.../datasheet/CD00115717.pdf

2. Конкретный ответ — я любитель, самоучка, прочитал спеки, поковырял в IDA, примерно прикинул (и не факт, что правильно), дальше ниасилил, это сказалось на самооценке. Попытался выяснить, занимается ли кто-то в Киеве именно реверс-инженерингом автопрошивок (а не «+100500 лошадей в таблицах»), безуспешно... Ты хотел простебать мой скилл? Так я и не спорю!

Джава для меня не первый язык, возможно и не 10й (но первый чисто ООП, каюсь, избегал), якобы на нее спрос на рынке, но проблемы старта джунов в другую ветку.
Я бы хоть Кобол доучил (в юности хелловорлд на нем написал, имхо он проще Джавы)) — просто за 15 лет вусмерть за-ал финанализ, модели, риски, винтик в системе обоснования коррупции. Хочу реализовать юношескую мечту, сделать профессией то, что нравится, программировать. У меня один скилл, в котором я уверен — наличие мозга, в остальном очень сильно сомневаюсь... Сорри, наболело.

1. Не толькшо лишь не все можно сделать через таблицы, а только то, что сервисникам менять доверили — например, таблицы адаптации можно только обнулить.
Все нормальные производители ушли от алгоритмов в ECU к таблицам трансляции. Не должен ECU думать, практика показала, что это плохо. Если это те таблицы адаптации под топливо и содержание кислорода в воздухе, что я думаю, то изменять её нет смысла, ECU изменит её сама через какое-то время.
Алгоритм коррекции по лямбда-зонду (а не пара переменных), аварийные режимы, много чего...
Какой алгоритм коррекции по лямбда-зонду? И зачем он там нужен — обычная зависимость между, что заливать на входе, если в прошлый раз на выходе было так. Все обычно делается через таблицы, включая температурную коррекцию состава топливно-воздушной смеси.
Насчет ассемблера — не уверен, может подскажешь насчет такого в неиспользуемом куске прошивки «STACK:... ... .R...REG:... SP:. CP:.).ENTER — next dump row, A — new adress, ESC — reset ...User Call — .Stack Overflow.Stack Underflow.Proc. Error.NMI...Debugger» ?
Похоже на обычный встроенный дебаггер или монитор в код, который на продакшене никогда работать не будет.
Ты хотел простебать мой скилл? Так я и не спорю!
Я вообще-то искренне восхитился. Сегодня скилл разума — сесть и разобраться со всем барахлом самому встречается на уровне редчайшего генетического отклонения, что можно сказать, что он утерян. Если не будешь проедать время всяким мусором типа Кобола то может ожидать большое будущее.
У меня один скилл, в котором я уверен — наличие мозга, в остальном очень сильно сомневаюсь.
Правильно. У 99.99% соискателей этого скилла нет, зато есть monkey see, monkey do ( en.wikipedia.org/...iki/Monkey_see,_monkey_do ), что совсем не то, что обычно необходимо :(

Спасибо, с моей стороны статистика выглядит оптимистично)
Написал в личку

було вкрай важко пояснити просту річ, що мені справді цікаво, як це працює
Ну тут вы, подозреваю, несколько слукавили. Ибо обычно в первую очередь хочется как-то его по итогу модифицировать в сторону увеличения мощности. )
А по итогу в процессе попадаешь в другой мир, не менее увлекательный, чем программирование и залипаешь в нем довольно надолго. Где физика и теория ДВС дополняются кучей интересностей типа технологий и погрешностей производства, многократного дублирования для работы при отказах датчиков и исполнительных устройств, таблиц, полученных по итогам многочасовых стендовых испытаний (часто очень далеко уходящих от теории) и даже старых добрых методов “научного тыка”.

Официалы не могли отловить плавающую ошибку (машина изредка глохла, в городе это п-ц), автофорумы (вот же источники ереси) советовали сменить прошивку. Я сменил, затем выявил таки глючный датчик, а там как-то занесло, решил разобраться что внутри — были идеи насчет алгоритмов по лямбде и таблицам адаптации, ниасилил) Насчет увеличения мощности (в основном развод) могу говорить долго, но не хочу плодить оффтопик

зачем было деревья реализовывать на java, а не нативно

Я не совсем понял, что значит «нативно»?

В данном случае — реализация в коде самой jvm, как system.arraycopy например

Рекомендую найти доклад Алексея Шипелева (чувак занимается оптимизацией в Питерском офисе Oracle). Соль следующая: GC не уступает(а иногда даже превосходит) ручному управлению памятью (через всякие там malloc/alloc в С/С++).

Спасибо, доклад сходу не нашел, ссылкой не поделитесь?
Я инфу по GC брал отсюда, глава 7.5. www.proklondike.com/...s/thobshee/compiler2.html
Вообще отличная книга для таких динозавров как я, которые когда-то знали Си и ассемблер, но новый альбом Моцарта уже не выйдет, и надо разбираться как работает то, на что переучиваешься, чисто для себя, чтоб полным кретином себя не чувствовать)

Смотрите все доклады Шипилёва. www.youtube.com/...ch_query=алексей шипилёв

А вообще умение нагуглить — нехилый скилл для программиста. Как бы не вообще основной.

Спасибо, дело в том, что я гуглил в печатном виде — цикл лекций по полтора часа это не самый быстрый путь изучения. Но нлпшник Шпилёв отличный (помимо основной темы)) Оракл хорошо выбрал)

Существуют много разных реализаций высокопроизводительных коллекций на Java: в качестве сторонних библиотек. Вот здесь неплохой список habrahabr.ru/...mpany/luxoft/blog/256877

В стандартную библиотеку такое не включают, потому что в большинстве случаев существующие имплементации — именно то, что нужно. Они работают за предсказуемое время, очень просты в использовании, удовлетворяют требованиям обратной совместимости и спецификации.

Спасибо, про существование сторонних быстрых библиотек я читал. У меня скорее вопрос, почему в самой java так сделали — я не думаю, что разработчики языка тупее меня, такое впечатление, что они сознательно забили на производительность, больше полугода учу язык, а все никак не привыкну)

Производительность чего конкретно Вам показалась недостаточной, и по сравнению с чем?
Что заставляет вас думать, что хотябы в 1% случаев использования коллекций их производительность может стать проблемой?

1.Производительность коллекций на основе, например, LinkedList или TreeSet по сравнению с их реализацией на параллельных массивах. Хотя-бы затраты на создание объекта и сборку мусора.
2. Предпосылка, что теоретически узким местом может стать активная работа с большой коллекцией не-на-массивах (как поступают на практике в подобных случаях?)

1) Дайте ссылку, что подразумевается под параллельными массивами, и на бенчмарки. Вряд ли вот это en.m.wikipedia.org/wiki/Parallel_array

2) На практике, мне известен лишь один класс задач, где скорость коллекций недостаточна — HFT. Попасть туда сложно, и на аутсорс такое не отдают. Почитайте про OpenHFT и LMAX Disruptor.

1) Икзектли) Мне лично легче в своем классе их парсить и конвертить на выходе, чем выучить 10 чужих методов) Понимаю, что вредная привычка)
2) Спасибо, почитаю.

Ну и, спасибо еще раз за ссылки, нашел сравнительные тесты сторонних библиотек, может кто не видел java-performance.info/...achs-hppc-koloboke-trove

Підписатись на коментарі