Какие структуры данных должен знать JavaScript разработчик?

Micasa

Frontend and mobile developer

Всего 6 записей

Последние статьи

Топ советов и хитростей NPM Какие структуры данных должен знать JavaScript разработчик?Как создать дискорд бота?gatsby-starter-calpa-blog README About Гостевая комната

Рекомендуемые ссылки

React Official Website Mozile Developer Network Javascript lessons

Введение

Понимание стуктур данных помогает во многих аспектах программирования. Не нужно использовать какую-то определенную реализацию, в котором бы вы использовали дерево или графы. Скажу больше, не думаю, что правильно реализовывал структуры данных за мои 8 лет опыта программирования, однако понимание их работы помогало мне в некоторых кейсах.

Понимание работы структур данных, их поведении можно использовать и в во многих областях. К примеру, нам нужно описать архитектуру на основанную на микросервисах, как ее описать? Теперь посмотрим на следующее изображение: Надеюсь, ты понимаешь к чему я клоню мармеладка :D Даже взвешенный граф можно рассматривать как представление архитектуры. При этом учитывать вес ребер (к примеру, как время обращения одного сервиса к другому). То же самое можно сказать и о других структурах.

Примечание: некоторые из этих структур могут быть легко представлены массивами, но вам нужно посмотреть немного дальше, чтобы понять всю их мощь. Структуры данных - это не только способ структурирования данных, но и связанная с ней логика. То, как вы вставляете данные, что с ними происходит внутри, и даже то, как вы извлекаете данные из своей структуры. В этом заключается настоящая магия структур данных и весь смысл их существования. В противном случае мы бы не парились и использовали массивы.

Очереди

Предположим, вам нужно обработать список задач в порядке их внесения, для решения поставленной проблемы подойдут очереди. Очереди - это простая структура, в которую вы можете вносить данные и извлекать их в соответствии с подходом FIFO: First In First Out. Другими словами, это структура данных похожа на очередь в KFC. Если человек пришел раньше, соответственно обслужат его быстрее.

Queue

Как видно из диаграммы выше, сама структура и реализация просты, особенно если вы используете массивы в качестве базовой структуры данных.

class Queue {
    data = []
    maxSize

    constructor(initialData, maxSize = -1) {
        this.data = Array.isArray(initialData) ? initialData : (typeof initialData == "undefined" ? [] : [initialData])
        this.maxSize = maxSize
    }
    
    isFull() {
        return this.maxSize != -1 ? (this.data.length == this.maxSize) : false
    }
    
    isEmpty() {
        return this.data.length == 0
    }
    
    enqueue(item) {
        if(this.isFull()) {
            return false
        }
        this.data.push(item)
    }
    
    *generator() {
        while(!this.isEmpty()) {
            yield this.data.shift()
        }
    }
    
    dequeue() {
       const { value, done } = this.generator().next() 
       if(done) return false
       return value
    }
}

Два основных метода из этой реализации - это методы enqueue и dequeue. С помощью первого вы можете добавлять элементы в очередь, а с помощью последнего - удалять.

Как видите, я выбрал массив для базовой структуры данных, потому что он значительно упрощает оба метода.

Постановка в очередь - это то же самое, что вставка элемента в массив, а исключение из очереди решается простым вызовом shift, который удаляет первый элемент и также возвращает его.

Функция генератора была добавлена в качестве дополнительной вишенки, позволяющей выполнять операции, подобные показанной ниже:

let q = new Queue(3, 2)

// Без генератора
q.enqueue(1)
q.enqueue(2) //ignored...

// С генератором
let x = 0
while(x = q.dequeue()) {
    console.log(x)
}

Помимо простой очереди, которую я вам здесь показываю, вы также можете найти:

