Проектирование алгоритмов, требующих пространства скреста

Ответ 1

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

Ответ 2

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

Два полезных алгоритма: 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());

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

Одна вещь, которую я сделал для моего байтового массива, заключается в том, что функция 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;
    }
}

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

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

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