005.测验.情景之男女相亲算法

# 005.测验.情景之男女相亲算法

相亲算法，源于剩男剩女的相亲，解决男女速配问题。
过程大概是：根据相亲喜好，男女互相，按分值匹配。

@史荣久 / 2015-02-02 / CC-BY-SA-3.0

## 任务说明

事实上，爱美之心人皆有之，追求物质符合自然选择。
现状是，韩剧里高富帅棒子稀缺，白富美洗白的居多。

现在，我们搞一个相亲算法，让高富帅和白富美速配。
有三对单身男女，姓名，特点和心中的TA的特点如下：

人及属性 | 对TA的喜好及分值
1：高　富 | 富:10,白:20,美:30
2：白　富 | 富:10,高:20,帅:30
3：高　帅 | 富:30,白:10,美:20
4：白　美 | 富:30,高:10,帅:20
5：高富帅 | 富:10,白:30,美:20
6：白富美 | 富:10,高:30,帅:20

这样，以男1号"高富"为例，他对女选手喜好如下：
女2号：白+富 = 20+10 = 30
女4号：白+美 = 20+30 = 50
女6号：白+富+美 = 10+20+30 = 60

算法只对喜好值求和，对存在加，不存在的不加。
以此类推，为每个单身者计算出候选人列表。

男1：女2（30），女4（50），女6（60）
女2：男1（30），男3（50），男5（60）
男3：女2（40），女4（30），女6（60）
女4：男1（40），男3（30），男5（60）
男5：女2（40），女4（50），女6（60）
女6：男1（40），男3（50），男5（60）

可以看到，男5和女6最受欢迎，但这只是单方面的。
以女6为例，把男相女和女相男的分值求和，得总分。

女6+男1 = 40+60 = 100
女6+男3 = 50+60 = 110
女6+男5 = 60+60 = 120

这样，女6和男5分值最高，匹配成功。以此类推。
最后，牵手情况：男5+女6，男1+女4，男3+女2

## 数据存储

以下几张表，无事务，只读不写，因此使用MyISAM表引擎。

CREATE TABLE IF NOT EXISTS `USER` (
`UID` INT NOT NULL COMMENT '单身用户ID',
`GENDER` INT NOT NULL COMMENT '性别：0-女，1-男',
`NAME` VARCHAR(45) NOT NULL COMMENT '用户姓名',
PRIMARY KEY (`UID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;

CREATE TABLE IF NOT EXISTS `LABEL` (
`LID` INT NOT NULL COMMENT '标签ID',
`NAME` VARCHAR(45) NOT NULL COMMENT '标签名字',
PRIMARY KEY (`LID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;

CREATE TABLE IF NOT EXISTS `USER_LABEL` (
`UID` INT NOT NULL COMMENT '用户',
`LID` INT NOT NULL COMMENT '用户的标签',
PRIMARY KEY (`UID`, `LID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;

CREATE TABLE IF NOT EXISTS `USER_LOVE` (
`UID` INT NOT NULL COMMENT '用户',
`LID` INT NOT NULL COMMENT '喜好的标签',
`SCORE` INT NULL COMMENT '喜好分值',
PRIMARY KEY (`UID`, `LID`))
ENGINE = MyISAM
DEFAULT CHARACTER SET = utf8
COLLATE = utf8_bin;

-- 插入记录
INSERT INTO `LABEL` (`LID`, `NAME`) VALUES 
(0, '富'),(1, '高'),(2, '白'),(3, '帅'),(4, '美');

INSERT INTO `USER` (`UID`, `GENDER`, `NAME`) VALUES 
(1, 1, '高富'),(3, 1, '高帅'),(5, 1, '高富帅'),
(2, 0, '白富'),(4, 0, '白美'),(6, 0, '白富美');

INSERT INTO `USER_LABEL` (`UID`, `LID`) VALUES 
(1, 0),(1, 1),
(2, 0),(2, 2),
(3, 1),(3, 3),
(4, 2),(4, 4),
(5, 0),(5, 1),(5, 3),
(6, 0),(6, 2),(6, 4);

INSERT INTO `USER_LOVE`(`UID`,`LID`,`SCORE`) VALUES
(1, 0, 10),(1, 2, 20),(1, 4, 30),
(2, 0, 10),(2, 1, 20),(2, 3, 30),
(3, 0, 30),(3, 2, 10),(3, 4, 20),
(4, 0, 30),(4, 1, 10),(4, 3, 20),
(5, 0, 10),(5, 2, 30),(5, 4, 20),
(6, 0, 10),(6, 1, 30),(6, 3, 20);

-- 检查数据
SELECT U.NAME,
GROUP_CONCAT(L.NAME ORDER BY L.LID) 
FROM USER_LABEL AS UL,USER AS U,LABEL AS L
WHERE UL.UID = U.UID AND UL.LID=L.LID 
GROUP BY U.NAME ORDER BY U.UID;

SELECT U.NAME,
GROUP_CONCAT(L.NAME,':',UL.SCORE ORDER BY L.LID) 
FROM USER_LOVE AS UL,USER AS U,LABEL AS L
WHERE UL.UID = U.UID AND UL.LID=L.LID 
GROUP BY U.NAME ORDER BY U.UID;

## 问题来了

我们称以上算法为相亲算法（blindate），请尽情发挥。

（1）实现相亲算法，输入男，输出候选女的列表和分值。
即：输入男（UID），得到候选女的列表（UID,SCORE）

（2）用户量增到男女各5万，人均标签从3个增到10个。
要重构程序实现，要求候选女的列表按喜比例分配。

例如：男1的喜好值仍为：富:10,白:20,美:30，
则输出列表中，富占1/6，白占2/6，美占3/6。
列表需要去重(distinct)，数量不足时需要补充。
优先满足每用户输出100个候选，然后考虑比例。

（3）假设，相亲算法在10万男x10万女时，有性能瓶颈。
请谈谈改善方法和依据。

----
题图：《非诚勿扰》是一档男女速配的相亲节目，很多人疑其真假，评其美丑，但这些真的那么重要么？
原文：http://www.moilioncircle.com/actions/005.quiz.case-blind-date.html