如何快速获取已排序向量中的已排序子向量

Question

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

struct X {
  float value;
  int id;
};

一个由大小为N（约100,000）的元素组成的向量，按值排序（在程序执行期间保持不变）：

std::vector<X> values;

现在，我想编写一个函数。

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

该函数填充传递的“ids”参数指定的值的已排序子集到“out”参数中（大小为Mvalues中偏移量的查找表lut（预处理，因此运行时间恒定）2.创建std::vector tmp，大小为N，填充无效ids（线性N）3.对于每个id，将values[lut[id]]复制到tmp[lut[id]]（线性M）4.循环遍历tmp，将项复制到out中（线性N）。尽管这是线性的，但是临时变量和重复复制会导致问题。是否有比这更快的方法？请注意，M将接近N，因此O(MlogN)的事情是不利的。

编辑：http://ideone.com/xR8Vp 是所提到算法的一个示例实现，以使期望输出更加清晰，并证明它可以在线性时间内完成 - 问题在于是否有可能避免临时变量或以其他方式加速它，任何不是线性的都不会更快 :）。

- etarion

---

那个 tmp 的目的是什么？它最初来自哪里？为什么不直接在 out 中构建输出，而不需要任何中间临时变量？ - AnT stands with Russia

使用 id 排序的第二个向量，可以通过使用 equal_range、copy 和最终按值排序 sort 来获得 M log N 的复杂度。 - clstrfsck

这些一定要是vector吗，特别是out吗？ - Wyatt Anderson

ids 的范围是 [0，N)。对于每个 0 <= id < N，在 values 中恰好有一个元素。 - etarion

好的，灯亮了。对于混淆感到抱歉。看起来你可以使用“稀疏数组”容器来减少临时数组的大小，但除了排序之外，我看不到其他方法。 - Mark Storer

Answer 1

您可以尝试另一种方法，使用哈希表而不是向量来查找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是常数时间（假设我们没有整数哈希问题）。然而，我怀疑实际上它可能不如最初使用向量的方法快。

- Peter

---

谢谢，这看起来很有趣。将与向量版本进行基准测试。 - etarion

Answer 2

由于您的向量已经排序，而且您想要一个按照相同方式排序的子集，我认为我们可以只是切出您想要的块而不重新排列它。

为什么不使用find_if()两次。一次找到您想要的范围的开始，一次找到范围的结束。这将给您子向量的开始和结束迭代器。使用这些迭代器构造一个新的向量。其中一个向量constructor重载需要两个迭代器。

或者使用partition算法也可以。

- Jay

---

不确定这会不会奏效。如果我正确理解了问题，OP已经按value对数组进行了排序，并希望按id进行选择。 - clstrfsck

是的，而且ID不连续（也不一定排序）。 - etarion

Answer 3

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

你目前的方法是拥有一个可能值的排序列表。 这需要线性时间到可能值数量N（理论上，假设映射搜索需要O(1)时间）。

你能做到的最好的方法是使用快速排序方法（O(MlogM)，例如快速排序、归并排序等）对数值（你从映射中找到的）进行排序，对于较小的M值可以进行线性搜索，而对于较大的M值则可以这样做。 例如，如果N为100000，而M为100，则只使用排序算法要快得多。

我希望你能理解我的话。如果你还有问题，我会尽力回答：)

编辑：（评论） 我将进一步解释我的意思。 假设你知道你的数字范围从1到100。 你已经在某个地方将它们排序了（实际上它们是“自然”排序的），你想以排序形式获取它们的子集。 如果能够以比O(N)或O(MlogM)更快的速度完成这项工作，排序算法就会使用这种方法来排序。

例如，如果你有数字集合{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）。

- George

---

不，我不想创建一个线性排序时间算法 - 我想从已经排序好的向量中获取值，因此不需要进行排序。请参见http://ideone.com/SNHVq以查看我在OP中概述的算法的示例实现。 - etarion