Pull to refresh

Comments 31

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

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

Да, делал для себя, хотелось в одном месте собрать полезную информацию по алгоритмам и попрактиковаться заодно.
Присоединяюсь к «спасибо»! Очень отличная подборка.
UFO just landed and posted this here
UFO just landed and posted this here
Я хоть и особо не работаю с js, но вы все отлично оформили, приятно глазу посмотреть!

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

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

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

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

Разве не?

Но за подборку — огромное спасибо!!!
Выбраная хэш-функция зело плохая.
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) работает только до шага определения нужного bucket. Если элемент там не один, включается поиск, который может быть реализован по разному. В данном случае реализован линейный поиск, потому получается О(n), т.к. при неудачных входных данных все элементы окажутся в одной корзине.
UFO just landed and posted this here
Указанный вариант сложности предполагает как-раз «плохую» хеш-функцию, так, что все данные будут попадать в одну ячейку. Я обновил табличку в репозитории и указал, что в случае с идеальной хеш функцией сложность будет действительно O(1).
Уж больно джавовский подход написания кода, немного увеличивает вес самих алгоритмов. Чем проще, тем лучше виден сам алгоритм. Я не против ООП, это мое имхо.
Почему для хеш-таблицы выбран именно связный список? Обычный массив работает не хуже: асимптотика та же самая, но нагрузка на GC меньше и локальность обращений к памяти лучше.

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

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

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

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

UFO just landed and posted this here
Алгоритмическая сложность для Binary Search Tree log(n) же. n будет только в худшем несбалансированном случае.
Да, все верно, O(log(n)) для сбалансированного дерева и O(n) в худшем несбалансированном случае. Я обновил табличку в репозитории и добавил комментарий к BST.
Я бы добавил timsort в секцию алгоритмов сортировки. Он довольно популярный и используемый.
Ты сделал очень крутую работу! Спасибо!

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

Sign up to leave a comment.

Articles