Wie wir alle wissen, verfügen moderne Betriebssysteme über Thread-Scheduler, die unterschiedliche Aufträge auswählen können, um Ihre Threads basierend auf der internen Logik zu planen, mit der Ihr Code nicht vertraut ist. Normalerweise erstellen Sie Ihren Multithread-Code, um sicherzustellen, dass dieser Ihnen auferlegte Nichtdeterminismus Ihre Ausgabe nicht wesentlich beeinflusst.

Das Ziel hier ist das Gegenteil. Erstellen Sie ein Programm, das die Ganzzahlen im Intervall [0,99] druckt, jedoch in einer Reihenfolge, die aufgrund des OS-Thread-Schedulers von Lauf zu Lauf unterschiedlich ist.

Sie müssen "genug Nichtdeterminismus" erreichen, definiert als:

In 10 aufeinanderfolgenden Sätzen von 10 Versuchen muss Ihr Programm mindestens 9 eindeutige Permutationen innerhalb jedes Versuchs erzeugen. Möglicherweise haben Sie eine angemessene Anzahl fehlgeschlagener Versuchsreihen auf beiden Seiten der aufeinanderfolgenden 10, die erfolgreich sind.

Oder anders ausgedrückt, Sie benötigen 100 Läufe Ihres Programms, wobei jeder Block mit 10 Läufen höchstens zwei Läufe enthält, die dasselbe ausgeben.

Wenn Sie also gelegentlich 98 und 99 tauschen, wird dies nicht ausreichen.

Dies ist ein Code-Golf , also gewinnt die Antwort, die die wenigsten Bytes verwendet.

Minutien

• Schreiben Sie Ihre Ausgabe in stdout, einen Eintrag pro Zeile
• Wenn Sie das Format durch das Verschachteln von Zeichen mit zwei Threads in stdout (auch gelegentlich) beschädigen, was zu dreistelligen Zahlen oder leeren Zeilen führt, ist Ihr Ergebnis ungültig
• Die einzige Ausnahme von der obigen Regel besteht darin, dass Sie nach dem Drucken der zuletzt erforderlichen Nummer eine einzelne leere Zeile ausgeben können (Sie sind willkommen).
• Wenn Sie jemals erforderliche Werte verpassen oder duplizieren, ist Ihr Ergebnis ungültig
• Ihr Programm muss auf einem Single-Core-Prozessor nicht nicht deterministisch sein (obwohl dies ein großes Lob ist).
• Ihr Programm verwendet möglicherweise grüne Threads / Fasern, die nicht vom Betriebssystemkern verwaltet werden, wenn es die anderen Anforderungen der Herausforderung noch erfüllt und das Threading-System Teil Ihrer Sprache oder der Standardbibliothek für Ihre Sprache ist
• Die Laufzeit Ihres Programms muss auf einem modernen Prozessor zuverlässig unter 5 Sekunden liegen
• Sie können keine Änderungen an der Umgebung angeben, die außerhalb Ihres Programms auftreten, wie z. B. Wartezeiten oder Änderungen der Einstellungen. Ihr Programm sollte bestehen, ob 100-mal hintereinander oder mit einer Stunde zwischen jedem Lauf oder 100-mal parallel ausgeführt wird (das würde wahrscheinlich tatsächlich helfen ...)
• Sie können einen Coprozessor wie eine GPU oder Xeon Phi und einen eigenen internen Planungsmechanismus für Aufgaben verwenden. Die Regeln gelten hier genauso wie für grüne Fäden.
• Fühlen Sie sich frei, den Planer mit allen Arten von Schlaf, Erträgen und anderen Tricks zu provozieren, solange Sie die in diesem Beitrag angegebenen Regeln befolgen

Verbotene Operationen

Die einzige Ursache für Nichtdeterminismus, auf die Sie zurückgreifen dürfen, ist, wenn der Scheduler die Ausführung Ihrer Threads plant. Die folgende Liste ist nicht vollständig und soll nur Beispiele für Dinge enthalten, die Sie nicht tun dürfen, da sie andere Quellen des Nichtdeterminismus zulassen.

