массив против вектора против списка

Question

Я поддерживаю таблицу фиксированной длины из 10 записей. Каждый элемент представляет собой структуру из 4 полей. Будут операции вставки, обновления и удаления, указанные числовой позицией. Мне интересно, какую структуру данных лучше всего использовать для ведения этой таблицы информации:

1. массив - вставка / удаление занимает линейное время из-за смещения; обновление занимает постоянное время; место для указателей не используется; доступ к элементу с помощью [] быстрее.

2. stl vector - вставка / удаление занимает линейное время из-за смещения; обновление занимает постоянное время; место для указателей не используется; доступ к элементу медленнее, чем к массиву, так как это вызов оператора [] и связанный список.

3. stl list - вставка и удаление занимают линейное время, поскольку перед применением вставки / удаления необходимо выполнить итерацию до определенной позиции; дополнительное место необходимо для указателей; доступ к элементу медленнее, чем к массиву, поскольку это линейный обход связанного списка.

Прямо сейчас мой выбор - использовать массив. Это оправданно? Или я что-то пропустил?

Что быстрее: обход списка, затем вставка узла или смещение элементов в массиве для получения пустой позиции, а затем вставка элемента в эту позицию?

Как лучше всего измерить эту производительность? Могу ли я просто отобразить отметку времени до и после операции?

Answer 1

Использовать STL vector. Он обеспечивает такой же богатый интерфейс, как и list, и устраняет необходимость управления памятью, которая требуется для массивов.

Вам придется очень постараться, чтобы раскрыть стоимость производительности operator[] - обычно она становится встроенной.

У меня нет номера, чтобы дать вам, но я помню анализ производительности чтения, который описывал, как vector<int> был быстрее, чем list<int> даже для вставок и удалений (при определенном размере, конечно). Дело в том, что эти процессоры, которые мы используем, очень быстрые - и если ваш вектор помещается в кэш L2, он будет работать очень быстро. Списки, с другой стороны, должны управлять объектами кучи, которые убьют ваш L2.

Answer 2

Преждевременная оптимизация - корень всего зла.

Исходя из вашего поста, я бы сказал, что нет никакой причины делать выбор структуры данных в данном случае основанной на производительности. Выберите то, что наиболее удобно, и вернитесь, чтобы изменить его, если и только если тестирование производительности покажет, что это проблема.

Answer 3

Действительно стоит потратить некоторое время на понимание фундаментальных различий между списками и векторами. Самое существенное различие между ними заключается в том, как они хранят элементы и отслеживают их.

- Списки -

Список содержит элементы, в которых хранится адрес предыдущего и следующего элемента. Это означает, что вы можете ВСТАВИТЬ или УДАЛИТЬ элемент в любом месте списка с постоянной скоростью O (1) независимо от размера списка. Вы также склеиваете (вставляете другой список) в существующий список в любом месте с постоянной скоростью. Причина в том, что список должен изменить только два указателя (предыдущий и следующий) для элемента, который мы вставляем в список.

Списки не годятся, если вам нужен произвольный доступ. Таким образом, если кто-то планирует получить доступ к n-му элементу в списке - нужно пройти список по одному - O (n) speed

- Векторы -

Вектор содержит элементы в последовательности, как массив. Это очень удобно для произвольного доступа. Доступ к «n-му» элементу в векторе является простым вычислением указателя (скорость O (1)). Добавление элементов в вектор, однако, отличается. Если кто-то хочет добавить элемент в середине вектора - все элементы, которые идут после этого элемента, должны быть перераспределены вниз, чтобы освободить место для новой записи. Скорость будет зависеть от размера вектора и от положения нового элемента. Наихудший сценарий - вставка элемента в позицию 2 в векторе, лучший вариант - добавление нового элемента. Поэтому - insert работает со скоростью O (n), где «n» - это количество элементов, которые необходимо переместить, а не обязательно размер вектора.

Существуют и другие различия, связанные с требованиями к памяти и т. Д., Но понимание этих основных принципов работы списков и векторов действительно стоит потратить некоторое время.

Как всегда ... " Преждевременная оптимизация - корень всего зла ", поэтому сначала подумайте, что удобнее, и заставьте вещи работать именно так, как вы хотите, а затем оптимизируйте. Для 10 записей, которые вы упомянули - это действительно не имеет значения, что вы используете - вы никогда не увидите какой-либо разницы в производительности независимо от используемого вами метода.

Answer 4

