刚刚看到网友关于亲戚关系算法的问题 [分享一个亲属关系的算法] : https://www.v2ex.com/t/408080#reply10
说道还差一个程序员实现,哈哈哈,看到我异常兴奋!因为…………我已经写完了~ 顺便打个广告
算法原理: http://www.jianshu.com/p/74290f1ae838
1
mumuy OP 不知道对方写成论文会不会被怀疑抄袭……我的算法是去年写的
|
2
mohoumk2 2017-11-24 11:35:38 +08:00 via Android 1
你需要个小米内置的亲戚关系计算器
|
3
mumuy OP @mohoumk2 小米内置的那个用的就是我的开源代码啊!不信你可以分析它的网页版本: http://www.miui.com/zt/calculator2016/dist.php
|
4
jasontse 2017-11-24 11:41:18 +08:00 via iPad 1
没有人记得「三姑六婆」
|
5
chuanqirenwu 2017-11-24 11:42:53 +08:00
他那算法不实用,只能做理论分析,或者作为你这个算法的前序处理。
|
6
mumuy OP @jasontse 记得呀,计算器的想法我是看到了这个 APP 的,但是算法是我自己写的,和它的思路不一样,你可以在我的算法原理文章内看到我说的不一样在哪里
|
7
mumuy OP @chuanqirenwu 感觉写成论文不合适了,没有具体阐明怎么实现,而且我的程序处理的问题更复杂。关键是,我的算法去年就开源了………
|
9
linKnowEasy 2017-11-24 11:51:53 +08:00
点个赞, 比较喜欢这种 生活 代码化 的处理
|
10
zhy0216 2017-11-24 12:06:37 +08:00
有向图 + 一堆数据 应该可以解决
`2.从“关系链-称谓集合”映射关系可知,这两个对象的关系链分别是:"m,xb,w"和"h,m",合并后的关系即:"m,xb,w,h,m"` 你的数据结构是不是需要 inverted index 下 会快一些 |
11
mumuy OP @zhy0216 现在用那个程序很慢吗?主要考虑问题是同一个关系链有多种称呼,一个称呼有多种关系链;比如外婆也可以叫成姥姥,表哥有舅家的姑家的姨家的
|
12
zhy0216 2017-11-24 12:18:33 +08:00
没用过。。。 只是理论上而已
字典可以有多个 key 对应同一个 value 的 |
14
zhy0216 2017-11-24 12:28:21 +08:00
我的意思可以调换一下 key-value
比如这样 {ab: [cc, dd]} => {cc: ab, dd: ab} 因为你查的是 cc,dd 第一种字典最坏的情况需要遍历所有的 value, 第二种一般认为是 O(1) |
15
mumuy OP @zhy0216 我的意思是{ab: [cc, dd],cd:[cc]} => {cc: ab, dd: ab}你要怎么办????
|
16
mumuy OP @zhy0216 我的意思是{ab: [cc, dd],cd:[cc]}怎么办? cc 在多个地方出现,而且不用遍历数组的,直接 indexOf 就好
|
17
chaoxu 2017-11-24 13:15:45 +08:00
@mumuy 我很高兴也有人想过这个问题. 但你有些评论并不适用于我们领域.
"感觉写成论文不合适了" 写成论文是否合适这个应该是学术界内的人评判. "没有具体阐明怎么实现" 做理论的关心的是算法的理论复杂度. 我们并不关心是否真的写成一个程序. 如果有程序员写出来那是极好的. 但那不是我们的工作. "而且我的程序处理的问题更复杂。" 我不知道你有没有看整个文章. 我们解决的不是同一个问题, 我们解决的是一个抽象的问题. 我在社交网络上所给的例子都是简单易懂的简化版, 所有词语都是相同权值的. 每个词语可以有不同权值, 我们要找的是最短的路径. 而且我的算法是适用于 sudanese pattern 的, 并没有专门对应中文亲属关系. 但是这都不是为什么我们发 paper. 重要的来自于我们证明了算法的复杂度和正确性(而正确性本身需要定义问题是什么). "关键是,我的算法去年就开源了………" 这是我的疏忽, 没有发现你的这个程序. 等 IPL 那边 review 过后, 会在 introduction 的提到你的 library. 因为你超越了我们说的现有的两个 benchmark 的弱点(三姑六婆和小米内置计算器, 其实蛮奇怪的因为你提到内置用的就是你的系统). 但是, 你的程序不能解决我们要解决的问题. |
18
zhy0216 2017-11-24 13:36:08 +08:00
@mumuy
indexOf 就是 O(n) 1. 原先的字典 里面可以是 set,可能考虑到 js 没有 set 用的 list 2. 按你说的情况 {ab: [cc, dd],cd:[cc]} => {cc: [ab, cd], dd: [ab]} |
19
mumuy OP @zhy0216 但是我算完回来还要把结果翻译一遍啊,比如算完是 ab,你不还得一样查一遍吗???我一份数据不可能存两种方式的
|
20
zhy0216 2017-11-24 14:07:19 +08:00
|
21
mumuy OP @zhy0216 如果我把空间换成了时间,在程序里面空间就是文件大小,文件的加载本身就是需要时间的,到头来我并不会占到便宜;软件开发我还需要考虑维护成本问题,如果一份数据有两种格式,本身就造成了维护的压力也容易出错,两种格式程序就要有两个参照,如果出错了以谁为主?
|
25
zhy0216 2017-11-24 14:50:51 +08:00
@mumuy 我觉得你可能还是没看明白我的意思
第二种数据格式你可以用几行代码生成出来的. 不是指程序的文件大小,而是使用内存的大小 |
26
Nott 2017-11-24 15:03:21 +08:00
只关注结果,小时候寄读于姑姑家,天天跟姑父的侄子们打交道,于是一查:爸爸的姐姐的老公的弟弟的儿子:貌似他 /她跟你不是很熟哦!
|
27
ningbo16 2017-11-24 15:13:37 +08:00
|
28
littiefish 2017-11-24 15:13:53 +08:00
@Nott 用三姑六婆试了下,你这个有两个称呼,姻兄 /姻弟。。。
|
29
Level5 2017-11-24 15:42:12 +08:00
为什么选择了性别以后就不能选“夫或妻”了?你叫同 x 志情何以堪?
|
32
Nott 2017-11-24 15:46:50 +08:00
@littiefish #28 我很怀疑生活中的通俗称呼中是否有这种称呼。
|
41
jiangzhuo 2017-11-24 18:22:33 +08:00
这个不方便啊,就不能搞个那种输入对方名字或者身份证号直接出关系的。
|
42
WAITUNG 2017-11-24 18:55:14 +08:00
WHAT ?过不了 QQ 安全验证? 红色感叹号
|
44
xfspace 2017-11-24 21:47:33 +08:00 via Android
App 放百度盘下载贼麻烦,来个直接的链接,谢谢~
|
47
cpdyj0 2018-11-13 22:06:02 +08:00
挖个坟,,想问下是不是可以用图实现(查表),我想下:
小米计算器可选择的关系有 10 种, 那么一个人一个节点就有 10 个对外的箭头。(我还没学过图论不懂得怎么说) 然后把能找到的称呼全部填进去,按照用户的点击跟踪就行了,也容易反向计算。 |