Разработка алгоритмов, которые требуют нуля пространства

Если вы используете функциональный объект, вы можете переносить любое нужное вам состояние.

Два полезных алгоритма transform а также accumulate,

transform Можно взять объект функции для выполнения преобразования каждого объекта в последовательности:

class TransformerWithScratchSpace {
public:
Target operator()(const Source& source);
};

vector<Source> sources;
vector<Target> targets;
targets.reserve(sources.size());

transform(sources.begin(), sources.end(),
back_inserter<Target>(targets),
TransformerWithScratchSpace());

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

class Accumulator {
public:
Accumulator& operator+()(const Source& source);
};

vector<Source> sources;

Accumulator accumulated = accumulate(sources.begin(), sources.end(),
Accumulator());

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

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

Рабочий алгоритм не должен каким-либо образом «манипулировать» пустым пространством, чтобы сделать его подходящим, когда его попросили его использовать, потому что такая манипуляция может быть дорогой.

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

Так что я закончил тем, что написал себе «универсальный»BufferPool«. Это класс, который управляет любой формой объекта буфера, будь то байтовый массив, какой-то другой фрагмент памяти или (в вашем случае) выделенное изображение. Я заимствовал эту идею из ThreadPool,

Это довольно простой класс, который поддерживает пул Buffer объекты, из которых вы можете acquire буфер, когда вам нужен и release это обратно в бассейн, когда вы закончите с ним. acquire Функция проверит наличие буфера в пуле и, если нет, создаст новый. Если есть один в бассейне, он будет reset Bufferто есть очистите его так, чтобы он вел себя идентично вновь созданному.

Затем у меня есть пара статических экземпляров этого BufferPoolпо одному на каждый другой тип Buffer Я использую: один для byte массивы, один для char массивы, … (я пишу на Java, на случай, если вам интересно … 🙂 Затем я использую эти статические экземпляры в все из библиотечных функций я пишу. Это позволяет мне, например, мои криптографические функции могут совместно использовать байтовые массивы с моими двоичными функциями выравнивания или любым другим кодом в моем приложении. Таким образом, я получаю максимальное повторное использование этих объектов, и это дало мне основной увеличение производительности во многих случаях.

В C ++ вы можете очень элегантно реализовать эту схему использования везде, написав пользовательский распределитель для структур данных, которые вам нужны на основе этой техники объединения (спасибо Эндрю за указание на это; см. комментарии).

Одна вещь, которую я сделал для своего буфера массива байтов, состоит в том, что acquire функция примет minimumLength параметр, который определяет минимальный размер нужного мне буфера. Затем он будет только возвращать байтовый массив по крайней мере этой длины из пула или создавать новый, если пул пуст или содержит только меньшие изображения. Вы можете использовать тот же подход с вашим буфером изображений. Пусть acquire функция принимает minWidth а также minHeight параметр, а затем вернуть изображение, по крайней мере, этих измерений из пула, или создать такое же с этими размерами. Вы могли бы тогда иметь reset Функция только очистить (0, 0) до (minWidth, minHeight) раздел изображения, если он вам даже нужен, очищен вообще.

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

Просто в качестве примера, вот код, который я использую для ByteArrayPool:

public class ByteArrayPool {

private static final Map<Integer, Stack<byte[]>> POOL = new HashMap<Integer, Stack<byte[]>>();

/**
* Returns a <code>byte[]</code> of the given length from the pool after clearing
* it with 0's, if one is available. Otherwise returns a fresh <code>byte[]</code>
* of the given length.
*
* @param length the length of the <code>byte[]</code>
* @return a fresh or zero'd buffer object
*/
public static byte[] acquire(int length) {
Stack<byte[]> stack = POOL.get(length);
if (stack==null) {
if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
return new byte[length];
}
if (stack.empty()) return new byte[length];
byte[] result = stack.pop();
Arrays.fill(result, (byte) 0);
return result;
}

/**
* Returns a <code>byte[]</code> of the given length from the pool after optionally clearing
* it with 0's, if one is available. Otherwise returns a fresh <code>byte[]</code>
* of the given length.<br/>
* <br/>
* If the initialized state of the needed <code>byte[]</code> is irrelevant, calling this
* method with <code>zero</code> set to <code>false</code> leads to the best performance.
*
* @param length the length of the <code>byte[]</code>
* @param zero T - initialize a reused array to 0
* @return a fresh or optionally zero'd buffer object
*/
public static byte[] acquire(int length, boolean zero) {
Stack<byte[]> stack = POOL.get(length);
if (stack==null) {
if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
return new byte[length];
}
if (stack.empty()) return new byte[length];
byte[] result = stack.pop();
if (zero) Arrays.fill(result, (byte) 0);
return result;
}

/**
* Returns a <code>byte[]</code> of the given length from the pool after setting all
* of its entries to the given <code>initializationValue</code>, if one is available.
* Otherwise returns a fresh <code>byte[]</code> of the given length, which is also
* initialized to the given <code>initializationValue</code>.<br/>
* <br/>
* For performance reasons, do not use this method with <code>initializationValue</code>
* set to <code>0</code>. Use <code>acquire(<i>length</i>)</code> instead.
*
* @param length the length of the <code>byte[]</code>
* @param initializationValue the
* @return a fresh or zero'd buffer object
*/
public static byte[] acquire(int length, byte initializationValue) {
Stack<byte[]> stack = POOL.get(length);
if (stack==null) {
if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
byte[] result = new byte[length];
Arrays.fill(result, initializationValue);
return result;
}
if (stack.empty()) {
byte[] result = new byte[length];
Arrays.fill(result, initializationValue);
return result;
}
byte[] result = stack.pop();
Arrays.fill(result, initializationValue);
return result;
}

/**
* Puts the given <code>byte[]</code> back into the <code>ByteArrayPool</code>
* for future reuse.
*
* @param buffer the <code>byte[]</code> to return to the pool
*/
public static byte[] release(byte[] buffer) {
Stack<byte[]> stack = POOL.get(buffer.length);
if (stack==null) {
stack = new Stack<byte[]>();
POOL.put(buffer.length, stack);
}
stack.push(buffer);
return buffer;
}
}

А потом, в остальном все мой код где мне нужно byte[]Я использую что-то вроде:

byte[] buffer = ByteArrayPool.acquire(65536, false);
try {
// Do something requiring a byte[] of length 65536 or longer
} finally {
ByteArrayPool.release(buffer);
}

Обратите внимание, как я добавил 3 разных acquire функции, которые позволяют мне указать, насколько «чистым» должен быть буфер, который я запрашиваю. Например, если я все это перезаписываю, нет необходимости тратить время на обнуление.