Нетология corporate blog
Data Mining
Big Data
Open data
Data visualization
Comments 29
+9
Хеш-таблица это вроде одна из реализаций ассоциативного массива (словаря). Почему ее выделили в отдельную структуру данных? Тогда уж надо было сказать что возможны и другие реализации ассоциативных массивов (красно-черные деревья и прочие деревья поиска).
0
Ну если на то пошло, сама реализация ассоциативного массива это дерево.
Я так понял пост просто перечисляет наиболее встречаемые сущности организации данных под общепринятыми наименованиями.
+10

Всё вперемешку. Ужас.
Очередь и стек — самостоятельные структуры данных? Ничего, что их можно реализовать и поверх массива, и поверх списка — с разными свойствами соответственно?
Мапа, сет, дерево, хэш-таблица на одном уровне? "Раньше я думал, что Карл Маркс и Фридрих Энгельс — муж и жена, а теперь я знаю, что это четыре разных человека" :-)


Рано вам кого-то учить.

0
Без сарказма, а расскажите чем будут отличаться свойства очереди и стека реализованные поверх массива? Поверх списка мне все понятно, а вот по массиву сходу не очевидно. При добавлении и удалении элементов будут постоянные реаллокации массива, что плохо, но возрастет скорость итерирования объектов (а очередь и стек не про итерирование).
+1
  1. Не будет выделений/освобождений в куче на каждый чих — существенный выигрыш. И вообще нет кучи мелких кусочков памяти, выделенных в куче, всё лежит локально (и удобно попадает в кэш проца для задач, где стек используется активно)
  2. Если не выделить сразу сколько надо памяти — иногда (например, при каждом удвоении размера массива) придётся реаллоцировать, тут мы проиграем (в среднем быстродействие всё равно выше, чем у списка, но иногда операция добавления элемента может оказаться долгой — в некоторых задачах это неприемлемо)

В общем, редко когда имеет смысл делать очередь или стек на списке.


Кстати, напомню об ещё одной структуре для хранения вектора переменного размера: массив массивов (или список массивов). Позволяет объединить плюсы обоих подходов за счёт некоторого усложнения кода, но нужен редко.

0
Спасибо, здорово.
Из той же серии, массивы предпочтительнее списков в играх для хранения объектов, потому что создание\удаление объектов на сцене редкая операция, а итерация по ним происходит каждый кадр понесколько раз.
0

Из смешного по теме: в C# класс List — на самом деле массив, реальный список — LinkedList. Вот до такой степени MS верит в преимущество массивов в большинстве случаев.

+1

LinkedList ― это конкретно «связный список».


Просто «список», без уточнений ― это абстрактная упорядоченная коллекция нефиксированного размера, которая реализована может быть как угодно. Когда термин «список» встречается в описании какого-нибудь алгоритма, если нет уточнений, лучше его именно так абстрактно и понимать.

0

Ну да, просто после STL и прочих библиотек, в которых list == linked list, это было непривычно.
А учитывая, что явно указана сложность Item[i] как O[1] — это не абстрактная реализация списка, а именно аналог std::vector.

0
Здравствуйте. Уточните, что есть реализация «поверх массива/списка», как для начинающего?
+2

Глядите. Очередь/стек — это не конкретная структура, а объект, реализующий две операции: положить в очередь (push) и взять из очереди (pull). Для очереди порядок выдаются объекты в том же порядке — FIFO (First In First Out), для стека в обратном — LIFO (Last In First Out). Ну, есть ещё очередь с приоритетами — это когда первым выдаёт объект с наивысшим приоритетом.
Итого, если мы сделали нечто, умеющее правильно выполнять эти операции — это очередь :-)


