复制几乎为空的数组的最快方法

Question

我必须优化一个非常糟糕的c++代码。制造它的人不知道如何编码：它有内存踩踏，索引从1开始而不是0，spagetthi代码，你能说出一个糟糕的做法，它就在那里。

因此，该算法40%的时间都在复制几乎为空的大型数组。我试图做出最小的更改，因为这可能意味着要更改成千上万行代码，任何错误都意味着得到完全不同的结果。

因此，与其像这样声明这个大的、几乎为空的数组：短HLLE[dimcl]//定义dimcl 600

我正在做类似的事情

ArrayTimes HLLE;

/////
// Stores the occupied positions in another array, when copying, instead of copying all, empty the occupied ones
// then fill with the other occupied ones
class ArrayTimes
{
public:
ArrayTimes(int numTasks);
ArrayTimes(const ArrayTimes& _other);
virtual ~ArrayTimes();
inline short& operator[](int _index)
{
auto &result = (*m_times)[_index];
if (result == 0) //if there was already a value doesn't count as occupied again
{
(*m_occupied)[m_numOccupied] = _index;
++m_numOccupied;
}
return result;
}

inline const short& operator[](int _index) const
{
return (*m_times)[_index];
}

inline ArrayTimes& operator= (const ArrayTimes &_other)
{
//vaciamos
for (int i = 0; i < m_numOccupied; ++i)
{
auto occIndex = m_occupied->operator[](i);
m_times->operator[](occIndex) = 0;
}

*m_occupied = *(_other.m_occupied);
m_numOccupied = _other.m_numOccupied;

for (int i = 0; i < _other.m_numOccupied; ++i)
{
auto occIndex = _other.m_occupied->operator[](i);
m_times->operator[](occIndex) = _other.m_times->operator[](occIndex);
}
return *this;
}
ArrayTimes::ArrayTimes(int numTasks) :
m_numOccupied(0)
{
m_occupied = new std::vector<int>();
m_times = new std::vector<short>();

m_times->resize(numTasks);
m_occupied->resize(numTasks / 4);
}

ArrayTimes::ArrayTimes(const ArrayTimes& _other)
{
m_occupied = new std::vector<int>();
m_times = new std::vector<short>();


auto datosGlobales = DatosGlobalesProblema::getInstance();
auto numTareas = datosGlobales->GetNumTareas() + 1;

m_occupied = new std::vector<int>();
m_times = new std::vector<short>();

m_times->resize(numTareas);
m_occupied->resize(numTareas / 4);

operator=(_other);
}

ArrayTimes::~ArrayTimes()
{
delete m_times;
delete m_occupied;
}


int ArrayTimes::Size() const
{
return m_occupied->size();
}

我尝试了几个容器来存储占用的位置：列表、集合、无序集合、映射。它们中没有一个比复制所有数组位置更快。

我想正确的答案是找到另一种方法来保存信息，而不会在这样的内存阵列中浪费内存，尽管这意味着重构数千行代码。

Answer 1

下面的代码有300到600次复制的时间。您不需要使用std::vector手动复制任何内容。

我已经更改了=运算符，但您必须遍历其中一个向量才能看到要复制的内容。

此外，您可以拥有比m_occupied中的索引更多的m_times，所以您不应该计算占用向量。

Size: 300, 75
Element: 90
real    0m0,002s
user    0m0,002s
sys 0m0,000s

class ArrayTimes
{
std::vector<int> m_occupied;
std::vector<short> m_times;
int m_numOccupied;

public:

ArrayTimes(int numTasks) :
m_numOccupied(0)
{
m_times.resize(numTasks);
m_occupied.resize(numTasks / 4);
}

ArrayTimes(const ArrayTimes& _other)
{
auto numTareas = 600;
m_times.resize(numTareas);
m_occupied.resize(numTareas / 4);

operator=(_other);
}

~ArrayTimes()
{
}

inline short& operator[](int _index)
{
auto &result = m_times[_index];
if (result == 0) //if there was already a value doesn't count as occupied again
{
m_occupied[m_numOccupied] = _index;
++m_numOccupied;
}
return result;
}

inline const short& operator[](int _index) const
{
return m_times[_index];
}

inline ArrayTimes& operator= (const ArrayTimes &_other)
{
m_times.reserve (_other.m_times.size());
for (auto e : _other.m_occupied) {
m_times[e] = _other.m_times[e];
}
m_numOccupied = _other.m_numOccupied;
return *this;
}

int OSize() const
{
return m_times.size();
}
int Size() const
{
return m_occupied.size();
}

};
int main ()
{
ArrayTimes a1(600);
ArrayTimes a2(300);
a2[3] = 9;
a1 = a2;
std::cout << "Size: " << a1.OSize() << ", " << a1.Size() << std::endl;
std::cout << "Element: " << a1[3] << std::endl; // copied value from a2

return 0;
}

Answer 2

我设法将数组缩减为几个元素，因此不需要这个棘手的类。谢谢你指出我的错误，至少我从这次经历中学到了一些东西