12

我有一个这样的数据结构：

struct X {
  float value;
  int id;
};

这些向量（大小N（想想 100000），按值排序（在程序执行期间保持不变）：

std::vector<X> values;

现在，我想写一个函数

void subvector(std::vector<X> const& values, 
               std::vector<int> const& ids, 
               std::vector<X>& out /*, 
               helper data here */);

用传递的id给出的值的排序子集填充out参数（大小M < N（大约 0.8 倍N）），快速（内存不是问题，这将重复完成，因此构建查找表（来自函数参数的辅助数据）或仅执行一次的其他操作完全可以）。

到目前为止，我的解决方案：
构建包含id ->值中的偏移量的可查找lut（准备，因此恒定运行时间） 创建，大小 N， 为每个 id填充无效 id（线性N） ，复制到（线性M） 循环tmp , 将项目复制到out (线性N )
std::vector<X> tmp
values[lut[id]]tmp[lut[id]]

这在N中是线性的（因为它比M大），但是临时变量和重复复制让我感到困惑。有没有比这更快的方法？请注意，M将接近N ，因此 O( M log N ) 的事情是不利的。

编辑： http: //ideone.com/xR8Vp是上述算法的示例实现，以使所需的输出清晰并证明它在线性时间内是可行的 - 问题是关于避免临时变量或加速它的可能性以其他方式，非线性的东西不会更快:)。

4

3 回答 3

2

您可以尝试的另一种方法是使用哈希表而不是向量在以下位置查找 id：

void subvector(std::vector<X> const& values, 
               std::unordered_set<int> const& ids, 
               std::vector<X>& out) {

    out.clear();
    out.reserve(ids.size());
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) {
        if(ids.find(i->id) != ids.end()) {
            out.push_back(*i);
        }
    }
}

这以线性时间运行，因为unordered_set::find是恒定的预期时间（假设我们没有问题散列整数）。但是我怀疑它在实践中可能不如您最初使用向量描述的方法那么快。

于 2010-11-30T01:39:44.847 回答
1

由于您的向量已排序，并且您希望它的子集以相同的方式排序，我假设我们可以切出您想要的块而不重新排列它。

为什么不直接使用 find_if() 两次。一次找到您想要的范围的开始，一次找到范围的结束。这将为您提供子向量的开始和结束迭代器。使用这些迭代器构造一个新向量。向量构造函数重载之一需要两个迭代器。

那或分区算法应该可以工作。

于 2010-11-29T23:01:56.833 回答
0

如果我正确理解了您的问题，您实际上会尝试创建一个线性时间排序算法（取决于数字 M 的输入大小）。这是不可能的。

您当前的方法是对可能的值进行排序。这需要线性时间到可能值 N 的数量（理论上，考虑到地图搜索需要 O(1) 时间）。

您能做的最好的事情是使用快速排序方法（O(MlogM) fe quicksort、mergesort 等）对 M 的小值进行排序（您从地图中找到），并可能对 M 的较大值进行线性搜索. 例如，如果 N 为 100000，M 为 100，则仅使用排序算法要快得多。

我希望你能明白我说的话。如果您仍有问题，我会尽力回答：）

编辑：（评论）我将进一步解释我的意思。假设您知道您的数字范围从 1 到 100。您将它们排序在某个地方（实际上它们是“自然”排序的），并且您希望以排序形式获得它们的子集。如果有可能比 O(N) 或 O(MlogM) 更快，排序算法将只使用这种方法进行排序。

Fe 通过拥有一组数字 {5,10,3,8,9,1,7}，知道它们是已排序的一组数字 {1,2,3,4,5,6,7} 的子集， 8,9,10} 您仍然无法比 O(N) (N = 10) 或 O(MlogM) (M = 7) 更快地对它们进行排序。

于 2010-11-29T23:38:39.960 回答