Классические алгоритмы и структуры данных на JavaScript

    Привет Всем! Я недавно запустил на GitHub проект JavaScript Algorithms and Data Structures, который содержит примеры классических алгоритмов и структур данных написанных на JavaScript с объяснениями, примерами и ссылками для дальнейшего изучения (в частности на соответствующие YouTube видео).

    Основная задача проекта — помочь программистам в изучении и применении алгоритмов и сделать это на JavaScript-е.

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

    Так же в корневом README вы найдете справочную информацию, которая может пригодиться при изучении. Например:

    • Графики Big O нотации (чтобы визуально быстро уловить разницу между O(n!) и O(n^2))
    • Список с конкретными значениями Big O (чтобы понимать насколько большое или маленькое значение у 10! (а оно у него аж 3628800))
    • Сложность выполнения базовых операций для структур данных (чтобы понять у каких структур быстрое чтение, а у каких поиск или удаление)
    • Сравнительная таблица сложности алгоритмов сортировки (чтобы понять какой способ сортировки выбрать и в каком случае, стабильная ли сортировка или нет)

    Весь код на 100% покрыт unit-тестами. Это сделано не только для того, чтобы сохранять код в работоспособном состоянии, но так же и для того, чтобы проиллюстрировать методы и случаи употребления данного конкретного алгоритма или структуры данных (что делать, например, если граф направленный в одном из алгоритмов).

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

    На данный момент в репозитории реализованы следующие структуры данных:

    • Linked List
    • Queue
    • Stack
    • Hash Table
    • Heap
    • Priority Queue
    • Trie
    • Tree (Binary Search Tree, AVL Tree)
    • Graph (both directed and undirected)
    • Disjoint Set

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

    • Brute Force Algorithms (перебор всех возможных комбинаций и выбор правильного решения)
    • Greedy Algorithms (выбор оптимального решения на каждом текущем шаге)
    • Divide and Conquer Algorithms (разделение проблемы на меньшие части и решение этих частей проблемы по-отдельности)
    • Dynamic Programming Algorithms (построение решения на основании вычисленных ранее на предыдущих шагах данных)
    • Backtracking Algorithms (перебор всех комбинаций (как и в Brute Force) с постоянной проверкой того, удовлетворяет ли текущее решение установленным ограничениям или нет, иначе — возврат на шаг назад)

    Репозиторий JavaScript Algorithms and Data Structures находится в активной разработке. Это значит, что там будут появляться новые имплементации алгоритмов и структур данных. Тем не менее, надеюсь уже сейчас этот репозиторий может быть вам полезен. Легкого кодинга!
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 31
    • –2
      Ещё бы алгоритмы архивации, и обработки изображений
      • +20
        И правда недовольные были даже в раю…
        • 0
          Какой странный комментарий, а вы точно со мной разговариваете?
          А то у меня недовольства нет, проект хорош, так почему же не принять идею для его улучшения?
      • +1

        Спасибо, что не в стол. Редкий случай хорошей подборки. Для себя же изначально собирали?

        • +7
          Да, делал для себя, хотелось в одном месте собрать полезную информацию по алгоритмам и попрактиковаться заодно.
          • +1
            Присоединяюсь к «спасибо»! Очень отличная подборка.
            • +1

              Могу подкинуть свои алгоритмы, но шлифовать их и покрывать тестами будешь сам

              • +2
                Ну, я так могу книжку Кормена подкинуть с десятками алгоритмов и псевдокодом.
          • +2
            Я хоть и особо не работаю с js, но вы все отлично оформили, приятно глазу посмотреть!

            Глазу зацепилась таблица со сложностью для Hash Table. Все-таки среднее время поиска/вставки/удаления у нее будет константным, и только в худшем случае, если подобрана совсем неудачная хеш-функция, сложность будет линейная.
            • +1
              Да, Вы правы, что поиск/вставка/удаление будут линейными в hash table, но это при условии хорошо подобранной хеш-функции.

              В табличке я указал O(n) для самого худшего случая, когда все данные попадают в одну «ячейку». Далее уже сложность зависит от реализации этой самой «ячейки» (массив это или linked list или что-то еще).

              Я обновил табличку в репозитории и в комментариях указал этот нюанс.
            • +1
              Супер подборка, спасибо большое!

              Вопрос про hash table — а почему сложность-то вставки и извлечениям линейные? У неё же вставка, получение = все равно О(1), если hash без коллизий.

              Разве не?

              Но за подборку — огромное спасибо!!!
              • +3
                Выбраная хэш-функция зело плохая.
                const hash = key => Array.from(key).reduce((hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)), 0);
                const hashes = ['key', 'kye', 'eyk', 'eky', 'yke', 'yek'].map(hash);
                console.log(hashes)


                Хотя бы стандартную из java взять надо.
                const hash = key => Array.from(key).reduce((hashAccumulator, keySymbol) => 31 * hashAccumulator + keySymbol.charCodeAt(0), 0)
                • –1
                  О(1) работает только до шага определения нужного bucket. Если элемент там не один, включается поиск, который может быть реализован по разному. В данном случае реализован линейный поиск, потому получается О(n), т.к. при неудачных входных данных все элементы окажутся в одной корзине.
                  • +2
                    В среднем будет за O(loadFactor), а за этим самым loadFactor можно (и нужно) следить.
                  • +1
                    Указанный вариант сложности предполагает как-раз «плохую» хеш-функцию, так, что все данные будут попадать в одну ячейку. Я обновил табличку в репозитории и указал, что в случае с идеальной хеш функцией сложность будет действительно O(1).
                  • +1
                    Уж больно джавовский подход написания кода, немного увеличивает вес самих алгоритмов. Чем проще, тем лучше виден сам алгоритм. Я не против ООП, это мое имхо.
                    • +2
                      Почему для хеш-таблицы выбран именно связный список? Обычный массив работает не хуже: асимптотика та же самая, но нагрузка на GC меньше и локальность обращений к памяти лучше.
                      • +1

                        Думаю, автор хотел сделать акцент на принципиальную реализацию, а не на нюансы js. Так то можно было и обычный object взять.

                        • +1
                          Использование массива вместо двусвязного списка может оказаться хорошей идеей в любом языке программирования. Если же библиотека использует связные списки — то всегда делается особая реализация именно для хеш-таблицы.

                          Вообще, связные списки в качестве готовых контейнеров работают ужасно: высокие накладные расходы и почти полное отсутствие плюсов.
                          • +3

                            А обычный массив мы будем реаллоцировать и копировать при каждой коллизии? Или все таки не совсем обычный массив нужен, а какой-нибудь array-list? И какой толк от локальности, если у нас в значениях например строки лежат и в бакете у нас указатели?
                            Мне кажется, для академических целей реализация автора вполне подходит. Понятно, что «на самом деле» все по-другому. Но общее представление о структуре даёт.

                            • 0
                              А обычный массив мы будем реаллоцировать и копировать при каждой коллизии?
                              Зачем?
                              en.wikipedia.org/wiki/Open_addressing
                              • +2
                                В этой ветке обсуждается реализация bucket hash table, а конкретно — какую структуру данных использовать для хранения значений в бакете.
                      • +2
                        Алгоритмическая сложность для Binary Search Tree log(n) же. n будет только в худшем несбалансированном случае.
                        • +1
                          Да, все верно, O(log(n)) для сбалансированного дерева и O(n) в худшем несбалансированном случае. Я обновил табличку в репозитории и добавил комментарий к BST.
                        • +1
                          Есть еще mnemonist.js
                          • +1
                            Я бы добавил timsort в секцию алгоритмов сортировки. Он довольно популярный и используемый.
                            • +1
                              Ты сделал очень крутую работу! Спасибо!

                              Я тоже что-то подобное начинал делать. Я правда просто решил переписать все примеры из книги на Dart (да он еще жив). Вот тут
                              Там еще идея была переписать все «воркшопы», которые представлены в книге. Они показывают как работает алгоритм, но там я остановился только на Array.
                              Надеюсь что я тоже когда-то закончу что запланировал!
                              Если нужна будет помощь, то пиши, я с радостью :)
                              • +1
                                Спасибо за работу и за щедрость!
                                • +1
                                  может кому полезно будет, давно о ресурсе знаю
                                  с него можно было бы реализовать ещё… и мне всегда казалось, что Radix очень удачный алгоритм, только не многие его используют почему-то (ещё хабр-статья на С++)
                                  • 0
                                    Всё мечтаю продолжить эту работу, да времени катастрофически нет… Уже накопилось некоторое количество новых сортировок, которые ещё не заливал на этот сайт и есть планы по выкладыванию в общественный доступ самого excel-приложения с макросами, с помощью которого делаю gif-анимацию алгоритмов.

                                  • 0
                                    Еще есть вот такая визуализация:
                                    www.cs.usfca.edu/~galles/visualization/Algorithms.html

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

                                    Самое читаемое