Варианты реализации (на примере LIFO очереди):


  1. Связный список. Ну, тут всё просто: push добавляет объект к концу списка, pull берёт из начала (и выкидывает этот объект из списка). Сложность обеих операций O(1), но надо выделять память на каждый push.
  2. Массив. Если ограничить длину очереди — поверх массива делается кольцевой буфер: указатели на "голову" и "хвост" очереди.
    • push — кладём элемент на место, куда указывает хвост, сдвигаем указатель на 1 элемент направо (возвращаясь к началу массива, если перешли за конец).
    • pull — берём элемент из места, куда указывает голова, сдвигаем голову на 1 направо (опять же "закольцевав" движение)
    • Сложность обеих операций опять же O(1), но нет выделения памяти на каждый чих — работает быстрее.
  3. В варианте 2 размер ограничен, если нужен неограниченный — при заполнении массива увеличиваем его — точнее, выделяем новый и копируем туда все данные. Удобно увеличивать размер ровно в два раза, тогда получаем амортизированную сложность (т.е. в среднем по куче операций) опять же O(1), но вот в худшем случае (когда увеличиваем массив) уже O(n).

Ну, можно придумать ещё кучу других реализаций, но это самые распространённые.

-2

Как-то прожил и даже заработал на бублики, зная только половину. Скажу так: для начинающих слишком сложно, для продолжающих гуглится по мере необходимости. Заранее забивать себе всем этим голову нужды нет.

+2
Я правильно понял, что, если не считать отдельных переменных, есть 10 типов данных: массив со ссылками и массив со ссылками на массивы?
(особенно тщательно офигел от «заземления» «связного списка»… Я за свою трудовую биографию, кроме того, что был программистом, еще был и чуть-чуть энергетиком с группой допуска… Заземление связного списка — это сильно!
Я бы не додумался. Надо изучить электричество тщательно. Вдруг заземление, которое возводится в абсолют энергетиками, это действительно просто нулевой указатель?..)
+1
Уважаемые программисты, пишите код ответственно. Всегда заземляйте ваши структуры данных!
0
Как так, сложность поиска для связного списка O(n), а удаления O(1)? Магия однако
0
Под «удалением» понимается, что мы уже имеем указатель на удаляемый элемент, его не нужно искать.
0
Спасибо, понял что под Insert/Delete имелись ввиду сами операции…
Просто может где-нибудь сноску сделать что для того что-бы что-то удалить нужно это найти еще, а если вставлять то пройтись по всему списку сначала.
Извиняюсь за конфуз.
0

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

0
Не обязательно. Вот такой, например, вариант удаления элемента из односвязного списка за O(1):
// Предполагается, что список имеет вид
// struct node {
//     node* next;
//     std::unique_ptr<data> data;
// };
// 
// Последний элемент списка имеет поле next == nullptr
// В конце списка может быть не более одного "мусорного" элемента с полем data == nullptr - он ничего не означает и с логической точки зрения элементом списка не является

// Единственный аргумент - удаляемый элемент списка
void erase(node& to_delete) {
    if (to_delete.next == nullptr) {
        // Нужно удалить последний элемент - превращаем себя в sentinel
        to_delete.data = nullptr;
    } else {
        // Общий случай - перемещаем следующий элемент в себя, после чего уничтожаем следующий
        to_delete.data = std::move(to_delete.next->data);
        to_delete.next = to_delete.next->next;
        delete to_delete.next;
    }
}
+2
Материал сложный для начинающих.
А для не начинающих слишком раздражительно детская подача материалами, с попытками смехуечности и вот этого вот.
0
Почему это insert в двоичную кучу O(1)? Когда вы вставляете элемент в кучу, потом еще нужно привести кучу к каноническому виду (вставка может нарушить правила формирования кучи), так что сложность логарифмическая
+1
Я, видимо, один такой, но мне в таких статьях всегда не хватает примеров. Видишь вот такую задачу — хватай вот такую структуру данных, она идеально для этого подойдёт.
UFO landed and left these words here
0
А откуда автор может знать, где применять?
У вас есть задача, вы знаете структуры данных — решаете какую лучше применить.
Автор ваших задач не знает. А абстрактное — «префиксное дерево удобно для словарей» — не имеет ценности.
UFO landed and left these words here
+1
Знаете структуру, знаете особенности — умеете применять. Ценность вполне очевидная
UFO landed and left these words here
Only those users with full accounts are able to leave comments. , please.