Меня зовут Абай Баймуканов, я – разработчик-алгоритмист. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.
Рубрика «структуры данных» - 2
Спортивное программирование: не все так просто, как кажется
2022-03-20 в 5:34, admin, рубрики: c++, Алгоритмы, жюри олимпиады, составление задач, Спортивное программирование, структуры данныхРеализация алгоритма Краскала на С#
2022-01-22 в 23:02, admin, рубрики: .net, C#, алгоритм, алгоритм краскала, Алгоритмы, графы, Краскала, математика, минимальное остовное дерево, Программирование, реализация, система непересекающихся множеств, сортировка графа, структуры данных, хранение информацииВ данной статье для реализации алгоритма будут рассмотрены:
-
Система хранения графа на основе List<>
-
Сортировка рёбер графа по весу
-
Система непересекающихся множеств
Алгоритм Краскала необходим для нахождения минимального остовного дерева графа.
О чём речь?
Если прочитав предложение выше вы невольно задались этим вопросом, то вам следует изучить пару книг по теории графов информацию, представленную в этом блоке.
Big O нотация в Swift
2022-01-14 в 19:58, admin, рубрики: big o, swift, Алгоритмы, разработка под iOS, структуры данныхЧто такое Big O нотация?
Обозначение Big O нотация (или просто Big O) — это способ оценки относительной производительности структуры данных или алгоритма, обычно по двум осям: времени и пространству.
Доминирующие операции
Способ, которым мы определяем Big O алгоритмов, заключается в том, чтобы посмотреть на худшую производительность в его доминирующих операциях.
Постоянное время - O(1)
func constantTime(_ n: Int) -> Int {
let result = n * n
return result
}Понимаем красно-черное дерево. Часть 1. Введение
2021-05-01 в 13:52, admin, рубрики: c++, бинарные деревья, структуры данныхДовольно долгое время я воевал с красно-черным деревом (далее - кчд). Вся информация, которую я находил, была в духе "листья и корень дерева всегда черные, ПОТОМУ ЧТО", "топ 5 свойств красно-черного дерева" или "3 случая при балансировке и 12 случаев при удалении ноды". Такой расклад меня не устраивал.
Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют "черной высотой"?
Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево,Читать полностью »
Immutable Trie: найди то, не знаю что, но быстро, и не мусори
2020-09-20 в 6:45, admin, рубрики: javascript, postgresql, trie, Алгоритмы, Блог компании Тензор, префиксное дерево, Программирование, структуры данныхПро префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:
И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by John Resig и разных оптимизированных версий до серии модулей в NPM.
Зачем же нам понадобилось использовать его для сервиса по сбору и анализу планов PostgreSQL, да еще и «велосипедить» какую-то новую реализацию?..
Читать полностью »
Структуры данных и алгоритмы, которыми я пользовался, работая в технологических компаниях
2020-08-15 в 14:18, admin, рубрики: Алгоритмы, Блог компании RUVDS.com, Программирование, разработка, Разработка веб-сайтов, структуры данныхПользуетесь ли вы структурами данных и алгоритмами в повседневной работе? Я обратил внимание на то, что всё больше и больше людей считает алгоритмы чем-то таким, чем, без особой связи с реальностью, технические компании, лишь по собственной прихоти, интересуются на собеседованиях. Многие жалуются на то, что задачи на алгоритмы — это нечто из области теории, имеющей слабое отношение к настоящей работе. Такой взгляд на вещи, определённо, распространился после того, как Макс Хауэлл, автор Homebrew, опубликовал твит о том, что произошло с ним на собеседовании в Google:
Google: 90% наших инженеров пользуются программой, которую вы написали (Homebrew), но вы не можете инвертировать бинарное дерево на доске, поэтому — прощайте.
Хотя и у меня никогда не возникало нужды в инверсии бинарного дерева, я сталкивался с примерами реального использования структур данных и алгоритмов в повседневной работе, когда трудился в Skype/Microsoft, Skyscanner и Uber. Сюда входило написание кода и принятие решений, основанное на особенностях структур данных и алгоритмов. Но соответствующие знания я, по большей части, использовал для того чтобы понять то, как созданы некие системы, и то, почему они созданы именно так. Знание соответствующих концепций упрощает понимание архитектуры и реализации систем, в которых эти концепции используются.
В эту статью я включил рассказы о ситуациях, в которых структуры данных, вроде деревьев и графов, а так же различные алгоритмы, были использованы в реальных проектах. Здесь я надеюсь показать читателю то, что базовые знания структур данных и алгоритмов — это не бесполезная теория, нужная только для собеседований, а что-то такое, что, весьма вероятно, по-настоящему понадобится тому, кто работает в быстрорастущих инновационных технологических компаниях.
Читать полностью »
Самые популярные структуры данных
2020-02-26 в 11:06, admin, рубрики: Анализ и проектирование систем, Программирование, структуры данных, хранение данныхЧто такое структура данных?
Проще говоря, структура данных — это контейнер, в котором хранятся данные в определенной компоновке (формате, или способе организации их в памяти). Эта «компоновка» позволяет структуре данных быть эффективной в одних операциях и неэффективной в других. Ваша цель — понять структуры данных, чтобы вы могли выбрать структуру данных, наиболее оптимальную для рассматриваемой проблемы.
Зачем нам нужны структуры данных?
Поскольку структуры данных используются для хранения данных в организованном виде, и поскольку данные являются наиболее важным элементом компьютерной науки, истинная ценность структур данных очевидна.
Независимо от того, какую проблему вы решаете, вам так или иначе приходится иметь дело с данными — будь то зарплата сотрудника, цены на акции, список покупок или даже простой телефонный справочник.
Исходя из разных сценариев, данные должны храниться в определенном формате. У нас есть несколько структур данных, которые покрывают потребность хранить данные в разных форматах.
Мобильная разработка — это просто и скучно? Доклад Яндекса
2020-01-24 в 11:26, admin, рубрики: hashmap, iOS, uikit, uikit dynamics, Блог компании Яндекс, мессенджеры, оценка сложности, очереди, разработка мобильных приложений, разработка под iOS, Системы обмена сообщениями, структуры данных
Существует миф, что создавать приложения для iOS или Android проще, чем быть, скажем, бэкенд-разработчиком. Разумеется, это не так: в работе с любой платформой есть свои сложности, всюду возникают неочевидные проблемы, требующие навыков в предметной области и за её пределами. Роман Абузяров из команды Яндекс.Чатов подготовил доклад о своих нескольких задачах, который показывает, насколько широкими знаниями должен обладать специалист по iOS. Доклад предназначен для начинающих и junior-разработчиков.
Читать полностью »
Как и зачем делать очередь на двух стеках
2020-01-14 в 13:50, admin, рубрики: Алгоритмы, интервью, Программирование, структуры данныхПривет!
Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат :)
Читать полностью »
Структуры данных в Java. Полезные методы вспомогательных классов
2019-11-16 в 12:29, admin, рубрики: arrays, Arrays.asList, Arrays.deepToString, Arrays.equals, Arrays.sort, Arrays.toString, collections, Collections.addAll, java, System.arraycopy, Блог компании EPAM, Программирование, структуры данныхПривет, habr!
Я Software Engineer в EPAM. Более 8 лет я работаю с legacy-кодом, написанном на языке Java (предвосхищая комментарии, отмечу, что понимание и терпимость к legacy началась задолго до EPAM, в заключении вы найдёте ответ, почему). Часто в работе я сталкивался с одними и теми же повторяющимися недочетами. Это побудило меня написать заметку, и начать я хочу со структур данных и вспомогательных классов Collections и Arrays. Почему-то некоторые разработчики пренебрегают их использованием, и напрасно
Разработчику на Java часто приходится сталкиваться с различными структурами данных. Это могут быть массивы, всевозможные коллекции или реализации Map. Казалось бы, всё с ними ясно и понятно, но существует несколько мелочей, о которые легко споткнуться.
Эта заметка может оказаться полезной как новичкам, которые ещё не знают этих нюансов, так и опытным разработчикам, которые могли что-то из этого забыть.
Photo by ammiel jr on Unsplash
КАТ
Сразу хочу оговориться, что этот материал актуален для Java 8. Понятно, что какие-то вещи уже сделаны лучше в Java 9+, но в большинстве крупных проектов чаще всего используется версия Java 8 (а иногда и Java 6).
Читать полностью »