百度笔试题 看看哪位高手可以解决 :)
百度笔试题 看看谁可以解决 :)
百度笔试题
《二》设计题：
有这么一个程序，每天要接受5千万个数据包（数据包的格式如下），数据被顺存储在一些文件中。程序每天定点对数据进行处理。对数据分组并按从大到小的顺序排序。已知一个文件的最大 大小为2G，一个进程的最大内存大小为2G。现在只允许用一个 CPU数量为4个，内存为16G 的服务器 完成整个过程，使得时间尽可能的短。
您的任务：尽可能的描述 数据结构（或文件结构），写出尽可能多的 伪代码，流程图。
Ps:
1.程序随机访问外存耗费的时间是顺序访问的10倍。
2.50G,5千万的数据包.顺序访问是20分，随机访问大概是4个小时。
tydef struct
{
int group;
int val;
char data[1024];//1k的数据域
} DataType;
------解决方案--------------------
主要就是两个问题
1、大文件操作：转换分区表到ntfs，用64位指针进行I/O操作，具体方法见《widows系统编程》第三版，提高内存利用率的话用用结构化存储
2、多核计算：《多核程序设计技术：通过软件多线程提升性能》参考一下
最后就是个文件存储的问题，效率好一点的用平衡树就差不多了
------解决方案--------------------
大概想了一下：
1、先用四个线程（因为是4个cpu）对所有文件（即50G/2G = 25个文件）单独排序，得到25个按组，组内按val排序的有序文件
2、同样用4个线程，在25个有序文件的基础上，采用归并排序，得到13对有序排列的文件（除了第25个文件外，其余相邻两个文件组成一对
3、按照第二条的方法，递归，最后即可得到要求的结果。
期待更详细，更巧妙的方法
------解决方案--------------------
想了个方法：
1：应该是主要考归并排序和分组排序的问题
2：我们这样利用内存，2G内存1G（应多于1G一点大约多10兆）用来存数据，也就是说一次读入一百万个数据包，剩下的1G留下给进程堆栈、程序地址段空间、和临时内存变量用。
3：一个数据包大小约为1024+8个大小，5千万个数据包也就相当于50G+50兆左右，我们建立51个文件，每个文件前1000字节为控制信息，剩下的1G(可能会多10兆）用于存数据。
4：多线程处理数据包，启用4个进程（每个进程启动一个内核级线程，这是因为***每个内核级线程可以使用一个Cpu处理***）
5：建立共享内存临界区,每个进程在完成本次数据包处理任务后，读取临界取（包处理完的个数 HaveDeal）
Lock(s_HaveDeal)
UNIT curDealBegin=HaveDeal;
UnLock(s_HaveDeal)
6:更新临界区
UNIT curDealEnd=CurDealBegin+1024*1024*1024(1G)+10*1024*1024(10兆）;
Lock(s_HaveDeal)
UNIT HaveDeal=curDealBegin;
UnLock(s_HaveDeal)
7：每次数据顺序读入内存，然后分组排序，根据组数可以将1G内存分散开，比如分4组，那么建立4个数组 T1,T2,T3,T4，内存中可分组排序，组内可简单的采用顺序排序方法（或其他好的排序方法），时间复杂读最大为 O(2)
8:将分组排序好的内存数据写到文件，文件的前1000字节控制信息可这样设计。
总组数
总包数
组1 包数
组1 开始索引
组1 结束索引
组2 包数
组2 最小值
组2 最大值
。。。。。
9：专门设一个排序文件SORTFILE，这个文件大小约为：组信息+包信息（10*5*1000*1000） <200兆，文件里记录如下信息：
总组数
组1 开始索引
组2 开始索引
。。。。。。
包1 所在文件号，索引，值（占10字节）
包2 所在文件号，索引，值
。。。。。。
10：一次顺序读取完成后,进行第二个任务，将SORTFILE文件总的记录信息加载到内存，
在内存总对包进行归并排序（具体可见任何一本数据结构书中的归并算法），再重新建立26个 2G的文件，当算法中 记录移动的时候，文件相应索引中的数据记录归并到新的2G的文件中，则任务完成
------解决方案--------------------
16G内存，那至少得开8个进程，才能最大利用内存；
因为‘程序随机访问外存耗费的时间是顺序访问的10倍’，所以要尽量用顺序访问；第一次顺序访问所有记录，把group和val提取出来，同时要记录位置信息，然后根据group分组，每组对val排序。
16G内存，如果能有12.5G用于保存数据，则再顺序访问4次，就可以把所有数据按排好的顺序写入文件
百度笔试题
《二》设计题：
有这么一个程序，每天要接受5千万个数据包（数据包的格式如下），数据被顺存储在一些文件中。程序每天定点对数据进行处理。对数据分组并按从大到小的顺序排序。已知一个文件的最大 大小为2G，一个进程的最大内存大小为2G。现在只允许用一个 CPU数量为4个，内存为16G 的服务器 完成整个过程，使得时间尽可能的短。
您的任务：尽可能的描述 数据结构（或文件结构），写出尽可能多的 伪代码，流程图。
Ps:
1.程序随机访问外存耗费的时间是顺序访问的10倍。
2.50G,5千万的数据包.顺序访问是20分，随机访问大概是4个小时。
tydef struct
{
int group;
int val;
char data[1024];//1k的数据域
} DataType;
------解决方案--------------------
主要就是两个问题
1、大文件操作：转换分区表到ntfs，用64位指针进行I/O操作，具体方法见《widows系统编程》第三版，提高内存利用率的话用用结构化存储
2、多核计算：《多核程序设计技术：通过软件多线程提升性能》参考一下
最后就是个文件存储的问题，效率好一点的用平衡树就差不多了
------解决方案--------------------
大概想了一下：
1、先用四个线程（因为是4个cpu）对所有文件（即50G/2G = 25个文件）单独排序，得到25个按组，组内按val排序的有序文件
2、同样用4个线程，在25个有序文件的基础上，采用归并排序，得到13对有序排列的文件（除了第25个文件外，其余相邻两个文件组成一对
3、按照第二条的方法，递归，最后即可得到要求的结果。
期待更详细，更巧妙的方法
------解决方案--------------------
想了个方法：
1：应该是主要考归并排序和分组排序的问题
2：我们这样利用内存，2G内存1G（应多于1G一点大约多10兆）用来存数据，也就是说一次读入一百万个数据包，剩下的1G留下给进程堆栈、程序地址段空间、和临时内存变量用。
3：一个数据包大小约为1024+8个大小，5千万个数据包也就相当于50G+50兆左右，我们建立51个文件，每个文件前1000字节为控制信息，剩下的1G(可能会多10兆）用于存数据。
4：多线程处理数据包，启用4个进程（每个进程启动一个内核级线程，这是因为***每个内核级线程可以使用一个Cpu处理***）
5：建立共享内存临界区,每个进程在完成本次数据包处理任务后，读取临界取（包处理完的个数 HaveDeal）
Lock(s_HaveDeal)
UNIT curDealBegin=HaveDeal;
UnLock(s_HaveDeal)
6:更新临界区
UNIT curDealEnd=CurDealBegin+1024*1024*1024(1G)+10*1024*1024(10兆）;
Lock(s_HaveDeal)
UNIT HaveDeal=curDealBegin;
UnLock(s_HaveDeal)
7：每次数据顺序读入内存，然后分组排序，根据组数可以将1G内存分散开，比如分4组，那么建立4个数组 T1,T2,T3,T4，内存中可分组排序，组内可简单的采用顺序排序方法（或其他好的排序方法），时间复杂读最大为 O(2)
8:将分组排序好的内存数据写到文件，文件的前1000字节控制信息可这样设计。
总组数
总包数
组1 包数
组1 开始索引
组1 结束索引
组2 包数
组2 最小值
组2 最大值
。。。。。
9：专门设一个排序文件SORTFILE，这个文件大小约为：组信息+包信息（10*5*1000*1000） <200兆，文件里记录如下信息：
总组数
组1 开始索引
组2 开始索引
。。。。。。
包1 所在文件号，索引，值（占10字节）
包2 所在文件号，索引，值
。。。。。。
10：一次顺序读取完成后,进行第二个任务，将SORTFILE文件总的记录信息加载到内存，
在内存总对包进行归并排序（具体可见任何一本数据结构书中的归并算法），再重新建立26个 2G的文件，当算法中 记录移动的时候，文件相应索引中的数据记录归并到新的2G的文件中，则任务完成
------解决方案--------------------
16G内存，那至少得开8个进程，才能最大利用内存；
因为‘程序随机访问外存耗费的时间是顺序访问的10倍’，所以要尽量用顺序访问；第一次顺序访问所有记录，把group和val提取出来，同时要记录位置信息，然后根据group分组，每组对val排序。
16G内存，如果能有12.5G用于保存数据，则再顺序访问4次，就可以把所有数据按排好的顺序写入文件