Comments 51
Статье понадобилось 2 минуты, чтобы я понял профит от деревьев поиска. В универе это заняло кучу времени и не сказал бы, что отложилось в памяти. Спасибо.
std::map из стандартной библиотеки С++ отлично показал, чем логарифмическое время вставки и поиска отличается от линейного, когда во входном файле оказалось 700 тысяч слов.
например: меньшепамяти, последующиеструктуры, найтисоответствующую и т.д.
исправите, если возможно?
А мне нравятся nested tree.
Можно получить информацию о местоположении элемента в структуре, сделав только один запрос.
Списки реализовывали еще в колледже на старом добром pascal, к сожалению про деревья рассказывали что они просто есть и ни одного сами не реализовывали.
Понимание принципов работы структур данных сильно упрощает жизнь разработчику. Вот по деревьям упоролся на совсем странной ситуации: делал сторонний проект суть которого — разбор xml файлов размером ~3гб.
Язык php (можете кинуть в меня камень, но не я такой — специфика заказчика).
Изначально работая с dom обработка файла с сохранением в базу занимала около 3 часов. Если посмотреть в сторону более легковесного simpleXML то уже 2.5 часа, сам объект simpleXmlElement компактнее серии объектов из dom.
Далее если изначально перегнать все данные из XML объектов в дерево на массивах то разбор обработка уже сократится до 20 минут (массивы куда более производительны чем объекты). Отказавшись от старого доброго mysql в пользу postgres с переносом некоторых операций разбора на саму базу время уже сократилось до 20-30 секунд.
Итог — понимание того как устроены структуры данных в конкретном языке сократило выполнение операции с 3 часов до 30 секунд, при этом еще и уменьшились затраты памяти и процессорного времени. Так что учите структуры данных и способы работы с ними — пригодиться в самый внезапный момент.
Наверное, больше времени будет занимать сам парсинг файла, нежели обработка.
Само создание и обход xml древа выполняется достаточно быстро. Но вот dom и simpleXML как результат разбора возвращают объект. И вот обработка коллекции из более миллиона объектов средствами php вызывает просто дикие тормоза и нагрузку на память и процессор, если при разборе сразу перевести объекты в массивы и построить коллекцию уже из массивов — тогда обработка идет уже намного быстрее.
Поэтому и использовал xml_parser_create.
Это ж ООП.
Чего вы хотели :)
Разбаловала Вас дешёвая ОЗУ, я помню лет 8 назад сталкивался по работе с аналогичной задачей… И свелась она к тому, чтобы построчно читать XML и как только нужный узел был прочитан, он сразу отправлялся в обработку, освобождая память для следующего. В итоге программа не выходила за 100 Mb по памяти (точное значение уже не помню), несмотря на 2 Gb обрабатываемого XML.
Хотя в итоге все оказалось как обычно — не нужно. Партнеры которые отдавали эти суровые xml теперь открыли публичное json api, написали модуль для популярной cms и даже запилили об этом статью на хабре. В итоге пол года отработавший код заменили на cms+модуль.
Только разные языки и разные платформы дают разные средства для оптимизации. В с/с++ множество подобных средств, думаю в C# тоже парочка найдется. Но вот в тех-же Ruby/Python/Ruby таких средств маловато в php способы писать эффективный код вообще на грани лайвхаков.
Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»
А почему не учтена сложность на операцию увеличения размера списка (grow)? этом случае сложность становится O(N).
Приведите, пожалуйста, пример.
Собственно пример уже приведён — добавление элемента в конец списка.
Посмотрел внимательнее описание списка в статье — нет слов. С чего начинать критику — неясно. Понятно одно. Уверенно говорить о сложности добавления в конец списка из статьи вообще нельзя.
Пойдём по пунктам.
То, что в статье наызвают списком, обычно списком не называется
Списком обычно называют то, что в статье называется связным списком. Обычно список и связный список — синонимы. Это вопрос терминологии, но он очень путает, потому что добавление в конец связного списка — действительно O(1), и если не вчитываться — можно не понять где тут читателя кидают :)
Массивы из статьи — особые уличные джваскриптовые массивы
Дальше интереснее. Список из статьи реализован на основе массива. Этот массив — джаваскриптовый, что означает, что туда можно добавить элемент с любым индексом. Например, если в массиве один элемент, то можно добавить туда элемент с индексом 10 и джаваскрипт это скушает. Правда в массиве будет "дырка" на 9 элементов. Или можно, как в статье, добавить туда элемент с индексом 1 и тогда в массиве будет элемент с индексом 0 и с индексом 1 и дырки не будет. То есть, если в массиве 1 элемент — можно безо всяких проблем добавить второй — массив автоматом вырастет.
Обычные массивы сами по себе не растут
Во многих других языках программирования при создании массива надо задавать его размер, поменять который нельзя — можно только создать новый массив побольше и скопировать туда элементы старого.
Запись в массив по индексу стоит O(1)
Так вот — например у нас есть массив из 20 элементов и на его основе мы сделали список в который пока положили 10 элементов. То есть переменная length равна 10. И вот мы хотим добавить в список ещё один элемент. Тогда мы запишем новый элемент в массив по индексу 10 и увеличим переменную length на еденицу. Она теперь равна 11. Вот эта операция действительно стоит O(1).
Расширение массива стоит O(N)
Но если в списке, внутри которого массив из 20 элементов уже 20 элементов и есть (переменная length равна 20), то мы не можем записать новый элемент в индекс 20 и увеличить значение length, потому что массив слишком маленький. Теперь нам надо сделать новый массив из 40 элементов, скопировать туда элементы из предыдущего массива и уже потом записать новый элемент в новый массив по индексу 20 и увеличить переменную length до 21. И эта операция, как несложно догадаться, происходит за O(N), потому что надо скопировать N элементов.
Можно подумать, что вот этот случай с O(N) — не показателен, так как мы выращиваем массив 2 раза и потом ещё 20 элементов добавим за O(1). Потом нам, конечно, придётся скопировать массив в новый ещё раз. Но ведь после этого мы добавим за O(1) ещё 40 элементов.
Но это иллюзия. Допустим у нас есть пустой массив и мы хотим добавить в
конец 10 элементов. Тогда нам надо сделать следующую последовательность действий.
- Создаём новый массив на 2 элемента и записываем туда 1 элемент по индексу 0. 1 действие.
- Записываем в массив элемент по индексу 1. 1 действие.
- Создаём новый массив из 4 элементов и копируем туда 2 элемента из старого массива. Потом записываем туда элемент по индексу 2. 3 действия.
- Записываем в массив элемент по индексу 3. 1 действие.
- Создаём новый массив из 8 элементов и копируем туда 4 элемента из старого массива. Потом записываем туда элемент по индексу 4. 5 действий.
- Записываем в массив элементы по индексу 5, 6, 7. 3 действия.
- Создаём новый массив из 16 элементов и копируем туда 8 элементов из старого массива. Потом записываем туда элемент по индексу 8. 9 действий.
- Записываем в массив элементы по индексу 9. Одно действие.
Итак, нам понадобилось добавить в список 10 элементов.
И для этого нам понадобилось произвести 24 действия.
Посчитаем только операции копирования, из старого массива в новый. Получится 2 + 4 + 8 = 14. Вот где она линейная сложность, то есть O(N). N = 10, надо сделать 14 дополнительных копирований.
Джаваскриптовые массивы — вообще не массивы
В джаваскрипте за массивом стоит очень хитрая структура данных
и если вы делаете так
var memory = [];
var length = 0;
memory[length] = 2;
++length;то для того, чтобы узнать O(1) у вас или O(N) или O(log(N)) — надо лезть в исходники интерпретатора. Возможно там не массив, а HashTable (чтобы можно было иметь нецифровые индексы и дырки), а может быть там гибридная структура, которая будет массивом, пока вы не начнёте добавлять нецифровые индексы и дырки, а потом распадётся на HashTable и обыкновенный массив. Сложно сказать наверняка, когда в ход идёт уличная магия и коварные оптимизации. Ну и сложность добавлений в конец списка, реализованного автором явным образом такая же как сложность добавления элемента в конец массива. То есть неизвестная.
Такие дела.
Учитывая, что максимальный размер массива ограничен, то ограничено и количество реаллокаций памяти под массив, и количество копирований элементов. Следовательно, можно ограничить сверху стоимость одного добавления константой С (для разных начальных размеров массива она будет разной). Время добавления в конец массива = О(С)= О(1). Конечно, стоит помнить, что это не совсем обычная константа, но О(N) является еще более грубой оценкой.
Это правда. Корректно говорить об O(1) в лучшем случае, O(N) в худшем и O(1) амортизированном. А то о чём написал я в предпоследней части — это дополнительная стоимость добавления первых N элементов. Надо было сделать дополнительнй заголовок.
Проблема статьи в том, что автор вообще никак не рассматривает момент, что массив надо выращивать и сколько это стоит в случае с джаваскриптом.
Нет, это не фича реализации. Это имманентное свойство структуры данных. В нашем случае списка на основе массива. Именно для такой структуры будет в лучшем случае O(1) и в худшем, когда надо увеличивать массив — O(N).
Для реализаций что-то действительно может меняться. Например, можно копировать элементы в другой массив не по одному, а блоками — это несколько улучшит ситуацию. Но в данном случае нам показывают не другую реализацию, а другую структуру данных — не список на основе массива, а список на основе джаваскриптового массива, который имеет совсем другие свойства. В том числе сам растёт и в том числе там не совсем понятно какова сложность даже доступа по индексу, не говоря уже о сложности увеличения размера.
Вас путает тот факт, что структура данных, которую автор называет списком, обычно называется динамическим массивом. Ключевым различием тут является то, что массив обязательно предоставляет произвольный доступ к элементам, а список такого контракта не имеет.
Вообще когда мы говорим о структуре данных без реализации, то об алгоритмической сложности особенно то ничего и не скажешь. В случае с тем же списком операции добавления и удаления имеют разную сложность в зависимости от реализации, а теория, насколько я помню лишь определяет список как структуру данных, хранящую множество элементов в определённой последовательности. Один и тот же элемент может встречаться в списке больше одного раза.
Спасибо за развернутый и полезный комментарий.
Надеюсь, вы понимаете, что статья рассчитана на нулевой уровень знаний, и её цель — дать минимальные зачатки предмета. Здорово, что вы акцентировали внимание на неточностях и задали направление, в котором следует разбираться дальше.
То, что статья рассчитана на нулевой уровень — не повод закрывать глаза на грубые ошибки. С таким же успехом можно в статье, посвящённой истории человечества рассказывать, что австралопитеки охотились с собаками и называть это неточностями.
В моем комментарии внимание акентировано не на неточностях, а именно на грубой ошибке — на том, что автор не написал, что кусок памяти нельзя просто расширить и что это расширение стоит O(N). Кроме того, создаётся впечатление, что автор и вправду считает джаваскриптовый массив просто пустым блоком памяти.
Я тут просмотрел статью ещё раз и списком то всё не исчерпывается. Описанная в статье хэш таблица просто напросто не работает. Что будет, если туда положить объект по какому-то ключу, а потом положить другой объект по другому ключу, у которого hashKey такой же как у первого ключа?
К сожалению, мне не хватает знаний, чтобы аргументированно спорить. Вероятно, автор ошибся. Вы можете написать ему об этом в оригинальный репозиторий.
Что касается хеш-таблиц, автор оговаривает, что коллизий не предполагается.
https://github.com/thejameskyle/itsy-bitsy-data-structures
Я думаю автор не ошибся, а считает, что рассказывать про расширение массива просто не нужно и тут я с ним не согласен. Свои сомнения я ему уже высказал, посмотрим что он ответит.
С хэш таблицами ведь похожая история — большая часть алгоритмов для хэш таблиц — это алгоритмы разрешения коллизий. Но тут автор хотя бы прямо написал, что коллизий не будет :)
// Проходимся по каждому элементу…
for (var address = 0; address < this.length; address++) {
// и заменяем его на следующий элемент списка.
this.memory[address] = this.memory[address + 1];
}
Во время последней итерации значение переменной address будет равно this.length-1, следовательно address+1 будет равно this.length — обратившись по этому адресу, мы выйдем за границы массива.
Поэтому цикл должен быть с такими параметрами:
for (var address = 0; address < (this.length-1); address++)
Разве не так?
ОХЕРЕННО!
Уважаемый переводчик, слово AWESOME не переводится, как ОХРЕНЕННО. Мальчик семи лет может сказать маме что It's AWESOME. А вот если мальчик семи лет скажет маме, что это ОХРЕНЕННО вообще, то не исключено, что его пороть будут.
не_надо_так.jpg
Структуры данных для самых маленьких