Рубрика «структуры данных»

Про префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:

Immutable Trie: найди то, не знаю что, но быстро, и не мусори - 1

И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.

Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
Читать полностью »

Пользуетесь ли вы структурами данных и алгоритмами в повседневной работе? Я обратил внимание на то, что всё больше и больше людей считает алгоритмы чем-то таким, чем, без особой связи с реальностью, технические компании, лишь по собственной прихоти, интересуются на собеседованиях. Многие жалуются на то, что задачи на алгоритмы — это нечто из области теории, имеющей слабое отношение к настоящей работе. Такой взгляд на вещи, определённо, распространился после того, как Макс Хауэлл, автор Homebrew, опубликовал твит о том, что произошло с ним на собеседовании в Google:

Google: 90% наших инженеров пользуются программой, которую вы написали (Homebrew), но вы не можете инвертировать бинарное дерево на доске, поэтому — прощайте.

Хотя и у меня никогда не возникало нужды в инверсии бинарного дерева, я сталкивался с примерами реального использования структур данных и алгоритмов в повседневной работе, когда трудился в Skype/Microsoft, Skyscanner и Uber. Сюда входило написание кода и принятие решений, основанное на особенностях структур данных и алгоритмов. Но соответствующие знания я, по большей части, использовал для того чтобы понять то, как созданы некие системы, и то, почему они созданы именно так. Знание соответствующих концепций упрощает понимание архитектуры и реализации систем, в которых эти концепции используются.

Структуры данных и алгоритмы, которыми я пользовался, работая в технологических компаниях - 1

В эту статью я включил рассказы о ситуациях, в которых структуры данных, вроде деревьев и графов, а так же различные алгоритмы, были использованы в реальных проектах. Здесь я надеюсь показать читателю то, что базовые знания структур данных и алгоритмов — это не бесполезная теория, нужная только для собеседований, а что-то такое, что, весьма вероятно, по-настоящему понадобится тому, кто работает в быстрорастущих инновационных технологических компаниях.
Читать полностью »

Что такое структура данных?
Проще говоря, структура данных — это контейнер, в котором хранятся данные в определенной компоновке (формате, или способе организации их в памяти). Эта «компоновка» позволяет структуре данных быть эффективной в одних операциях и неэффективной в других. Ваша цель — понять структуры данных, чтобы вы могли выбрать структуру данных, наиболее оптимальную для рассматриваемой проблемы.

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

Читать полностью »

Существует миф, что создавать приложения для iOS или Android проще, чем быть, скажем, бэкенд-разработчиком. Разумеется, это не так: в работе с любой платформой есть свои сложности, всюду возникают неочевидные проблемы, требующие навыков в предметной области и за её пределами. Роман Абузяров из команды Яндекс.Чатов подготовил доклад о своих нескольких задачах, который показывает, насколько широкими знаниями должен обладать специалист по iOS. Доклад предназначен для начинающих и junior-разработчиков.
Читать полностью »

Привет!

Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат :)
Читать полностью »

Привет, habr!

Я Software Engineer в EPAM. Более 8 лет я работаю с legacy-кодом, написанном на языке Java (предвосхищая комментарии, отмечу, что понимание и терпимость к legacy началась задолго до EPAM, в заключении вы найдёте ответ, почему). Часто в работе я сталкивался с одними и теми же повторяющимися недочетами. Это побудило меня написать заметку, и начать я хочу со структур данных и вспомогательных классов Collections и Arrays. Почему-то некоторые разработчики пренебрегают их использованием, и напрасно

Разработчику на Java часто приходится сталкиваться с различными структурами данных. Это могут быть массивы, всевозможные коллекции или реализации Map. Казалось бы, всё с ними ясно и понятно, но существует несколько мелочей, о которые легко споткнуться.

Эта заметка может оказаться полезной как новичкам, которые ещё не знают этих нюансов, так и опытным разработчикам, которые могли что-то из этого забыть.

image
Photo by ammiel jr on Unsplash

КАТ

Сразу хочу оговориться, что этот материал актуален для Java 8. Понятно, что какие-то вещи уже сделаны лучше в Java 9+, но в большинстве крупных проектов чаще всего используется версия Java 8 (а иногда и Java 6).
Читать полностью »

В своей предыдущей статье "Рукоблудие вокруг ImmutableList в Java" я предложил вариант решения поднятой в статье "Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо" проблемы отсутствия в Java неизменяемых списков.

Решение тогда было проработано только на уровне «есть такая идея», а реализация в коде была кривовата, поэтому и воспринято всё было несколько скептически. В данной статье предлагаю доработанный вариант решения. Логика использования и API доведены до приемлемого уровня. Реализация в коде – до уровня бета-версии.

Читать полностью »

Прочитал статью "Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо" и подумал, что проблема отсутствия в Java неизменяемых списков, из-за которой грустит автор статьи, вполне решаема в ограниченных масштабах. Предлагаю свои мысли и куски кода на этот счёт.

Читать полностью »

Всем привет!

Сегодня вашему вниманию предлагается перевод вдумчиво написанной статьи об одной из базовых проблем Java — изменяемости, и о том, как она сказывается на устройстве структур данных и на работе с ними. Материал взят из блога Николая Парлога (Nicolai Parlog), чей блестящий литературный стиль мы очень постарались сохранить в переводе. Самого Николая замечательно характеризует отрывок из блога компании JUG.ru на Хабре; позволим себе привести здесь этот отрывок целиком:

Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо - 1

Николай Парлог — такой масс-медиа чувак, который делает обзоры на фичи Java. Но он при этом не из Oracle, поэтому обзоры получаются удивительно откровенными и понятными. Иногда после них кого-то увольняют, но редко. Николай будет рассказывать про будущее Java, что будет в новой версии. У него хорошо получается рассказывать про тренды и вообще про большой мир. Он очень начитанный и эрудированный товарищ. Даже простые доклады приятно слушать, всё время узнаёшь что-то новое. При этом Николай знает за пределами того, что рассказывает. То есть можно приходить на любой доклад и просто наслаждаться, даже если это вообще не ваша тема. Он преподаёт. Написал «The Java Module System» для издательства Manning, ведёт блоги о разработке ПО на codefx.org, давно участвует в нескольких опенсорсных проектах. Прямо на конференции его можно нанять, он фрилансер. Правда, очень дорогой фрилансер. Вот доклад.

Читаем и голосуем. Кому пост особенно понравится — рекомендуем также посмотреть комментарии читателей к оригиналу поста.

Читать полностью »

image

Любому программисту будет полезно понимание различных структур данных и способов анализа их производительности. Но на практике мне ни разу не пригождались АВЛ-деревья, красно-чёрные деревья, префиксные деревья, списки с пропусками, и т.д. Некоторые структуры данных я использую только для одного конкретного алгоритма и ни для чего больше (например, кучи для реализации очереди с приоритетом в алгоритме поиска пути A*).

В повседневной работе я обычно обхожусь на удивление малым количеством структур данных. Чаще всего мне пригождаются:

  • Общие массивы данных (Bulk data) — способ эффективного хранения большого количества объектов.
  • Слабые ссылки (Weak reference) (или дескрипторы (handle)) — способ обращения к объектам в bulk data без сбоев программы в случае, если объект удалён.
  • Индексы — способ быстрого доступа к отдельным подмножествам в bulk data.
  • Массивы массивов — способ хранения объектов bulk data с динамическими размерами.

Я посвящу несколько статей тому, как я обычно реализую все эти структуры. Давайте начнём с простейшей и самой полезной — bulk data.Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js