c**m
发帖数: 30 | 1 要处理些数据，用map,set,recursion搞搞，结果有点慢。有没有好的algorithm?
Data can be quite large.
Given a list of sequences, each of which is a combination of ids, group the
sequences that share at least one id into a single sequence composed of all
the unique ids.
For example, say sequences are people's names, group people who share first
and/or last name.
ie.
John Smith
Paul Smith
John Hunt
Paula Foster
Kelly Foster
Chapman Kelly
would give two new sequences:
John Smith Paul Hunt
Paula Foster Kelly Chapman | w***g
发帖数: 5958 | 2 这东西本质上是个图划分问题. 图的节点为各个ID, 每个子列表给出的节点间互相连接
. 问题要求把大图分解成几个独立的连通子图.
算法可以分两步．
１. 建立大图. 大图的节点用map表示.
每读到一个新的节点就往大图中加上这个节点.
没读到一个子列表,如a b c d, 就加入边, , . 对于保证连通性, 这些就
够了.
2. 遍历大图找出联通子图.
while (图不空) {
从任意节点起广度优先搜索大图
搜到的部分就是一个联通子图了, 输出成一个列表
把上面搜到的节点从图中去掉
}
算法复杂度为O(N), 应该不至于很慢.
the
all
first
【在 c**m 的大作中提到】
: 要处理些数据，用map,set,recursion搞搞，结果有点慢。有没有好的algorithm?
: Data can be quite large.
: Given a list of sequences, each of which is a combination of ids, group the
: sequences that share at least one id into a single sequence composed of all
: the unique ids.
: For example, say sequences are people's names, group people who share first
: and/or last name.
: ie.
: John Smith
: Paul Smith
| c**m
发帖数: 30 | 3 用map要加O(nlgn).
看中文technical我不是很熟，有一点不清楚。大图随便一个key你怎样找到所有和它连
起来的其它key?
还有一个要求没说出来，就是order preservation，有办法实现吗？
ie:
b c, a b, d a => b c a d
a b, b c, d a => a b c d
连接
些就
【在 w***g 的大作中提到】
: 这东西本质上是个图划分问题. 图的节点为各个ID, 每个子列表给出的节点间互相连接
: . 问题要求把大图分解成几个独立的连通子图.
: 算法可以分两步．
: １. 建立大图. 大图的节点用map表示.
: 每读到一个新的节点就往大图中加上这个节点.
: 没读到一个子列表,如a b c d, 就加入边, , . 对于保证连通性, 这些就
: 够了.
: 2. 遍历大图找出联通子图.
: while (图不空) {
: 从任意节点起广度优先搜索大图
| w****i
发帖数: 964 | 4 if using hash table to compare existing ids, the speed should be ok
in python:
ids, group = {}, []
for seq in seqlist:
....n = len(group)
....g = [ids.get(id, n) for id in seq]
....groupid = min(g)
....if groupid == n: group.append([])
....for i in xrange(len(seq)):
........if g[i] == n:
............group[groupid].append(seq[i])
............ids[seq[i]] = groupid | c**m
发帖数: 30 | 5 maybe my description wasn't clear or misleading or just wrong, but two
totally unrelated sequences X, Y could be linked by two other sequences
linked by a common id and share common ids with X and Y.
so a b, c d, e b, e d => a b c d e
here, while "a b" and "c d" are unrelated, but "e b" and "e d" are related
by 'e', and then in turn link to "a b" by 'b', and "c d" by 'd'. | c**m
发帖数: 30 | 6 actually, two unrelated sequences could be linked by another sequence,
like this: a b, c d, e b d => a b c d e
【在 c**m 的大作中提到】
: maybe my description wasn't clear or misleading or just wrong, but two
: totally unrelated sequences X, Y could be linked by two other sequences
: linked by a common id and share common ids with X and Y.
: so a b, c d, e b, e d => a b c d e
: here, while "a b" and "c d" are unrelated, but "e b" and "e d" are related
: by 'e', and then in turn link to "a b" by 'b', and "c d" by 'd'.
| w****i
发帖数: 964 | 7 ye that's more complicated than i thought
you can still merge the group if there's a sequence connect them, it doesn't
add too much time. I think the key is to hash id to groups. How big is
your data? | w****i
发帖数: 964 | 8 Try this,
group, hash = [], {}
for seq in seqlist:
....n = len(group)
....g = [hash.get(id, n) for id in seq]
....groupid = min(g)
....if groupid == n:
........group.append([])
....else:
........for dupid in list(set(g)):
............if dupid > groupid and dupid < n:
................for x in group[dupid]: hash[x] = groupid
................group[groupid] += group[dupid]
....for i in xrange(len(seq)):
........hash[seq[i]] = groupid
........if g[i] == n: group[groupid].append(seq[i])
it doesn't gi |
| c**m
发帖数: 30 | 9 Data is kind of big, total size can be up to multi GiB. The sequence links
can run very long. Also need to run multi passes based on different
parameters. A 16GB 8-core xeon machine can't handle the biggest data so
have to split up among multiple machines. Your solution looks better than
mine, but I think they are similar except I use c++ std::map not hash.
actually I don't see you using hash in your first solution, but that one
doesn't really work. | s***e
发帖数: 122 | 10 我觉得这个问题可能得先想清楚数据结构。我的想法是：
用一个二维的链表来存储你最后的结果(行内是单向链接，行头双向链接)：
a->b
|
c->d
节点的结构: (string s, int order, node* prevHead, node* nextHead, node* next)
用一个哈希表来存储所有的单词和对应的行头：
a->pa，b->pa，c->pc，d->pc
用一个哈希表来存储行头和对应的行尾：
pa->pb, pc->pd
这样当你加一个新的单词组的时候，我们先建一个关联列表，用来存储该单词组关联到
的所有行头。
对每个词先查哈希表看这个词是否以前出现过。如果出现过，我们就找到那个词所在
的行头，放到一个关联列表中；如果没有出现我们就把新词加到二维链表中，然后加到
哈希表中，同时把这个新行头也放到关联列表中。
当所有的单词扫描完，把关联列表排一下序，然后把二维链表中对应的行合并起来。
比如如上的时候，我们要加一个单词组e b f d：
1) 加e：哈希表中没找到，我们把它加到二维链表中
a->b
|
c->d
|
e
然后加到哈希表中
a->pa，b->pa，c
【在 c**m 的大作中提到】
: Data is kind of big, total size can be up to multi GiB. The sequence links
: can run very long. Also need to run multi passes based on different
: parameters. A 16GB 8-core xeon machine can't handle the biggest data so
: have to split up among multiple machines. Your solution looks better than
: mine, but I think they are similar except I use c++ std::map not hash.
: actually I don't see you using hash in your first solution, but that one
: doesn't really work.
| | | g*****g
发帖数: 34805 | 11 听着挺复杂，其实就是画一个无向图，最后列出所有子图。
数据结构也很简单。用Java表示的话结构如此。
class Word {
Set linkedWords;
boolean marker;
}
用一个哈希表指向每个单词。
每个单词是一个节点，顺序两个单词是一个无向边。比如句子
A B C
给AB, 和BC做双向连接表示无向边，Set会自动过滤重复边，任何语言应该有
这样的类实现，set本身可以是哈希表。比如Java里HashSet就是一个实现。
最后Iterate哈希表，从任一结点出发，做深度优先遍历，
用marker标识一下是否已经被访问，没访问过设成访问，
打印并将此节点从哈希表中剔除。哈希表空结束。
如果有N个单词，M条边。这个算法复杂度是O(N+M), N
也就是文章单词总数。
【在 s***e 的大作中提到】
: 我觉得这个问题可能得先想清楚数据结构。我的想法是：
: 用一个二维的链表来存储你最后的结果(行内是单向链接，行头双向链接)：
: a->b
: |
: c->d
: 节点的结构: (string s, int order, node* prevHead, node* nextHead, node* next)
: 用一个哈希表来存储所有的单词和对应的行头：
: a->pa，b->pa，c->pc，d->pc
: 用一个哈希表来存储行头和对应的行尾：
: pa->pb, pc->pd
| s***e
发帖数: 122 | 12 你这个跟wdong说的方法差不多，但是不能保证顺序吧。
【在 g*****g 的大作中提到】
: 听着挺复杂，其实就是画一个无向图，最后列出所有子图。
: 数据结构也很简单。用Java表示的话结构如此。
: class Word {
: Set linkedWords;
: boolean marker;
: }
: 用一个哈希表指向每个单词。
: 每个单词是一个节点，顺序两个单词是一个无向边。比如句子
: A B C
: 给AB, 和BC做双向连接表示无向边，Set会自动过滤重复边，任何语言应该有
| g*****g
发帖数: 34805 | 13 原题没要求要保证顺序，要保证顺序很容易。
出现新单词的时候给个数字标号，打印子图之前
排序一下即可。因为节点数远远小于边的数目。
这个复杂度在最坏情况下就是O(mlogm + n)
通常mlogm < N < m^2，所以计算复杂度不变仍然是O(N)。
存储复杂度是O(m^2)，
【在 s***e 的大作中提到】
: 你这个跟wdong说的方法差不多，但是不能保证顺序吧。
| s***e
发帖数: 122 | 14 只是问问哈，你的m和n代表什么？O(m^2)会不会太大？
【在 g*****g 的大作中提到】
: 原题没要求要保证顺序，要保证顺序很容易。
: 出现新单词的时候给个数字标号，打印子图之前
: 排序一下即可。因为节点数远远小于边的数目。
: 这个复杂度在最坏情况下就是O(mlogm + n)
: 通常mlogm < N < m^2，所以计算复杂度不变仍然是O(N)。
: 存储复杂度是O(m^2)，
| g*****g
发帖数: 34805 | 15 M是不重复单词数，N是文章总单词数。
M就是节点，N是边。会不会太大要看你
处理什么东西了。
【在 s***e 的大作中提到】
: 只是问问哈，你的m和n代表什么？O(m^2)会不会太大？
| s***e
发帖数: 122 | 16 感觉这个方法除了存储复杂度之外还是免除不了最终排序的复杂性：需要把最终生成的
哈希表扫一遍，建成一个List>类型的新结构，然后将每个List要排序
一次，然后将List>再排一次序。原因在于扫描原始数据的时候没有保留顺
序。
【在 g*****g 的大作中提到】
: M是不重复单词数，N是文章总单词数。
: M就是节点，N是边。会不会太大要看你
: 处理什么东西了。
| w****i
发帖数: 964 | 17 其实就是产生一个id到group的hash，用得了这么麻烦？
我的code时间O(N), 存储O(M) | s***e
发帖数: 122 | 18 仔细看了一下你的方法，发现我的思路完全就是copy你的。。呵呵
我只对你的代码改了一点：第二遍扫描可以不用，因为第一遍扫描进去的时候实际上保
持了顺序的。(我查了一下你的list(set(g))好像会排序，为了保险我又sort了一下。) 所以只需要在合并group[groupid]和group[dupid]之后，把group[dupid]
清空就可以了。输出的时候只需要忽略空group就可以了。
感叹一下这类代码用python写起来真是简单清晰。
seqlist = [['abstract', 'b'],['c','d'],['d','e','f','b'], ['h','i']]
group, hash = [], {}
for seq in seqlist:
....n = len(group)
....g = [hash.get(id, n) for id in seq]
....groupid = min(g)
....if groupid == n:
........group.append([])
....else:
........g_sorted = list(set(
【在 w****i 的大作中提到】
: 其实就是产生一个id到group的hash，用得了这么麻烦？
: 我的code时间O(N), 存储O(M)
| w***g
发帖数: 5958 | 19 排序不是个问题. 因为所有的单词按出现顺序是有序的, 如果按出现顺序存下来的话是
不需要再排序的.
我觉得O(NlogN)是没法避免的. 因为不管怎么样新来一个单词后要在已有单词中查找.
。) 所以只需要在合并group[groupid]和group[dupid]之后，把group[dupid]
【在 s***e 的大作中提到】
: 仔细看了一下你的方法，发现我的思路完全就是copy你的。。呵呵
: 我只对你的代码改了一点：第二遍扫描可以不用，因为第一遍扫描进去的时候实际上保
: 持了顺序的。(我查了一下你的list(set(g))好像会排序，为了保险我又sort了一下。) 所以只需要在合并group[groupid]和group[dupid]之后，把group[dupid]
: 清空就可以了。输出的时候只需要忽略空group就可以了。
: 感叹一下这类代码用python写起来真是简单清晰。
: seqlist = [['abstract', 'b'],['c','d'],['d','e','f','b'], ['h','i']]
: group, hash = [], {}
: for seq in seqlist:
: ....n = len(group)
: ....g = [hash.get(id, n) for id in seq]
| s***e
发帖数: 122 | 20 不用啊，你看我们之前说的建立一个 Word->Group 哈希表，就是为了实现O(N)。
其中只有一次需要排序就是把新单词组涉及到的所有已有Group要排序一次，这样这些
Group合并的时候才会继续有序。
找.
【在 w***g 的大作中提到】
: 排序不是个问题. 因为所有的单词按出现顺序是有序的, 如果按出现顺序存下来的话是
: 不需要再排序的.
: 我觉得O(NlogN)是没法避免的. 因为不管怎么样新来一个单词后要在已有单词中查找.
:
: 。) 所以只需要在合并group[groupid]和group[dupid]之后，把group[dupid]
| w****i
发帖数: 964 | 21 第二遍扫描是必须的,一遍扫描不能保证顺序
consider this case
a b
c d
b e
c e
the correct order should be [a b c d e]
if you only scan once and simply merge the group, you get [a b e c d] | s***e
发帖数: 122 | 22 你说的有道理，不过第二遍扫描可以在不重复的单词中做，而不需要在原始数据上做了
，设想原始数据如果有几个G，而且假设要从文件里面读取的话，很费时间。
我的想法是增加一个uni_words的list，然后新词依照顺序加进去，也就是加进hashtable的时候。
然后就按照你第二次扫描应该就可以了。
【在 w****i 的大作中提到】
: 第二遍扫描是必须的,一遍扫描不能保证顺序
: consider this case
: a b
: c d
: b e
: c e
: the correct order should be [a b c d e]
: if you only scan once and simply merge the group, you get [a b e c d]
|
|
