这是一个创建于 2555 天前的主题，其中的信息可能已经有所发展或是发生改变。
刚刚看到网友关于亲戚关系算法的问题 [分享一个亲属关系的算法] ： 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 2
@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 个对外的箭头。（我还没学过图论不懂得怎么说） 然后把能找到的称呼全部填进去，按照用户的点击跟踪就行了，也容易反向计算。 |
Select Language