• Direkter oder indirekter Zugriff auf jede Art von PRNG- oder Hardware-RNG-Fähigkeit (es sei denn, dies ist ein fester Bestandteil des Schedulers).
• Einlesen jeglicher Art von Eingabe (Systemzeit, Dateisystem, Netzwerk usw.)
• Thread-IDs oder Prozess-IDs lesen
• Anpassen des OS-Schedulers; Sie müssen einen Standard-OS-Scheduler von einem Mainstream-Betriebssystem verwenden
• Das Anpassen Ihres Green Thread / Fiber Schedulers ist ebenfalls untersagt. Dies bedeutet, dass Sie Betriebssystemthreads verwenden müssen , wenn Sie eine Sprache für diese Herausforderung schreiben .

Antwortvalidierung

Eine Antwort würde vorzugsweise für alle gängigen Betriebssysteme und modernen Prozessoren funktionieren, wobei das Lob proportional zur Breite der Unterstützung vergeben wird. Dies ist jedoch keine Voraussetzung für die Herausforderung. Eine Antwort muss mindestens einen modernen SMP-Prozessor und ein modernes Betriebssystem unterstützen. Ich werde führende Antworten auf das Ausmaß meiner Hardwareverfügbarkeit testen.

• Wenn Ihr Eintrag auf einem i7 5960x unter Windows 10 v1607 x64 nicht die erforderliche Ausgabe erzeugt, geben Sie die erforderliche Umgebung an
• Wenn ich es mit VMWare Workstation problemlos reproduzieren kann, geben Sie die genauen Betriebssystem- und VM-Spezifikationen an
• Wenn es unter keiner dieser Bedingungen erstellt werden kann, zeichnen Sie eine gleichzeitige Bildschirmaufnahme des Tests auf, wie im Abschnitt "Kopfzeile" beschrieben, und eine Handvideoaufzeichnung Ihres Bildschirms mit Ihrer Maus- und Tastaturinteraktion (oder einem beliebigen Steuerungsschema Ihrer nicht standardmäßigen Berechnung) Gerät verwendet) deutlich sichtbar und poste beide Videos zusammen mit deiner Antwort und füge eine Erklärung hinzu, warum es funktioniert
• Alternativ können Sie einen seriösen, langjährigen Benutzer (der nicht Sie ist) mit passender Hardware beauftragen, das Ergebnis zu reproduzieren und für Sie zu bürgen
• Wenn Ihr Eintrag in einer exotischen Programmiersprache vorliegt, die ein typischer Entwickler nicht zum Kompilieren / Jit / Interpretieren eingerichtet hat, geben Sie Anweisungen zum Einrichten
• Wenn Ihre Eingabe von einer bestimmten Version des JVM / Python-Interpreters / other abhängt, geben Sie an, welche
• Wenn es mehr als 10 Minuten hintereinander dauert, um Ihre 10 erfolgreichen aufeinanderfolgenden Versuchsreihen in meinen Tests zu erhalten, schlagen Sie fehl (lassen Sie die Erfolgsbedingung also nicht zu einem ungewöhnlichen Ereignis werden, insbesondere wenn Sie sich in der Nähe des oberen Bereichs befinden Laufzeit gebunden)

Perl 6 , 27 Bytes

await map {start .say},^100

Erläuterung:

      map {          },^100  # Iterate over the range 0..99, and for each of number:
           start             # Send the following task to a thread pool of OS threads:
                 .say        # Print the number, followed by a newline.
await                        # Wait until all tasks have completed.

Ich hoffe das erfüllt die Aufgabe. (Wenn nicht, lassen Sie es mich bitte wissen).

Testen:

Das Shell-Skript, mit dem ich ausreichend Nichtdeterminismus getestet habe:

#!/usr/bin/bash
for i in {1..10}; do
    set=""
    for j in {1..10}; do
        set="${set}$(perl6 nondet.p6 | tr '\n' ',')\n"
    done
    permutations="$(echo -e "$set" | head -n -1 | sort | uniq | wc -l)"
    echo -n "$permutations "
