同学百度笔试，在线等
高手解决一下，谢谢
假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用
问题点数：10、回复次数：12Top
1 楼everpom（）回复于 2006-10-09 10:16:50 得分 0
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明Top
2 楼everpom（）回复于 2006-10-09 10:17:03 得分 0
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？Top
3 楼XINYONGHUCSDN（柯风）回复于 2006-10-09 10:58:36 得分 0
typedef struct
{
int id;
}URLID;
typedef struct
{
URLID *urllist;
int list_max;
int actual_url;
}SongItem;
用一个最大为2^24的SongItem数组存储每一首歌对应的url列表，设该数组名为SongArray。
另外再用一个位图标识每个url的可用情况，所好资源大小为2^30/8=4MB。
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
查找SONG_ID对应的SongArray中的项，对其中的每个URL查询位图看是否可用，返回可用URL_ID列表和计数。
2) 给定一个SONG_ID，为其添加一个新的URL_ID
添加URL_ID到对应的SONG_ID列表的末尾,若列表已满，申请更大空间的数组再添加。
3) 添加一个新的SONG_ID
将SONG_ID其对应的SongArray值初始化。
4) 给定一个URL_ID，将其置为不可用
更改url位图域。
如果需要扩展到多个分布式的系统中去，可添加一个MachineID用于标识Song所在的机器，而一台机器上的所有的歌曲对应的url都存在歌曲所在的机器上，因此，url无须设MachineID。
以上数据结构只是满足楼主简单的功能，可作进一步改进一提供一些更积极的功能。
Top
4 楼XINYONGHUCSDN（柯风）回复于 2006-10-09 11:03:16 得分 0
仔细想了一下，如果有2^30个url，那么urlid设为32位会导致内存不够用（对32位机器）。Top
5 楼XINYONGHUCSDN（柯风）回复于 2006-10-09 11:07:39 得分 0
csdn怎么不能修改帖子啊？
位图所消耗资源应为为2^30/8=128MB，晕……
Top
6 楼whbjob（）回复于 2006-10-09 11:10:35 得分 0
这样的操作，应该直接使用数据库，即使做在数据结构，这样调度内存，内存的要求就太了了点Top
7 楼everpom（）回复于 2006-10-09 11:16:15 得分 0
谢谢柯枫Top
8 楼XINYONGHUCSDN（柯风）回复于 2006-10-09 11:22:43 得分 0
如果对于32位机器，内存是不够存储这些url的，那么可以将数据写入若干个文件中。
文件的总大小大约为2^24*2^10*4=2^36=64GB.根据SongID即可计算出在哪个文件的哪个未知
那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。
url的是否可用仍用位图来标识。Top
9 楼everpom（）回复于 2006-10-09 11:33:35 得分 0
麻烦你说的更详细一点，谢谢Top
10 楼kulongus（公司会计说：零钱太少了，你还是半年领一次工资吧）回复于 2006-10-09 15:12:54 得分 0
mkTop
11 楼XINYONGHUCSDN（柯风）回复于 2006-10-09 15:50:28 得分 0
everpom()
麻烦你说的更详细一点，谢谢
-----------------------------
见另一贴！Top
12 楼XINYONGHUCSDN（柯风）回复于 2006-10-10 14:07:53 得分 10
【 在 lifeistrue (lifeistrue) 的大作中提到: 】
:四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
1. 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用
限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
:================================================
内存不够存储这些url，所以将数据写入若干个文件中。
每一首歌曲对应的存储在文件中的信息格式为（url1, url2……）。
文件的总大小大约为2^24*2^10*4 =2^36 =64GB.根据SongID即可计算出在哪个文件的哪个位置，那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际，大约是ms级别。
将每首歌曲的信息存入文件中，由于每首歌的url不超过2^10个，所以在文件中每首歌的存储结构是2^10个int数，每个int数字标识着一个url。-1表示url不存在。初始化时将文件中每个int数初始化为-1.
这样每个SongID对应的信息占用的空间为2^10*4=4KB，设每个文件大小1G，那么每个文件可存储2^18=256K个Song的信息。总共需要64个文件，把这些文件编号从0-63.
对于任意一个SongID，他所对应的url信息所在的文件编号是：SongID>>18,在文件中的位置是：(SongID&0x3FFFF)<<12.
另外内存中用一个2^24大小的short int型数组来保存每一首歌曲对应的url的个数，计数组名为urlCount[]，初始化时值为-1,表示对应的Song_ID不存在。此数组占用空间2^25Byte=32MB;
url是否可用的信息用位图来标识。位图保存在内存中，占用的空间为2^30/8=2^27 Byte=128MB.
对所要求的操作：
:1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
通过SONG_ID计算出文件号和对应在文件中的位置，从urlCount[]中读取url个数，读出所有的url,并对每个url_ID查询位图看是否可用，若可用，将此url加入返回列表。
:2) 给定一个SONG_ID，为其添加一个新的URL_ID
通过SONG_ID计算出文件号和对应在文件中的位置，设为start，在通过urlCount[]得到url个数，假设有n个url,那么将新的URL_ID写入文件的start+sizeof(int)*n处。修改urlCount[SONG_ID]的值。
:3) 添加一个新的SONG_ID
检查将对应的urlCount[SONG_ID]，若为-1，则修改为0,若大于等于0，则表明改Song_ID已经存在。
:4) 给定一个URL_ID，将其置为不可用
修改url位图，标识URL_ID对应的位，表示为不可用。Top
