Основная задача проекта — помочь программистам в изучении и применении алгоритмов и сделать это на 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 находится в активной разработке. Это значит, что там будут появляться новые имплементации алгоритмов и структур данных. Тем не менее, надеюсь уже сейчас этот репозиторий может быть вам полезен. Легкого кодинга!
Комментарии (28)
maggg
23.05.2018 22:38Спасибо, что не в стол. Редкий случай хорошей подборки. Для себя же изначально собирали?
trehleb Автор
23.05.2018 22:46+4Да, делал для себя, хотелось в одном месте собрать полезную информацию по алгоритмам и попрактиковаться заодно.
oYASo
24.05.2018 03:36Я хоть и особо не работаю с js, но вы все отлично оформили, приятно глазу посмотреть!
Глазу зацепилась таблица со сложностью для Hash Table. Все-таки среднее время поиска/вставки/удаления у нее будет константным, и только в худшем случае, если подобрана совсем неудачная хеш-функция, сложность будет линейная.trehleb Автор
25.05.2018 07:37Да, Вы правы, что поиск/вставка/удаление будут линейными в hash table, но это при условии хорошо подобранной хеш-функции.
В табличке я указалO(n)для самого худшего случая, когда все данные попадают в одну «ячейку». Далее уже сложность зависит от реализации этой самой «ячейки» (массив это или linked list или что-то еще).
Я обновил табличку в репозитории и в комментариях указал этот нюанс.
capjdcoder
24.05.2018 05:24Супер подборка, спасибо большое!
Вопрос про hash table — а почему сложность-то вставки и извлечениям линейные? У неё же вставка, получение = все равно О(1), если hash без коллизий.
Разве не?
Но за подборку — огромное спасибо!!!aleksandy
24.05.2018 06:28Выбраная хэш-функция зело плохая.
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)
Mikluho
24.05.2018 06:39-1О(1) работает только до шага определения нужного bucket. Если элемент там не один, включается поиск, который может быть реализован по разному. В данном случае реализован линейный поиск, потому получается О(n), т.к. при неудачных входных данных все элементы окажутся в одной корзине.
s-kozlov
24.05.2018 14:23+1В среднем будет за O(loadFactor), а за этим самым loadFactor можно (и нужно) следить.
trehleb Автор
25.05.2018 08:00Указанный вариант сложности предполагает как-раз «плохую» хеш-функцию, так, что все данные будут попадать в одну ячейку. Я обновил табличку в репозитории и указал, что в случае с идеальной хеш функцией сложность будет действительно
O(1).
kolesoffac
24.05.2018 09:34Уж больно джавовский подход написания кода, немного увеличивает вес самих алгоритмов. Чем проще, тем лучше виден сам алгоритм. Я не против ООП, это мое имхо.
mayorovp
24.05.2018 09:47Почему для хеш-таблицы выбран именно связный список? Обычный массив работает не хуже: асимптотика та же самая, но нагрузка на GC меньше и локальность обращений к памяти лучше.
f0rk
24.05.2018 11:28Думаю, автор хотел сделать акцент на принципиальную реализацию, а не на нюансы js. Так то можно было и обычный object взять.
mayorovp
24.05.2018 11:39Использование массива вместо двусвязного списка может оказаться хорошей идеей в любом языке программирования. Если же библиотека использует связные списки — то всегда делается особая реализация именно для хеш-таблицы.
Вообще, связные списки в качестве готовых контейнеров работают ужасно: высокие накладные расходы и почти полное отсутствие плюсов.f0rk
24.05.2018 11:49А обычный массив мы будем реаллоцировать и копировать при каждой коллизии? Или все таки не совсем обычный массив нужен, а какой-нибудь array-list? И какой толк от локальности, если у нас в значениях например строки лежат и в бакете у нас указатели?
Мне кажется, для академических целей реализация автора вполне подходит. Понятно, что «на самом деле» все по-другому. Но общее представление о структуре даёт.anjensan
25.05.2018 15:16-1А обычный массив мы будем реаллоцировать и копировать при каждой коллизии?
Зачем?
en.wikipedia.org/wiki/Open_addressing
Ogoun
24.05.2018 16:44+2Алгоритмическая сложность для Binary Search Tree log(n) же. n будет только в худшем несбалансированном случае.
trehleb Автор
25.05.2018 08:02Да, все верно, O(log(n)) для сбалансированного дерева и O(n) в худшем несбалансированном случае. Я обновил табличку в репозитории и добавил комментарий к BST.
nlog
25.05.2018 08:03Я бы добавил timsort в секцию алгоритмов сортировки. Он довольно популярный и используемый.
artem-galas
25.05.2018 08:03Ты сделал очень крутую работу! Спасибо!
Я тоже что-то подобное начинал делать. Я правда просто решил переписать все примеры из книги на Dart (да он еще жив). Вот тут
Там еще идея была переписать все «воркшопы», которые представлены в книге. Они показывают как работает алгоритм, но там я остановился только на Array.
Надеюсь что я тоже когда-то закончу что запланировал!
Если нужна будет помощь, то пиши, я с радостью :)
zacisco
25.05.2018 08:09может кому полезно будет, давно о ресурсе знаю
с него можно было бы реализовать ещё… и мне всегда казалось, что Radix очень удачный алгоритм, только не многие его используют почему-то (ещё хабр-статья на С++)
RouR
Ещё бы алгоритмы архивации, и обработки изображений
AstarothAst
И правда недовольные были даже в раю…
RouR
Какой странный комментарий, а вы точно со мной разговариваете?
А то у меня недовольства нет, проект хорош, так почему же не принять идею для его улучшения?