Структуры данных I: Списки
Эта статья начинает серию, посвящённую структурам данных, разбираемым через "оптику" JavaScript и функционального программирования.
Мотивация
Зачем вообще программисту и, в частности, JS-разработчику данная тема? С моей точки зрения, специалист начального уровня вполне может без неё обойтись. Хотя в серьёзных технических ВУЗах как давали так и дают структуры данных именно первокурсникам.
Дело в том, что, с определённого момента, вы сами неизбежно выйдете на эту тему. Окажется, что тот же Angular базируется на библиотеке реактивного программирования RxJS, попытка разобраться в исходниках которой инициирует у вас фазу депрессии. Вам будет понятна каждая строчка, но что вообще происходит – будет оставаться загадкой, сколько бы времени вы ни сидели над кодом.
Почему? Потому что вы не знакомы с потоками и реактивным программированием. А разбирать их через код реальной библиотеки – примерно то же самое, что учить квантовую механику, не имея представления о векторах и линейной алгебре. Больно и совершенно непродуктивно.
Для того-же RxJS минимальное дерево знаний выглядит так (сверху-вниз):
Computer Science Asynchronisity
--------------------- -------------------------------
Вычисления ->
Ленивые вычисления ->
Списки -> Событийный цикл ->
Ленивые списки -> Асинхронное программирование ->
Reactivity
---------------------------
Потоки ->
RxJS API ->
Реактивное Программирование
Попытка изучить последние звенья, не владея первыми, заведомо обречена.
Структуры данных являются фундаментальной темой. Совершенно необходимой для полноценного понимания потоков. Потоки же и реактивное программирование, очевидно, выходят в мейнстрим как Фронтенд (Angular, React...), так и Бэкенд (GraphQL, NoSQL...) разработок. Поэтому всё более сложно представить себе специалиста, которого бы не касалась тема данной серии. Она требуется в работе, она требуется в обучении, её спрашивают на собеседованиях.
Стоит различать два формата технических текстов: туториал и гайд. Туториал подразумевают возможность мгновенного "практического" использования: скопипастил, запустил, что там дальше? Гайд же направлен на изучение, требует самостоятельной проработки и интереса к теме. Оба формата имеют право на жизнь. Однако большинство из нас, имеет строгое предпочтение между ними.
Данная серия статей, как и все прочие тексты автора, пишется в формате гайда. Поэтому здесь и далее, мы будем подразумевать самоценность тематики, не пытаясь промотивировать каждую строчку примером "практического" использования. Также мы не будем стесняться смены направлений, примеров на других языках и т.д. Примеров кода будет очень много. Но их потребуется прорабатывать самостоятельно. Это не серия для копипасты "работающего кода", это не серия для единоразового чтения.
В процессе чтения серии вы будете находить всё больше ассоциаций излагаемого материала с вашими текущими знаниями и практиками. К концу серии, у тех кто доберётся туда, на вопрос "Зачем это всё?" появятся собственные варианты ответа.
План действий
Насколько это возможно, мы будем избегать педантства, связанного с производительностью и прочими микро-оптимизациями. Вместо этого нас будут интересовать структуры, связи, аналогии, альтернативы и прочие интегральные вещи.
Так, например, мы будем использовать рекурсии, а не циклы, вопреки отсутствию соответствующих оптимизаций в современном V8. Рекурсия является намного более мощным и выразительным инструментом, чем цикл. Что соответствует установкам данной серии статей.
Мы будем разбираться в теме через реализацию соответствующей структуры данных "с нуля". Без использования библиотек, за исключением библиотек хелперов типа: Lodash / Ramda. Только в таком варианте мы будем уверены, что в наших знаниях не останется пробелов.
В первых частях серии мы реализуем обычные и ленивые списки. Затем сравним последние с генераторами. После чего будем готовы рассмотреть потоки. Приблизительный план серии выглядит следующим образом:
- Списки
- Ленивые списки
- Генераторы vs Ленивые списки
- Push потоки
- Pull потоки
Списки
Что такое Cписок (Linked List)? Смотрим Википедию.
In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence.
Обязательно прочитайте хотя-бы первые параграфы по указанной ссылке. Однако, имейте в виду, что под массивом там имеется в виду C-подобный массив, фиксированного размера. Массив в JS базируется на хеш-таблицах и имеет другие характеристики.
Ключевое наблюдение, для нашего текущего разговора, состоит в том, что список – это фундаментальная структура данных, заменяющая массивы во многих языках. Заменяющая, в смысле резервации канонического литерала [] под них. Первое преимущество списка проявляется в паттерн-матчинге (в силу структуры его типа). Это неприменимо к базовому JS, но важно и заслуживает упоминания.
Следующее преимущество списка – простота, включающая, в т.ч. простоту реализации ленивости на их базе. Под "ленивостью" здесь я имею в виду "по-элементную ленивость". Такие ленивые списки можно рассматривать как синхронные pull потоки, подходящие для описания длинных или бесконечных последовательностей: натуральных чисел, чисел фибоначчи и т.д.
Современный JS поддерживает генераторы, однако, многие другие языки используют ленивые структуры данных вместо них. Так что, должно быть интересно попробовать такую альтернативу.
Недостатками списков являются: O(n) вставка в конец и O(n) поиск / индексация. См. сравнительную таблицу.
Впрочем, не будем углубляться в теорию. Справочные данные будут представлять интерес после изучения материала текущей статьи, а не перед ним.
Поэтому, без дальнейших промедлений, рассмотрим простейший ссылочный список:
let A3 = null
let A2 = {value: "a2", next: A3}
let A1 = {value: "a1", next: A2}
let A0 = {value: "a0", next: A1}
console.log(A0) // {value: "a0", next: [Object]}
console.log(A0.next) // {value: "a1", next: [Object]}
console.log(A0.next.next) // {value: "a2", next: [Object]}
console.log(A0.next.next.next) // null
Или с другого ракурса:
let A0 = {
value: "a0",
next: {
value: "a1",
next: {
value: "a2",
next: null
}
}
}
– Нет ли каких-либо ограничений на вложенность? – можете спросить вы. И да и нет. Парсеры часто ограничены каким то числом уровней, например 512-ю. Но вы не будете описывать бесконечные и даже просто длинные последовательности литералами. Вы создадите генеративные функции, и тогда эти "уровни вложенности" окажутся не ограниченными ссылками, что очевидно из первого примера.
Что касается JSON, то невозможно представить бесконечный поток конечным файлом. Зато можно представить каждый элемент потока отдельным JSON объектом. И полагаться на время, а не пространство для стриминга. Мы вернёмся к этому вопросу позднее.
Базовая функция для ссылочных списков традиционно называется Cons (от "constructor"). Вы встретите это имя во многих источниках. Почему не List? Не могу говорить за McCarthy, который, вероятно, придумал термин, но Cons описывает один элемент, а список является производной. Выглядит обосновано, как по мне.
function Cons(value, next) {
return {value, next}
}
Несколько улучшает ситуацию:
let A3 = null
let A2 = Cons("a2", A3)
let A1 = Cons("a1", A2)
let A0 = Cons("a0", A1)
Мы будем использовать null для обозначения пустой cons ячейки (оригинальное имя), для краткости. В языках со статической типизацией это, обычно, отдельный тип-синглтон, называемый, например, Nil. Возможности типизации в базовом JS — ограничены, равно как и представление о ней у среднестатистического JS-разработчика. Пропустим некоторые детали.
Структура данных определяется через свои поведения. Наша следующая задача состоит в реализации базовых функций над списками. Однако, для верификации их результатов, было бы неплохо иметь парочку доп. утилит. От console.log толку не много. Давайте реализуем toArray:
let toArray = (xs) => {
if (xs) {
return [xs.value].concat(toArray(xs.next))
} else {
return []
}
}
console.log(toArray(A0)) // ["a0", "a1", "a2"]
и вспомогательную функцию log:
let logList = (list) => console.log(toArray(list))
logList(A0) // ["a0", "a1", "a2"]
Мы уже имеем prepend под псевдонимом Cons. Что насчёт append? Как мы увидели ранее, это нежелательная операция для списка. Для бесконечных списков добавление в конец вообще невозможно.
Как бы то ни было, вот append:
let append = (x, xs) => {
if (xs) {
return Cons(xs.value, append(x, xs.next))
} else {
return Cons(x, null)
}
}
logList(append("a3", A0)) // ["a0", "a1", "a2", "a3"]
Пересобираем список через Cons(xs.value, append(x, xs.next)), а затем создаём новый завершающий элемент через Cons(x, null).
Теперь concat:
let concat = (xs, ys) => {
if (xs) {
return Cons(xs.value, concat(xs.next, ys))
} else {
return ys
}
}
logList(concat(A0, A0)) // ["a0", "a1", "a2", "a0", "a1", "a2"]
И, наконец, map:
let map = (fn, xs) => {
if (xs) {
return Cons(fn(xs.value), map(fn, xs.next))
} else {
return null
}
}
logList(map(x => x + "!", A0)) // ["a0!", "a1!", "a2!"]
В следующей части мы реализуем ленивые версии всего вышеперечисленного.
P.S.
Сознаюсь в лёгком читинге. Сначала я как-бы говорю о правильных рекурсиях, а затем реализую map и другие функции в не-хвостовом стиле.
Реалистичный (не-ленивый) map выглядит более мудрёно:
let map2 = (fn, xs) => {
return (function go(acc, xs) {
if (xs) {
return go(Cons(fn(xs.value), xs.next))
} else {
return acc
}
})(null, xs)
}
Моё оправдание состоит в том, что немногие JS-программисты вообще слышали о хвостовой рекурсии. По этой причине, а также по причине невозможности протестировать эти вещи в данный момент, я опускаю излишнюю сложность. Виды рекурсий совершенно точно тянут на отдельную статью (если не серию).
Ссылки
- Data structure (wiki)
- Common data structures (wiki)
- Linked List (wiki)
- Big-O cheatsheet (site)
- LL interview questions (site)
В качестве домашнего задания, рекомендую решить любые три задачи из последней ссылки. Можно выбрать самые простые.