セットベースのアプローチ:
しきい値が低い場合 (たとえば 40% 未満)、推奨されるアプローチは次のとおりです。
- 最後に
N*T生成された値のセットとキューを用意します。
- 値を生成するときは、セットに含まれなくなるまで再生成を続けます。
- キューにプッシュするときは、最も古い値をポップしてセットから削除します。
擬似コード:
generateNextValue:
// once we're generated more than N*T elements,
// we need to start removing old elements
if queue.size >= N*T
element = queue.pop
set.remove(element)
// keep trying to generate random values until it's not contained in the set
do
value = getRandomValue()
while set.contains(value)
set.add(value)
queue.push(value)
return value
しきい値が高い場合は、上記を逆にすることができます。
- 最後に生成された値に含まれていないすべての値をセットに表すようにします。
N*T
- すべての set 操作を反転します (すべての set の add を remove に、またはその逆に置き換え、
containsをに置き換えます!contains)。
擬似コード:
generateNextValue:
if queue.size >= N*T
element = queue.pop
set.add(element)
// we can now just get a random value from the set, as it contains all candidates,
// rather than generating random values until we find one that works
value = getRandomValueFromSet()
//do
// value = getRandomValue()
//while !set.contains(value)
set.remove(value)
queue.push(value)
return value
シャッフルベースのアプローチ: (上記よりやや複雑)
しきい値が高い場合、既に存在する値を生成し続ける可能性があるため、上記の処理に時間がかかる場合があります。
この場合、いくつかのシャッフル ベースのアプローチの方が適切な場合があります。
- データをシャッフルします。
- 最初の要素を繰り返し処理します。
- その際、抜き差し範囲内のランダムな位置に差し込んでください
[N*T, N]。
例：
N*T = 5 としましょう。すべての可能な値は[1,2,3,4,5,6,7,8,9,10]です。
次に、最初にシャッフルして、たとえば[4,3,8,9,2,6,7,1,10,5].
次に、それを削除して、範囲内のインデックス(インデックス 5 など)4に挿入し直します。[5,10]
次に、 があり[3,8,9,2,4,6,7,1,10,5]ます。
そして、必要に応じて次の要素を削除し、挿入し直します。
実装：
効率性をあまり気にしないのであれば、配列は問題ありません。1 つの要素を取得するには時間がかかりO(n)ます。
これを効率的にするには、効率的なランダム位置の挿入と最初の位置の削除をサポートする順序付きデータ構造を使用する必要があります。最初に頭に浮かぶのは、インデックス順に並べられた (自己均衡型の) 二分探索木です。
実際のインデックスは保存しません。インデックスはツリーの構造によって暗黙的に定義されます。
各ノードには、子の数 (+ 1 自体) があります (挿入/削除時に更新する必要があります)。
挿入は次のように行うことができます: (自己平衡部分は今のところ無視します)
// calling function
insert(node, value)
insert(node, N*T, value)
insert(node, offset, value)
// node.left / node.right can be defined as 0 if the child doesn't exist
leftCount = node.left.count - offset
rightCount = node.right.count
// Since we're here, it means we're inserting in this subtree,
// thus update the count
node.count++
// Nodes to the left are within N*T, so simply go right
// leftCount is the difference between N*T and the number of nodes on the left,
// so this needs to be the new offset (and +1 for the current node)
if leftCount < 0
insert(node.right, -leftCount+1, value)
else
// generate a random number,
// on [0, leftCount), insert to the left
// on [leftCount, leftCount], insert at the current node
// on (leftCount, leftCount + rightCount], insert to the right
sum = leftCount + rightCount + 1
random = getRandomNumberInRange(0, sum)
if random < leftCount
insert(node.left, offset, value)
else if random == leftCount
// we don't actually want to update the count here
node.count--
newNode = new Node(value)
newNode.count = node.count + 1
// TODO: swap node and newNode's data so that node's parent will now point to newNode
newNode.right = node
newNode.left = null
else
insert(node.right, -leftCount+1, value)
現在のノードでの挿入を視覚化するには:
次のようなものがある場合：
4
/
1
/ \
2 3
5そして、現在の場所を挿入したい1場合、次のようになります。
4
/
5
\
1
/ \
2 3
たとえば、 red-black treeが自身のバランスを維持するために操作を実行する場合、比較は行われないため、既に挿入されている要素の順序 (つまりインデックス) を知る必要がないことに注意してください。ただし、カウントを適切に更新する必要があります。
全体の効率はO(log n)、1 つの要素を取得することになります。