Jak wszyscy wiemy, nowoczesne systemy operacyjne mają harmonogramy wątków, które mogą wybierać różne zamówienia do planowania wątków w oparciu o wewnętrzną logikę, do której kod nie jest wtajemniczony. Zwykle architektujesz swój wielowątkowy kod, aby mieć pewność, że narzucony ci niedeterminizm nie wpłynie znacząco na wynik.

Cel tutaj jest odwrotny. Utwórz program, który drukuje liczby całkowite w przedziale [0,99], ale w kolejności, która będzie się różnić w zależności od uruchomienia z powodu harmonogramu wątków systemu operacyjnego.

Musisz osiągnąć „wystarczającą niedeterminizm”, zdefiniowaną jako:

W 10 kolejnych zestawach po 10 prób twój program musi wygenerować co najmniej 9 unikalnych kombinacji w każdej próbie. Możesz mieć rozsądną liczbę nieudanych zestawów prób po obu stronach kolejnych 10, które się powiodły.

Innymi słowy, potrzebujesz 100 uruchomień programu, w których każdy blok 10 uruchomień ma co najwyżej dwa uruchomienia, które generują to samo.

Od czasu do czasu zamiana 98 i 99 go nie uciszy.

To jest golf golfowy , więc wygrywa odpowiedź wykorzystująca najmniej bajtów.

Drobne szczegóły

• Napisz wyjście na standardowe wyjście, po jednym wpisie w wierszu
• Jeśli zmienisz format, gdy dwa wątki przeplatają zapisywanie znaków na standardowe wyjście (nawet sporadycznie), czego rezultatem są liczby trzycyfrowe lub puste linie, wynik jest nieprawidłowy
• Jedynym wyjątkiem od powyższej zasady jest to, że możesz wydrukować pojedynczy pusty wiersz po wydrukowaniu ostatniego wymaganego numeru (nie ma za co)
• Jeśli kiedykolwiek pominiesz lub powielisz wymagane wartości, wynik jest nieważny
• Twój program nie musi być niedeterministyczny w przypadku procesorów jednordzeniowych (choć w przypadku uznania)
• Twój program może używać zielonych wątków / włókien, które nie są w rzeczywistości zarządzane przez jądro systemu operacyjnego, jeśli nadal spełnia inne wymagania wyzwania, a system wątków jest częścią twojego języka lub standardowej biblioteki dla twojego języka
• Środowisko wykonawcze dla Twojego programu musi działać niezawodnie poniżej 5 sekund na nowoczesnym procesorze
• Nie można określić zmian w środowisku, które mają miejsce poza programem, takich jak zmiany oczekiwania lub zmiany ustawień; Twój program powinien przejść bez względu na to, czy uruchamia się 100 razy z powrotem do tyłu, czy z godziną między każdym uruchomieniem, czy 100 razy równolegle (prawdopodobnie pomogłoby to faktycznie ...)
• Do zadań możesz użyć koprocesora, takiego jak GPU lub Xeon Phi i własnego wewnętrznego mechanizmu planowania. Reguły mają do tego zastosowanie w taki sam sposób, jak dotyczą zielonych nici.
• Nie krępuj się sprowokować harmonogramu wszystkimi rodzajami snu, wydajności i innymi sztuczkami, o ile przestrzegasz zasad określonych w tym poście

Zablokowane operacje

Jedynym źródłem niedeterminizmu, z którego możesz korzystać, jest harmonogram, w którym harmonogram uruchamia wątki. Poniższa lista nie jest wyczerpująca, ma jedynie na celu przedstawienie przykładów rzeczy, których nie wolno ci robić, ponieważ dopuszczają inne źródła niedeterminizmu.

• Bezpośredni lub pośredni dostęp do dowolnego rodzaju PRNG lub sprzętu RNG (chyba że jest to nieodłączna część harmonogramu).
• Odczytywanie dowolnego rodzaju danych wejściowych (czas systemowy, system plików, sieć itp.)
• Odczytywanie identyfikatorów wątków lub identyfikatorów procesów
• Dostosowywanie harmonogramu systemu operacyjnego; musisz użyć standardowego harmonogramu systemu operacyjnego z głównego systemu operacyjnego
• Dostosowywanie harmonogramu zielonej nici / włókna jest również zabronione. Oznacza to, że jeśli piszesz język dla tego wyzwania, musisz używać wątków systemu operacyjnego.

Odpowiedź Walidacja

