我请问高手一个问题

我是师兄

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

                               
登录/注册后可看大图

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

你得把你读文件的时间算进去之后 再来和我的代码比较时间

另外评价一个算法好不好有2个方面
一个是 时间复杂度[简单理解就是执行时间]
一个是 空间复杂度[简单理解就是使用多少内存]

然后你的代码用了大量malloc分配的大块
我的代码 最大的内存只是那个51个元素的数组

最后 我的代码有一点没做好 我忘记fclose文件了

我是师兄

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

                               
登录/注册后可看大图

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

没多大必要 对全部数据进行排序

只需要不停保留50当前最小数据 一直到 全部数据读取完毕

飞飞2013

我是师兄 发表于 2013-5-16 15:03

                               
登录/注册后可看大图

你得把你读文件的时间算进去之后 再来和我的代码比较时间

另外评价一个算法好不好有2个方面

包进去了以后是0.9秒，慢了0.025秒左右，我的算法比你的快，这是事实；读取文件再慢也用不了0.2秒吧；总共才23MB的文件而已。关于你说的第二点，我觉得很对。

飞飞2013

我的这个程序倒不是堆开了多的问题，堆只是用来存放数据的；我开的堆其中80%在子程序结束前就释放了。我是想通过指针直接操作数据把结果再拷贝进堆里面去，而不是通过在栈中直接计算的方法来提高速度，但是这样栈中就存放了大量的指向堆的指针。我试过最极端的情况，当我读取的数组是按顺序排列的话（也就是从0到6249999这么排列的话），栈会溢出，看不到结果。太追求极端总是不好。

我是师兄

多次运行
你的最好是 1.171
我的最差是 1.109

开优化之后
你的 0.656
我的 0.468

我是师兄

如果我一次性读取全部数据
那么不开优化
多次运行 平均是0.963
开优化多次运行 平均是 0.343

飞飞2013

我是师兄 发表于 2013-5-16 17:36

                               
登录/注册后可看大图

如果我一次性读取全部数据
那么不开优化
多次运行 平均是0.963

请你不要做全部相同的数据，做全部随机的可以不？我说了，我的代码在数据过于整齐的情况下可能会溢出的，尤其是你把1.txt的数据以按顺序的情况下写入会的不到任何结果（0到6249999地址分别写入0到6249999），因为栈会不够用。

我是师兄

飞飞2013 发表于 2013-5-16 17:47

                               
登录/注册后可看大图

请你不要做全部相同的数据，做全部随机的可以不？我说了，我的代码在数据过于整齐的情况下可能会溢出的， ...

汗 我用rand 函数产生的数据好不好 6250000个随机数里面 某一个数 出现不止50次很意外吗

在说你的代码也是输出 50个同一个数吧

飞飞2013

而且我的题目就是给随机的625万整型数据（随机的看不到么）。你拿你的最优化情况跟我的最差情况比，有可比性吗？

飞飞2013

我是师兄 发表于 2013-5-16 17:50

                               
登录/注册后可看大图

汗 我用rand 函数产生的数据好不好 6250000个随机数里面 某一个数 出现不止50次很意外吗

在说你的代码 ...

你可以先随机种子，再用rand三次或者四次相加，我的代码在数据过于整齐的情况下内存会不够用；

我是师兄

飞飞2013 发表于 2013-5-16 17:53

                               
登录/注册后可看大图

而且我的题目就是给随机的625万整型数据（随机的看不到么）。你拿你的最优化情况跟我的最差情况比，有可比性 ...

难道 rand产生的数据不是随机的??????!!

另外 我是用同一个文件做测试 哪里来的 用我的最优和你的最差作比较

而且我在25楼是用我的最差和你的最优作比较吧

喜欢散步

我都还没有学算法吖。。

飞飞2013

我是师兄 发表于 2013-5-16 18:02

                               
登录/注册后可看大图

难道 rand产生的数据不是随机的??????!!

另外 我是用同一个文件做测试 哪里来的 用我的最优和你的最差 ...

好吧，你快就你快吧，可是我就是不懂，为什么在我的机器（XP系统）上运行你的代码时间总是在1.485到1.531秒之间（而且是用一个rand），为什么到了你的机器上了就变快了那么多？你是用的什么系统？而且你说的优化是什么？是用软件吗？菜鸟求教。

飞飞2013

