开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
prio_test.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：3k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

prio_test.c：源码内容
  1. #include <LEDA/_prio.h>
  3. #include <LEDA/impl/m_heap.h>
  4. #include <LEDA/impl/k_heap.h>
  5. #include <LEDA/impl/p_heap.h>
  6. #include <LEDA/impl/list_pq.h>
  8. typedef float FLOAT;
  11. void prio_test(priority_queue<int,int>& D, int N, int* A, char* name)
  12. { 
  13.   pq_item* I = new pq_item[N];
  15.   cout << string("%-12s",name);
  16.   cout.flush();
  18.   float T;
  19.   float T0 = T = used_time();
  21.   int i;
  22.   for(i=0; i<N; i++)  I[i] = D.insert(i,A[i]);
  23.   cout << string("%10.2f",used_time(T));
  24.   cout.flush();
  26.   for(i=0; i<N; i++)  D.decrease_inf(I[i],A[i]/2);
  27.   cout << string("%14.2f",used_time(T));
  28.   cout.flush();
  30.   int old_min = -MAXINT;
  32.   for(i=0; i<N; i++)  
  33.   { if (D.inf(D.find_min()) < old_min) cout << "error in del_minn";
  34.     old_min = D.inf(D.find_min()); 
  35.     D.del_min();
  36.    }
  38.   cout << string("%10.2f",used_time(T));
  40.   cout << string("%10.2f",used_time(T0));
  42.   if (!D.empty()) cout << " NOT EMPTY !!n";
  44.   newline;
  46.   delete I;
  47. }
  50. void prio_test(priority_queue<FLOAT,FLOAT>& D, int N, FLOAT* A, char* name)
  51. { 
  52.   pq_item* I = new pq_item[N];
  54.   cout << string("%-12s",name);
  55.   cout.flush();
  57.   float T;
  58.   float T0 = T = used_time();
  61.   int i;
  62.   for(i=0; i<N; i++)  I[i] = D.insert(i,A[i]);
  63.   cout << string("%10.2f",used_time(T));
  64.   cout.flush();
  66.   for(i=0; i<N; i++)  D.decrease_inf(I[i],A[i]/2);
  67.   cout << string("%14.2f",used_time(T));
  68.   cout.flush();
  70.   FLOAT old_min = -MAXINT;
  72.   for(i=0; i<N; i++)  
  73.   { if (D.inf(D.find_min()) < old_min) cout << "error in del_minn";
  74.     old_min = D.inf(D.find_min());
  75.     D.del_min();
  76.    }
  78.   cout << string("%10.2f",used_time(T));
  80.   cout << string("%10.2f",used_time(T0));
  82.   if (!D.empty()) cout << " NOT EMPTY !!n";
  84.   newline;
  86.   delete I;
  87. }
  91. main()
  92. { priority_queue<int,int>            Q;
  93.   priority_queue<FLOAT,FLOAT>        Qf;
  95.   int    N     = read_int("# keys = ");
  96.   int*   Int   = new int[N];
  97.   FLOAT* Float = new FLOAT[N];
  99.   random_source ran(0,1000000);
  101.   for(int i=0; i<N; i++) Float[i] = Int[i] = ran();
  103.   _priority_queue<int,int,m_heap>    m_q(N);
  104.   _priority_queue<int,int,k_heap>    k_q(N);
  105.   _priority_queue<int,int,p_heap>    p_q;
  106.   _priority_queue<int,int,list_pq>   l_q;
  108.   _priority_queue<FLOAT,FLOAT,m_heap>    m_qf(N);
  109.   _priority_queue<FLOAT,FLOAT,k_heap>    k_qf(N);
  110.   _priority_queue<FLOAT,FLOAT,p_heap>    p_qf;
  111.   _priority_queue<FLOAT,FLOAT,list_pq>   l_qf;
  114.   newline;
  115.   cout << "                insert   decrease_inf  del_min    totaln";
  116.   newline;
  118.   prio_test(Q,N,Int,"prio");
  119.   //prio_test(m_q,N,Int,"m_heap");
  120.   prio_test(k_q,N,Int,"k_heap");
  121.   prio_test(p_q,N,Int,"p_heap");
  122.   //prio_test(l_q,N,Int,"list_pq");
  123.   newline;
  126.   prio_test(Qf,N,Float,"prio");
  127.   //prio_test(m_qf,N,Float,"m_heap");
  128.   prio_test(k_qf,N,Float,"k_heap");
  129.   prio_test(p_qf,N,Float,"p_heap");
  130.   //prio_test(l_qf,N,Float,"list_pq");
  131.   newline;
  132.  
  133.   return 0;
  134. }