Comments 31
Ещё бы алгоритмы архивации, и обработки изображений
-2
Спасибо, что не в стол. Редкий случай хорошей подборки. Для себя же изначально собирали?
+1
Я хоть и особо не работаю с js, но вы все отлично оформили, приятно глазу посмотреть!
Глазу зацепилась таблица со сложностью для Hash Table. Все-таки среднее время поиска/вставки/удаления у нее будет константным, и только в худшем случае, если подобрана совсем неудачная хеш-функция, сложность будет линейная.
Глазу зацепилась таблица со сложностью для Hash Table. Все-таки среднее время поиска/вставки/удаления у нее будет константным, и только в худшем случае, если подобрана совсем неудачная хеш-функция, сложность будет линейная.
+2
Да, Вы правы, что поиск/вставка/удаление будут линейными в hash table, но это при условии хорошо подобранной хеш-функции.
В табличке я указал
Я обновил табличку в репозитории и в комментариях указал этот нюанс.
В табличке я указал
O(n)
для самого худшего случая, когда все данные попадают в одну «ячейку». Далее уже сложность зависит от реализации этой самой «ячейки» (массив это или linked list или что-то еще).Я обновил табличку в репозитории и в комментариях указал этот нюанс.
+1
Супер подборка, спасибо большое!
Вопрос про hash table — а почему сложность-то вставки и извлечениям линейные? У неё же вставка, получение = все равно О(1), если hash без коллизий.
Разве не?
Но за подборку — огромное спасибо!!!
Вопрос про hash table — а почему сложность-то вставки и извлечениям линейные? У неё же вставка, получение = все равно О(1), если hash без коллизий.
Разве не?
Но за подборку — огромное спасибо!!!
+1
Выбраная хэш-функция зело плохая.
Хотя бы стандартную из java взять надо.
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)
+3
О(1) работает только до шага определения нужного bucket. Если элемент там не один, включается поиск, который может быть реализован по разному. В данном случае реализован линейный поиск, потому получается О(n), т.к. при неудачных входных данных все элементы окажутся в одной корзине.
-1
Указанный вариант сложности предполагает как-раз «плохую» хеш-функцию, так, что все данные будут попадать в одну ячейку. Я обновил табличку в репозитории и указал, что в случае с идеальной хеш функцией сложность будет действительно
O(1)
. +1
Уж больно джавовский подход написания кода, немного увеличивает вес самих алгоритмов. Чем проще, тем лучше виден сам алгоритм. Я не против ООП, это мое имхо.
+1
Почему для хеш-таблицы выбран именно связный список? Обычный массив работает не хуже: асимптотика та же самая, но нагрузка на GC меньше и локальность обращений к памяти лучше.
+2
Думаю, автор хотел сделать акцент на принципиальную реализацию, а не на нюансы js. Так то можно было и обычный object взять.
+1
Использование массива вместо двусвязного списка может оказаться хорошей идеей в любом языке программирования. Если же библиотека использует связные списки — то всегда делается особая реализация именно для хеш-таблицы.
Вообще, связные списки в качестве готовых контейнеров работают ужасно: высокие накладные расходы и почти полное отсутствие плюсов.
Вообще, связные списки в качестве готовых контейнеров работают ужасно: высокие накладные расходы и почти полное отсутствие плюсов.
+1
А обычный массив мы будем реаллоцировать и копировать при каждой коллизии? Или все таки не совсем обычный массив нужен, а какой-нибудь array-list? И какой толк от локальности, если у нас в значениях например строки лежат и в бакете у нас указатели?
Мне кажется, для академических целей реализация автора вполне подходит. Понятно, что «на самом деле» все по-другому. Но общее представление о структуре даёт.
+3
А обычный массив мы будем реаллоцировать и копировать при каждой коллизии?Зачем?
en.wikipedia.org/wiki/Open_addressing
0
Алгоритмическая сложность для Binary Search Tree log(n) же. n будет только в худшем несбалансированном случае.
+2
Есть еще mnemonist.js
+1
Я бы добавил timsort в секцию алгоритмов сортировки. Он довольно популярный и используемый.
+1
Ты сделал очень крутую работу! Спасибо!
Я тоже что-то подобное начинал делать. Я правда просто решил переписать все примеры из книги на Dart (да он еще жив). Вот тут
Там еще идея была переписать все «воркшопы», которые представлены в книге. Они показывают как работает алгоритм, но там я остановился только на Array.
Надеюсь что я тоже когда-то закончу что запланировал!
Если нужна будет помощь, то пиши, я с радостью :)
Я тоже что-то подобное начинал делать. Я правда просто решил переписать все примеры из книги на Dart (да он еще жив). Вот тут
Там еще идея была переписать все «воркшопы», которые представлены в книге. Они показывают как работает алгоритм, но там я остановился только на Array.
Надеюсь что я тоже когда-то закончу что запланировал!
Если нужна будет помощь, то пиши, я с радостью :)
+1
Спасибо за работу и за щедрость!
+1
может кому полезно будет, давно о ресурсе знаю
с него можно было бы реализовать ещё… и мне всегда казалось, что Radix очень удачный алгоритм, только не многие его используют почему-то (ещё хабр-статья на С++)
с него можно было бы реализовать ещё… и мне всегда казалось, что Radix очень удачный алгоритм, только не многие его используют почему-то (ещё хабр-статья на С++)
+1
Еще есть вот такая визуализация:
www.cs.usfca.edu/~galles/visualization/Algorithms.html
www.cs.usfca.edu/~galles/visualization/Algorithms.html
0
Only those users with full accounts are able to leave comments. Log in, please.
Классические алгоритмы и структуры данных на JavaScript