K******g
发帖数: 1870 | 1 一个很open的问题，一个十分大的log file，每一行是URL+session ID+timestamp
请问怎么建立一个数据结构，给定一个URL，能快速的知道有哪些Session ID访问了它。
基本思路是建立hashtable， 但是这个hashtable怎么建立。问题问的很细，比如怎么
选hashfunction， 怎么规划hash table的大小，。。。
如果不用hashtable，有其他的数据结构吗？
请高手指教。 |
g**e
发帖数: 6127 | 2 如果url是unique的，用url本身做hash function就可以。如果url很长，我想可以用字
符串的长度＋字符串做hash。也许有更好的办法。
不用hash，那就用B+ tree呗，这就是一个很普通的数据库表结构
我觉得这里hashtable还不见得有B+ tree效率高
它。
【在 K******g 的大作中提到】
: 一个很open的问题，一个十分大的log file，每一行是URL+session ID+timestamp
: 请问怎么建立一个数据结构，给定一个URL，能快速的知道有哪些Session ID访问了它。
: 基本思路是建立hashtable， 但是这个hashtable怎么建立。问题问的很细，比如怎么
: 选hashfunction， 怎么规划hash table的大小，。。。
: 如果不用hashtable，有其他的数据结构吗？
: 请高手指教。
|
k*n
发帖数: 150 | 3 思路是你提的人家顺着说的还是人家说的让你发挥？
如果是我的话，第一反应就是awk，基本上是线性时间内处理一遍
虽然很笨，但是这是最直接和方便的办法，如果是面试，我肯定会先说
接下来，十分大的logfile本身我觉得不应该完全放到内存数据结构里
如果是logfile的话，它是不断增长的是比较合理的假设，所以不能考虑重写它
所以就是以空间换时间的办法，建立一个内存中的索引
这一般来说又有两种选择，hashtable或者B+树
仍然视实际情况而定，如果为了实现快速使用方便，我首选hashtable
因为大多数高级语言都有很好的hashtable的实现
其实我觉得对url来说，hashfunction并不是关键
hashtable在这个应用中最关键的缺陷在于这个索引几乎必须完全保存在内存里
那么当问题是GB数量级的话还可以handle，再增长的话就基本不work了
这种情况下，B+树或者类似的树索引是我能想到的最后的解决方案了
占用多少内存自己说的算，访问也很快，最大缺陷是实现复杂
每一个细节处理都很麻烦，这就没法再细说了
它。
【在 K******g 的大作中提到】
: 一个很open的问题，一个十分大的log file，每一行是URL+session ID+timestamp
: 请问怎么建立一个数据结构，给定一个URL，能快速的知道有哪些Session ID访问了它。
: 基本思路是建立hashtable， 但是这个hashtable怎么建立。问题问的很细，比如怎么
: 选hashfunction， 怎么规划hash table的大小，。。。
: 如果不用hashtable，有其他的数据结构吗？
: 请高手指教。
|
g**e
发帖数: 6127 | 4 赞，文件小awk直接就搞定了
其实我还是觉得这个应该存在数据库而不是logfile
【在 k*n 的大作中提到】
: 思路是你提的人家顺着说的还是人家说的让你发挥？
: 如果是我的话，第一反应就是awk，基本上是线性时间内处理一遍
: 虽然很笨，但是这是最直接和方便的办法，如果是面试，我肯定会先说
: 接下来，十分大的logfile本身我觉得不应该完全放到内存数据结构里
: 如果是logfile的话，它是不断增长的是比较合理的假设，所以不能考虑重写它
: 所以就是以空间换时间的办法，建立一个内存中的索引
: 这一般来说又有两种选择，hashtable或者B+树
: 仍然视实际情况而定，如果为了实现快速使用方便，我首选hashtable
: 因为大多数高级语言都有很好的hashtable的实现
: 其实我觉得对url来说，hashfunction并不是关键
|
s*********e
发帖数: 36 | 5 如果以后经常会range search，那么用B+ tree适合。如果确定说就用hash table，我
赞同这句
“hashtable在这个应用中最关键的缺陷在于这个索引几乎必须完全保存在内存里”，
logfile应该是
不断增大的，一台机器的内存很快就无法承受。如果可以用distributed hash table，
把hash
table分到几台联机的机器上用consistent hashing可以做。
【在 k*n 的大作中提到】
: 思路是你提的人家顺着说的还是人家说的让你发挥？
: 如果是我的话，第一反应就是awk，基本上是线性时间内处理一遍
: 虽然很笨，但是这是最直接和方便的办法，如果是面试，我肯定会先说
: 接下来，十分大的logfile本身我觉得不应该完全放到内存数据结构里
: 如果是logfile的话，它是不断增长的是比较合理的假设，所以不能考虑重写它
: 所以就是以空间换时间的办法，建立一个内存中的索引
: 这一般来说又有两种选择，hashtable或者B+树
: 仍然视实际情况而定，如果为了实现快速使用方便，我首选hashtable
: 因为大多数高级语言都有很好的hashtable的实现
: 其实我觉得对url来说，hashfunction并不是关键
|
K******g
发帖数: 1870 | 6 请问用trie可不可以呢？每个leave结点代表一个完整的URL，它的key可以建立一个
session ID的链表。
这个跟hashtable 和 B tree比起来，怎么样呢。多谢。
【在 k*n 的大作中提到】
: 思路是你提的人家顺着说的还是人家说的让你发挥？
: 如果是我的话，第一反应就是awk，基本上是线性时间内处理一遍
: 虽然很笨，但是这是最直接和方便的办法，如果是面试，我肯定会先说
: 接下来，十分大的logfile本身我觉得不应该完全放到内存数据结构里
: 如果是logfile的话，它是不断增长的是比较合理的假设，所以不能考虑重写它
: 所以就是以空间换时间的办法，建立一个内存中的索引
: 这一般来说又有两种选择，hashtable或者B+树
: 仍然视实际情况而定，如果为了实现快速使用方便，我首选hashtable
: 因为大多数高级语言都有很好的hashtable的实现
: 其实我觉得对url来说，hashfunction并不是关键
|
g**e
发帖数: 6127 | 7 trie适合处理电话号码，字典什么的。这里url太长，字符太多，更消耗内存。另外
trie 查询复杂度O(n)，没有优势
【在 K******g 的大作中提到】
: 请问用trie可不可以呢？每个leave结点代表一个完整的URL，它的key可以建立一个
: session ID的链表。
: 这个跟hashtable 和 B tree比起来，怎么样呢。多谢。
|
p********7
发帖数: 549 | |
p********7
发帖数: 549 | 9 我第一时间想到map>
用hashtable也可以，效率高些。这时，set可以改为linked list。我认为ID
可以转化为long，这样一来，linked list可以按照ID顺序插入或者查找，可以用
binary search。对于设计hash function，我认为url可以用一个函数提取感兴趣的部
分，如果想统计网站，就只用提取域名，比如http://www.mitbbs.com/mitbbs_bbsedit.php?brdname=JobHunting&title=Re%3A+%BC%B1%A3%AC+%C7%EB%BD%CC%B8%F6%C3%E6%CA%D4%CE%CA%CC%E2&author=paul198247&file=M.1277911431_2.40&id=31639529&gid=31638769 域名是mitbbs，还要记录com，其他部分可以省略。这么一来可以简单设计一个hash function：假设合法的郁闷符号有NUM个，name[i]表示每一位域名的数值，定义a－z是11－36，加数 |
s*******s
发帖数: 46 | |
