Windows XP wählte dein Profilbild per Zufallsalgorithmus
What algorithm did Windows XP use to choose your initial user picture?
Raymond Chen erklärt, wie Windows XP das anfängliche Benutzerbild auswählte: Ein Ein-Pass-Zufallsalgorithmus mit RtlRandomEx und GetTickCount() als Seed. Statt alle Dateien zu zählen und dann eine auszuwählen, wird jedes Bild mit einer Wahrscheinlichkeit von 1/n gewählt. Das reduziert Dateisystemaufrufe und bleibt stabil, falls sich die Anzahl der Dateien während der Ausführung ändert. Nach 100 Bildern stoppt der Algorithmus, um pathologische Fälle zu vermeiden.
Der Ein-Pass-Algorithmus ist ein Spezialfall des Reservoir-Samplings, bei dem k gleich 1 ist.
- mawadev
Das ist ein Fall, der mir erst bewusst wird, wenn ich Blogs wie diesen lese. Technisch gesehen könnte ich es genauso lösen, aber heutzutage hat man so viele Aufgaben auf dem Tisch, dass man über das Problem und seine Implikationen gar nicht nachdenkt, und dieses Bewusstsein/diese Disziplin ertrinkt im Lärm/verlernt man mit der Zeit.
Wenn mir jemand nur 2 Minuten dafür geben würde, weil er denkt, es sei sehr einfach (wie immer), hätte ich eine Zählung der Dateien mit einem bestimmten Muster im Verzeichnis gemacht und dann einen zufälligen Index ausgewählt, sehr naiv und schnell und schmutzig programmiert, ohne Sampling, nur um Diskussionen darüber zu vermeiden, warum es so lange dauert, mit Leuten, die es nicht hören wollen.
Das erinnert mich daran, als ich in meinem Leben viel C#, Java, JS, Python gemacht habe und Maps von Strings und Objekten gefüllt habe, bis ich mit zig anfing und bemerkte, wie teuer und kompliziert Strings und Datenstruktur-Allokationen sein können. Es hat mich irgendwie umgehauen, wie viel Speicher und Rechenleistung wir verschwenden, wenn wir versuchen, Dinge so schnell wie möglich zu erledigen, wegen Budget-/Zeitbeschränkungen.
- lyorig
Mann, jeder Beitrag von Raymond Chen über Windows-Interna ist wie ein kleines Weihnachtsfest. Ich frage mich allerdings, ob er jemanden um Erlaubnis bitten muss, bevor er dieses Wissen veröffentlicht.
- EMIRELADERO
Für die Interessierten, hier ist der tatsächliche Code, über den Chen spricht: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...
- impoppy
>Raymond war mehr als 30 Jahre lang an der Entwicklung von Windows beteiligt. Gelegentlich erscheint er im Windows Dev Docs Twitter-Account, um Geschichten zu erzählen, die keine nützlichen Informationen vermitteln.
- scrumper
Dies ist ein lustiges Beispiel für den kognitiven Umschwung, den man vollziehen muss, wenn man anfängt, einen Computer zu programmieren. Für einen Menschen ist es extrem einfach, zufällig eine Sache aus einem Haufen Dinge auszuwählen: Man streckt die Hand aus und greift sie, vielleicht wirbelt man sie vorher auf dem Tisch herum, um die Reihenfolge zu mischen. Für einen Computer gibt es dafür keine direkte Analogie. Sie können es einfach nicht. Und der menschliche Prozess ist nicht einmal im Entferntesten wie der, den der Computer befolgt: Wir müssen nicht die Mengen zählen und über sie iterieren, oder die Elemente zählen und dann eine Zufallszahl generieren, um das n-te Element auszuwählen, oder riskieren, ein Null-Element auszuwählen.
- cgio
Die Zeiten, in denen Leute einen zusätzlichen Gehirnzyklus aufwendeten, um Milliarden von Sekunden zu vermeiden.
- rietta
Ich liebe das untertriebene "vor einiger Zeit", das auf einen Blogbeitrag von 2004 verlinkt. Raymond ist schon lange dabei :-)
- ape4
Es ist etwas seltsam, dass Dateisysteme keinen Aufruf haben, der einem sagt, wie viele Dateien sich in einem Ordner befinden.