Комментарии 20
Я совсем не упомянул, про комбинирование различных коллекций, благодаря которым образуются матрицы, таблицы. Также я не затронул деревья, кольцевое множество, почти ничего не написал про очереди, очень мало информации по хешированию (я таки отделался парой слов от этой темы) и другим методам оптимизации.
Вот очень жалко, честно говоря.
Ох, где вы были пять часов назад, когда я придумывал велосипед для хранения json… Спасибо за весьма полезную статью в любом случае.
мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).
При наличии указателя на это место, т.е. в начало и, возможно, в конец, если список двусвязный. В противном случае требуется проход по всем элементам листа до нужного, что при рандомном расположении элементов в памяти может вылиться в серьезную проблему производительности. И часто получается так, что замечательная структура, предназначенная для быстрой вставки и удаления элементов, проигрывает глупому вектору.
Как же много скобочек
Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу
Вы вроде про структуры данных пытаетесь рассказывать, а постоянно соскальзываете в реализацию. Нигде не сказанно, как хранятся элементы списка, есть только контракт на добавление/удаление элементов. В качестве примера тот же List(T) в шарпе основан на саморасширчющемся массиве, а для описанной вами структуры существует отдельный класс LinkedList(T). А все потому, что связный список является частной реализации структуры данных список
Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями.В том же питоне словарь — это set со всеми вытекающими вроде неупорядоченности.
И не только в питоне…
Если что, то в питоне есть и OrderedDict, кому нужен словарь как в PHP.
docs.python.org/2/library/collections.html#collections.OrderedDict
docs.python.org/2/library/collections.html#collections.OrderedDict
Если нет привязки к языку программирования, то обычно оперируют понятиями из классических трудов. У вас же всё свалено к кучу. Например, List в Java всего лишь интерфейс, реализация которого ничего не гарантирует кроме наличия определённых методов. ArrayList — уже реализация о которой можно что-то говорить. Vector — потоко-защищённый ArrayList. Я представляю, какая каша была бы у человека в голове, если бы он использовал эти классы после прочтения вашей статьи.
«Старый паскаль» — это вообще что такое?
«Старый паскаль» — это вообще что такое?
Причем для обозначения этого самого числа — индекса используют букву i.Какой-то карго-культ.
Слабенькая статья, очень невнятная и путанная. Автор путает интерфейсы, о которых зачем-то упомянул вначале, и реальные структуры данных, постоянно выдавая черты одного за черты другого.
Молчу уже про «изображение в памяти» std::map. По-хорошему за такое сразу отхабривать надо.
Лажанулся автор и с обильным применением списков, так как сейчас все больше применяются массивы, потому они работают существенно быстрее на современной сильно кэшированной памяти.
Ну и до кучи, «тот-же» и «потому-что» пишутся без дефиса!
Молчу уже про «изображение в памяти» std::map. По-хорошему за такое сразу отхабривать надо.
Лажанулся автор и с обильным применением списков, так как сейчас все больше применяются массивы, потому они работают существенно быстрее на современной сильно кэшированной памяти.
Ну и до кучи, «тот-же» и «потому-что» пишутся без дефиса!
Информация 1го курса любого института, плохо поданная.
>ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.
Звучит спорно.
>Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.
Из этого утверждения следует, что вектор бесконечен.
Звучит спорно.
>Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.
Из этого утверждения следует, что вектор бесконечен.
А где multiset, он же bag, я вас спрашиваю?! Уж если затронули такие свойства как unique/non-unique и ordered/non-ordered, то извольте расписать все четыре варианта.
боян и оффтоп
Разницу между стеком и очередью, а также преобразование стека в очередь, хорошо демонстрирует автомат Калашникова.
> Я очень хочу про все это написать
Пишите, умоляю!
Пишите, умоляю!
Горшочек, не вари.
Поддержу вышеотписавшихся: каша получается какая-то. Я не представляю, как человек, не знающий таких вещей после прочтения этой статьи получит от этого больше пользы, чем каши. Про асимптотики вскользь (а ведь они довольно «стандартизованы»), да и то только про часть операций, примеры с котятами не сильно запоминающиеся (да и их избыток не добавляет статье читабельности, но это уже имхо).
Если уж лезть в реализацию, так давайте объясним как (хотя бы как вариант) могут реализовываться структуры с такими асимптотиками и интерфейсом — куда полезнее, мне кажется, чем. Скажем, почему push_back в std::vector может быть реализован за O(1) в среднем, хотя иногда нам придётся переаллоцировать всё за O(n).
А так получается смесь из статьи вида «STL за 12 часов» (в которой есть и свой смысл, и своя аудитория) и статьи про юзкейсы и ограничения для более знакомых с предметом людей (опять же, свой смысл и своя аудитория).
Если уж лезть в реализацию, так давайте объясним как (хотя бы как вариант) могут реализовываться структуры с такими асимптотиками и интерфейсом — куда полезнее, мне кажется, чем. Скажем, почему push_back в std::vector может быть реализован за O(1) в среднем, хотя иногда нам придётся переаллоцировать всё за O(n).
А так получается смесь из статьи вида «STL за 12 часов» (в которой есть и свой смысл, и своя аудитория) и статьи про юзкейсы и ограничения для более знакомых с предметом людей (опять же, свой смысл и своя аудитория).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Просто о списках, словарях и множествах или ТОП 5 структур данных