プログラミング珠玉学習ノートpython実現

最近「プログラミング珠玉」という神器を研究するつもりで、第1章では主にビットマップという構造を利用していくつかの問題を便利に解決することを話した.
ビットマップでソートされたアルゴリズムを見ると、いくつかの小さな問題がまとめられます.
1.0からn-1の間にあるk個の異なるランダム順序のランダム整数をどのように生成するか
生成されるk個の乱数は重複せず、各乱数はn未満であることが要求される.
この問題はn,k値が比較的小さい場合に解決しやすいが,n値が比較的大きい場合,例えば1000000ではアルゴリズムの効率を考慮せざるを得ない.
2つの解法(Python実装):

'''

Created on 2012-7-31



@author: wanglei

'''

import random

def rand1(n,k):

    numlist=[i for i in range(0,n)]

    #print numlist

    klist=[0]*k

    for i in range(0,k):

        j=random.randint(i,n-1)

        tmp=numlist[j]

        numlist[j]=numlist[i]

        numlist[i]=tmp

        klist[i]=numlist[i]

    return klist

#print numlist

def rand2(n,k):

    boollist=[False]*n

    klist=[0]*k

    for i in range(0,k):

        j=-1

        j=random.randint(0,n-1)

        while(boollist[j]):

            j=random.randint(0,n-1)

        klist[i]=j

        boollist[j]=True

    return klist

n=10000000

k=5000000

print rand1(n,k)

print rand2(n,k)

rand 1(n,k)は,0−n−1の数をまずすべて1つのリストに格納し,変数iを0からk−1にループし,(i,n−1)で乱数jを生成し,numlist[i]とnumlist[j]の値を交換するたびに,最後にnumlistリストの前のkの数(すなわちklist)を求める無繰返し乱数とすることを構想している.
rand 2(n,k)構想は,長さnのブール値の配列を定義することである.Falseに初期化します.次に、boollist[j]がFalseになるまで乱数jを生成し、j値をklistに計上する