Очереди приоритета (элементы отсортированы внутри по значению приоритета);
Круговые очереди (последний элемент которых указывает на первый);
Двойная очередь (позволяет добавлять и удалять элементы как вначале, так и в конце.

Стэк

Я пиши о стэке после очереди, потому что они похожи, настолько, что иногда их путают друг с другом.

Вы можете думать об этой структуре данных как о стопке книг, если вы начнете класть одну поверх другой, а когда вы захотите получить одну, вам придется удалить все книги с нее. Этот способ обработки данных известен как FILO или First In Last Out.

Стеки полезны для изменение порядка в списке, так как вы можете перемещаться по списку от первого до последнего и сохранять каждый элемент в стек, затем вы начнете их извлекать (вынимая их по шаблону FILO) и последний из них будет первым элементом исходного списка.

Еще один интересный вариант использования, который мы видели бесчисленное количество раз: возможность отменить действие. Если вы хотите что-то отменить, вы либо пытаетесь отменить последнее действие, либо пытаетесь отменить несколько действий.

class Operation {

    constructor(val) {
        this.value = val
    }
}

class Add extends Operation {

    apply(value) {
        return value + this.value
    }
    
    undo(value) {
        return value - this.value 
    }
}

class Times extends Operation {
    apply(value) {
        return value * this.value
    }
    undo(value) {
        return value / this.value
    }
}

class Stack {

    constructor() {
        this.value = 0
        this.operations = new Stack()
    }
    
    add(op) {
        this.value = op.apply(this.value)
        this.operations.add(op) 
    }
    
    undo() {
        if(this.operations.isEmpty()) {
            return false
        }
        this.value = (this.operations.pop()).undo(this.value)
    }
}

Вы можете увидеть, как мы используем собственный стек. Операции представлены в виде классов, каждый из которых имеет два метода:

apply (делает операцию эффективной)
undo (представляет собой противоположную операцию)

В нашем настраиваемом стеке также есть метод отмены, который использует структуру стека, в которой хранятся все операции, и может отменять их эффекты одну за другой.

И, как вы догадались, реализация стека почти идентична классу очереди из предыдущего:

class Stack {
    data = []
    maxSize

    constructor(initialData, maxSize = -1) {
        this.data = Array.isArray(initialData) ? initialData : (typeof initialData == "undefined" ? [] : [initialData])
        this.maxSize = maxSize
    }
    
    isFull() {
        return this.maxSize != -1 ? (this.data.length == this.maxSize) : false
    }
    
    isEmpty() {
        return this.data.length == 0
    }
    
    add(item) {
        if(this.isFull()) {
            return false
        }
        this.data.push(item)
    }
    
    *generator() {
        while(!this.isEmpty()) {
            yield this.data.pop()
        }
    }
    
    pop() {
       const { value, done } = this.generator().next() 
       if(done) return false
       return value
    }
}

Вы можете заметить единственную разницу? Проверьте 27 строку. К счастью для нас, класс Array из JavaScript также предоставляет нам метод pop, который делает то же самое: он удаляет последний добавленный элемент в массив и возвращает его.

Стеки и очереди - это круто, но давайте посмотрим на что-то более сложное, но при этом более мощное и универсальное.

Деревья

За деревьями стоит много теории... Я не буду вдаваться в подробности, потому что теория есть в интернете, просто загляните в Википедию или одну из многих книг, посвященных дереьям. Вместо этого я дам вам короткую версию.

Дерево - это рекурсивно определенная структура, образованная родительским узлом и несколькими дочерними узлами, связанными с одним родительским. Как я уже сказал, это рекурсивное определение в том смысле, что каждый из этих дочерних узлов может одновременно быть родительскими узлами для других дочерних узлов.

![Tree]/images/2020-11-30-stuctures-3.png)

На приведенной выше диаграмме показано, как растет дерево, есть несколько интересных фактов:

Родственные узлы (то есть узлы с одним и тем же родителем) не соединяются друг с другом.
Дерево обычно изображается растущим вниз (в отличие от обычного дерева, растущего вверх).
Узлы не могут быть связаны сами с собой (я знаю, это звучит странно, но подождите, пока мы не дошли до графов...).

Основные определения используемые в деревьях:

Корневой узел(родительский узел): узел с дочерними узлами под ним.
Концевой узел: узел без связанных с ним дочерних узлов.
Ребро: связь между двумя узлами.

А из диаграммы ниже мы также можем определить еще несколько вещей:

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

При этом существует несколько различных типов деревьев в зависимости от логики, связанной с вставкой и извлечением данных из структуры:

