有1000亿条记录，每条记录由url,ip,时间组成，设计一_百度笔试题

推荐

Aesthetic92

答：首先，1000亿条记录全部放到内存肯定不够，那就是分成小文件了，然后整合；
公共的时间段，因为精确到分钟，我们把这每一分钟建成一个小文件，每个小文件肯定会有许多重复的ip，url；
现在统计每个小的文件中url的访问量和ip的访问次数，方法就是建立索引；
（建立索引的目的是为了减少查询次数，但是随着索引级数增多也会造成花更多的时间在建立索引上）；
建立url的索引，假如是www.nowcoder.com/question,可以分别给www.nowcoder.com和question建立索引，那么来了一条url，先看一级索引是不是匹配，匹配再看二级索引，相同的话就是我们要的url目标；
ip的索引也是一样，ip分成4段建立索引；
所以这里影响效率的就是在索引建立这块，索引建立好那就是查询的事了的，就会变得非常快。
假定给定了某个时间段，找出url的访问量，那么先找到给定的时间段，对应着刚开始分割的小的文件（每一个分钟）中搜索，通过索引找到相同的url之后，开始统计，直到搜索完所有的给定时间段内的所有的小的文件；
求ip的访问次数也是一样，按照给定的时间段，找到对应的小的文件，通过索引找到相同的ip后统计，直到搜索完了给定时间段内的所有的小的文件。

编辑于 2015-02-09 09:50:41 回复(0)

真-阿里内推

MapReduce思想：

1.按照时间对日志数据进行分区。

2.对url或者ip做hash，然后分桶。

3.merge最终结果。

发表于 2014-12-29 10:40:55 回复(0)

牛客-007

一种方法是用现有的大数据框架如Hadoop的Map/Reduce来处理

一种是将这项数据放在Hbase中，Hbase是一种列式NoSQL数据库，存放时用记录中的时间代替默认的时间戳，正好可以满足需求。这是最好的解决办法。

如果不允许使用分布式计算，那就只能将数据分成小文件计算了，一般单个计算机内存没有这么大。这1000亿条数据的ip和Url肯定有很多重复的，就是去重生成目标文件，然后排好顺序，这样就可以用二分查找快速得到想要的结果了

发表于 2015-01-09 11:11:07 回复(0)

指上弹兵赵小括

1、将记录按照时间(精确到分钟)写到不同的文件time_record.data

2、使用MapReduce，输入为所有time_record.data文件，输出为time_url_count.data和time_ip_count.data。也就是分别统计每一分钟内的url的次数和ip的次数(每行格式为url count或者ip count)；

3、根据时间段[time1,time2]和所要统计的类型(url/ip)确定MapReduce的输入文件##_xx_count.data，对统计结果进行合并。便可以得出[time1,time2]时间段内url或ip的数量；

或者省略2，直接根据时间段[time1,time2]和所要统计的类型(url/ip)确定MapReduce的输入文件time_record.data，匹配每个文件中的url或ip并计数，最后进行合并即可。

编辑于 2015-08-27 11:18:24 回复(0)

黄小斜

答：首先，1000亿条记录全部放到内存肯定不够，那就是分成小文件了，然后整合；
公共的时间段，因为精确到分钟，我们把这每一分钟建成一个小文件，每个小文件肯定会有许多重复的ip，url；
现在统计每个小的文件中url的访问量和ip的访问次数，方法就是建立索引；
（建立索引的目的是为了减少查询次数，但是随着索引级数增多也会造成花更多的时间在建立索引上）；
建立url的索引，假如是www.nowcoder.com/question,可以分别给www.nowcoder.com和question建立索引，那么来了一条url，先看一级索引是不是匹配，匹配再看二级索引，相同的话就是我们要的url目标；
ip的索引也是一样，ip分成4段建立索引；
所以这里影响效率的就是在索引建立这块，索引建立好那就是查询的事了的，就会变得非常快。
假定给定了某个时间段，找出url的访问量，那么先找到给定的时间段，对应着刚开始分割的小的文件（每一个分钟）中搜索，通过索引找到相同的url之后，开始统计，直到搜索完所有的给定时间段内的所有的小的文件；
求ip的访问次数也是一样，按照给定的时间段，找到对应的小的文件，通过索引找到相同的ip后统计，直到搜索完了给定时间段内的所有的小的文件。

发表于 2017-04-03 16:46:54 回复(0)

欧志