Najlepiej byłoby, gdyby odpowiedź działała we wszystkich popularnych systemach operacyjnych i nowoczesnych procesorach, a nagrody uznania byłyby proporcjonalne do zakresu wsparcia. Nie jest to jednak wymaganie związane z wyzwaniem. Odpowiedź musi co najmniej obsługiwać jeden nowoczesny procesor SMP i nowoczesny system operacyjny. Przetestuję wiodące odpowiedzi w zakresie mojej dostępności sprzętu.

• Jeśli twoja pozycja nie wygeneruje wymaganego wyjścia na i7 5960x z systemem Windows 10 v1607 x64, określ wymagane środowisko
• Jeśli jest to coś, co mogę łatwo odtworzyć za pomocą VMWare Workstation, podaj dokładne specyfikacje systemu operacyjnego i maszyny wirtualnej
• Jeśli nie można go wyprodukować w żadnym z tych warunków, należy zarejestrować jednoczesne przechwytywanie ekranu testu zgodnie z opisem w sekcji nagłówka oraz ręczne nagrywanie wideo ekranu za pomocą interakcji myszy i klawiatury (lub dowolnego schematu sterowania niestandardowego obliczenia urządzenie używa) wyraźnie widoczne i opublikuj oba filmy wraz z odpowiedzią oraz wyjaśnij, dlaczego to działa
• Alternatywnie, uzyskaj renomowanego długoletniego użytkownika (który nie jest tobą) z pasującym sprzętem, aby odtworzyć wynik i ręczyć za ciebie
• Jeśli Twój wpis jest w egzotycznym języku programowania, którego typowy programista nie zostanie skonfigurowany do kompilacji / jit / interpret, podaj instrukcje instalacji
• Jeśli wpis zależy od konkretnej wersji interpretera JVM / Python / innej, określ którą
• Jeśli zajmie Ci więcej niż 10 minut ciągłych przebiegów, aby uzyskać 10 udanych sekwencyjnych zestawów prób w moim teście, nie powiedzie się (więc nie pozwól, aby warunek powodzenia był dziwnym zjawiskiem, szczególnie jeśli jesteś blisko górnej granicy związany ze środowiskiem uruchomieniowym)

Perl 6 , 27 bajtów

await map {start .say},^100

Wyjaśnienie:

      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.

Mam nadzieję, że spełni to zadanie. (Jeśli nie, proszę dać mi znać).

Testowanie:

Skrypt powłoki, którego użyłem do przetestowania wystarczającego niedeterminizmu:

#!/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

Dla mnie to daje:

10 10 10 10 10 10 10 10 10 10 

Instrukcje instalacji:

Test uruchomiłem na najnowszym Rakudo Perl 6 na 64-bitowym Linuksie, ale myślę, że zadziała na innych platformach.

Strona pobierania Rakudo zawiera instrukcje konfiguracji. Skompilowałem mój z git w ten sposób:

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

Wypróbuj online:

Lub po prostu przetestuj online, korzystając z linku Wypróbuj online dostarczonego przez @ b2gills. Sprawdziłem kilka przebiegów i za każdym razem otrzymywałem inne zamówienie, ale nie miałem cierpliwości, aby uruchomić je 100 razy przez ten interfejs online.

bash, 32 28 bajtów

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

Uruchomiłem to 100 razy i uzyskałem 100 różnych wyników.

Edycja: Zapisano 4 bajty dzięki @DigitalTrauma.

PowerShell , 54 46 44 39 bajtów

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

Przepływy pracy programu PowerShell nie są obsługiwane w TIO, więc nie możesz go tam wypróbować. Powinien jednak świetnie działać na komputerze z systemem Windows 10 :)

Definiuje funkcję, pktóra po wywołaniu wyświetli listę liczb.

wyczucie czasu

Pojedynczy przebieg niezawodnie działa na moim komputerze w około 600 ms. 100 zdefiniowanych poniżej testów kończy się w niecałe 2 minuty.

Testowanie

Oto pełny kod do przetestowania:

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"
    }
}

Dane wyjściowe na moim komputerze:

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 w systemie Linux, 47 bajtów

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

To dało mi różne wyniki prawie za każdym razem, po kompilacji z gccwersją 4.9.2 (bez flag). W szczególności byłem na 64-bitowym Debianie 8.6 (wersja jądra 3.16.31).

Wyjaśnienie

Jeśli fork()zwraca zero (proces potomny), idrukowana jest wartość , a warunek pętli jest fałszywy, ponieważ printfzwróci wartość większą niż zero. W procesie nadrzędnym warunek pętli jest po prostu i--.