mysql - SQL 选择最符合标准的 10 条记录集

Question

我的 table :

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(又名“有多少哈希匹配每个规则”)

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

2) 选出10条最好的规则(ruleIds)，即选出10条组合匹配的唯一哈希数最多的规则。这意味着如果另一个规则涵盖所有相同的哈希值，则匹配大量哈希值的规则不一定是好的规则。基本上我想选择 10 个捕获最独特的 hashId 的 ruleId。

?

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

Answer 1

我认为您的问题是 "knapsack problem" 的变体.

我想你已经明白你不能随便拿ruleIds最匹配hashIds就像其他答案所暗示的那样，因为虽然每个 ruleIds匹配说 100 hashIds , 他们可能都匹配 same 100 hashIds ...但如果您选择了其他 10 个 ruleIds仅匹配 25 hashIds , 但对于每个 hashIds由每个 ruleId 匹配是独一无二的，你最终会得到更独特的hashIds用那一套。

要解决这个问题，您可以从选择 ruleId 开始。匹配最多 hashIds , 然后接下来选择 ruleId匹配最多 hashIds未包含在 hashIds 中的与前一个 ruleIds 匹配...继续此过程，直到您选择了 10 ruleIds .

您的数据分布中仍然可能存在异常，这会导致无法生成 ruleIds 的最佳集合。 ...因此，如果您想发疯，可以考虑实现遗传算法来尝试提高 10 组 ruleIds 的“适合度” .

这不是 SQL 特别适合处理的任务，but here's an example of the knapsack problem being solved with a genetic algorithm written in SQL(!)

---

编辑

---

这是一个未经测试的解决方案实现，其中 ruleIds一次选择 1 个，每次迭代选择 ruleId拥有最独特的hashIds以前没有被任何其他选定的ruleIds 覆盖:

--------------------------------------------------------------------------
-- 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;