массив по сравнению с вектором по сравнению со списком
Я поддерживаю таблицу фиксированной длины 10 записей. Каждый объект является структурой подобных 4 полей. Будет вставка, обновит и удалит операции, указанные числовым положением. Я задаюсь вопросом, который является лучшей структурой данных для использования для поддержания этой таблицы информации:
массив - вставляет/удаляет, занимает время из-за смещения; обновление занимает время; никакое пространство не используется для указателей; доступ к использованию объекта [] быстрее.
вектор stl - вставляет/удаляет, занимает время из-за смещения; обновление занимает время; никакое пространство не используется для указателей; доступ к объекту медленнее, чем массив, так как это - вызов к оператору [] и связанный список.
список stl - вставляет и удаляет, занимает время, так как необходимо выполнить итерации к определенной позиции прежде, чем применить вставление/удаление; дополнительное пространство необходимо для указателей; доступ к объекту медленнее, чем массив, так как это - связанный список линейный обход.
Прямо сейчас мой выбор состоит в том, чтобы использовать массив. Действительно ли это допустимо? Или я пропускал что-то?
Который быстрее: пересечение списка, затем вставка узла или смещение объектов в массиве для создания пустого положения, затем вставляющего объект в то положение?
Что лучший способ состоит в том, чтобы измерить этот уровень? Я могу просто отобразить метку времени прежде и после операций?
5 ответов
Используйте вектор STL . Он предоставляет такой же богатый интерфейс, как list , и устраняет боль, связанную с управлением памятью, которая требуется массивам.
Вам придется очень постараться, чтобы выявить затраты на производительность оператора [] - обычно он встроен.
У меня нет числа, чтобы дать вам, но я помню, как читал анализ производительности, в котором описывалось, как vector был быстрее, чем list ] даже для вставки и удаления (конечно, до определенного размера). Дело в том, что эти процессоры, которые мы используем, очень быстрые - и если ваш вектор помещается в кэш L2, то он будет работать очень быстро. Списки, с другой стороны, должны управлять объектами кучи, которые убивают ваш L2.
Преждевременная оптимизация - это корень всех зол.
Основываясь на вашем сообщении, я бы сказал, что нет причин делать ваш выбор структуры данных здесь, основанной на производительности. Выберите наиболее удобный вариант и вернитесь, чтобы изменить его, если и только если тестирование производительности покажет, что это проблема.
Предпочитайте std :: vector над массивом. Некоторые преимущества вектора:
- Они выделяют память из свободного пространства при увеличении размера.
- Они НЕ являются замаскированным указателем.
- Они могут увеличивать / уменьшать размер во время выполнения.
- Они может выполнять проверку диапазона с помощью at () .
- Вектор знает свой размер, поэтому вам не нужно считать элементы.
Самая веская причина для использования вектора - это то, что он освобождает вас от явного управления памятью, и это не приводит к утечке памяти. Вектор отслеживает объем памяти, который он использует для хранения своих элементов. Когда вектору требуется больше памяти для элементов, он выделяет больше; когда вектор выходит за пределы области видимости, он освобождает эту память. Следовательно, пользователю не нужно беспокоиться о распределении и освобождении памяти для векторных элементов.
Вы делаете предположения, которые не должны делать, например, «доступ к элементу происходит медленнее, чем к массиву, поскольку это вызов оператора []». Я могу понять логику, лежащую в основе этого, но вы и я не можем знать, пока мы не профилируем его.
Если вы это сделаете, вы обнаружите, что при включенной оптимизации нет никаких накладных расходов. Компилятор встраивает вызовы функций. Есть разница в производительности памяти. Массив выделяется статически, а вектор - динамически. Список выделяется для каждого узла, что может ограничить кэш, если вы не будете осторожны.
Некоторые решения должны иметь вектор , выделяемый из стека, и иметь распределитель пула для списка , чтобы узлы могли поместиться в кэш.
Поэтому вместо того, чтобы беспокоиться о неподдерживаемых утверждениях, Вам следует позаботиться о том, чтобы ваш дизайн был как можно более чистым. Итак, что имеет больше смысла? Массив, вектор или список? Я не знаю, что вы пытаетесь сделать, поэтому не могу вам ответить.
Контейнером "по умолчанию" обычно является вектор . Иногда вполне приемлем и массив.
PNG может вам подойти. Он может обрабатывать большие изображения, метаданные, а формат PNG может иметь некоторую чересстрочную развертку , так что вы можете легко получить (вплоть до?) Субдискретизированное изображение n / 8 xn / 8.
I Не уверен, что PNG может делать быстрый произвольный доступ. Он разбит на части, но этого может быть недостаточно.
Вы можете представить разреженные данные с помощью канала прозрачности.
если вы изучили все возможности и определили, что массив - ваш лучший выбор, начните заново. Вы сделали что-то очень неправильное. Списки STL не поддерживают operator [] , и если они это сделали, то причина, по которой это будет медленнее, чем индексирование массива, не имеет ничего общего с накладными расходами функции call.
Как говорится, вектор здесь явный победитель. Вызов оператора [] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. В основном это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции.
Списки STL не поддерживают operator [] , и если они это сделали, то причина, по которой это будет медленнее, чем индексирование массива, не имеет ничего общего с накладными расходами функции call.
Как говорится, вектор здесь явный победитель. Вызов оператора [] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. В основном это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции.
Списки STL не поддерживают operator [] , и если они это сделали, причина, по которой это будет медленнее, чем индексирование массива, не имеет ничего общего с накладными расходами функции call.
Как говорится, вектор здесь явный победитель. Вызов оператора [] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. В основном это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции.
Как говорится, вектор здесь явный победитель. Вызов оператора [] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. В основном это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции.
Как говорится, вектор здесь явный победитель. Вызов оператора [] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. По сути, это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции.
[] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. В основном это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции. Вызов оператора [] по существу незначителен, поскольку содержимое вектора гарантированно непрерывно в памяти. Он поддерживает операции insert () и erase () , которые вам, по сути, придется написать самостоятельно, если вы используете массив. В основном это сводится к тому, что вектор - это, по сути, обновленный массив, который уже поддерживает все необходимые вам операции.