std :: vector clear函数慢 [英] std::vector clear function slow

问题描述

我有一个嵌套的向量，如下所示：

I have a nested vector as shown:

std::vector<std::vector<std::vector<int>>> tst;

我将整数值插入到尺寸为1000 x 512 x 512的嵌套向量中。在使用clear（）函数清除向量时，需要大量的时间。任何人都可以帮忙解决这个问题。

And i am inserting integer values into the nested vector with dimension 1000 x 512 x 512. While clearing the vector using clear() function, it takes a lot of time. Can anyone pls help to solve the issue.

推荐答案

看起来 vector :: clear ha线性复杂度甚至虽然包含基本类型，但请参阅 std :: vector :: clear at cppreference.com [ ^ ]和堆栈溢出线程 [ ^ ] 。





[更新]

我做了以下测试（ g ++ 4.7 ）

It looks that vector::clear ha linear complexity even while containing primitive types, see std::vector::clear at cppreference.com[^] and this Stack Overflow thread[^].


[update]
I made the following test (g++ 4.7)

#include <vector>
#include <time.h>
#include <iostream>

using namespace std;

#define N 40000000
int main()
{

  struct timespec ts[5];

  // step 0
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts[0]);
  vector <int> v;
  v.reserve(N);
  // step 1
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts[1]);

  for (int i=0; i<N; i++)
    v[i] = i;
  // step 2
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts[2]);

  v.clear();

  //step 3
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts[3]);

  for (int i=0; i<N; i++)
    v.push_back(i);

  // step 4
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts[4]);

  for (int i=0; i<5; i++)
  {
    cout << "step " << i << ", " << ts[i].tv_sec << " sec, " << ts[i].tv_nsec << " nsec " << endl;
  }
}

带输出：

with output:

step 0, 0 sec, 12653759 nsec
step 1, 0 sec, 12798215 nsec
step 2, 0 sec, 752234621 nsec
step 3, 0 sec, 752239235 nsec
step 4, 1 sec, 936184156 nsec

清除操作看起来并不昂贵。

[/ update]

the clear operation doesn''t look expensive.
[/update]

你的代码没有显示你如何填充数组......当你打电话给 clear（）功能。你想在结尾处有一个0×0×0矩阵，或者仍然有一个1000 x 512 x 512矩阵但是填充0？



以下链接可能帮助您找到一些替代方案：

http://www.google.ca/# q = multidimensional％20array％20class [ ^ ]



正如其他人所说，这是一个非常庞大的阵列......实现高效解决方案的最佳方法是知道这个类是怎样的用过的。你需要记忆中的所有值还是只有少数值？为什么要清除对象以及之后对它的期望是什么。



例如，清除整个结构是没有意义的（如果再次填充为1000 x 512 x 512，则为0 x 0 x 0）。

Your code does not show how you fill your array... and it is not clear what you want to do when you call clear() function. Do you want to have a 0 by 0 by 0 matrix at the end or still have a 1000 x 512 x 512 matrix but filled with 0 ?

The following link might help you find some alternatives:
http://www.google.ca/#q=multidimensional%20array%20class[^]

As mentioned by others, this is a quite large array... and the best way to implement an efficient solution is too know how the class is used. Do you need all those values in memory or only a few of them? Why do you want to clear the object and what do you expect it to be afterward.

For example, it won''t make sense to clear the whole structure (to be 0 x 0 x 0) if you fill it again to be 1000 x 512 x 512.

正如CPallini已经指出的那样，您正在尝试清除三维数组int拥有2.56亿个元素，换句话说大约1千兆字节的内存！



有几种方法可以优化：



（a）改为使用线性int数组，并手动进行索引计算（这是图像处理中大多数人在2D数组中所做的事情）。然后，您可以通过单次调用memset清除该内存，这比清除嵌套向量< ...>更有效。但是，性能提升将受到限制。如果你幸运，也许是2或3的因素。