我还有一件事情不明白，如果真的是用rand种子求得随机数，我测试了不下20次，没有一次最小值是连续的50次零的情况，如果是50次零的话，那几率按着正确的算法应该是50乘以6250000除以(32767的50次方),这概率几乎为0吧。为什么在你的结果里面却出现了50次0的情况，我就是不明白，想问一下。

飞飞2013

事实上，我求了最小值20次，连续两次最小值0的情况都未遇见。为什么你的结果却是求出了50次最小值0？

仰望天上的光

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <cstdlib>
   
4. #include <cstdio>
   
5. #include <ctime>
   
6. using namespace std;
   
7. 
   
8. const int TOTAL = 6250000;
   
9. struct MyData{
   
10.         int data;
    
11.         int index;
    
12. };
    
13. 
    
14. inline bool small( const MyData& m1, const MyData& m2 ) {
    
15.         return m1.data < m2.data;
    
16. }
    
17. 
    
18. 
    
19. void MySort( MyData* first, MyData* middle, MyData* beyond  ) {
    
20.         make_heap(first, middle, small);
    
21.         for (MyData* i = middle; i < beyond; ++i) {
    
22.                 if (small(*i, *first)) {
    
23.                         //若遍历到比大根堆顶小的元素
    
24.                         //将此元素和堆顶对调
    
25.                         //并维持堆的特性
    
26.                         MyData tmp = *i;
    
27.                         *i = *first;
    
28.                         ptrdiff_t hole = 0;
    
29.                         ptrdiff_t number = middle - first;
    
30.                         ptrdiff_t j = hole;
    
31.                         ptrdiff_t k = 2 * hole + 2;//k是hole的右儿子节点
    
32.                         for (; k < number; k = 2 * k + 2) {
    
33.                                 if (small(*(first + k), *(first + (k - 1)))) --k;
    
34.                                 *(first + hole) = *(first + k), hole = k;
    
35.                         }
    
36.                         if (k == number)
    
37.                                 *(first + hole) = *(first + (k - 1)), hole = k - 1;
    
38.                         for (ptrdiff_t m = (hole - 1) / 2; j < hole && small(*(first + m), tmp);
    
39.                                 m = (hole - 1) / 2)
    
40.                         *(first + hole) = *(first + m), hole = m;
    
41.                         *(first + hole) = tmp;
    
42.                 }
    
43.         }
    
44.         //现在堆中的元素是数组中的最小元素
    
45.         //将堆排序即可
    
46.         sort_heap(first, middle, small);
    
47. }
    
48. 
    
49. 
    
50. int main () {
    
51.         int i;
    
52.         struct MyData *pData = (struct MyData*)malloc( sizeof(struct MyData) * TOTAL );
    
53.         FILE* fp = fopen("1.txt", "rb") ;
    
54.         for( i=0;i<TOTAL;++i ) {
    
55.                 fread ( &pData[i].data, sizeof(int), 1 , fp) ;
    
56.                 pData[i].index = i;
    
57.         }
    
58.         fclose( fp );
    
59. 
    
60.         time_t start, finish;
    
61.         start = clock();  
    
62.         MySort(pData, pData+50, pData+TOTAL);
    
63.         finish  = clock();
    
64.         for( i=0;i<50;++i ) {
    
65.                 cout<<pData[i].data<<":"<<pData[i].index<<endl;
    
66.         }       
    
67.         cout<<"time:"<<((double)(finish - start)/CLOCKS_PER_SEC)<<endl ;
    
68.         free(pData);
    
69. }

复制代码

我把“我是师兄”的代码优化了下，把对50个元素的每次排序去掉，将这50个元素构成一个大根堆，每次都维护这个堆，得到以上程序（是C++的代码，为了直接使用建堆和堆排序函数，其它的基本还是兼容C代码），速度似乎快了不少。

仰望天上的光

我是师兄 发表于 2013-5-16 18:02

                               
登录/注册后可看大图

难道 rand产生的数据不是随机的??????!!

另外 我是用同一个文件做测试 哪里来的 用我的最优和你的最差 ...

把对50个数的每次排序改为维护50个元素的大根堆，速度可以快很多。此外为了比较速度，可以无视空间效率，以开始就读入所有数据，这样算法效率比较得更清晰。

仰望天上的光

我出100鱼币求超越~~~（要明显超越的那种，大家都知道的小改动不能算。）

☆小韦QQ

强烈支持楼主ing……

飞飞2013

谢了，十分感谢，感谢大家。