Быть умным в распределении векторной памяти

Question

Допустим, мне нужно перебрать потенциально очень большой вектор чисел и скопировать четные и нечетные элементы в новые отдельные векторы.(Исходный вектор может иметь любую пропорцию четных значений к коэффициентам; это могут быть все четные значения, все коэффициенты или где-то между ними.)

Для простоты push_back часто используется для такого рода вещей:

for (std::size_t Index; Index < Source.size(); Index++)
{
    if (Source[Index] % 2) Odds.push_back(Source[Index]);
    else Evens.push_back(Source[Index]);
}

Однако меня беспокоит, что это будет неэффективно и будет вредным, если оно будет использоваться как часть реализации для чего-то вроде алгоритма сортировки, где производительность имеет первостепенное значение.Например, быстрая сортировка включает в себя разделение элементов, наподобие этого.

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

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

Есть ли лучший метод, который я пропускаю?* push_back() обычно доверяют управлять такими вещами для программиста, или это может стать обременительным для чувствительных алгоритмов?

Answer 1

Я собираюсь ответить на вопрос, который, я думаю, вы действительно хотели задать, а именно: «Следует ли push_back() избегать во внутренних циклах тяжелых алгоритмов?" а не то, что другие, кажется, прочитали в вашем посте, а именно: «имеет ли значение, если я вызову push_back перед выполнением несвязанной сортировки на большом векторе?» Кроме того, я собираюсь ответить из своего опыта, а не тратить время на поиск цитат и рецензируемых статей.

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

1. push_back () - это постоянное время (действительно, мгновенное), когда у вектора достаточно места, предварительно зарезервированного для дополнительного элемента, но медленное, когда у вас заканчивается зарезервированное пространство.
2. Выделение памяти обходится дорого (malloc() просто медленно , даже когда педанты делают вид, что new - это нечто иное)
3. Копирование векторных данных из одного региона в другой после перераспределения также происходит медленно : когда push_back () обнаруживает, что ему не хватает места, он должен пойти и выделить больший вектор, затем скопируйте все элементы . (Теоретически для векторов, размер которых много страниц ОС, волшебная реализация STL могла бы использовать VMM для перемещения их по виртуальному адресному пространству без копирования & mdash; на практике я никогда не видел такой, которая могла бы .) * * тысяча двадцать-одна
4. Чрезмерное распределение выходных векторов вызывает проблемы: это вызывает фрагментацию, делая будущие распределения медленнее; он сжигает кеш данных, делая все медленнее; если он постоянен, он связывает дефицит свободной памяти, что приводит к подкачке диска на ПК и сбою на встроенных платформах.
5. Недостаточное распределение выходных векторов вызывает проблемы, поскольку перераспределение вектора является операцией O (n), поэтому перераспределение его m раз равно O (m & times; n). Если распределитель по умолчанию STL использует экспоненциальное перераспределение (делая резерв вектора в два раза больше его предыдущего размера каждый раз, когда вы перераспределяете), это делает ваш линейный алгоритм O (n + n log m).

Следовательно, ваш инстинкт верен: всегда предварительно резервируйте пространство для векторов, где это возможно, не потому, что push_back медленный, а потому, что он может вызвать перераспределение, которое медленное . Кроме того, если вы посмотрите на реализацию shrink_to_fit, вы увидите, что она также перераспределяет копии, временно удваивая ваши затраты памяти и вызывая дальнейшую фрагментацию.

Ваша проблема в том, что вы не всегда точно знаете, сколько места вам понадобится для выходных векторов; Обычный ответ - использовать эвристический и, возможно, пользовательский распределитель. Зарезервируйте n / 2 + k входного размера для каждого из ваших выходных векторов по умолчанию, где k - некоторый запас прочности. Таким образом, у обычно будет достаточно места для вывода, если ваш вход разумно сбалансирован, а push_back может перераспределить в редких случаях, когда это не так. Если вы обнаружите, что экспоненциальное поведение push_back тратит слишком много памяти (в результате чего вам нужно зарезервировать 2n элементов, когда на самом деле вам просто нужно n + 2), вы можете назначить ему собственный распределитель, который увеличивает размер вектора на меньшие линейные куски & mdash; но, конечно, это будет намного медленнее в случаях, когда векторы действительно не сбалансированы, и вы в конечном итоге делаете много изменений.

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

Answer 2

Как насчет сортировки исходного вектора с помощью пользовательского предиката, который ставит все четности перед всеми коэффициентами?

bool EvenBeforeOdd(int a, int b)
{
  if ((a - b)  % 2 == 0) return a < b;

  return a % 2 == 0;
}

std::sort(v.begin(), v.end(), EvenBeforeOdd);

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

Обновление: Как прокомментировал @Blastfurnace, гораздо эффективнее использовать std::partition, а не sort, посколькунам на самом деле не нужны элементы, упорядоченные внутри каждого раздела:

bool isEven(int a) { return 0 == a % 2; }
std::vector<int>::const_iterator it =  std::partition(v.begin(), v.end(), isEven);

std::vector<int> evens, odds;
evens.reserve(std::distance(v.begin(), it);
odds.reserve(std::distance(it, v.end());

std::copy(v.begin(), it, std::back_inserter(evens));
std::copy(it, v.end(), std::back_inserter(odds));

Answer 3

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

Затем позвоните на номер shrink_to_fit

Однако я беспокоюсь, что это будет неэффективно и навредит как алгоритмы сортировки. ... push_back () обычно доверяют для управления такого рода вещи для программиста, или это может стать обременительным для чувствительные алгоритмы?

Да, push_back является доверенным. Хотя, честно говоря, я не понимаю, о чем вы беспокоитесь. Предположительно, если вы используете алгоритмы для вектора, вы уже поместили элементы в вектор. О каком алгоритме вы говорите, где будет иметь значение как элементы вектора попадают туда, будь то push_back или что-то еще?

Answer 4

Если ваши субвекторы ровно наполовину (нечетные / четные), просто выделите 50% исходного вектора для каждого.Это позволит избежать потерь и shrink_to_fit.

Answer 5

Если ваши объекты создаются динамически, то векторы буквально просто хранят указатели. Это делает векторы значительно более эффективными, особенно когда речь идет о внутреннем перераспределении. Это также сэкономит память, если одни и те же объекты существуют в нескольких местах.

std::vector<YourObject*> Evens;

Примечание. Не выдвигайте указатели из контекста функции, так как это приведет к повреждению данных за пределами этого фрейма. Вместо этого объекты должны быть размещены динамически.

Возможно, это не решит вашу проблему, но, возможно, это полезно.