例如：

As CPallini has already pointed out, you are attempting to clear a 3-dimensional array of int''s with 256 million elements, in other words roughly 1 gigabyte of memory!

There are several ways to optimize that:

(a) Use a linear int array instead, and do the index calculations manually (that''s what most people in image processing do in their 2D arrays). Then you can clear that memory with a single call to memset, which is more efficient than clearing nested vector<...>. The performance gain will be limited, though. Perhaps a factor of 2 or 3 if you are lucky.

For example:

int* pArray = new int [1024 * 512 * 512];

// clearing the array
memset (pArray, 0, sizeof (int) * 1024 * 512 * 512);

// access to cell (x, y, z)
int cellValue = pArray [x + 512*y + 512*512*z];

（b）重做你的问题，这样你就不需要256百万个细胞了。如果可能的话，这将是最好的替代方案。



（c）如果您的3D矩阵稀疏填充，请将您的巨大阵列分成16x16x16单元的子矩阵和仅为包含不等于零的值的子多维数据集分配空间。这不仅可以节省大量内存，而且还可以节省大量内存。使用2的幂来表示子立方体的边缘尺寸是有利的，因为它简化了子立方体索引的计算。单元格（x，y，z）将在子多维数据集中找到（x>> 4，y>>>>>> 4），这是一种非常快速的操作。在该子立方体内部，单元格具有索引（x& 0xf，y& 0xf，z& 0xf）。



这是相当多的工作，但是对于巨大的问题，这肯定是值得的。



修改日期2013年1月5日：



In对另一篇文章的评论，您告诉我们您正在存储一组图像。在这种情况下，安排你这样的数据是有意义的：

(b) Rework your problem, so that you don''t need 256 million cells. That would be the best alternative if that is possible.

(c) If your 3D matrix is sparsely filled, divide your huge array up into subcubes of say 16x16x16 cells and allocate only space for those subcubes that contain values unequal to zero. That not only saves a lot of memory, but also a lot of time clearing that memory. Using a power of 2 for the edge size of the subcubes is advantageous as it simplifies the calculation of the subcube index. Cell (x, y, z) will be found in subcube (x>>4, y>>4, z>>4), a very fast operation. Inside that subcube the cell has the index (x & 0xf, y & 0xf, z & 0xf).

This is quite a bit of work, but for huge problems it sure is worth the effort.

AMENDED 5-Jan-2013:

In a comment to another post you let us know that you are storing a set of images. In that case it makes sense to arrange you data like that:

std::vector<Image*> images;

其中Image是一个类，它将单个图像保存为像素值的2D数组。这样，您可以在不删除整个存储的情况下添加或删除该集中的图像。这基本上是利用上面显示的技术（c），并选择图像作为子立方体。



你提到你将使用多线程来操作图像。然后，您可以使用锁定技术锁定其中一个线程的整个图像。在图像矢量中实现比在3D阵列方法中更容易实现。



另外：如果您要存储图像，您可能不想要将 int 作为单个像素的类型。您的像素很可能是8位数量，或3 x 8位RGB值。您的图像类可能会为您解决此问题。谷歌是公共领域中许多图像类别中的一个，它将需要大量的工作。

where Image is a class that holds a single image as a 2D array of pixel values. That way you can add or remove images from that set without deleting the entire storage. This is basically making use of technique (c) shown above, and choosing an image as a subcube.

You mentioned that you would be using multi-threading to operate on the images. Then you could use a locking technique that locks an entire image for one of your threads. That is also a lot easier to implement in a vector of images than in your 3D array approach.

Also: If you are storing images you probably don''t want to have int as the type for a single pixels. Most likely your pixels are 8-bit quantities, or 3 x 8-bit RGB values. Your image class will probably solve this problem for you. Google for one of the many image classes that are in the public domain and it will take a lot of work off your shoulders.

这篇关于std :: vector clear函数慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！