Предпочитают std :: vector over и array. Некоторые преимущества вектора:

• Они выделяют память из свободного пространства при увеличении размера.
• Они НЕ замаскированные указатели.
• Они могут увеличиваться / уменьшаться в размере во время выполнения.
• Они могут выполнять проверку диапазона, используя at () .
• Вектор знает свой размер, поэтому вам не нужно считать элементы.

Наиболее убедительная причина использования вектора заключается в том, что он освобождает вас от явного управления памятью и не дает утечки памяти. Вектор отслеживает память, которую он использует для хранения своих элементов. Когда для вектора требуется больше памяти для элементов, он выделяет больше; когда вектор выходит из области видимости, он освобождает эту память. Поэтому пользователю не нужно заботиться о выделении и освобождении памяти для векторных элементов.

Answer 5

Вы делаете предположения, которые не должны делать, например, «доступ к элементу медленнее, чем к массиву, поскольку это вызов оператора []». Я могу понять логику этого, но вы и я не можем знать, пока мы не профилируем это.

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

В некоторых решениях предусмотрено выделение vector из стека и выделение пула для list, чтобы узлы могли помещаться в кэш.

Поэтому, вместо того, чтобы беспокоиться о неподдерживаемых утверждениях, вам следует позаботиться о том, чтобы сделать свой дизайн максимально чистым. Итак, что имеет больше смысла? Массив, вектор или список? Я не знаю, что вы пытаетесь сделать, поэтому я не могу ответить вам.

Контейнер «по умолчанию» имеет тенденцию быть vector. Иногда массив тоже вполне приемлем.

Answer 6

Первые пару заметок:

Хорошее практическое правило по выбору структур данных: как правило, если вы изучили все возможности и определили, что массив является вашим лучшим выбором, начните сначала. Вы сделали что-то очень неправильно.

Списки STL не поддерживают operator[], и если они сделали причину, что это будет медленнее, чем индексирование массива, не имеет никакого отношения к издержкам вызова функции.

Как говорится, вектор - явный победитель. Призыв к operator[] по существу незначителен, поскольку содержимое вектора гарантированно будет непрерывным в памяти. Он поддерживает операции insert() и erase(), которые вы должны были бы написать сами, если бы использовали массив. По сути, это сводится к тому, что вектор по сути является обновленным массивом, который уже поддерживает все необходимые операции.

Answer 7

Я поддерживаю таблицу фиксированной длины из 10 записей. Каждый предмет структура как 4 поля. Там будет вставить, обновить и удалить операции, заданные числовой позицией. Мне интересно, что является Лучшая структура данных для использования в этой информационной таблице:

Основываясь на этом описании, кажется, что список может быть лучшим выбором, поскольку его O (1) при вставке и удалении в середине структуры данных. К сожалению, вы не можете использовать числовые позиции при использовании списков для вставки и удаления, как вы можете для массивов / векторов. Эта дилемма приводит к множеству вопросов, которые могут быть использованы для принятия первоначального решения о том, какую структуру лучше всего использовать. Эта структура может быть позже изменена, если тестирование четко показывает неправильный выбор.

Вопросы, которые вам нужно задать, состоят из трех частей. Во-первых, как часто вы планируете делать удаления / вставки в середине относительно случайного чтения. Во-вторых, насколько важно использовать числовую позицию по сравнению с итератором. Наконец, важен ли порядок в вашей структуре.

Если ответом на первый вопрос является случайное чтение, оно будет более распространенным, чем вектор / массив, вероятно, будет работать хорошо. Заметим, что итерация по структуре данных не считается случайным чтением, даже если используется запись оператора []. Что касается второго вопроса, если вам абсолютно необходима числовая позиция, то потребуется вектор / массив, даже если это может привести к снижению производительности. Более поздние испытания могут показать, что это снижение производительности незначительно по сравнению с более простым кодированием с числовыми позициями. Наконец, если порядок не важен, вы можете вставлять и удалять в векторе / массиве с помощью алгоритма O (1). Пример алгоритма показан ниже.

template <class T>
void erase(vector<T> & vect, int index) //note: vector cannot be const since you are changing vector
{
  vect[index]= vect.back();//move the item in the back to the index
  vect.pop_back(); //delete the item in the back
}

template <class T>
void insert(vector<T> & vect, int index, T value) //note: vector cannot be const since you are changing vector
{
  vect.push_back(vect[index]);//insert the item at index to the back of the vector
  vect[index] = value; //replace the item at index with value
}