SQL选择10个记录集合最符合标准的记录

Question

我的桌子:

CREATE TABLE `beer`.`matches` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `hashId` int(10) unsigned NOT NULL,
  `ruleId` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

如果哈希匹配规则,则此表中有一个条目.

1)计算每个唯一ruleId有多少个hashId(AKA"每个规则匹配多少个哈希")

SELECT COUNT(*), ruleId FROM `beer`.`matches` GROUP BY ruleId ORDER BY COUNT(*)

2)选择10个最佳规则(ruleIds),即选择组合的10个规则匹配最大数量的唯一哈希值.这意味着,如果另一个规则涵盖所有相同的哈希值,那么匹配大量哈希值的规则不一定是一个好的规则.基本上我想选择捕获最独特的hashIds的10个ruleIds.

?

编辑:基本上我在这里有一个PHP/SQL的次优解决方案,但根据数据,它不一定给我问题2的最佳答案.我对更好的解决方案感兴趣.阅读评论以获取更多信息.

Answer 1

我认为你的问题是"背包问题"的变种.

我想你已经明白,你不能只是采取任何ruleIds比赛最hashIds像其他答案建议,因为虽然每个那些ruleIds比赛说100 hashIds,他们可能都匹配相同的 100 hashIds...但如果你已经选择了其他10个ruleIds这只匹配25 hashIds,但每个hashIds匹配的每一个ruleId都是唯一的,你最终会得到更多的独特性hashIds.

为了解决这个问题,你可以选择任何开始ruleId匹配最hashIds,然后接下来选择任何ruleId匹配的最hashIds不包含在hashIds由符合先前ruleIds...继续这个过程,直到您选择10 ruleIds.

您的数据分布中可能仍然存在异常,这会导致无法生成最佳的ruleIds...因此,如果您想要发疯,可以考虑实施遗传算法以尝试提高您的设置的"适应性" 10 ruleIds.

这不是SQL特别适合处理的任务,但是这里是用SQL编写的遗传算法解决的背包问题的一个例子(!)

编辑

这是一个未经测试的解决方案实现ruleIds,每次选择1个,每次迭代选择以前未被任何其他选择覆盖ruleId的最独特的内容:hashIdsruleIds

--------------------------------------------------------------------------
-- Create Test Data
--------------------------------------------------------------------------
create create matches (
  id  int(10) unsigned not null auto_increment,
  hashId int(10) unsigned not null,
  ruleId int(10) unsigned not null,
  primary key (id)
);

insert into matches (hashid, ruleid)
values 
(1,1), (2,1), (3,1), (4,1), (5,1), (6,1), (7,1), (8,1), (9,1), (10,1),
(1,2), (2,2), (3,2), (4,2), (5,2), (6,2), (7,2), (8,2), (9,2), (10,2),
(1,3), (2,3), (3,3), (4,3), (5,3), (6,3), (7,3), (8,3), (9,3), (10,3),
(1,4), (2,4), (3,4), (4,4), (5,4), (6,4), (7,4), (8,4), (9,4), (10,4),
(1,5), (2,5), (3,5), (4,5), (5,5), (6,5), (7,5), (8,5), (9,5), (10,5),
(1,6), (2,6), (3,6), (4,6), (5,6), (6,6), (7,6), (8,6), (9,6), (10,6),
(1,7), (2,7), (3,7), (4,7), (5,7), (6,7), (7,7), (8,7), (9,7), (10,7),
(1,8), (2,8), (3,8), (4,8), (5,8), (6,8), (7,8), (8,8), (9,8), (10,8),
(1,9), (2,9), (3,9), (4,9), (5,9), (6,9), (7,9), (8,9), (9,9), (10,9),
(11,10), (12,10), (13,10), (14,10), (15,10),
(11,11), (12,11), (13,11), (14,11), (15,11),
(16,12), (17,12), (18,12), (19,12), (20,12),
(21,13), (22,13), (23,13), (24,13), (25,13),
(26,14), (27,14), (28,14), (29,14), (30,14),
(31,15), (32,15), (33,15), (34,15), (35,15),
(36,16), (37,16), (38,16), (39,16), (40,16),
(41,17), (42,17), (43,17), (44,17), (45,17),
(46,18), (47,18), (48,18), (49,18), (50,18),
(51,19), (52,19), (53,19), (54,19), (55,19),
(56,20), (57,20), (58,20), (59,20), (60,20)
--------------------------------------------------------------------------
-- End Create Test Data
--------------------------------------------------------------------------

create table selectedRules (
  ruleId int(10) unsigned not null
);

set @rulesSelected = 0;

while (@rulesSelected < 10) do
  insert into selectedRules (ruleId)
  select m.ruleId
  from 
    matches m left join (
      select distinct m2.hashId
      from
        selectedRules sr join
        matches m2 on m2.ruleId = sr.ruleId
      ) prev on prev.hashId = m.hashId
  where prev.hashId is null
  group by m.ruleId
  order by count(distinct m.hashId) desc
  limit 1;

  set @rulesSelected = @rulesSelected + 1;
end while;

select ruleId from selectedRules;

Answer 2

如果你真的想找到最好的解决方案（optimal Solution），问题是你必须检查10个ruleId的所有可能组合，并找出每个可能的组合返回多少个hashId。问题在于，组合的数量完全是不同数量的ruleid ^ 10（事实上，数量更小，如果你考虑到不能在组合中重复相同的ruleId...它是m个元素的组合10 人一组）。

• 注意：准确地说，可能的组合数是

  m!/(n! (mn)!) => m!/(10! (m-10!)) 其中 ! 是阶乘：m！=米*米-1*米-2...*3*2*1

要执行此组合，您必须将表与其自身连接 10 次，不包括之前的规则 ID 组合，有点像这样：

select m1.ruleid r1, m2.ruleid r2, m3.ruleid r3 ...
from matches m1 inner join matches m2 on m2<>m1 
   inner join matches m3 on m3 <> m1 and m3 <> m2
     ...

然后你必须找到最高的计数

select r1, r2, r3..., count(distinct hashid) 
from ("here the combinations of 10 ruleIds define above") G10
inner join M
  on ruleid = r1 or ruleid = r2 or ruleid=r3...
group by r1, r2, r3...

这个巨大的查询将花费大量时间来运行。

可能有更快的程序，但会给您带来次优的结果。

一些优化：

这可以在某种程度上进行优化，具体取决于数据形状，寻找等于或包含在其他组中的组。这将需要少于 (m*(m+1))/2 次操作，与其他数字相比，这是一个大问题，特别是如果很可能找到几个可以丢弃的组，这将降低 m。无论如何，主要成本仍然巨大。