如何将一个向量分割成n个“几乎相等”的部分？

Question

我有一个问题，我想使用ImageMagick的convert.exe合并大量图像，但在Windows下我有一个8192字节长的命令行限制。

我的解决方案是将任务分割成较小的子任务，运行它们，然后进行最终任务，将它们组合在一起。

我的想法是编写一个函数，该函数接受一个图像矢量和一个整数，并将矢量拆分为n个子矢量，每个子矢量都具有“几乎相等”的部分。

例如，如果我想将11分成3组，则应为4-4-3。

你能告诉我如何使用C ++实现它吗？ 我的意思是编写一个函数。

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

哪个函数进行分割？

此外，如果我不需要创建新的向量，只需迭代子部分，您能告诉我最有效的方法是什么？就像使用 std::string 的 std::substr 函数一样？

注意：我已经在项目中使用了 Boost，所以如果 Boost 中有一些好的工具可用于此，则对我来说是完美的。

- hyperknot

Answer 1

要得到每个部分的基础大小，只需将总数除以部件数量：11/3 = 3。显然，有些部分需要比这更大才能获得正确的总数，但那只是余数：11％3 = 2。因此，现在您知道其中2个部分将是大小为3 + 1，剩下的部分将是3。

- Mark Ransom

---

谢谢，这是我想到的代码：double loop = number / parts; for( int i = 0; i < parts; i++ ) { int start = i * loop; int end = ( i + 1 ) * loop - 1; } - hyperknot

@zsero，如果number和parts都是整数，那么在进行除法运算之前，您需要将其中一个转换为double类型。此外，您还需要注意四舍五入误差，有些情况下，当您转换回整数时可能会出现偏差。 - Mark Ransom

实际上，在函数定义中我使用了双精度浮点数，并且使用了round()函数来处理起始和结束值。你认为在使用round()函数时会出现舍入误差吗？（我使用stringstream来进行舍入） - hyperknot

@zsero，如果你在开始和结束时使用四舍五入而不是截断，那么你应该没问题。你在之前的评论中漏掉了这一部分。 - Mark Ransom

Answer 2

这是我的解决方案:

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;
}

- Yury

Answer 3

你曾考虑过使用 xargs 程序吗？这或许是解决问题的高层次方案。

- Mike

---

我经常在我的Windows机器上使用“unix”实用程序。请查看：unxutils.sf.net和/或www.cygwin.com。 - Mike

谢谢你的提示，虽然我担心这对他在别人的电脑上运行代码没有帮助 :-P - spraff

为什么？xargs是一个独立的程序。将它与他的程序一起分发。 - Mike

Answer 4

CreateProcess有32kb的限制

或者，如果你想通过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 ());

- spraff

Answer 5

您不必创建新的子向量，可以使用以下代码：

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));
}

希望这能有所帮助。

- BrandonSun

---

Brandon应该返回什么？我不明白ProcessSubVec函数的返回值。 - Hani Goc

Answer 6

您可以创建一个模板，返回一个std :: vector 并接收要拆分的向量和分割数量。使用for循环和迭代器非常容易。

#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;
}

- Moises Rojo

Answer 7

这是我的做法（我知道它和答案非常相似，但那是我的实际代码哈哈）：

template<typename T>
std::vector<std::vector<T>> splitVector(const std::vector<T>& vec, size_t n)
{
    std::vector<std::vector<T>> out_vec;
    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 < n; ++i)
    {
        end += length + (i < remain);
        out_vec.emplace_back(vec.begin() + begin, vec.begin() + end);
        begin = end;
    }

    return out_vec;
}

如果您不喜欢复制，也可以返回迭代器对或类似的内容。

- G.Azma

Answer 8

你可以使用迭代器来遍历问题的子部分。迭代器的使用类似于指向向量元素的指针

你想在图像上做的事情可以被实现为一个函数

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 ;
    }
}

- Louen