done

Für mich ergibt dies:

10 10 10 10 10 10 10 10 10 10 

Installationsanweisungen:

Ich habe den Test mit einem aktuellen Rakudo Perl 6 unter 64-Bit-Linux durchgeführt, obwohl ich denke, dass es auf anderen Plattformen funktionieren wird.

Die Rakudo-Download-Seite enthält Anweisungen zur Einrichtung. Ich habe meine aus git so zusammengestellt:

git clone git@github.com:rakudo/rakudo.git
cd rakudo
perl Configure.pl --gen-moar --make-install
export PATH="$(pwd)/install/bin/:$PATH"

Probieren Sie es online aus:

Oder testen Sie es einfach online über diesen von @ b2gills bereitgestellten Link Try It Online . Ich habe einige Läufe überprüft und jedes Mal eine andere Bestellung erhalten, hatte aber nicht die Geduld, sie 100 Mal über diese Online-Schnittstelle auszuführen.

Bash, 32 28 Bytes

for i in {0..99};{ echo $i&}

Ich bin das 100 Mal gelaufen und habe 100 verschiedene Ergebnisse erzielt.

Bearbeiten: 4 Bytes dank @DigitalTrauma gespeichert.

PowerShell , 54 46 44 39 Byte

workflow p{foreach -p($i in 0..99){$i}}

PowerShell-Workflows werden in TIO nicht unterstützt, daher können Sie sie dort nicht ausprobieren. Sollte aber auf Ihrem Windows 10-Computer großartig funktionieren :)

Definiert eine Funktion, pdie beim Aufrufen die Liste der Zahlen ausgibt.

Zeitliche Koordinierung

Ein einzelner Lauf läuft auf meinem Computer zuverlässig in ca. 600 ms. Die unten definierten 100 Tests dauern weniger als 2 Minuten.

Testen

Hier ist der vollständige Code zum Testen:

workflow p{foreach -p($i in 0..99){$i}}
#workflow p{foreach($i in 0..99){$i}}
# uncomment above to prove testing methodology does detect duplicates

1..10 | % {
    $set = $_
    Write-Host "Set $set of 10"
    1..10 | % -b {
        $runs = @()
    } -p {
        $run = $_
        Write-Host "-- Run $run of 10 in set $set"
        $runs += "$(p)"
    } -e {
        Write-Host "-- There were $(10-($runs|Get-Unique).Count) duplicate runs in set $set"
    }
}

Ausgabe auf meinem Computer:

