当前在线人数12137
首页 - 分类讨论区 - 电脑网络 - 葵花宝典版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Comparison Re: 组合的枚举算法?
[版面:葵花宝典][首篇作者:Pront] , 2004年09月22日23:46:28 ,683次阅读,6次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
Pront
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: Pront (阿呆), 信区: Programming
标  题: Comparison Re: 组合的枚举算法?
发信站: Unknown Space - 未名空间 (Wed Sep 22 23:48:35 2004) WWW-POST

I think proof is better than arguing. So I changed tjq's program a little bit
to do a comparison:

Here is the result: with M=11, N=30, compiling with VC 6, SP5,

With optimization as Max speed,
==================
recursive
Time 1952
non-recursive
Time 1503
Count 54627300

recursive is 450 ms slower than non-recursive. But this is in when we almost
did nothing with the result (in the function "output", uncomment the return).
If I just do a sum over all data in output, the result is:
===================
recursive
Time 2954
non-recursive
Time 2584
Count 54627300

An interesting result after turning off Optimization,
==================
recursive
Time 4356
non-recursive
Time 4216
Count 54627300

I think in real life, most times we need to do much more than summing up the
output. Usually the overhead of recursion can be ignored.

All runs are on my dell notebook inspiron 4150 with 1.8GHz CPU, 512 MB.

Apended program (changed from tjq's):


#include <windows.h>
#include <iostream>
#include <vector>
using namespace std;

int M=11, N=30;
vector<int> data;
int count = 0;

void output()
{
count ++;
//return;
int x = 0;
    for (int i=0;i<M;i++)
x += data[i];
        //cout << data[i] << (i==M-1?'\n':' ');
}

void go(int index)
{
    if (index == M)
    {
output();
        return;
    }
    for (int i= index == 0? 0 : data[index-1] +1; i < N;i++)
    {
        data[index] = (i);    
        go(index + 1);
    }
}

int next_comb()
{
    int i;
    for (i=M-1;i>=0;i--)
        if (data[i]+M-i<N) 
        {
            data[i]++;
            break;
        }
    for (int j=i+1;j<M;j++)
        data[j]=j?data[j-1]+1:0;
    return i>=0;
}

void go2()
{
data.clear();
    for (int i=0;i<M;i++)
        data.push_back(i);
    do 
    {
output();
    } while (next_comb());
}

int main()
{
DWORD time1, time2;
DWORD dw = GetTickCount();
data.resize(M, 0);
    go(0);
time1 = GetTickCount() - dw;

cout << "==================" << endl;

dw = GetTickCount();
data.clear();
go2();
time2 = GetTickCount() - dw;

    cout << "recursive" << endl;
cout << "Time " << time1 << endl;
    cout << "non-recursive" << endl;
cout << "Time " << time2 << endl;
cout << "Count " << count/2 << endl;

    return 0;
}


【 在 tjq (只是交换没有爱) 的大作中提到: 】
: let's end the discussion with my program.
: #include <iostream>
: #include <vector>
: using namespace std;
:
: int M=5, N=3;
: vector<int> data;
:
: void go()
: {
:     if (data.size() == N)
:     {
:         for (int i=0;i<N;i++)
:             cout << data[i] << (i==N-1?'\n':' ');
:         return;
:     }
:     for (int i=data.empty()?0:data.back()+1;i+N-data.size()<=M;i++)
:     {
:         data.push_back(i);   
:         go();
:         data.pop_back();
:     }
: }
:
: int next_comb()
: {
:     int i;
:     for (i=N-1;i>=0;i--)
:         if (data[i]+N-i<M)
:         {
:             data[i]++;
:             break;
:         }
:     for (int j=i+1;j<N;j++)
:         data[j]=j?data[j-1]+1:0;
:     return i>=0;
: }
: int main()
: {
:     cout << "recursive" << endl;
:     go();
:     cout << "non-recursive" << endl;
:     for (int i=0;i<N;i++)
:         data.push_back(i);
:     do
:     {
:         for (int i=0;i<N;i++)
:             cout << data[i] << (i==N-1?'\n':' ');
:     } while (next_comb());
:     return 0;






--
※ 修改:·Pront 於 Sep 22 23:48:35 修改本文·[FROM: 24.16.]
※ 来源:.Unknown Space - 未名空间 mitbbs.com.[FROM: 24.16.]

 
[分页:1 ]
[快速返回] [ 进入葵花宝典讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996