Cómo dividir un vector en n partes "casi iguales"

Question

Tengo un problema que me gustaría fusionar una gran cantidad de imágenes con el convert.exe de ImageMagick, pero en Windows tengo un límite de línea de comandos de 8192 bytes.

Mi solución a esto es dividir la tarea en una subtarea más pequeña, ejecutarlas y realizar una tarea final que las combine.

Mi idea es escribir una función, que toma un vector de imágenes y un número entero, y divide el vector en n sub-vector teniendo todas las partes "casi iguales".

Entonces, por ejemplo, si me gustaría dividir 11 en 3 grupos, sería 4-4-3.

¿Puede decirme cómo puedo hacerlo en C++? Quiero decir, para escribir una función

split_vec(const vector<image> &images, int split) 

que hace la división?

Además, ¿puede decirme cuál es la forma más eficiente de hacer si no necesito crear nuevos vectores, simplemente itere a través de las subpartes? ¿Te gusta la función std::substr con std::string?

Nota: Ya uso Boost en el proyecto, así que si hay alguna buena herramienta en Boost para esto, entonces es perfecto para mí.

Answer 1

Para obtener un número de base para el tamaño de cada parte, simplemente divida el total por el número de partes: 11/3 = 3. Obviamente, algunas de las partes necesitarán ser más grandes para obtener el total adecuado , pero eso es sólo el resto: 11% 3 = 2. Así que ya saben que 2 de las partes habrá de tamaño 3 + 1, y lo que sobra será 3.

Answer 2

CreateProcess has a 32kb limit

O, si quiere ir a través del shell,

vec::const_iterator i = vec .begin(); 
vec::const_iterator j = i + stride; 

while (j < vec .end()) { 
    do_range (i, j); 
    i = j; 
    j += stride; 
} 

do_range (i, vec .end()); 

Answer 3

Puede usar iterators para recorrer las partes secundarias del problema. el uso de iteradores es similar a los punteros a los elementos de la vector

Lo que se quiere en las imágenes no podría ser implementado como una función

using namespace std; 
void do_some_work(vector<image>::iterator begin, vector<image>::iterator end) { 
    vector<image>::iterator i = begin ; 
    while(i != end) { 
     // do something using *i , which will be of type image 
     ++i ; 
    } 
} 

Answer 4

¿Ha pensado en utilizar el programa xargs. Esto tal vez una solución de alto nivel al problema.

Answer 5

Usted no tiene que crear nuevos sub-vectores, usar algo como lo siguiente:

size_t ProcessSubVec(const vector<Image>& images, size_t begin, size_t end) 
{ 
    // your processing logic 
} 

void SplitVec(const vector<Image>& images, int cnt) 
{ 
    size_t SubVecLen = images.size()/cnt, 
      LeftOvers = images.size() % cnt, 
      i = 0; 

    // Split into "cnt" partitions 
    while(i < images.size()) 
     i += ProcessSubVec(images, i, i + SubVecLen + (LeftOvers-- == 0 ? 0 : 1)); 
} 

Espero que esto ayude.

Answer 6

Aquí está mi solución:

template<typename T> 
std::vector<std::vector<T>> SplitVector(const std::vector<T>& vec, size_t n) 
{ 
    std::vector<std::vector<T>> outVec; 

    size_t length = vec.size()/n; 
    size_t remain = vec.size() % n; 

    size_t begin = 0; 
    size_t end = 0; 

    for (size_t i = 0; i < std::min(n, vec.size()); ++i) 
    { 
     end += (remain > 0) ? (length + !!(remain--)) : length; 

     outVec.push_back(std::vector<T>(vec.begin() + begin, vec.begin() + end)); 

     begin = end; 
    } 

    return outVec; 
} 

Answer 7

Se puede crear una plantilla que devuelve un std :: vector < std :: vector> y recibe el vector que desea dividir, y el número de divisiones. usando para e iterador es muy fácil.

#include <iostream> 
#include <iomanip> 
#include <vector> 
#include <algorithm> 
#include <numeric> 

template<typename T> 
std::vector< std::vector<T> > split(std::vector<T> vec, uint64_t n) { 
    std::vector< std::vector<T> > vec_of_vecs(n); 

    uint64_t quotient = vec.size()/n; 
    uint64_t reminder = vec.size() % n; 
    uint64_t first = 0; 
    uint64_t last; 
    for (uint64_t i = 0; i < n; ++i) { 
    if (i < reminder) { 
     last = first + quotient + 1; 
     vec_of_vecs[i] = std::vector<T>(vec.begin() + first, vec.begin() + last); 
     first = last; 
    } 
    else if (i != n - 1) { 
    last = first + quotient; 
    vec_of_vecs[i] = std::vector<T>(vec.begin() + first, vec.begin() + last); 
    first = last; 
    } 
    else 
    vec_of_vecs[i] = std::vector<T>(vec.begin() + first, vec.end()); 
} 

return vec_of_vecs; 
} 

#define ONE_DIMENSION 11 
#define SPLITS 3 

int main(void) 
{ 
    std::vector<uint64_t> vector(ONE_DIMENSION); 
    std::iota(std::begin(vector), std::end(vector), 1); 

    std::vector<std::vector<uint64_t>> vecs(SPLITS); 
    vecs = split(vector, SPLITS); 

    for (uint64_t m = 0; m < vecs.size(); ++m) { 
    for (auto i : vecs[m]) 
     std::cout << std::setw(3) << i << " "; 
    std::cout << std::endl; 
    } 


    return 0; 
}