里用了线性搜寻(linear search)……另外也可以用二分搜寻(binary search)那么复杂度会降低为O(lg N)……那么还有没有更快的方法呢答案是肯定的例如别名方法(alias method)、*似方法等有兴趣的读者可参考……当然在N很小的情况下线性搜寻和二分搜寻也足够。笔者撰写本文灵感来自这篇博文(指《实》)。其算法实际上是储存CDF的逆函数采样利用空间和有限的CDF精确度换取O(1)的时间复杂度。衡量N的大小、精确度、空间需求、缓存延迟后或许该方法也能适合某些个别需求。但对于该文作者说N最大为100二分搜寻只需最多7次迭代因缓存问题可能二分搜寻更快。之后肖舸在另一篇博文《做程序要“专注”和“客观”》中当中有一段似乎是回应上文:就好比我前面写的一篇博文《实》我在文中的代码里明明实现了O(1)的复杂度但是就有人为了攻击我本人和我的书《……》专门撰文说用其他办法O(7)的复杂度也可以实现我这个办法不值得提倡。我晕我们做算法优化有时候O(n)这个值能减少1都是巨大的成功因为程序是有循环的循环次数是被乘数哦这是乘法关系这个核心算法复杂度减少1放出去就是几千万甚至几亿的时钟开销效率提升就是巨大的。很多时候我做优化都在为了减少这个1在努力。不过这毕竟是少数人准确的讲说这话的人不能算技术人员因为针对到科学的算法的优化的问题上一是一二是二不能带着个人感情讨论。这是技术人员特别是程序员基本的职业道德。这里我希望广大程序员朋友一定要养成一个习惯“客观”和“严谨”是程序员的基本职业修养也是我们能在这个行业里面立足的根本千万不要丢掉了。因为文中说“O(7)”我想应该是回应我写的7次迭代如果不是 就当本人对号入座吧。对于算法是否属于“科学”大家可以想想。我自问只谈到技术上的意见不知道为什么会说到“个人感情”甚至推理至是否一个技术人员、有没有职业道德问题了。也许是本人写得不够清楚也许是读者有误解无论如何本人也在此解释一下。复杂度与性能首先肖舸说“O(n)这个值”、“ 核心算法复杂度减少1” 、“O(7)”都是不正确的说法。研究算法的运行时间最常见是采用Big-O表示法例如O(1)、O(n)等。这表示法是指算法在n接*无限大的时候其运行时间的渐*复杂度(asymptotic complexity)的上界(upper bound)。举个例子例如解决同一问题的两个算法﹐它们的运行时间(例如单位是秒)为:用Big-O表示法A算法是线性速度O(n)B算法是常数速度O(1)。也就是说n大到某个程度算法A比算法B慢。那么n要有多大只要联合两个函数即可求出当n 4时算法A比B慢。相反当n4时算法A会比算法B快。如果有另一组算法其方程求出来的n是少于或等于0说明当中的其中一个算法永远比另一个优。使用Big-O表示法的目的是方便比较不同的算法。 Big-O会隐藏的算法实现时的系数(例如上面例子中的2、1、9)。而在实际应用中设计或实现算法还要考虑多个因素例如算法的应用场合: 算法所需的精确度、时间要求(通常二者须此消彼长)。如算法分为几个步骤(如本问题可分割为初始化和采样)每个步骤的实际使用次数。另外亦要考虑输入数据的分布。内存的使用: 同时间内所需的内存最大值(可用Big-O表示法)、内存存取模式(access pattern)。算法实现的难度: 除了开发及维护时间还影响程序是否健壮(robust)例如复杂的浮点运算会做成误差。硬件: 例如主频、核心数量、内存速度、特殊指令(如SIMD)或者不同架构的可编程系统(如GPU)、设备等软件: 会执行于什么操作系统、编译器、库等等这些软件对算法是否有影响。很多时候解决同一问题有许多算法并没有绝对的好坏之分(当然有时候也有些能完全取胜有些完全无用)每个算法都其优点缺点。程序员须要分析实际应用去选择及实现算法。理想地更可以实验多个算法用实际数据去作出比较。评论肖舸的实现这个是肖舸在《实》公布的实现代码(本人加入了#ifdef MILO_HOTFIX及GetMemory()):123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143#define CTonyRandomArea_TOKEN_MAX 100 //最大类型数#define CTonyRandomArea_TOKEN_AREA_MAX 10000 //类型数组单元数精确到小数点后两位//输入最大100个元素的数组每个数组表示每类占有的百分比内部自带百分比调整。//即如果外部输入的数字之和不是整数100内部会根据百分比自动调整其比例使总和100.0//然后内部建立10000个单元的类型数组根据传入的每种类型的比例在类型数组中批量填充对应的类型值//总之类型数组中每种类型的数量占据的比例正好是输入的百分比//最后在0~10000中取随机然后在对应的类型数组单元中取类型值即为返回的类型classCTonyRandomArea{public:CTonyRandomArea(double* pTokenPercentArray,charcTokenCount){m_nTokenCountcTokenCount;if(CTonyRandomArea_TOKEN_MAXm_nTokenCount)m_nTokenCountCTonyRandomArea_TOKEN_MAX;inti0;for(i0;im_nTokenCount;i){m_dTokenPercentArray[i]*(pTokenPercentArrayi);}//动态调整内部的值//有时候试验人员测得几个状态出现的数字可能懒得再计算成百分比//程序帮忙自动计算doubledNumberCount0;for(i0;im_nTokenCount;i){dNumberCountm_dTokenPercentArray[i];}if(100.0!dNumberCount){for(i0;im_nTokenCount;i){m_dTokenPercentArray[i]/dNumberCount;m_dTokenPercentArray[i]*100;}}//以小数点后两位精度开始计算在10000个总单元中每种类型对应的数量。for(i0;im_nTokenCount;i){m_sTokenPercentArray[i](short)(m_dTokenPercentArray[i]*100);}//按比例填充类型数组intj0;intnFillMin0;intnFillMax0;#ifdef MILO_HOTFIXfor(i0;iCTonyRandomArea_TOKEN_AREA_MAX;i){m_cTokenPercentArrayAreaUp[i]0;}#elsefor(i0;im_nTokenCount;i){m_cTokenPercentArrayAreaUp[i]-1;}#endiffor(i0;im_nTokenCount;i){nFillMaxnFillMinm_sTokenPercentArray[i];for(jnFillMin;jnFillMax;j){m_cTokenPercentArrayAreaUp[j]i;}nFillMinnFillMax;}// m_cTokenPercentArrayAreaUp[CTonyRandomArea_TOKEN_AREA_MAX-1]i-1;}~CTonyRandomArea(){}voidPrintfInfo(void){inti0;doubledNumberCount0;for(i0;im_nTokenCount;i){dNumberCountm_dTokenPercentArray[i];printf(%d %f\n,i,m_dTokenPercentArray[i]);}printf(All %f\n,dNumberCount);//打印10000个单元的类型分布看看排得对不对//这段打印起来太长一般隐掉需要了再打印// int nOutMax400;// int nInMax25; //二者相乘为10000// int j0;// for(i0;inOutMax;i)// {// printf(%05d - ,i*nInMax);// for(j0;jnInMax;j)// {// printf(%d ,m_cTokenPercentArrayAreaUp[i*nInMaxj]);// }// printf(\n);// }}//取类型数组对应单元的值charGetType(intnTypeIndex)//输入参数0~10000{if(10000nTypeIndex) nTypeIndex9999;if(0nTypeIndex) nTypeIndex0;returnm_cTokenPercentArrayAreaUp[nTypeIndex];}//真实的工作函数利用输入的概率来产生随机typecharGetRandomType(void){returnGetType(GetRandomBetween(0,10000));}// MILO ADD {size_tGetMemory()const{returnsizeof(*this);}// } MILOprivate:doublem_dTokenPercentArray[CTonyRandomArea_TOKEN_MAX];//比例数组shortm_sTokenPercentArray[CTonyRandomArea_TOKEN_MAX];//比例数组,短整型1~10000相当于精确到小数点后两位charm_nTokenCount;charm_cTokenPercentArrayAreaUp[CTonyRandomArea_TOKEN_AREA_MAX];//类型数组};////这是测试代码//void TestCTonyRandomArea(void)//{// double dTokenPercentArray[100];//// dTokenPercentArray[0]12.0;// dTokenPercentArray[1]40.0;// dTokenPercentArray[2]40.0;// dTokenPercentArray[3]7.0;// dTokenPercentArray[4]1.0;//// CTonyRandomArea Area1(dTokenPercentArray,5);// Area1.PrintfInfo();//// int i0;// for(i0;i20;i)// {// printf(RandType %d\n,Area1.GetRandomType());// }//}崩溃Bug