Двоичные деревья - это деревья, в которых родительские узлы могут иметь до двух дочерних элементов.
Деревья двоичного поиска - особый вид двоичных деревьев. При вставке элемента в дерево сравнивает его со значением родительского узла, и если оно меньше, оно проверяет левый дочерний элемент, в противном случае он проверяет правый. Эта логика повторяется до тех пор, пока вы не найдете листовой узел. Классический вариант использования для них - сохранить упорядоченную структуру элементов с минимальными усилиями.
Поиск в глубину (DFS) - это способ прохода дерева в поисках чего-либо. Это работает следующим образом: сначала вы проходите всю левую сторону и постепенно проверяете правую сторону.

Посмотрите на диаграмму выше, если вы напечатаете значение каждого узла, когда дойдете до него, вы получите: A-> B-> C-> D-> E. Порядок узлов определяется методом DFS.

Хочу отметить, что направление обхода можно менять (идти справа налево). Этот алгоритм может использоваться и с графами.

Я знаю, это звучит так, будто это очень похоже, но позвольте мне показать вам пример того, как вы реализуете двоичное дерево поиска (один из моих любимых видов деревьев), чтобы увидеть, насколько они не такие сложные и на самом деле очень полезны.

Ниже приведена реализация бинарного дерева

class BinaryTreeNode {

    constructor(value) {
        this.value = value
        this.left_child = null
        this.right_child = null
    }
    
    compare(v) {
        if(this.value > v) return -1
        if(this.value == v) return 0
        if(this.value < v) return 1
    }
}

module.exports = class BST {

    constructor() {
        this.root_node = null
    }
    
    add(elem) {
        if(!this.root_node) {
            this.root_node = new BinaryTreeNode(elem)
            return
        }
        
        let inserted = false
        let currentNode = this.root_node
        do {
            let comp = currentNode.compare(elem)
            if(comp == -1) {
                if(!currentNode.left_child) {
                    currentNode.left_child = new BinaryTreeNode(elem)
                    inserted = true
                } else {
                    currentNode = currentNode.left_child
                }
            }
            
            if(comp != -1) {
                if(!currentNode.right_child) {
                    currentNode.right_child = new BinaryTreeNode(elem)
                    inserted = true
                } else {
                    currentNode = currentNode.right_child
                }
            }
        } while (!inserted)
    }
    
    inorder(parent) {
        if(parent) {
            this.inorder(parent.left_child)
            console.log(parent.value)
            this.inorder(parent.right_child)
        }
    }
    
    print() {
        this.inorder(this.root_node)
    }
}

Графы

Узлы в графе в отличие от деревьев неограничены (узел может быть соеденен с любым другим и в том числе с самим собой).

Графы универсальны! Их можно использовать для представления практически любого сценария, в котором объекты связаны друг с другом. Сценарии использования варьируются от макетов сети до архитектур на основе микросервисов, реальных карт...

Графы настолько практичная структура данных, что существуют даже движки СУБД основанные на концепции графов.

Ниже приведена реализация графов на скорую руку в JavaScript, включая метод обхода с поиском в глубину.

class Node {

    constructor(value) {
        this.value = value
        this.links = []
    }
    
    linkTo(node, weight) {
        this.links.push(new Link(this, weight, node))
    }
}

class Link {

    constructor(a, weight, b) {
        this.left = a;
        this.weight = weight
        this.right = b
    }
}

class Graph {

    constructor(root_node) {
        this.root_node = root_node
        this.dfs_visited = new Set();
    }
    
    dfs(starting_node) {
        if(!starting_node) starting_node = this.root_node
        let node = starting_node 
        console.log(node.value);
        this.dfs_visited.add(node);
        node.links.forEach( neighbour => {
            if (!this.dfs_visited.has(neighbour.right)) {
                this.dfs(neighbour.right);
            }
        })
    }

}

Из примера выше мы видим, что каждый узел (Node) имеет свой набор ссылок на другие узлы. При этом мы получаем взвешенный граф, то есть помимо ссылки на узел мы еще задаем вес (вес, к примеру, может указывать на задержку между узлами в ЛВС). Метод dfs позабоится об обходе графа, убедившись в том, что мы посетили каждый узел графа только один раз.