将访问记录拆分成两个数据表，表1是IP地址、时间段、时间和对应访问url在表2的主键和段内序号，表2是url、时间段、时间和对应IP地址在表1的主键和排序，
将两个数据表存储在NoSQL数据中，将一天分成4个时间段以后，每个IP地址按照访问时间在对应的时间段下增加一条时间记录，给该条记录一个序号。同理，表2
也按照时间段分开存储记录，拆分后，进行水平分表，按照IP地址和时间段拆分表1，按照url和时间段拆分表2。进行检索的时候，首先根据查询时间段和表2中
时间段划分，将一条查询分成一条或多条查询，将跨时间大段的查询转换为每个大时间段里面的查询，根据划分后的查询时间，索引到表2中的数据记录，
在该条记录中统计访问次数，最后进行结果相加。给定IP地址和时间段的查询同理。
表1设计为{"ip_id":"111","IP":"x.x.x.x","time_segment":"20170401-1","recorde":[{"time":"20170401052223","ip_order":1,"url":url_id,"url_order":1}]}
表1设计为{"url_id":"2","url":"qq.com","time_segment":"20170401-1","recorde":[{"time":"20170401052223","url_order":1,"ip":ip_id,"ip_order":1}]}

发表于 2017-04-01 17:16:16 回复(0)

小白走天下

这个题属于哪类知识范畴啊

发表于 2016-09-21 16:49:57 回复(0)

牛客7313754号

发表于 2016-08-21 17:19:59 回复(0)

Echo001

1.
//将1000亿条记录分成1000个文件：t1,t2,t3....t1000，每个文件有1亿条记录
//使用多线程技术同时处理1000个文件，构造每个文件所对应的hashtable HT，包含<url,time>
//根据url访问HT，判断时间是否在指定范围内，如果在则将访问次数累加

2.

//将1000亿条记录分成1000个文件：t1,t2,t3....t1000，每个文件有1亿条记录

//使用多线程技术同时处理1000个文件，构造每个文件所对应的hashtable HT，包含<ip,time>

//根据ip访问HT，判断时间是否在指定范围内，如果在则将访问次数累加

发表于 2016-03-25 10:03:30 回复(0)

牛客838955号

<div> 1.将URL和ip都创建为数据库的索引； </div> <div> 查询url访问次数，url作为hashMap的key；value中存放访问次数。 </div> <div> 查询ip访问次数，ip作为HashMap的key。 </div>

发表于 2015-08-13 14:53:18 回复(0)

NSDaBen

映射Map[url][time],将url进行字符串hash，再进行枚举统计。

这两题如果做成两维映射，内存吃不消，既然两题中的一维是已经指定的，变化的只是时间段，因此可以用一维表示，先预处理，再进行统计。
用的MapReduce的思想。

按时间分成小文件，各自对url和ip进行hash。
再分级做桶，同时merge各时间区段的hash表。
这样查询就能做到Log级别。

发表于 2015-05-18 23:34:24 回复(0)

米207

1000亿条记录数据量很大，可以使用hadoop生态圈中的HBase，它是一种nosql的分布式列式数据库，它的特点是支持海量数据在简单查询下的秒级响应。

如果历史数据是存放在关系型数据库中，可以使用sqoop或者编写mapreduce导入到HBase中；如果数据是日志类文本数据，可以编写mapreduce导入HBase中。

使用Hbase时，把rowkey设计成url_time以及ip_time,查询时设置scan条件，类似的startRowKey：19216812210_20150511000 endRowKey：19216812210_20150511000，然后使用HBase自带的协处理器来统计次数。

发表于 2015-05-11 11:03:35 回复(0)

放作夥

没有经验，但大致认为属于map-reduce思路范围。按某种哈希把记录分片到各个机器上，然后map-reduce。

发表于 2015-04-26 18:39:39 回复(0)

luulsj

ip转换成数字存储，

时间增加索引

发表于 2015-04-16 12:37:24 回复(0)

雷大锤

Template<typename T>
unsigned long Count(Time t_s, Time t_e, T t) {
    index==type(url) ? 0 : 1;
    search_s = Find_s(t_s);
    search_e = Find_e(t_e);
    p = search_s;
    count = 0;
    for(; p<search_e+1); ++p)
        if((*p)[index]==t) {count++;}
    return count;
}

for loop build hash.
    data[2] = {url, ip};
    hash[time] = data;

发表于 2015-04-01 22:36:39 回复(0)

zxjcarrot

1.使用这样的一个数据结构V: (url, S{time(精确到分钟), count}) 也就是每一个url都有一个列表S,里面按时间排序升序存放着到time时间点总共访问次数,这样某个时段[i,j]的访问次数就可以通过S[j].count - S[i - 1].count来计算出来.

首先把文件进行按url和时间来排序,计算出数据结构V并按照url的顺序序列化到一个结果文件中.

查询的时候首先使用url进行二分查找, 找到这个url的数据结构v之后,在v.S里通过二分查找分别找到时间段I, J的对应项, 并通过上述方法计算出访问次数.

2.做法和1类似,只不过把url改成ip.

编辑于 2015-04-01 17:38:34 回复(0)

weidwonder

使用索引,创建两张索引,一张以url为key,一张以ip为key,使用链式存储,并对个链表进行时间排序,进行时间段选取的时候使用二分查找.将这两张表加载到多台主机的内存中,一台主机进行分段索引,然后请求发送到对应主机进行统计

发表于 2015-03-31 18:06:56 回复(0)

有1000亿条记录，每条记录由url,ip,时间组成，设计一

问题信息

热门推荐

相关试题