如何以这种方式对布尔向量的向量进行排序?(“排名分析”)

How can I sort a vector of boolean vectors in this way? ('ranking analysis')

提问人:David Irimia 提问时间:9/30/2019 最后编辑:David Irimia 更新时间:10/1/2019 访问量:92

问:

我们需要对大量仅包含真和假(1 和 0)的向量(数组的数组)进行排序,所有向量的大小都相同。 我们有 1 + 1 = 1(真 + 真 = 真)和 1 + 0 = 1 和 0 + 0 = 0 的规则。

  • 第一个向量是具有最多 1 的向量。
  • 第二个向量是除了我们在第一个向量中已有的向量之外带来更多 1 的向量。
  • 第三个向量是除了我们在前 2 个向量中已有的向量之外带来更多 1 的向量。
  • 等等。

例如,假设我们有这 3 个向量:

a. (0, 1, 0, 0, 1, 1, 0)
b. (1, 0, 1, 1, 0, 1, 1)
c. (0, 1, 1, 1, 0, 1, 0)

我们同类中的第一个是 b,因为它的 1 最多。 下一个是。尽管 c 的 1 比 a 多,但 a 除了 b 中的 1 之外,还有更多的 1。 到现在为止,a + b 的总和是 (1, 1, 1, 1, 1, 1, 1),所以最后一个是 c,因为它不会给排序带来任何新内容。

如果两个向量带来相同数量的额外 1,则它们的顺序并不重要。我相信这种排序有多种可能的结果,而且它们都一样好。

我们在这里称之为“排名分析”,但我们对这种分类没有明确的术语,谷歌也没有提供非常有用的信息。

最简单的方法是用 O(n^2) 将它们一一取出。然而,我们正在处理大数据,我们已经有一个软件,它太慢了,所以我们需要一些真正优化的东西。

我们怎样才能做到这一点?编程语言无关紧要,我们可以使用任何东西。这可以并行化吗(在多个 CPU 上运行它以加快进程)?欢迎任何来源或想法。

编辑:我检查了;显然,我们有一个情况,这些向量的长度是 103,因此它们可以超过 64 个插槽。

算法 排序与 语言无关的 排名

评论

0赞 Qubit 9/30/2019
不过,这种 O(n^2) 方法可以进行相当多的优化,所以也许这是一个值得探索的途径。我目前还不清楚你是否能做得更好,因为排序取决于你已经设置的排序,所以像快速排序这样的东西是不可能的。也就是说,你不满足大多数快速排序算法所依赖的一个非常基本的属性。
0赞 David Irimia 9/30/2019
我们将进一步探讨这个想法。目前,任何帮助都是值得赞赏的。谢谢!
0赞 Qubit 10/1/2019
这些载体有多长?
0赞 David Irimia 10/1/2019
根据类别,它们的范围从大约 10 到 50 不等。(但它们在类别中的长度都相同)。向量的数量以百万计。
0赞 Qubit 10/2/2019
然后,这些操作本身可以很容易地进行优化,即使您必须使用 2 个 64 位整数来存储一个,正如您的编辑所提到的。然而,对于任何 O(n^2) 方法来说,大量的向量都可能是一个问题。考虑到向量的数量,如果找不到更好的方法,在算法的每个步骤中并行搜索实际上可能是有益的。

答: 暂无答案