Windows XPが最初のユーザー画像を選ぶのに使ったアルゴリズムとは？
What algorithm did Windows XP use to choose your initial user picture?
Windows XPは初期ユーザー画像を%ALLUSERSPROFILE%配下のDefault Picturesからランダムに選んでいた。その仕組みはRtlRandomExとGetTickCount()をシードにした一巡選択アルゴリズムで、リザーバーサンプリング(k=1)の特殊ケースにあたる。ファイルシステム呼び出しを減らし、実行中にファイル数が変わっても破綻しない利点がある。安全策として100枚で打ち切る。
このアルゴリズムの仕組みは、n個のアイテムのコレクションにおいて、最後のアイテムがランダムに選ばれる確率が1/nであることを利用している。
HNでの議論
146- mawadev
それは、このようなブログを読んで初めて気づくケースだ。技術的には同じように解決できるだろうが、最近は机の上にタスクが山積みで、問題やその影響について考える余裕など全くなく、そうした意識や規律はノイズに埋もれ、時間とともに失われていく。
もし誰かが「これはとても簡単だから」と（いつものように）2分しかくれなかったら、私はディレクトリ内の特定のパターンのファイル数を数えて、ランダムなインデックスを選ぶだけの、非常に素朴で場当たり的なプログラミングをしていただろう。サンプリングもせず、ただ、なぜそんなに時間がかかるのかを聞きたがらない人たちとの議論を避けるためだけに。
これは、私が人生で大量のC#、Java、JS、Pythonを書いて、文字列やオブジェクトのマップを埋め尽くしていた頃を思い出させる。そしてzigを始めて、文字列やデータ構造の割り当てがいかに高コストで複雑になり得るかに気づいた。予算や時間の制約のためにできるだけ早く物事を片付けようとするあまり、どれだけのメモリと計算を無駄にしているかに、ある種衝撃を受けた。
- lyorig
本当に、Windowsの内部に関するRaymond Chenの投稿はどれも小さなクリスマスのようだ。ただ、彼がこうした知識を公開する前に誰かの許可を取らなければならないのかどうかは気になる。
- EMIRELADERO
興味のある人向けに、Chenが話している実際のコードはこちらだ：https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...
- impoppy
>Raymondは30年以上にわたりWindowsの進化に関わってきた。彼は時折Windows Dev DocsのTwitterアカウントに登場し、役に立つ情報を何も伝えない話をする。
- scrumper
これは、コンピュータのプログラミングを始めたばかりのときに使わなければならない認知の切り替えの楽しい例だ。人間にとって、山のようなものの中からランダムに一つを選ぶのは極めて簡単だ。手を伸ばして掴む、あるいはまずテーブルの上でかき混ぜて順番をシャッフルするかもしれない。コンピュータにとって、それに直接対応するものはない。彼らにはそれができないのだ。そして人間のプロセスは、コンピュータが従うものとは似ても似つかない。私たちは集合を数えて反復処理したり、項目を数えてから乱数を生成してn番目の項目を選んだり、nullの項目を選ぶリスクを負ったりする必要はない。
- cgio
何十億秒もの節約のために、人々が余分な脳のサイクルを費やしていた時代。
- rietta
2004年のブログ投稿にリンクする控えめな「少し前」が大好きだ。Raymondは長い間これをやってきたんだな :-)
- ape4
ファイルシステムに、フォルダ内に何個のファイルがあるかを教えてくれる呼び出しがないのは、やや奇妙だ。