Пример использования:

// Объявление узлов
let A = new Node("A")
let B = new Node("B")
let C = new Node("C")
let D = new Node("D")
let E = new Node("E")
let F = new Node("F")
let G = new Node("G")

// Объявление связей узлов
A.linkTo(B, 1)
A.linkTo(C, 2)
B.linkTo(D, 1)
C.linkTo(E, 10)
D.linkTo(E, 10)
D.linkTo(F, 1)
D.linkTo(G, 1)
G.linkTo(G, 1)

let g = new Graph(A)
// Обход графа
g.dfs()

Результат будет следующмим:

A
B
D
E
F
G
C

Другими словами, каждый узел посещался только один раз. С помощью грфаов вы можете делать более интересные вещи, например, реализовать алгоритм Дейкстры, чтобы найти кратчайший путь между двумя узлами, или реализовать нейронную сеть.

Hash Map

Последняя структура данных, о которой я расскажу в этой статье - это Hash Map. Она позволяет вам хранить пары ключ-значение и довольно быстро извлекать их (она имеет порядок сложности O(1) в лучшем случае, что круто!).

Давайте представим, у вас есть 300 пар ключ-значение, которые вам нужно сохранить в памяти, вы можете легко прибегнуть к массиву для этого. Если вам нужно получить конкретный элемент, вам нужно будет обойти весь массив в поисках его (это будет наихудшим случаем, учитывая, что элемент, который вы ищете, является последним). В случае с 300 элементами - это не проблема, но если бы это был вариант использования, когда вам нужно будет искать один элемент в списке из 1 000 000 элементов? Это займет некоторое время, и если базовое число продолжает расти, массивы в этом случае становятся все менее и менее полезными.

Попробуем теперь рассмотреть в качестве альтернативы Hash Map. Hash Map позволяют вам создать структуру, которую вы можете использовать, где ключ может использоваться для быстрого доступа к значению в постоянное время. В JavaScript реализовать Hash Map значительно проще, учитывая, что у нас есть объектные литералы, которые мы можем использовать для добавления случайных свойств (то есть наших ключей). Вот быстрая реализация Hash Map, которая позволяет использовать числовые ключи.

class HashMap {
    
    constructor() {
        this.map = {}
    }
    
    hash(k) {
        return k % 10
    }
    
    add(key, value) {
        let k = this.hash(key)
        if(!this.map[k]) {
            this.map[k] = []
        }
        this.map[k].push(value)
    }
    
    get(key) {
        let k = this.hash(key)
        return this.map[k]
    }
    
}

let h = new HashMap()

h.add(10, "hello")
h.add(100001, "world")
h.add(1, "this is a string")

console.log(h)

Результат выполнения скрипта будет следующий:

HashMap {
  map: { '0': [ 'hello' ], '1': [ 'world', 'this is a string' ] }
}

Обратите внимание, как "world" и "this is a string" связаны с одним и тем же ключом, это так называемый хэш-конфликт. В данном случае hash метод вычисляет ключ используя операцию остаточно деления на 10 для гарантирантированного хранения до 10 ключей. Это реализация полезна, если у вас ограниченный объем памяти. Реализуете метода хеширования во многом определяет эффективность hash map'a.

При правильной реализации эта структура настолько эффективна, что широко используется при индексация базы данных (обычно вы устанавливаете поля в качестве индексов, когда вам нужна операция быстрого поиска) и даже при реализации кеширования, позволяя использовать быстрый поиск для извлечения кешированного контента. Как вы догадались это структура достаточно эффективна, если вы хотите иметь быстрый и повторяющийся поиск.

Вывод

Понимание структур данных, независимо от того, используете ли вы их в повседневных задачах или нет, очень важно. Оно открывает вам глаза на известные шаблоны и дает на них взглянуть под иным углом.

Можете поиграться с приведенными выше реализациями. Попробуйте создать свою собственную реализацию. Какой из них ваш любимый структура данных? Оставьте комментарий внизу и поделитесь им со товарищами!