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

[@RouR]

Ещё бы алгоритмы архивации, и обработки изображений

[@AstarothAst]

И правда недовольные были даже в раю…

[@RouR]

Какой странный комментарий, а вы точно со мной разговариваете?
А то у меня недовольства нет, проект хорош, так почему же не принять идею для его улучшения?

[@maggg]

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

[@trehleb]

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

[@sergeyvolobuev]

Присоединяюсь к «спасибо»! Очень отличная подборка.

[@oYASo]

Я хоть и особо не работаю с js, но вы все отлично оформили, приятно глазу посмотреть!

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

[@trehleb]

Да, Вы правы, что поиск/вставка/удаление будут линейными в hash table, но это при условии хорошо подобранной хеш-функции.

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

Я обновил табличку в репозитории и в комментариях указал этот нюанс.

[@capjdcoder]

Супер подборка, спасибо большое!

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

Разве не?

Но за подборку — огромное спасибо!!!

[@aleksandy]

Выбраная хэш-функция зело плохая.

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]

О(1) работает только до шага определения нужного bucket. Если элемент там не один, включается поиск, который может быть реализован по разному. В данном случае реализован линейный поиск, потому получается О(n), т.к. при неудачных входных данных все элементы окажутся в одной корзине.

[@trehleb]

Указанный вариант сложности предполагает как-раз «плохую» хеш-функцию, так, что все данные будут попадать в одну ячейку. Я обновил табличку в репозитории и указал, что в случае с идеальной хеш функцией сложность будет действительно O(1).

[@kolesoffac]

Уж больно джавовский подход написания кода, немного увеличивает вес самих алгоритмов. Чем проще, тем лучше виден сам алгоритм. Я не против ООП, это мое имхо.

[@mayorovp]

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

[@f0rk]

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

[@mayorovp]

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

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

[@f0rk]

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

[@anjensan]

А обычный массив мы будем реаллоцировать и копировать при каждой коллизии?

Зачем?
en.wikipedia.org/wiki/Open_addressing

[@Ogoun]

Алгоритмическая сложность для Binary Search Tree log(n) же. n будет только в худшем несбалансированном случае.

[@trehleb]

Да, все верно, O(log(n)) для сбалансированного дерева и O(n) в худшем несбалансированном случае. Я обновил табличку в репозитории и добавил комментарий к BST.

[@inook]

Есть еще mnemonist.js

[@nlog]

Я бы добавил timsort в секцию алгоритмов сортировки. Он довольно популярный и используемый.

[@artem-galas]

Ты сделал очень крутую работу! Спасибо!

Я тоже что-то подобное начинал делать. Я правда просто решил переписать все примеры из книги на Dart (да он еще жив). Вот тут
Там еще идея была переписать все «воркшопы», которые представлены в книге. Они показывают как работает алгоритм, но там я остановился только на Array.
Надеюсь что я тоже когда-то закончу что запланировал!
Если нужна будет помощь, то пиши, я с радостью :)

[@imouseR]

Спасибо за работу и за щедрость!

[@zacisco]

может кому полезно будет, давно о ресурсе знаю
с него можно было бы реализовать ещё… и мне всегда казалось, что Radix очень удачный алгоритм, только не многие его используют почему-то (ещё хабр-статья на С++)

[@valemak]

Всё мечтаю продолжить эту работу, да времени катастрофически нет… Уже накопилось некоторое количество новых сортировок, которые ещё не заливал на этот сайт и есть планы по выкладыванию в общественный доступ самого excel-приложения с макросами, с помощью которого делаю gif-анимацию алгоритмов.

[@JDTamerlan]

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