Como todos sabemos, os sistemas operacionais modernos têm agendadores de encadeamentos que podem escolher pedidos diferentes para agendar seus encadeamentos com base na lógica interna da qual seu código não tem acesso. Normalmente, você arquiteta seu código multithread para garantir que esse não determinismo imposto a você não afete significativamente sua saída.

O objetivo aqui é o oposto. Produza um programa que imprima os números inteiros no intervalo [0,99], mas em uma ordem que varia de execução para execução devido ao agendador de encadeamentos do SO.

Você deve obter "não-determinismo suficiente", definido como:

Em 10 conjuntos seqüenciais de 10 tentativas, seu programa deve produzir pelo menos 9 permutações exclusivas dentro de cada tentativa. Você pode ter um número razoável de conjuntos de testes com falha em ambos os lados dos 10 consecutivos que tiverem êxito.

Ou, dito de outra maneira, você precisa de 100 execuções do seu programa, onde cada bloco de 10 execuções possui no máximo duas execuções que produzem a mesma coisa.

Portanto, ocasionalmente, trocar 98 e 99 não será suficiente.

Este é um código-golfe , então a resposta que usa o menor número de bytes vence.

Minutiae

• Escreva sua saída em stdout, uma entrada por linha
• Se você alterar o formato com duas threads que intercalam gravações de caracteres em stdout (mesmo que ocasionalmente), resultando em números de três dígitos ou linhas vazias, seu resultado será inválido.
• A única exceção à regra acima é que você pode emitir uma única linha vazia após imprimir o último número necessário (de nada)
• Se você perder ou duplicar algum valor necessário, seu resultado será inválido.
• Seu programa não precisa ser não determinístico em um processador de núcleo único (apesar de parabéns, se for o caso)
• Seu programa pode usar linhas / fibras verdes que não são realmente gerenciadas pelo kernel do sistema operacional, se ele ainda atender aos outros requisitos do desafio e o sistema de encadeamento fizer parte do seu idioma ou da biblioteca padrão do seu idioma
• O tempo de execução do seu programa deve ser inferior a 5 segundos em um processador moderno
• Você não pode especificar alterações no ambiente que ocorram fora do seu programa, como esperas ou alterações nas configurações; seu programa deve passar se executado 100 vezes vezes consecutivas ou com uma hora entre cada execução ou 100ish vezes em paralelo (isso provavelmente ajudaria realmente ...)
• Você pode usar um coprocessador como uma GPU ou Xeon Phi e seu próprio mecanismo de agendamento interno para tarefas. As regras se aplicam a isso da mesma maneira que se aplicam às linhas verdes.
• Sinta-se à vontade para provocar o agendador com todos os tipos de sonecas, rendimentos e outros truques, desde que você obedeça às regras especificadas nesta postagem

Operações proibidas

A única fonte de não determinismo que você pode usar é quando o agendador agenda seus threads para execução. A lista a seguir não é exaustiva, destina-se apenas a fornecer exemplos de coisas que você não tem permissão para fazer, pois admitem outras fontes de não-determinismo.

• Acessar direta ou indiretamente qualquer tipo de capacidade de PRNG ou RNG de hardware (a menos que seja parte integrante do planejador).
• Leitura em qualquer tipo de entrada (hora do sistema, sistema de arquivos, rede, etc.)
• Lendo IDs de Threads ou Process IDs
• Customizando o agendador do SO; você deve usar um agendador padrão do sistema operacional a partir de um sistema operacional principal
• Também é proibido personalizar seu agendador de linha / fibra verde. Isso significa que, se você escrever um idioma para esse desafio, deverá usar os threads do SO.

Resposta Validação

De preferência, uma resposta funcionaria em todos os sistemas operacionais comuns e processadores modernos, com elogios concedidos proporcional à amplitude do suporte. No entanto, este não é um requisito do desafio. No mínimo, uma resposta deve suportar um processador SMP moderno e um SO moderno. Testarei as principais respostas na extensão da minha disponibilidade de hardware.

• Se sua entrada não produzir a saída necessária em um i7 5960x executando o Windows 10 v1607 x64, especifique o ambiente necessário
• Se for algo que eu possa reproduzir facilmente com o VMWare Workstation, forneça as especificações exatas de SO e VM
• Se não puder ser produzido em nenhuma dessas condições, grave uma captura de tela simultânea do teste, conforme descrito na seção do cabeçalho e uma gravação de vídeo portátil da sua tela com a interação do mouse e do teclado (ou qualquer esquema de controle que seu cálculo não seja padrão) uso do dispositivo) claramente visível e publique os dois vídeos junto com sua resposta e inclua uma explicação do motivo pelo qual ele funciona
• Como alternativa, obtenha um usuário de longa data respeitável (que não seja você) com o hardware correspondente para reproduzir o resultado e atestá-lo
• Se sua entrada estiver em uma linguagem de programação exótica em que um desenvolvedor típico não será configurado para compilar / jit / interpretar, forneça instruções de configuração
• Se sua entrada depender de uma versão específica do interpretador JVM / Python / outro, especifique qual
• Se você levar mais de 10 minutos de execuções consecutivas para obter seus 10 conjuntos de testes sequenciais bem-sucedidos em meus testes, você falhará (portanto, não permita que a condição de sucesso seja uma ocorrência esquisita, especialmente se você estiver próximo da parte superior). limite de tempo de execução)

Perl 6 , 27 bytes

await map {start .say},^100

Explicação:

      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.

Espero que isso satisfaça a tarefa. (Se não, por favor me avise).

Teste:

O script de shell que usei para testar o não determinismo suficiente:

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

Para mim, isso gera:

10 10 10 10 10 10 10 10 10 10 

Instruções de configuração:

Fiz o teste com um Rakudo Perl 6 atualizado no Linux de 64 bits, mas acho que ele funcionará em outras plataformas.

A página de download do Rakudo possui instruções de configuração. Eu compilei o meu do git assim:

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

Experimente online:

Ou apenas teste-o on-line, usando o link Try It Online, fornecido por @ b2gills. Verifiquei algumas execuções e recebi um pedido diferente a cada vez, mas não tive a paciência de executá-lo 100 vezes por meio dessa interface online.

Bash, 32 28 bytes

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

Corri isso 100 vezes e obtive 100 resultados diferentes.

Editar: salvou 4 bytes graças a @DigitalTrauma.

PowerShell , 54 46 44 39 bytes

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

Os fluxos de trabalho do PowerShell não são suportados no TIO, portanto você não pode experimentá-lo lá. No entanto, deve funcionar muito bem na sua máquina Windows 10 :)

Define uma função pque produzirá a lista de números quando chamada.

Cronometragem

Uma única execução é executada de forma confiável em cerca de 600ms na minha máquina. Os 100 testes definidos abaixo terminam em menos de 2 minutos.

Teste

Aqui está o código completo para testá-lo:

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

Saída na minha máquina:

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 no Linux, 47 bytes

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

Isso me deu resultados diferentes praticamente todas as vezes, tendo sido compilado com gcc(sem sinalizadores) versão 4.9.2. Especificamente, eu estava no Debian 8.6 de 64 bits (versão 3.16.31 do kernel).

Explicação

Se o fork()retorno zero (processo filho), o valor de ié impresso e a condição do loop é falsa, porque printfretornará um valor maior que zero. No processo pai, a condição do loop é justa i--.