В этой статье рассмотрим добавление в программу на Julia пользовательского типа данных и перегрузку стандартных функций для удобной работы с новым типом.
Рубрика «структуры данных» - 3
Julia: пользовательские типы
2019-08-24 в 21:05, admin, рубрики: 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 и почему же на мой взгляд все не так однозначно, как может показаться.
Читать полностью »
Низкоуровневая реализация префиксного дерева trie на PHP
2018-07-04 в 15:30, admin, рубрики: php, trie, Алгоритмы, Программирование, структуры данныхПредисловие
Описанная здесь реализация trie на PHP делает пока слишком жирный словарь, который соответственно довольно долго загружается в память, что нивелирует довольно неплохую скорость её работы. Скорость поиска составляет ~80 тыс. слов в секунду. Словарь сделан из списка лемм словаря opencorpora.org и включает в себя 389844 слова. В несжатом виде словарь весит ~150мб, а сжатый gzip ~6мб. Однако довольно неплохие результаты быстродействия доказывают, что на чистом PHP можно сделать вполне работоспособное префиксное дерево trie.
Читать полностью »
Как мы добавили подъезды на карту и сократили размер баз на 10%
2018-06-27 в 4:12, admin, рубрики: json, Алгоритмы, базы данных, Блог компании 2ГИС, Программирование, сжатие данных, структуры данных, хранение данных
В конце прошлого месяца 2ГИС начал отображать подъезды. Входы в организации мы показываем аж с 2013 года, а подъезды — вроде бы те же входы. Так почему только сейчас? Все внутренние продукты и процессы готовы, всего-то нужно дособрать ещё чуть-чуть да подправить отображение в UI.
Кроме стандартного ответа «Были другие приоритеты» есть и не совсем стандартный: «Не всё так просто». Эта статья про то, какие были сложности и как мы их решили.
Читать полностью »
Cofree Will Tear Us Apart
2018-05-20 в 19:34, admin, рубрики: apart, cofree, haskell, структуры данных, функциональное программированиеВсем привет.
В последнее время я работаю с распределенными системами и часто я встречаюсь с проблемами работы с данными, части которых могут в находится в различных местах. Ну и так как я уже продолжительное время пишу на Haskell, описание проблемы и мощная система типов здорово помогли в дальнейшем развитии этой идеи. Речь пойдет о том, как всего одна несущая алгебраическая конструкция позволила решить задачу рециркулирующих данных в общем виде.
Что будет если объединить ArrayList и LinkedList?
2018-04-05 в 16:36, admin, рубрики: arraylist, collections, java, java core, list, nkedlist, скорость работы, список, сравнение, структуры данныхПриветствую вас!
После изучения коллекций, а именно такие реализации List, как ArrayList и LinkedList, возникла идея, а почему бы не объединить эти структуры данных в одну и посмотреть, что из этого получится.
Зачем это нужно?
- Проблема
ArrayList— у него есть начальный размер по умолчаниюDEFAULT_CAPACITYили заданный размерinitialCapacity, при превышении этого размера, создается новый массив большего размера, при этом туда копируются данные из старого массива, что по времени очень затратно и именно это дает в наихудшем случае алгоритмическую сложностьO(n) - Проблема
LinkedList— здесь наоборот, добавить новый элемент, это всего лишь добавить новую связь (создать еще однуNodeи добавить ссылку на неё), но операция получения элемента по индексу очень затратна, т.к. нужно будет пройтись по всему списку от начала, что очень затратно и даетO(n)
Решение
Что если создать такую структуру данных, при которой вставка и получение любого элемента будет за константное время. Буду использовать технологию ArrayList без пересоздания массива, что конечно же проигрывает по памяти, но выигрывает в скорости, т.к. память дешевая и её очень много, выигрыш в производительности считаю приоритетным.
Для того чтобы связать их между собой, буду использовать двусвязный список:
