注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Kandy

长风破浪会有时,直挂云帆济沧海!

 
 
 

日志

 
 

【转】比较好的随机算法  

2010-09-08 17:54:50|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
//  random.hpp
//  Copyright (C) 2008  Chipset
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Affero General Public License as       
//  published by the Free Software Foundation, either version 3 of the    
//  License, or (at your option) any later version. 
//    
//  but WITHOUT ANY WARRANTY; without even the implied warranty of 
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
//  GNU Affero General Public License for more details.
//
//  You should have received a copy of the GNU Affero General Public License
//  along with this program. If not, see <http://www.gnu.org/licenses/>.   
//

#ifndef RANDOM_HPP_
#define RANDOM_HPP_
#include 
<ctime>

class random
{
public:
  
explicit random(unsigned long s = 0) : seed(s)
  {
    
if (0 == seed) seed = std::time(0);
    randomize();
  }
  
void reset(unsigned long s = 0)
  {
    seed 
= s;
    
if (0 == seed) seed = std::time(0);
    randomize();
  }
  unsigned 
long rand()
  {
  
//returns a random integer in the range [0, -1UL)
    randomize();
    
return seed;
  }
  
double real()
  {
  
//returns a random real number in the range [0.0, 1.0)
    randomize();
    
return double(seed) / -1UL;
  }
private:
  unsigned 
long seed;
  
void randomize() { seed = 1103515245UL * seed + 123456789UL; }
};

class rand_help
{
  
static random r;
public:
  rand_help() {}
 
void operator()(unsigned long s) { r.reset(s); }
  unsigned 
long operator()() const { return r.rand(); }
 
double operator()(double) { return r.real(); }
};
random rand_help:: r;

extern
void srandom(unsigned long ns = 0) { rand_help()(ns); } //reset seed
extern unsigned long irand() { return rand_help()(); }         //negative numbers disallowed
extern double drand() { return rand_help()(1.0); }             //for real numbers

#endif  // RANDOM_HPP_

//以上随机数产生器产生的随机数比rand()产生的随机数更加随机(可以用数学方法检验),
//范围更大(一目了然),速度更快(测试一下便知,稍加修改我还可以让它再快一些,如果有必要)。

/*假设随机数均匀分布为理想分布, 粗略估计随机性*/
#include 
<iostream>
#include 
<vector>
#include 
<iomanip>
#include 
"random.hpp"
int main()
{
  srand(time(
0));
  
//SZ分别取值2^3, 2^4, 【转】比较好的随机算法 - Kandy - Kandy, 2^15进行测试
  const size_t SZ = 1 << 15;
  std::vector
<unsigned> v1(SZ), v3(SZ);
  std::vector
<unsigned> v2(SZ), v4(SZ);
  
for(size_t i = 0; i < SZ; ++i)
  {
    
++v1[rand() % SZ];//对应元素计数 ,理论上v1[0] ~ v1[SZ - 1]之间每个都应该是1
    ++v2[irand() % SZ];
  }

  
for(size_t i = 0; i < SZ; ++i)
  {
    
++v3[v1[i]]; //统计频度
    ++v4[v2[i]];
  }
  
//假设[0, SSZ)之间不存在间断点, (即使有间断点也无所谓,我们只做粗略模糊统计,因为没有必要那么精确)
  
//最理想的显示结果应该是0:    0,   1:   SZ,    2:    0,   3:    0,   4:    0,   other:    0
  
//0:表示间断,1:表示均匀,2:, 3:, 4:, other: 都表示不同程度的重复
  const size_t SSZ = 5;
  std::cout.fill(
' ');
  
for(size_t i = 0; i < SSZ; ++i)
    std::cout 
<< i << "" << std::setw(SSZ) << v3[i] << ",   ";
  std::cout 
<< "other: " << std::setw(SSZ)
            
<< v3.size() - v3[0- v3[1- v3[2- v3[3- v3[4<< '\n';
  
for(size_t i = 0; i < SSZ; ++i)
    std::cout 
<< i << "" << std::setw(SSZ) << v4[i] << ",   ";
  std::cout 
<< "other: " << std::setw(SSZ)
            
<< v4.size() - v4[0- v4[1- v4[2- v4[3- v4[4<< '\n';
  system(
"pause");
}


//做速度测试
#include <iostream>
#include 
<ctime>
#include 
<cstdlib>
#include 
<windows.h>
#include 
"random.hpp"

int main()
{
  
const size_t SZ = 1 << 27;
  std::cout 
<< "generating random numbers in progress 【转】比较好的随机算法 - Kandy - Kandy\n";
  std::cout 
<< SZ << " random numbers generated.\n";
  std::cout 
<< "random used: ";
  Sleep(
1000);
  std::clock_t time 
= clock();
  
for(size_t i = 0; i < SZ; ++i)
    irand();
  std::cout 
<< clock() - time << "ms, ";

  std::cout 
<< "rand() used: ";
  Sleep(
1000);
  std::srand(std::time(
0));
  std::clock_t t 
= clock();
  
for(size_t i = 0; i < SZ; ++i)
    std::rand();
  std::cout 
<< clock() - t << "ms\n";

  std::system(
"PAUSE");
  
return 0;
}
  评论这张
 
阅读(150)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017