Feeds:
Posts
Comments

Archive for November, 2010

Pearls from

  • "72"法则:假设r%年利率投资一笔钱y年,如果ry=72,那么投资差不多会翻番。推导很简单,二项式展开,用头三项近似一下就行了。更有用的说法应该是,72/r年后投资能翻番。
  • Little定律:考虑一个带有输入和输出的任意系统,Little定律指出“系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积”,如果出入平衡的话,离开速率等于进入速率。
  • 旋转数组ab为ba的方法:ab -> a’b -> a’b’ -> ba,a’表示a的倒转。这个算法比分解为gcd数目个轮换的方法要cache友好得多。
  • 从n个元素{0,1,…,n-1}中均匀随机采样m个元素的算法,
    spot=m;
    for(int i=0;i<n;i++)
    if( rand(0,n-i-1) < spot)spot–,printf("%d\n",i);

    实际上就是把元素i随机放到n-i个可能的位置上,如果这个位置在spot之内,则选中。每次要去掉已经被占的位置。

  • 另外有一个只需要生成m个随机数的算法:
    int* p=new int[n];
    for(int i=0;i<n;i++)p[i]=i;
    for(int i=0;i<m;i++)swap(p[i],p[rand(i,n-1)]);
    for(int i=0;i<m;i++)printf("%d\n",p[i]);

    本质是从后向前用经典算法生成一个随机排列,然后取前m个元素。实际上只需要重排前m个元素。

  • 如果要求采样算法的时间和空间复杂度跟n无关,则有以下的算法
    selected={}
    for i in range(n-m,n):
    t=random.randint(0,i)
    if t in selected: selected[i]=1
    else: selected[t]=1

    可以用数学归纳法证明这个算法的正确性。前n-1个元素中选取的m-1个元素的概率平均性推导到n个元素中选取m个概率平均性。

  • 为单链表增加一个指针p[i],指向第2*i个元素,那么可以简单的在对数时间内访问第n个元素。
  • new操作符分配的内存块有额外开销,比如sizeof不超过12字节的结构体,new实际上总是分配48字节。
Advertisements

Read Full Post »