我请问高手一个问题

飞飞2013

我在一个TXT文件中放了625万个随机大小的四字节无符号整型数据，我现在要求出这625万个四个字节整型的最小50个数据的大小，以及它们的下标位置，（假如这TXT文件中第一个数据下标为0，第6250000个数据下标为6249999），我想问问你们，你们的程序计算出结果的时间是多少，我计算过，我的程序大约用了0.875秒，提这问题是想知道我和高手的差距在哪里。如果你的算法更好（结果正确而且时间更少），能不能透露下思路呢？我先把我的代码发出来，大家看看有没有bug;

飞飞2013

自己占沙发;P

飞飞2013

大家都来看看吧，自己试着做做，这问题没有看上去的那么复杂的；

友来友网

这么大的数据你只用了0.875秒，
我表示很佩服，
能否发出来借鉴一下

仰望天上的光

这些整数是否有重复呢？有重复的话如何比较两个相等数字呢？

bafengao

强烈支持楼主ing……

飞飞2013

我把自己的源码发上去了，大家帮忙看看。

飞飞2013

说明一下，1.txt文件在记事本程序中看不见内容的，但是可以用ultraedit或者notepad++打开显示内容。因为时间比较仓促没有做错误检查，高手见谅！

仰望天上的光

飞飞2013 发表于 2013-5-16 07:40

                               
登录/注册后可看大图

说明一下，1.txt文件在记事本程序中看不见内容的，但是可以用ultraedit或者notepad++打开显示内容。因为时间 ...

我想知道，在运气非常差的情况下，比如生成的625万个数都是5，是不是随便输出50个下标都是正确的？

飞飞2013

仰望天上的光 发表于 2013-5-16 08:24

                               
登录/注册后可看大图

我想知道，在运气非常差的情况下，比如生成的625万个数都是5，是不是随便输出50个下标都是正确的？

你先看完我的源码再说吧。:(

飞飞2013

可能有bug，但是绝对不是瞎蒙出来的，而且我对重复的数据也做了一定的检查。

飞飞2013

已知的BUG是当数据排列过于整齐，或者集中，可能会栈溢出，看不到结果。但是没有办法，我在这个程序中已经开了12万8千多块堆，我实在是想不出来其他办法解决这问题。

a1c2c3

新手表示很有压力:dizzy:

我是师兄

1. #include <stdio.h>
   
2. #include <time.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. typedef struct
   
6. {
   
7.         unsigned int key;
   
8.         int index;
   
9. }StData;
   
10. 
    
11. int comp(unsigned int* fir, unsigned int* sec)
    
12. {
    
13.         if(*fir < *sec)
    
14.                 return -1;
    
15.         if(*fir ==*sec)
    
16.                 return 0;
    
17.         return 1;
    
18. }
    
19. 
    
20. int main(int argc, char *argv[])
    
21. {
    
22.         StData stArr[51];
    
23.         int end = 1;
    
24.         int i;
    
25.         unsigned int t;
    
26.         int j;
    
27.         FILE* fp = fopen("D:\\123.txt", "rb");        //数据文件 存放在绝对路径 D:\\123.txt中
    
28.         clock_t begin = clock();
    
29.       
    
30.         if(fp == NULL)        //文件打开失败 退出
    
31.                 return EXIT_FAILURE;
    
32. 
    
33.         for(i=0; i<50; ++i)        //初始化stArr数组
    
34.         {
    
35.                 fread(&stArr[i].key, sizeof(unsigned int), 1, fp);
    
36.                 stArr[i].index = i;
    
37.         }
    
38.         qsort(stArr, 50, sizeof *stArr, comp);        //对找出的50个数据进行排序
    
39. 
    
40.         for(i=50; fread(&t, sizeof t, 1, fp); ++i)        //主流程
    
41.         {
    
42.                 for(j=0; j<50; ++j)
    
43.                         if(t < stArr[j].key)
    
44.                                 break;
    
45.                 if(j == 50)
    
46.                         continue;
    
47.                 memmove(stArr+j+1, stArr+j, (50-j)*sizeof *stArr);
    
48.                 stArr[j].key = t;
    
49.                 stArr[j].index = i;
    
50.         }
    
51.         printf("i %d\n", i);
    
52.         
    
53.         for(i=0; i<50; ++i)        //输出结果
    
54.                 printf("%16d%16d\n", stArr[i].key, stArr[i].index);
    
55.                
    
56.         printf("time : %g\n", (clock()-begin)*1.0/CLOCKS_PER_SEC);        //输出程序运行时间
    
57.         
    
58.         fclose(fp);
    
59.         
    
60.         return EXIT_SUCCESS;
    
61. }

复制代码

仰望天上的光

基本可以这样做：
1. 把数据平均分成2块一样大小的数组。对每块数组排序，然后做50次2路归并。
2.显然上面的效率不高，所以可以把数据平均分成N块一样大小的数组，对每块数组排序，然后做50次N路归并。

分析，平均分成M块后，每块数据为N,所以数据总数为M*N
对每块数据为N排序，最好的基于比较的排序法（如快排）时间是NLOGN
进行M次快排，时间为M*NLOGN
然后做50次归并，每次归并时间是M，50次就是50*M
所以总共时间是M*NLOGN+50M
其中M*N为常量C，代入上算式得：
总时间为:
CLOGN+50*C/N
应该根据此式计算N的最佳值使该时间最少，然后以此为依据进行数据的划分。

飞飞2013

我是师兄 发表于 2013-5-16 10:28

                               
登录/注册后可看大图

你的结果和我的一样，只是速度不一样，你用时1.54秒，我用时0.875秒。额，结果是一样的。

飞飞2013

仰望天上的光 发表于 2013-5-16 11:07

                               
登录/注册后可看大图

基本可以这样做：
1. 把数据平均分成2块一样大小的数组。对每块数组排序，然后做50次2路归并。
2.显然上面 ...

额，我之所以设计625万这个数目是因为6250000=50*50*50*50。我就是闲着无聊，想看看速度最快的算法是咋样的。而且625万个整型数据是23.8MB的内存大小，不可能全部都放进栈里计算，这就很考验设计者内存管理的功夫。

飞飞2013

高手都来看看，如果是你的话，怎样把计算时间压进0.8秒以内？也欢迎其他的语言的高手:loveliness:

wjb8love_9c7c9c

飞飞2013 发表于 2013-5-16 11:31

                               
登录/注册后可看大图

你的结果和我的一样，只是速度不一样，你用时1.54秒，我用时0.875秒。额，结果是一样的。

大哥 你的程序在读数据的时候不算时间，而他的这个程序从读数据就开始算起的。不能这么算吧。

C.hing.

强烈支持楼主ing……