在0~N(不包括N)范围内随机生成一个长度为M(M <= N)且内容不重复的数组
PS: 代码涉及的随机函数和一些容器虽然是C++的, 但算法是通用的, 这些容器java等其它语言里也都能找到类似的存在.
1. 最朴素暴力的做法.
N = 10,000, M = 10,000 : (方法2的logn优势已经显现, 方法3的龟速放大的很明显)
N = 30,000, M = 30,000 : (方法2较之1的优势更加明显, 方法3依然最耗时)
N = 50,000, M = 50,000 : (方法1和2已经算不出结果了, 方法1下班没关机, 执行了一宿第二天还是没出结果, 方法2等了15分钟也没结果, 虽然会比1会快点, 原理是一样的, 就是越到后面随机出不重复数的几率越小了, 做太多无用功. 方法3虽然慢, 还是出的来结果的, 方法4依然坚挺, 0ms!)
N = 100,000, M = 100,000: (十万, 依旧是0)
N = 1,000,000, M = 1,000,000: (1百万, GetTickCount()函数有10~16ms的误差, 从下面1千万和1亿的时间来看, 这个算法是绝对线性的, 因此此时实际时间应该在23ms左右. 当然, 这时开始已经换成了堆数组)
N = 10,000,000, M = 10,000,000: (1千万)
N = 100,000,000, M = 100,000,000: (1亿, 将近100M的内存啦, 十亿的时候编译器不支持了)
总结: 无论从代码的实现来看, 还是实际的效率来看, 方法4都是当之无愧的佼佼者. 当然, 文中所测都是在M和N相等的情况, 这种测试用例数量级越大, 对于方法1和2来说越是艰难. 算法是死的, 实际情况是多变的, 实际应用中我们灵活选择甚至混合使用这些方法, 比如N非常大, M相对N来说却又比较小(比如N=1亿, M=1万), 这时候方法1也是完全可以接受的, 毕竟方法1比较省空间, 而方法4是用空间换了时间. 可以说M和N越趋近, 方法4的多余空间开销是越值得的, 否则也可能会有得不偿失的情况呀.
鉴于此, 又一种思路浮现出来, 可以再继续演化一下, 用于M比较大但是仍远小于N的情况.
5. 我们把方法4的data数组去掉, 但是想象中是有这么个数组的. 初始时这个数组里的值都等于其下标. 循环的过程中, 如果某个坐标index被随机到了, 那么把这个记录加到map里, key为index, 从数组尾部拿来一个元素作为value.
这是N = 10,000,000, M = 10,000时的结果, 可见纯数组操作还是更快些, 虽然有很多轮无用功.
N = 10,000,000, M = 100,000时, 方法1就已经无响应了, 而方法5的优点则显而易见了, 这个速度还是可以接受的.
可见, N越大, M和N越接近, 方法1越无力, 反之方法1甚至是个不错的方法, 速度快, 省空间. 所以还是那句话, 算法是死的, 而实际情况是复杂的, 但是我们可以把死的算法进行灵活运用.没有最好只有最适合的, 一切取舍依实际情况吧! : )
全文完.
版权所有, 转载请标明出处. http://blog.csdn.net/aa2650/article/details/12507817
