-1

这是手头的问题：
我有几万个数组。每个数组的长度可以在 2-15 个单位之间。可以使用一些非常低成本的计算来计算所有数组中所有元素的总长度和数组的数量。但是在完成一些相当昂贵的计算之前，每个数组中的确切数字是未知的。

由于我知道所有数组中所有元素的总长度，我想只使用一个 new/malloc 为其分配数据，并在此分配中设置指针。在我当前的实现中，我使用 memmove 在插入某个项目后移动数据并相应地更新所有指针。

有没有更好的方法来做到这一点？

谢谢，

  • 席德
4

4 回答 4

2

目前尚不清楚您所说的更好的方法是什么意思。如果您正在寻找运行速度更快并且可以提供一些额外内存的东西，那么您可以保留两个数组，一个包含数据，另一个包含它所属数组的索引。添加完所有数据后，您可以按索引排序，然后将所有数据按数组拆分，最后扫描数组并获取指向每个数组所属位置的指针。

关于内存消耗，取决于你有多少数组，以及你的数据有多大，你可以将索引数据压缩到数据的最后一位，如果你有一些数字限制的话。这样，您只需要对数字进行排序，当您扫描检索每个数组开始的指针时，您可以清除最高位。

于 2012-12-04T22:19:41.597 回答
1

由于我知道所有数组中所有元素的总长度，我想只使用一个 new/malloc 为其分配数据，并在此分配中设置指针。

您可以使用一个大向量。您需要自己手动计算每个子数组的偏移量。

向量保证它们的数据存储在连续的内存中，但是如果向量的使用方式可能会使其重新分配，请注意维护指向单个元素的引用或指针。应该不是问题，因为您没有添加超出初始大小的任何内容。

int main() {    
    std::vector<T> vec;
    vec.reserve(calc_total_size());
    // now you'll need to manually translate the offset of
    // a given "array" and then add the offset of the element to that 

    T someElem = vec[array_offset + element_offset];
}
于 2012-12-04T22:19:20.127 回答
0

您是在寻找内存效率、速度效率还是简单性？

您始终可以编写或下载一个非常简单的池分配器，然后将其作为分配器传递给适当的数据结构。因为您事先知道总大小，并且永远不需要调整向量的大小或添加新的向量，所以这甚至比典型的池分配器更简单。只是malloc将所有存储都放在一个大块中，并保留一个指向下一个块的指针。要分配 n 个字节，T *ret = nextBlock; nextBlock += n; return ret;. 如果你的对象是微不足道的并且不需要销毁，你甚至可以free在最后做一个大的。

这意味着您可以使用任何您想要的数据结构，或者比较和对比不同的数据结构。一个vectors vector? 一个巨大vector的细胞加上一个vector偏移量？你想出的其他东西听起来很疯狂，但可能会奏效？您可以比较它们的可读性、可用性和性能，而不必担心内存分配方面的问题。

（当然，如果您的目标是速度，那么以这种方式打包可能不是最好的答案。您通常可以通过浪费一点空间来改善缓存和/或页面对齐来获得很多速度。您可以编写一个花哨的分配器，例如，以转置的方式分配向量空间以提高算法的性能，该算法在应该执行行优先的情况下执行列优先，反之亦然，但在这一点上，调整算法可能比分配器更容易。 )

于 2012-12-05T03:04:02.123 回答
0

是的，有一个更好的方法：

std::vector<std::vector<Item>> array;
array.resize(cheap_calc());
for(int i = 0; i < array.size(); ++i) {
  array[i].resize(expensive_calc(i));
  for(int j = 0; j < array[i].size(); j++) {
    array[i][j] = Item(some_other_calc());
  }
}

没有指针，没有混乱，没有大惊小怪。

于 2012-12-04T22:01:35.677 回答