性能：用N/m个元素对'm'个向量进行排序与对N个元素的单个向量进行排序相比较

Question

操作 A

我有 N 个向量，每个向量包含一定数量的唯一 3D 点。例如：std::vector<double*> vec1;等等。

我正在对每个向量执行排序操作：

 std::sort(vec1.begin(), vec1.end(), sortCriteria());
 std::sort(vec2.begin(), vec2.end(), sortCriteria());
 std::sort(vec3.begin(), vec3.end(), sortCriteria());

操作 B

假设我有一个名为“all_point_vector”的向量，其中包含来自vec1、vec2、vec3等的三维点。

即 all_point_vector 中的三维点 = vec1 中的点 + ... + vector3 中的点。

我正在执行排序操作：

std::sort(all_point_vec.begin(), all_point_vec.end(), sortCriteria());

我的问题是，通常情况下哪种方法（操作A或B）更快？对单个向量（all_point_vector）进行排序还是对各个向量进行排序。我只关心这两个操作的执行速度。

谢谢

- memC

---

但是使用“操作A”仍然需要另一步来合并这三个向量，对吧？否则你会比较两个具有非常不同结果的算法。 - Manuel

不需要合并结果，假设如此。 - memC

那么我想“操作B”会更慢，因为它需要做更多的工作，这是合乎逻辑的。 - Manuel

Answer 1

排序是一个 O(n log n) 的操作。对于 N 个向量，每个向量有 m/N 个元素进行排序将比对一个有 m 个元素的单一向量进行排序更快，随着 m 的增加，速度差距会越来越大。

无论对于任何固定的 m，哪种方法更快只能通过分析性能才能确定。

- avakar

---

@avakar：谢谢，我期望的是类似的想法，但不确定...在接受任何答案之前，我会等待更多的投票/回答 :-) - memC

请注意，仅当排序标准导致vec1中的所有点位于vec2之前（vec2的点位于vec3之前）时，操作A才会产生正确的结果。如果是这种情况，则第一个操作将更快并产生正确的结果。 请注意，如果您从一个大向量开始，然后将其分成两个单独的向量（一个用于“小”点，一个用于“大”点），然后对这些向量进行排序，那么实际上正在执行快速排序的一阶段。 - Patrick

@Patrrick：你对业务规则做出了毫无根据的假设。 - MSalters

它更快，因为它正在解决一个不同（更简单）的问题。 - Mike Dunlavey

Answer 2

avakar说，在理论上，对几个短向量进行排序比对整个序列进行排序更快，但在实践中，你应该进行测量。我想再展示一些数学内容：

假设有k个序列，第i个序列有n_i个元素。让总元素数为N=n₁+...+n_k。对单个序列进行排序的复杂度为O(n₁logn₁+...+n_klogn_k)。对整个序列进行排序的复杂度为O(N logN)=O((n₁+...+n_k)logN)=O(n₁logN+...+n_klogN)。现在我们需要比较：

A=n₁logn₁+...+n_klogn_k B=n₁logN+...+n_klogN

由于对所有的i，N > n_i，所以对于所有的i，logN > logn_i。因此，B严格大于A，即对整个序列进行排序将需要更长的时间。

- sbk

---

特别是，如果向量大小都大致相同，即为 N/k，那么您的算法将从 O(N log N) 降至 O(N log N - N log k)。（可以通过注意到 log(N/k) = log N - log k 来轻松验证。） - Rex Kerr

Answer 3

对于排序单个包含m元素的数组与将相同数量的元素分成N个数组进行排序是不同的问题，因为在分割情况下，你仍然没有所有元素的总序。

假设m = 1024，在单例情况下，m log m = 1024*10 = 10240。

如果N=2，则有512*9 + 512*9 = 9216，但你仍然需要执行1024次比较的合并步骤，而9216 + 1024 = 10240，所以它是相同的。

[实际上，在每个排序级别中，比较次数比要合并的项目数少1，但整体结果仍然是O(n log n)]

补充：如你所评论的那样，如果你不需要执行合并，则分割情况更快。 （当然，在这种情况下，你可以将m项分成N=m个数组，甚至不必排序；-）

- Mike Dunlavey

---

@Mike：是的，我不需要将这些元素合并在一起。像操作A中那样拥有简单的向量将会使代码设计更好。但是，我想检查一下，通过这样做，是否会影响性能。看起来理论上它确实会提供更好的性能。所以问题解决了。操作A是赢家。谢谢！ - memC

@memC：性能提升确实有，但只是微不足道的。我建议你尝试一下这个链接：https://dev59.com/mnNA5IYBdhLWcg3whuV_#927773 - Mike Dunlavey