Прочитал статью "Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо" и подумал, что проблема отсутствия в Java неизменяемых списков, из-за которой грустит автор статьи, вполне решаема в ограниченных масштабах. Предлагаю свои мысли и куски кода на этот счёт.
Рубрика «структуры данных» - 3
Рукоблудие вокруг ImmutableList в Java
2019-10-05 в 18:21, admin, рубрики: ImmutableList, java, наследование, ооп, Программирование, структуры данныхНеизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо
2019-10-04 в 12:43, admin, рубрики: guava, java, Блог компании Издательский дом «Питер», наследование, ооп, Программирование, Профессиональная литература, структуры данных, чистый кодВсем привет!
Сегодня вашему вниманию предлагается перевод вдумчиво написанной статьи об одной из базовых проблем Java — изменяемости, и о том, как она сказывается на устройстве структур данных и на работе с ними. Материал взят из блога Николая Парлога (Nicolai Parlog), чей блестящий литературный стиль мы очень постарались сохранить в переводе. Самого Николая замечательно характеризует отрывок из блога компании JUG.ru на Хабре; позволим себе привести здесь этот отрывок целиком:
Николай Парлог — такой масс-медиа чувак, который делает обзоры на фичи Java. Но он при этом не из Oracle, поэтому обзоры получаются удивительно откровенными и понятными. Иногда после них кого-то увольняют, но редко. Николай будет рассказывать про будущее Java, что будет в новой версии. У него хорошо получается рассказывать про тренды и вообще про большой мир. Он очень начитанный и эрудированный товарищ. Даже простые доклады приятно слушать, всё время узнаёшь что-то новое. При этом Николай знает за пределами того, что рассказывает. То есть можно приходить на любой доклад и просто наслаждаться, даже если это вообще не ваша тема. Он преподаёт. Написал «The Java Module System» для издательства Manning, ведёт блоги о разработке ПО на codefx.org, давно участвует в нескольких опенсорсных проектах. Прямо на конференции его можно нанять, он фрилансер. Правда, очень дорогой фрилансер. Вот доклад.
Читаем и голосуем. Кому пост особенно понравится — рекомендуем также посмотреть комментарии читателей к оригиналу поста.
Структуры данных для программистов игр: bulk data
2019-10-04 в 4:23, admin, рубрики: bulk data, C, c++, виртуальная память, Клиентская оптимизация, массивы, массивы структур, Программирование, разработка игр, структуры данных, структуры массивов, указатели
Любому программисту будет полезно понимание различных структур данных и способов анализа их производительности. Но на практике мне ни разу не пригождались АВЛ-деревья, красно-чёрные деревья, префиксные деревья, списки с пропусками, и т.д. Некоторые структуры данных я использую только для одного конкретного алгоритма и ни для чего больше (например, кучи для реализации очереди с приоритетом в алгоритме поиска пути A*).
В повседневной работе я обычно обхожусь на удивление малым количеством структур данных. Чаще всего мне пригождаются:
- Общие массивы данных (Bulk data) — способ эффективного хранения большого количества объектов.
- Слабые ссылки (Weak reference) (или дескрипторы (handle)) — способ обращения к объектам в bulk data без сбоев программы в случае, если объект удалён.
- Индексы — способ быстрого доступа к отдельным подмножествам в bulk data.
- Массивы массивов — способ хранения объектов bulk data с динамическими размерами.
Я посвящу несколько статей тому, как я обычно реализую все эти структуры. Давайте начнём с простейшей и самой полезной — bulk data.Читать полностью »
И ещё о сортировках
2019-09-15 в 18:04, admin, рубрики: boost, BSD, c++, processing, stl, Алгоритмы, алгоритмы сортировки, Программирование, сортировки, строки, структуры данныхИ ещё о сортировках
Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать полностью »
Julia: пользовательские типы
2019-08-24 в 21:05, admin, рубрики: Julia, интерфейсы, Программирование, структуры данныхВ этой статье рассмотрим добавление в программу на Julia пользовательского типа данных и перегрузку стандартных функций для удобной работы с новым типом.
Почему на собеседованиях так часто спрашивают про связные списки
2019-06-06 в 13:32, admin, рубрики: C, Алгоритмы, Карьера в IT-индустрии, связный список, собеседования, структуры данныхПримечание переводчика: оригинальная статья опубликована в серии твитов
Вероятно, вы уже читали кучу объяснений, почему обработка связных списков — плохой вопрос для собеседования. Я же в первую очередь хочу объяснить, откуда он вообще взялся. Всем пристегнуться, погружаемся в теорию игр ИСТОРИЮ!
Хотя индустрия программного обеспечения процветала в 80-е годы, но действительно взлетела в 90-е. В это десятилетие число работников отрасли в США утроилось и превысило миллион человек. Со взрывным ростом пришла необходимость нанимать массу сотрудников и оценивать их.
Что нужно оценить? Ну, в первую очередь, знание языков. Согласно TIOBE, в 1986−2006 годы самым популярным языком в мире был C, далее следовал C++. К 2006 году Java вышла на первое место, но C остался рядом.
C работал близко к железу без лишних абстракций. Пустой словарь Python расходует аж 288 байт, то есть 5% всего объёма памяти первого поколения Apple II. Абстракции слишком дороги, слишком много накладных расходов. Если вам нужна сложная структура данных, вы должны построить её самостоятельно с помощью массивов, структур и указателей.
Читать полностью »
Чем быстрее вы забудете ООП, тем лучше для вас и ваших программ
2019-05-17 в 4:59, admin, рубрики: архитектура приложений, критика, ооп, паттерны проектирования, Программирование, Совершенный код, структуры данных
Объектно-ориентированное программирование — чрезвычайно плохая идея, которая могла возникнуть только в Калифорнии.
— Эдсгер Вибе Дейкстра
Возможно, это только мои ощущения, но объектно-ориентированное программирование кажется стандартной, самой распространённой парадигмой проектирования ПО. Именно его обычно преподают студентам, объясняют в онлайн-туториалах и, по какой-то причине, спонтанно применяют даже тогда, когда не собирались этого делать.
Я знаю, насколько она привлекательна, и какой замечательной кажется эта идея на поверхности. На разрушение её чар у меня ушли многие годы, и теперь я понимаю, насколько она ужасна, и почему. Благодаря этой точке зрения у меня есть чёткая уверенность в том, что люди должны осознать ошибочность ООП и знать решения, которые можно использовать вместо него.
Многие люди и раньше обсуждали проблемы ООП, и в конце этого поста я приведу список своих любимых статей и видео. Но прежде я хочу поделиться собственным взглядом.
Читать полностью »
Экзотические структуры данных: Modified Merkle Patricia Trie
2019-04-03 в 6:58, admin, рубрики: Ethereum, merkle patricia tree, modified merkle patricia trie, open source, python, криптография, Программирование, структуры данных"Какого дьявола я должен помнить наизусть все эти чёртовы алгоритмы и структуры данных?".
Примерно к этому сводятся комментарии большинства статей про прохождение технических интервью. Основной тезис, как правило, заключается в том, что всё так или иначе используемое уже реализовано по десять раз и с наибольшей долей вероятности заниматься этим рядовому программисту вряд ли придётся. Что ж, в какой-то мере это верно. Но, как оказалось, реализовано не всё, и мне, к сожалению (или к счастью?) создавать Структуру Данных всё-таки пришлось.
Загадочное Modified Merkle Patricia Trie.
Так как на хабре информации об этом дереве нет вообще, а на медиуме — немногим больше, хочу поведать о том, что же это за зверь, и с чем его едят.
Big O
2019-03-22 в 20:19, admin, рубрики: big-O notation, javascript, Алгоритмы, бинарный поиск, Программирование, сложность, сложность алгоритма, структуры данныхПримечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».
Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.
Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.
Структуры данных
Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.
Часто, выбирая ту или иную структуру, мы просто копируем общепринятое решение. В большинстве случаев этого достаточно. Но на самом деле, не разобравшись в сложности алгоритмов, мы не можем сделать осознанный выбор. К теме структур данных можно переходить только после сложности алгоритмов.
Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.
Читать полностью »
Как подготовиться к собеседованию в Google и не пройти его. Дважды
2018-08-21 в 5:29, admin, рубрики: Google, Алгоритмы, интервью, Карьера в IT-индустрии, структуры данных, Учебный процесс в ITЗаголовок статьи звучит как epic fail, но на самом деле все не так однозначно. Да и в общем и целом эта история закончилась весьма позитивно, хоть и не в Google. Но это уже тема для другой статьи. В этой же статье я расскажу о трех вещах: каким образом проходил мой процесс подготовки, каким образом проходили интервью в Google и почему же на мой взгляд все не так однозначно, как может показаться.
Читать полностью »