如何用约束为一大批“泛滥的群体”贴上标签？

Question

约束 ：在我的情况下，可以将问题分解为约100个iten或更小的碎片，但只能选择一组约10个itens并丢弃所有其他约90个itens …

有一个通用的算法可以添加和使用这种“预选”，以减少二次 O（N ^ 2）的 时间？ 如评论和@wildplasser所示，也许是 O（N
log（N））
时间；但我希望通过“预选”可以减少 O（N） 时间。

（编辑）

我尝试使用替代算法，但是在这里用作解决方案需要一些改进。或者，要真正提高性能（至_O（N）_ 时间），需要使用“预选”。

“预选择”（约束）基于“超集分组”…最初用“如何用SQL标记’传递组’进行说明？”进行说明。问题
t1表

  table T1
  (original T1 augmented by "super-set grouping label" ssg, and more one row)
  ID1 | ID2 | ssg
  1   | 2   | 1
  1   | 5   | 1
  4   | 7   | 1
  7   | 8   | 1 
  9   | 1   | 1
  10  | 11  | 2

因此，共有三组，

• g1：{1,2,5,9}，因为“ 1 t 2”，“ 1 t 5”和“ 9 t 1”
• g2：{4,7,8}，因为“ 4 t 7”和“ 7 t 8”
• g3：{10,11}，因为“ 10 t 11”

超级组只是辅助分组，

• ssg1：{g1，g2}
• ssg2：{g3}

如果我们有 M个 超级组项目和 N 个T1项目，则平均组长度将少于N / M。我们可以假设（对于我的典型问题）ssg最大长度也为〜N /
M。

因此，如果使用约束， 则“标签算法”只需要对〜N / M个项目运行M次ssg。

Answer 1

仅SQL解决方案似乎在这里有点问题。借助SQL上的一些过程编程，该解决方案似乎简单而有效。这是解决方案的简要概述，可以使用任何调用SQL的过程语言来实现。

R使用主键声明table
，ID其中key与table的ID域相同。该表包含另一个非关键列，一个数字ID1``ID2``T1``R``Label

R使用中找到的值范围填充表T1。设置Label为零（无标签）。使用您的示例数据，的初始设置R如下所示：

Table R
ID Label
== =====
 1 0
 2 0
 4 0
 5 0
 7 0
 8 0
 9 0

使用主语言光标和辅助计数器，从中读取每一行T1。查找ID1和ID2中R。您会发现以下四种情况之一：

 Case 1: ID1.Label == 0 and ID2.Label == 0

在这种情况下，以下任何一个ID都没有被“看到”：将1加到计数器上，然后将的两行都更新R为计数器的值：update R set R.Label = :counter where R.ID in (:ID1, :ID2)

 Case 2: ID1.Label == 0 and ID2.Label <> 0

在这种情况下，ID1是new，但是ID2已经被分配了标签。ID1需要分配给与以下标签相同的标签ID2：update R set R.Lablel = :ID2.Label where R.ID = :ID1

 Case 3: ID1.Label <> 0 and ID2.Label == 0

在这种情况下，ID2是new，但是ID1已经被分配了标签。ID2需要分配给与以下标签相同的标签ID1：update R set R.Lablel = :ID1.Label where R.ID = :ID2

 Case 4: ID1.Label <> 0 and ID2.Label <> 0

在这种情况下，该行包含冗余信息。的两行R应包含相同的Label值。如果不是，则存在某种数据完整性问题。啊…不太明白编辑…

编辑
我只是意识到，在某些情况下，两个Label值都可能为非零且不同。如果两者都不为零且不同，则此时Label需要合并两个组。您所需要做的就是选择一个，Label然后更新其他内容以匹配：update R set R.Label to ID1.Label where R.Label = ID2.Label。现在，两个组已合并为相同的Label值。

游标完成后，表R将包含需要更新的Label值T2。

Table R
ID Label
== =====
 1 1
 2 1
 4 2
 5 1
 7 2
 8 2
 9 1

进程表T2 使用的线沿线的东西：set T2.Label to R.Label where T2.ID1 = R.ID。最终结果应为：

  table T2
  ID1 | ID2 | LABEL 
  1   | 2   | 1
  1   | 5   | 1
  4   | 7   | 2
  7   | 8   | 2
  9   | 1   | 1

该过程是反复的迭代，应该毫不费力地扩展到相当大的表。