Set 1 of 10
-- Run 1 of 10 in set 1
-- Run 2 of 10 in set 1
-- Run 3 of 10 in set 1
-- Run 4 of 10 in set 1
-- Run 5 of 10 in set 1
-- Run 6 of 10 in set 1
-- Run 7 of 10 in set 1
-- Run 8 of 10 in set 1
-- Run 9 of 10 in set 1
-- Run 10 of 10 in set 1
-- There were 0 duplicate runs in set 1
Set 2 of 10
-- Run 1 of 10 in set 2
-- Run 2 of 10 in set 2
-- Run 3 of 10 in set 2
-- Run 4 of 10 in set 2
-- Run 5 of 10 in set 2
-- Run 6 of 10 in set 2
-- Run 7 of 10 in set 2
-- Run 8 of 10 in set 2
-- Run 9 of 10 in set 2
-- Run 10 of 10 in set 2
-- There were 0 duplicate runs in set 2
Set 3 of 10
-- Run 1 of 10 in set 3
-- Run 2 of 10 in set 3
-- Run 3 of 10 in set 3
-- Run 4 of 10 in set 3
-- Run 5 of 10 in set 3
-- Run 6 of 10 in set 3
-- Run 7 of 10 in set 3
-- Run 8 of 10 in set 3
-- Run 9 of 10 in set 3
-- Run 10 of 10 in set 3
-- There were 0 duplicate runs in set 3
Set 4 of 10
-- Run 1 of 10 in set 4
-- Run 2 of 10 in set 4
-- Run 3 of 10 in set 4
-- Run 4 of 10 in set 4
-- Run 5 of 10 in set 4
-- Run 6 of 10 in set 4
-- Run 7 of 10 in set 4
-- Run 8 of 10 in set 4
-- Run 9 of 10 in set 4
-- Run 10 of 10 in set 4
-- There were 0 duplicate runs in set 4
Set 5 of 10
-- Run 1 of 10 in set 5
-- Run 2 of 10 in set 5
-- Run 3 of 10 in set 5
-- Run 4 of 10 in set 5
-- Run 5 of 10 in set 5
-- Run 6 of 10 in set 5
-- Run 7 of 10 in set 5
-- Run 8 of 10 in set 5
-- Run 9 of 10 in set 5
-- Run 10 of 10 in set 5
-- There were 0 duplicate runs in set 5
Set 6 of 10
-- Run 1 of 10 in set 6
-- Run 2 of 10 in set 6
-- Run 3 of 10 in set 6
-- Run 4 of 10 in set 6
-- Run 5 of 10 in set 6
-- Run 6 of 10 in set 6
-- Run 7 of 10 in set 6
-- Run 8 of 10 in set 6
-- Run 9 of 10 in set 6
-- Run 10 of 10 in set 6
-- There were 0 duplicate runs in set 6
Set 7 of 10
-- Run 1 of 10 in set 7
-- Run 2 of 10 in set 7
-- Run 3 of 10 in set 7
-- Run 4 of 10 in set 7
-- Run 5 of 10 in set 7
-- Run 6 of 10 in set 7
-- Run 7 of 10 in set 7
-- Run 8 of 10 in set 7
-- Run 9 of 10 in set 7
-- Run 10 of 10 in set 7
-- There were 0 duplicate runs in set 7
Set 8 of 10
-- Run 1 of 10 in set 8
-- Run 2 of 10 in set 8
-- Run 3 of 10 in set 8
-- Run 4 of 10 in set 8
-- Run 5 of 10 in set 8
-- Run 6 of 10 in set 8
-- Run 7 of 10 in set 8
-- Run 8 of 10 in set 8
-- Run 9 of 10 in set 8
-- Run 10 of 10 in set 8
-- There were 0 duplicate runs in set 8
Set 9 of 10
-- Run 1 of 10 in set 9
-- Run 2 of 10 in set 9
-- Run 3 of 10 in set 9
-- Run 4 of 10 in set 9
-- Run 5 of 10 in set 9
-- Run 6 of 10 in set 9
-- Run 7 of 10 in set 9
-- Run 8 of 10 in set 9
-- Run 9 of 10 in set 9
-- Run 10 of 10 in set 9
-- There were 0 duplicate runs in set 9
Set 10 of 10
-- Run 1 of 10 in set 10
-- Run 2 of 10 in set 10
-- Run 3 of 10 in set 10
-- Run 4 of 10 in set 10
-- Run 5 of 10 in set 10
-- Run 6 of 10 in set 10
-- Run 7 of 10 in set 10
-- Run 8 of 10 in set 10
-- Run 9 of 10 in set 10
-- Run 10 of 10 in set 10
-- There were 0 duplicate runs in set 10

GCC unter Linux, 47 Bytes

main(i){for(i=99;fork()?i--:!printf("%d\n",i););}

Dies gab mir gccfast jedes Mal andere Ergebnisse, nachdem ich mit (ohne Flags) Version 4.9.2 kompiliert worden war. Insbesondere war ich auf 64-Bit-Debian 8.6 (Kernel-Version 3.16.31).

Erläuterung

Wenn der fork()Wert Null zurückgibt (untergeordneter Prozess), wird der Wert von igedruckt und die Schleifenbedingung ist falsch, da printfein Wert größer als Null zurückgegeben wird. Im übergeordneten Prozess ist die Schleifenbedingung gerecht i--.