|
锁定老帖子 主题：百度笔试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-10
重复的url肯定很多，我想尽可能将相同的url都放在一个文件，到时查就不必遍历所有数据
大楷意思： 根据url hash 对1000 取模，让所有数据分布到1000个文件中去，当你要查一个url某段时间的访问量，就只需把对应的那一个文件加入内存再查询。如果内存不够，那就在细分。 不知道这样行不行 |
| 返回顶楼 | |
|
发表时间：2011-05-10
ip数字化，url分词，再抽取dimension重编码，查总数尽量走索引全扫,建索引不够，还应该降低索引本身的尺寸，1000亿减几个字节就能减很大io
反复说按时间段，说明时间是必选条件，按时间分区，建分区索引 考实习生这个问题面试官就有问题，这是运维和设计的经验，实习生根本没道理能提高效的方案 nosql其实解决日志问题还挺好，因为对事务和一致性没太大需求，查询也不复杂 |
| 返回顶楼 | |
|
发表时间：2011-05-10
完全没答上来，基础太差，数据库的基本概念基本忘光了，看来还是先打好基础，其它的应用神马的，慢慢来吧，一口是吃不成个胖子的，只能这样安慰自己了
|
| 返回顶楼 | |
|
发表时间：2011-05-10
wang8118 写道 kanny87929 写道 如果要设计一个系统那真的是难为你了
但要是让你设计查询的思路还是可以的 假设就一张表，表里3个字段 url, ip, date 存上1000亿条数据，你需要在这3个字段上都建立索引，利用分词 如果里面有一条数据 url:http://www.iteye.com/topic/1037635 分解这个url的词源可以为http，www.iteye.com，topic/1037635 ip:192.168.1.3 分解这个ip的词源可以为192，168，1，3 date:2011-05-10 21:56:37 分解这次date的词源可以为2011-05-10, 21, 56, 37 每个词源都可以建立索引 比如说你查的就是这条url，由于你本条url已经被分词，并且建立了索引， 也许符合http索引里有900亿，在这900亿里符合www.iteye.com的有10亿，10亿里符合topic/1037635的有103191条，那么这个就是此url的总访问量，如果加上时间的判断就是某段时间段的访问量 在1000亿条的数据表上对每一个字段，进行分词和建立索引，是一个需要精密排序算法，和也许需要多CPU分布计算处理的过程，建立索引再优化的算法也需要一定的时间，但一旦索引建立好，通过索引的归类排序查询起来就非常的快。 我不知道楼主是不是深刻理解，索引的真正目的 在数据上建立索引就是把数据进行归类排序的过程 比如我公司有100人，我为了快速在员工手册上找到这个人 我首先要知道这个员工的一些最基本属性，比如姓名，性别，年龄（当然大多就知道个姓名就够了） 那么我的员工手册的目录就要有几种讲究 如果 按，性别分为男和女，男员工从第1页到第200页，女员工从第201页到400页 然后在性别男的结果集中分，20到30岁之间的几页到几页，30到40岁之间的几页到几页 然后如果我想看一下30到40岁之间的就可以翻到拿一页开始看。 这里的排版只是个比喻，一般企业都是按职位和部门分排，这样看到那个部门就知道下面有那些员工 如果我设计了一个索引算法 有一个人叫张峰，那么把张和峰分开建立索引，那么就会把姓张的或是名字里有张这个字的人全部归类到张这个索引下（当然算法是自己定了，定的时候只要求名字开头第一个字为张的才归类，名字里有张的不算也是可以的），然后名字里有峰的人归到一类。这样就很容易快速找到 如果归类的数据集比较大，那么在归类的数据集上在归类。这个就是索引上再建立索引， 所以说为什么索引的建立和修改是需要花大量的计算和时间的 但最好还是只建立一层索引，多种索引，看到新华字典的编排就是一个典型的例子 就2种索引，一种按拼音，一种按偏旁，而按偏旁的索引又是一个层次索引，因为找到某个偏旁后，翻到那页还要有一个数笔画确认字的索引。最后你才能确认这个字在具体哪一页。 总结：索引的目的就是为了最大限度减少查询的次数。 那么百度这个1000亿数据的题目，其实应该考查你对建立索引和查询索引的一个思路，如果让你写算法，那真不是一朝一夕就马上出来的事。 学习了  +1非常好，学习了。谢谢！ |
| 返回顶楼 | |
|
发表时间：2011-05-10
厉害，我喜欢
kanny87929 写道 如果要设计一个系统那真的是难为你了
但要是让你设计查询的思路还是可以的 假设就一张表，表里3个字段 url, ip, date 存上1000亿条数据，你需要在这3个字段上都建立索引，利用分词 如果里面有一条数据 url:http://www.iteye.com/topic/1037635 分解这个url的词源可以为http，www.iteye.com，topic/1037635 ip:192.168.1.3 分解这个ip的词源可以为192，168，1，3 date:2011-05-10 21:56:37 分解这次date的词源可以为2011-05-10, 21, 56, 37 每个词源都可以建立索引 比如说你查的就是这条url，由于你本条url已经被分词，并且建立了索引， 也许符合http索引里有900亿，在这900亿里符合www.iteye.com的有10亿，10亿里符合topic/1037635的有103191条，那么这个就是此url的总访问量，如果加上时间的判断就是某段时间段的访问量 在1000亿条的数据表上对每一个字段，进行分词和建立索引，是一个需要精密排序算法，和也许需要多CPU分布计算处理的过程，建立索引再优化的算法也需要一定的时间，但一旦索引建立好，通过索引的归类排序查询起来就非常的快。 我不知道楼主是不是深刻理解，索引的真正目的 在数据上建立索引就是把数据进行归类排序的过程 比如我公司有100人，我为了快速在员工手册上找到这个人 我首先要知道这个员工的一些最基本属性，比如姓名，性别，年龄（当然大多就知道个姓名就够了） 那么我的员工手册的目录就要有几种讲究 如果 按，性别分为男和女，男员工从第1页到第200页，女员工从第201页到400页 然后在性别男的结果集中分，20到30岁之间的几页到几页，30到40岁之间的几页到几页 然后如果我想看一下30到40岁之间的就可以翻到拿一页开始看。 这里的排版只是个比喻，一般企业都是按职位和部门分排，这样看到那个部门就知道下面有那些员工 如果我设计了一个索引算法 有一个人叫张峰，那么把张和峰分开建立索引，那么就会把姓张的或是名字里有张这个字的人全部归类到张这个索引下（当然算法是自己定了，定的时候只要求名字开头第一个字为张的才归类，名字里有张的不算也是可以的），然后名字里有峰的人归到一类。这样就很容易快速找到 如果归类的数据集比较大，那么在归类的数据集上在归类。这个就是索引上再建立索引， 所以说为什么索引的建立和修改是需要花大量的计算和时间的 但最好还是只建立一层索引，多种索引，看到新华字典的编排就是一个典型的例子 就2种索引，一种按拼音，一种按偏旁，而按偏旁的索引又是一个层次索引，因为找到某个偏旁后，翻到那页还要有一个数笔画确认字的索引。最后你才能确认这个字在具体哪一页。 总结：索引的目的就是为了最大限度减少查询的次数。 那么百度这个1000亿数据的题目，其实应该考查你对建立索引和查询索引的一个思路，如果让你写算法，那真不是一朝一夕就马上出来的事。 |
| 返回顶楼 | |
|
发表时间：2011-05-10
tianshiyeben 写道 厉害，我喜欢
kanny87929 写道 如果要设计一个系统那真的是难为你了
但要是让你设计查询的思路还是可以的 假设就一张表，表里3个字段 url, ip, date 存上1000亿条数据，你需要在这3个字段上都建立索引，利用分词 如果里面有一条数据 url:http://www.iteye.com/topic/1037635 分解这个url的词源可以为http，www.iteye.com，topic/1037635 ip:192.168.1.3 分解这个ip的词源可以为192，168，1，3 date:2011-05-10 21:56:37 分解这次date的词源可以为2011-05-10, 21, 56, 37 每个词源都可以建立索引 比如说你查的就是这条url，由于你本条url已经被分词，并且建立了索引， 也许符合http索引里有900亿，在这900亿里符合www.iteye.com的有10亿，10亿里符合topic/1037635的有103191条，那么这个就是此url的总访问量，如果加上时间的判断就是某段时间段的访问量 在1000亿条的数据表上对每一个字段，进行分词和建立索引，是一个需要精密排序算法，和也许需要多CPU分布计算处理的过程，建立索引再优化的算法也需要一定的时间，但一旦索引建立好，通过索引的归类排序查询起来就非常的快。 我不知道楼主是不是深刻理解，索引的真正目的 在数据上建立索引就是把数据进行归类排序的过程 比如我公司有100人，我为了快速在员工手册上找到这个人 我首先要知道这个员工的一些最基本属性，比如姓名，性别，年龄（当然大多就知道个姓名就够了） 那么我的员工手册的目录就要有几种讲究 如果 按，性别分为男和女，男员工从第1页到第200页，女员工从第201页到400页 然后在性别男的结果集中分，20到30岁之间的几页到几页，30到40岁之间的几页到几页 然后如果我想看一下30到40岁之间的就可以翻到拿一页开始看。 这里的排版只是个比喻，一般企业都是按职位和部门分排，这样看到那个部门就知道下面有那些员工 如果我设计了一个索引算法 有一个人叫张峰，那么把张和峰分开建立索引，那么就会把姓张的或是名字里有张这个字的人全部归类到张这个索引下（当然算法是自己定了，定的时候只要求名字开头第一个字为张的才归类，名字里有张的不算也是可以的），然后名字里有峰的人归到一类。这样就很容易快速找到 如果归类的数据集比较大，那么在归类的数据集上在归类。这个就是索引上再建立索引， 所以说为什么索引的建立和修改是需要花大量的计算和时间的 但最好还是只建立一层索引，多种索引，看到新华字典的编排就是一个典型的例子 就2种索引，一种按拼音，一种按偏旁，而按偏旁的索引又是一个层次索引，因为找到某个偏旁后，翻到那页还要有一个数笔画确认字的索引。最后你才能确认这个字在具体哪一页。 总结：索引的目的就是为了最大限度减少查询的次数。 那么百度这个1000亿数据的题目，其实应该考查你对建立索引和查询索引的一个思路，如果让你写算法，那真不是一朝一夕就马上出来的事。 那么就是说这一千亿得先插入表中，这得需要多久呀， |
| 返回顶楼 | |
|
发表时间：2011-05-10
chinaagan 写道 采用缓存，然后写进日志文件里面，然后采用分布式比如hadoop来分析日志。不知道有没有道理？
我也同意你的看法 |
| 返回顶楼 | |
|
发表时间：2011-05-10
大家看这样行不行哈
创建一个数组 数组大小为 24*60*60=86400 (一天的秒数) 然后把数据中对应的时间按秒插入数组. 比如数组中索引为0的就是00:00:01秒 依次排开. 这样如果要取得某段时间的数据,取得该时间段对应数组下标的索引即可. 前提是URL的参数有时间这个参数. 但是对于IP我就完全没有思路了... 除非IP后面也跟了参数的 |
| 返回顶楼 | |
|
发表时间：2011-05-10
100亿条数据放在数据库里会死人的。
直接参考apache log机制就可以，按日期时间分目录和文件保存，一般一小时一个log文件应该够了，如果log文件很大那10分钟一个文件，最后用awk统计数据。 - 20110510 - 20110510_15.log - 20110510_16.log |
| 返回顶楼 | |
