多数のフラグを「フラグを表す配列を初期化せずに」初期化して使う方法

http://d.hatena.ne.jp/kaminarioyaji/20081204/1228387500
http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html
下のリンクは長い英語なので読んでないが、同じことを言ってるらしい。
完全に理解したわけではないが、この方法が正しく動作する証明はできるようになった。
まず、この方法をC#で実装したFlagクラスのコードを示す。

using System;

//N個のフラグを管理するクラス（最大でM個しか立たないことを前提とする）
class Flag
{
	readonly uint N, M;
	readonly uint[] flag, link;//非負整数である必要がある
	uint count;
	
	public Flag(uint N, uint M)
	{
		this.N = N;
		this.M = M;
		flag = new uint[N];//Mまでの数値が扱えればいい（Mが0x10000以下ならushortでいい）
		link = new uint[M];//Nまでの数値が扱えればいい（Nが0x10000以下ならushortでいい）
		clear();
	}
	public Flag(uint N) : this(N, N)
	{
	}
	
	//N個全てのフラグをfalseに設定する
	public void clear()
	{
//		//ここをコメント解除しても正しく動作する
//		Random rnd = new Random();
//		for (uint n = 0; n < N; n++){
//			flag[n] = (uint)rnd.Next();
//		}
//		for (uint m = 0; m < M; m++){
//			link[m] = (uint)rnd.Next();
//		}
		count = 0;
	}
	
	//フラグnを状態bに設定する
	public int set(uint n, bool b)
	{
		uint m;
		if (b == get(n)) return 0;
		
		if (b){
			if (count >= M) return 1;//フラグを立てられるのはM個まで
			m = count++;
		} else {
			//linkで最後のフラグをfalseにするにはcountを1減らすだけでいい
			//そこで、falseにしたいフラグを最後のフラグと入れ替える
			m = flag[n];
			n = link[--count];
			if (m == count) return 0;//この行は、必要ではない
		}
		flag[n] = m;//フラグnが立っていれば、linkではm個目で管理されている
		link[m] = n;//m個目のフラグが立っていれば、それはフラグnである
		//※m個目のフラグが立っていることは、（mが非負整数なら）m<countと同値
		return 0;
	}
	
	//フラグnの状態を得る
	public bool get(uint n)
	{
		uint m = flag[n];
		//この時点ではm>=Mである可能性もあるが、問題ない
		return m < count && link[m] == n;
		//m<countならばm個目のフラグは立っているので、それがフラグnかどうかの問題となる
	}
	
	//立っているフラグの個数を返す
	public uint Count
	{
		get
		{
			return count;
		}
	}
	
	//立っているフラグを全て出力する（小さい順に出力されるとは限らない）
	public int put()
	{
		uint n, m;
		Console.WriteLine("count = {0}", count);
		//このforループの回数は、（N以下ではなく）M以下に抑えられる
		for (m = 0; m < count; m++){
			n = link[m];
			if (get(n)) Console.Write("{0} ", n);
		}
		Console.WriteLine();
		return 0;
	}
}

class Sosuu
{
	public static int Main()
	{
		uint i, j, n, nn, m;
		
		//n未満の素数を列挙する
		n = 10000;
		nn = (uint)Math.Sqrt(n - 1);
		
		//0以上n未満の、全ての合成数を得る
		Flag composite = new Flag(n);
		for (i = 2; i <= nn; i++){
			if (composite.get(i)) continue;
			for (j = i * i; j < n; j += i){
				composite.set(j, true);
			}
		}
		m = n - composite.Count;//n未満の素数はm個以下
		
		//合成数でない2以上n未満の整数（n未満の素数）を得る
		Flag prime = new Flag(n, m);
		for (i = 2; i < n; i++){
			if (!composite.get(i)) prime.set(i, true);
		}
		prime.put();
		
		return 0;
	}
}

下のSosuuクラスは、Flagクラスを利用して（というか無理矢理利用させられて）
10000未満の素数を表示するサンプル。
これはただの使用例で、Flagクラスを使う意味は全くない。
そもそもC#は配列を自動で初期化してくれちゃうし、
本来1bitで済むフラグに32bitも食われてしまうので、たとえメモリが足りても遅い。
めちゃくちゃ多い数のフラグを管理する必要があって、
それと比べれば少ないが絶対量では少なくない数のフラグが立つ可能性があり、
よほどメモリに余裕があって、フラグのクリアや立ってるフラグの列挙を高速にしたい、
そういうときにしか使う意味がないけど、どういうときなんだろうか。
HDD上でフラグを管理するような場合にいいかなあ。
さて、上のコードの説明。
フラグ0からフラグN-1までのN個のフラグを管理するクラス。
flag[n]は、フラグnが立っているときに、それがlinkで何個目かを示す。
フラグnが立っていないときは、何が入っているかわからない（何が入っててもいい）。
link[m]は、mがcount未満のときに、（n=link[m]として）フラグnが立っていることを示す。
mがcount以上M未満のときは、何が入っているかわからない（何が入っててもいい）。
countは、フラグが何個立っているかを表している。
以上の条件を満たすように作ったのがFlagクラスで、これでFlag.get()が正しく動作する。
例えば、10個のフラグのうちフラグ3だけが立っていたとする。
ここで保証されているのは、flag[3] == 0 && link[0] == 3 && count == 1。
flag[5] = 0としてフラグ5が立っていると偽装しようとしても、
link[0]が5じゃないのでバレてしまう。
link[1] = 5としても、1がcount未満じゃないので見てもらえない。
配列を初期化せずに使えるというのだけ聞くと不思議に思えるが、
link[0]〜link[count-1]にどのフラグが立っているかを保存してあるわけだから、
ぶっちゃけ（遅くてもいいなら）linkだけあればflagは要らない。
速度を保つためにflagを導入したというように捉えれば、
それほどトリッキーな手法ではないだろう。
最後に、（m = flag[n]として）m < count && link[m] == nというのが、
フラグnが立っていることと同値（必要かつ十分）というのがすごい。
link[m]にアクセスするときにmが0以上M未満であると保証されているのだ。
フラグnが立っていればflag[n]はcount未満だから、mがcount以上ならfalseを返すし、
そうでないならlink[m]の内容は「必ず」m個目に立っているフラグを表している。
それがnならフラグnは立っているし、nでなければflag[n]が嘘だったことになるので、
フラグnが立っていたと仮定すると規約に矛盾するからフラグnは立っていない。