Vektorfaltung unter C++

Die Problemstellung

Wir haben zwei Vektoren, a und b, gesucht wird das Produkt c = a * b. Die Anwendung ist zum Beispiel die 1. Ableitung des Vektors, durch Faltung mit dem Vektor [-1 1].

Die triviale Lösung

StackOverflow schlägt folgende Implementierung vor:

for(size_t i = K/2; i < l - K/2; ++i)
{
    outvec[i] = 0.0;
    for(size_t j = 0; j < K+1; j++)
    {
         outvec[i - K/2] += invec[i - K/2 + j] * kernel[j];
    }
}

Diese Lösung liefert auch gültige Ergebnisse, sie hat nur einen entscheidenden Nachteil: Sie erwartet den wahlfreien Zugriff über operator[](index). Damit legt sich diese Implementierung auf einige Container fest:

  • std::aray
  • std::vector
  • std::deque
  • std::map
  • std::unordered_map

Was ist nun zum Beispiel mit std::list?

Die Verfeinerung

Die Lösung ist relativ simpel - Verwende Interatoren.

template <class OutputIter, class InputIter, class KernelIter>
OutputIter
convolute(OutputIter output_begin, OutputIter output_end, InputIter input_begin, InputIter input_end, KernelIter kernel_begin, KernelIter kernel_end)
{
    const auto input_size = std::distance(input_begin, input_end), kernel_size = std::distance(kernel_begin, kernel_end),
               output_size = std::distance(output_begin, output_end);

    if (kernel_size > input_size || output_size < input_size || input_size < 1 || kernel_size < 1)
        throw std::out_of_range(std::string("input_size: ") + std::to_string(input_size) + std::string(", kernel_size: ") +
                                std::to_string(kernel_size) + std::string(", output_size: ") + std::to_string(output_size));

    const auto input_stop = std::prev(input_end, kernel_size / 2);
    auto output = std::next(output_begin, kernel_size / 2);
    for (auto input = std::next(input_begin, kernel_size / 2); input != input_stop && output != output_end; ++input, ++output) {
        *output = 0;
        auto input_filtered = std::prev(input, kernel_size / 2);
        for (auto kernel = kernel_begin; kernel != kernel_end; ++kernel, ++input_filtered)
            *output += (*input_filtered) * (*kernel);
    }
    return output;
}

Damit ist die Implementierung nur noch auf Iteratoren (genauer: std::ForwardIterator) basiert.

Comments !