Quão alto você pode ir? (Um desafio de codificação + algoritmos)

34

Agora que todos desenvolveram sua (muitas vezes incrível) experiência em codificação de baixo nível para Quão lento é realmente o Python? (Ou qual a velocidade da sua linguagem?) E Qual a velocidade do Python (parte II)? é hora de um desafio que também aumentará sua capacidade de melhorar um algoritmo.

O código a seguir calcula uma lista de comprimento 9. A posição ina lista conta o número de vezes que iforam encontrados pelo menos zeros consecutivos ao calcular os produtos internos entre Fe S. Para fazer isso exatamente, ele itera sobre todas as listas possíveis Fde comprimento ne listas Sde comprimento n+m-1.

#!/usr/bin/python
import itertools
import operator

n=8
m=n+1
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n+m-1):
    for F in itertools.product([-1,1], repeat = n):
        i = 0
        while (i<m and sum(map(operator.mul, F, S[i:i+n])) == 0):
            leadingzerocounts[i] +=1
            i+=1
print leadingzerocounts

A saída é

[4587520, 1254400, 347648, 95488, 27264, 9536, 4512, 2128, 1064]

Se você aumentar n para 10,12,14,16,18,20 usando esse código, muito rapidamente se tornará muito lento.

Regras

  • O desafio é fornecer a saída correta para o maior número possível de n. Apenas valores pares de n são relevantes.
  • Se houver um empate, a vitória vai para o código mais rápido da minha máquina para o maior n.
  • Reservo-me o direito de não testar o código que leva mais de 10 minutos.
  • Você pode alterar o algoritmo da maneira que desejar, desde que ele produza a saída correta. Na verdade, você terá que alterar o algoritmo para fazer um progresso decente em direção à vitória.
  • O vencedor será premiado uma semana a partir do momento em que a pergunta foi feita.
  • A recompensa será concedida no vencimento, um pouco depois do vencimento do vencedor.

Minha máquina Os horários serão executados na minha máquina. Esta é uma instalação padrão do ubuntu em um processador AMD FX-8350 de oito núcleos. Isso também significa que eu preciso poder executar seu código. Como conseqüência, use apenas software livre facilmente disponível e inclua instruções completas sobre como compilar e executar seu código.

Status .

  • C . n = 12 em 49 segundos por @Fors
  • Java . n = 16 em 3:07 por @PeterTaylor
  • C ++ . n = 16 em 2:21 por @ilmale
  • Rpython . n = 22 em 3:11 por @primo
  • Java . n = 22 em 6:56 por @PeterTaylor
  • Nimrod . n = 24 em 9:28 segundos por @ReimerBehrends

O vencedor foi Reimer Behrends com uma entrada em Nimrod!

Como verificação, a saída para n = 22 deve ser [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680].


A competição terminou agora ... Oferecerei 200 pontos por cada envio que aumentar n em 2 (dentro de 10 minutos no meu computador) até que eu fique sem pontos. Esta oferta está aberta para sempre .

Comunidade
fonte
1
"Eu me reservo o direito de não testar o código que leva mais de alguns minutos." > Você deve especificar um horário exato em sua máquina, caso contrário, esta questão não terá um critério de ganho objetivo.
usar o seguinte comando
14
Eu amo esses desafios de "aumentar minha velocidade". Se você estiver construindo um produto comercial com eles, terá um produto rápido e também um gênio do mal .
Rainbolt
1
Talvez um título mais informativo chame a atenção para isso?
TheDoctor
8
Se continuarmos fazendo esse tipo de desafio, acho que devemos pelo menos tentar resolver um problema diferente para mantê-lo interessante (não uma variação no mesmo problema com especificações extras).
GrovesNL
2
@ Claudiu, sua CPU possui 8 núcleos físicos, mas as unidades de busca / decodificação e FPU são compartilhadas entre os núcleos. Portanto, quando o gargalo está em uma dessas áreas, ele se comporta mais como um quadcore. Abuse a lógica de números inteiros e evite códigos grandes, e é mais como um núcleo de 8 núcleos.
Stefan

Respostas:

20

Nimrod (N = 22)

import math, locks

const
  N = 20
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, int]
  ComputeThread = TThread[int]

var
  leadingZeros: ZeroCounter
  lock: TLock
  innerProductTable: array[0..FMax, int8]

proc initInnerProductTable =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)

initInnerProductTable()

proc zeroInnerProduct(i: int): bool =
  innerProductTable[i] == 0

proc search2(lz: var ZeroCounter, s, f, i: int) =
  if zeroInnerProduct(s xor f) and i < M:
    lz[i] += 1 shl (M - i - 1)
    search2(lz, (s shr 1) + 0, f, i+1)
    search2(lz, (s shr 1) + SStep, f, i+1)

when defined(gcc):
  const
    unrollDepth = 1
else:
  const
    unrollDepth = 4

template search(lz: var ZeroCounter, s, f, i: int) =
  when i < unrollDepth:
    if zeroInnerProduct(s xor f) and i < M:
      lz[i] += 1 shl (M - i - 1)
      search(lz, (s shr 1) + 0, f, i+1)
      search(lz, (s shr 1) + SStep, f, i+1)
  else:
    search2(lz, s, f, i)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for f in countup(base, FMax div 2, numThreads):
    for s in 0..FMax:
      search(lz, s, f, 0)
  acquire(lock)
  for i in 0..M-1:
    leadingZeros[i] += lz[i]*2
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)

Ajuntar com

nimrod cc --threads:on -d:release count.nim

(O Nimrod pode ser baixado aqui .)

Isso é executado no tempo alocado para n = 20 (e para n = 18 ao usar apenas um único encadeamento, levando cerca de 2 minutos no último caso).

O algoritmo usa uma pesquisa recursiva, removendo a árvore de pesquisa sempre que um produto interno diferente de zero é encontrado. Também cortamos o espaço de pesquisa pela metade, observando que, para qualquer par de vetores (F, -F), precisamos considerar apenas um porque o outro produz exatamente os mesmos conjuntos de produtos internos (negando Stambém).

A implementação usa os recursos de metaprogramação do Nimrod para desenrolar / alinhar os primeiros níveis da pesquisa recursiva. Isso economiza um pouco de tempo ao usar o gcc 4.8 e 4.9 como o back-end do Nimrod e uma quantidade razoável de clang.

O espaço de pesquisa poderia ser ainda mais podado, observando que só precisamos considerar valores de S que diferem em um número par das primeiras posições N da escolha de F. de N, dado que o corpo do loop é completamente ignorado nesses casos.

Tabular onde o produto interno é zero parece ser mais rápido do que usar qualquer funcionalidade de contagem de bits no loop. Aparentemente, acessar a tabela tem uma boa localidade.

Parece que o problema deve ser passível de programação dinâmica, considerando como a pesquisa recursiva funciona, mas não há uma maneira aparente de fazer isso com uma quantidade razoável de memória.

Exemplo de saídas:

N = 16:

@[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]

N = 18:

@[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

N = 20:

@[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

Para fins de comparação do algoritmo com outras implementações, N = 16 leva cerca de 7,9 segundos na minha máquina ao usar um único encadeamento e 2,3 segundos ao usar quatro núcleos.

N = 22 leva cerca de 15 minutos em uma máquina de 64 núcleos com o gcc 4.4.6, como o back-end do Nimrod e transborda números inteiros de 64 bits leadingZeros[0](possivelmente os não assinados, que ainda não viram).


Atualização: Encontrei espaço para mais algumas melhorias. Primeiro, para um determinado valor de F, podemos enumerar as 16 primeiras entradas dos Svetores correspondentes com precisão, porque elas devem diferir exatamente em N/2locais. Portanto, pré-calculamos uma lista de vetores de bits de tamanho Ncom N/2bits definidos e os usamos para derivar a parte inicial de Sfrom F.

Segundo, podemos melhorar a pesquisa recursiva, observando que sempre sabemos o valor de F[N](como o MSB é zero na representação de bits). Isso nos permite prever com precisão em qual ramo recorreremos do produto interno. Embora isso nos permita transformar toda a pesquisa em um loop recursivo, isso acaba atrapalhando bastante a previsão do ramo, por isso mantemos os níveis mais altos em sua forma original. Ainda economizamos algum tempo, principalmente reduzindo a quantidade de ramificações que estamos realizando.

Para alguma limpeza, o código agora está usando números inteiros não assinados e os corrige em 64 bits (caso alguém queira executar isso em uma arquitetura de 32 bits).

A aceleração geral está entre um fator de x3 e x4. N = 22 ainda precisa de mais de oito núcleos para rodar em menos de 10 minutos, mas em uma máquina de 64 núcleos agora é de cerca de quatro minutos (com numThreadsaumento de acordo). Não acho que haja muito mais espaço para melhorias sem um algoritmo diferente.

N = 22:

@[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

Atualizado novamente, fazendo uso de outras reduções possíveis no espaço de pesquisa. É executado em cerca de 9:49 minutos para N = 22 na minha máquina quadcore.

Atualização final (eu acho). Melhores classes de equivalência para opções de F, reduzindo o tempo de execução de N = 22 para 3:19 minutos e 57 segundos (editar: eu acidentalmente executei isso com apenas um thread) na minha máquina.

Essa alteração utiliza o fato de que um par de vetores produz os mesmos zeros à esquerda se um puder ser transformado no outro girando-o. Infelizmente, uma otimização de baixo nível bastante crítica exige que o bit superior de F na representação de bits seja sempre o mesmo e, ao usar essa equivalência, reduziu bastante o espaço de pesquisa e reduziu o tempo de execução em cerca de um quarto, usando um espaço de estado diferente redução em F, a sobrecarga de eliminar mais a otimização de baixo nível do que compensá-la. No entanto, verifica-se que esse problema pode ser eliminado considerando-se também o fato de que F que são inversos um do outro também são equivalentes. Embora isso tenha aumentado um pouco a complexidade do cálculo das classes de equivalência, ele também me permitiu manter a otimização de baixo nível mencionada, levando a uma aceleração de cerca de x3.

Mais uma atualização para oferecer suporte a números inteiros de 128 bits para os dados acumulados. Para compilar com 128 bit inteiros, você vai precisar longint.nimde aqui e para compilar com -d:use128bit. N = 24 ainda leva mais de 10 minutos, mas incluí o resultado abaixo para os interessados.

N = 24:

@[761152247121980686336, 122682715414070296576, 19793870419291799552, 3193295704340561920, 515628872377565184, 83289931274780672, 13484616786640896, 2191103969198080, 359662314586112, 60521536552960, 10893677035520, 2293940617216, 631498735616, 230983794688, 102068682752, 48748969984, 23993655296, 11932487680, 5955725312, 2975736832, 1487591936, 743737600, 371864192, 185931328, 92965664]

import math, locks, unsigned

when defined(use128bit):
  import longint
else:
  type int128 = uint64 # Fallback on unsupported architectures
  template toInt128(x: expr): expr = uint64(x)

const
  N = 22
  M = N + 1
  FSize = (1 shl N)
  FMax = FSize - 1
  SStep = 1 shl (N-1)
  numThreads = 16

type
  ZeroCounter = array[0..M-1, uint64]
  ZeroCounterLong = array[0..M-1, int128]
  ComputeThread = TThread[int]
  Pair = tuple[value, weight: int32]

var
  leadingZeros: ZeroCounterLong
  lock: TLock
  innerProductTable: array[0..FMax, int8]
  zeroInnerProductList = newSeq[int32]()
  equiv: array[0..FMax, int32]
  fTable = newSeq[Pair]()

proc initInnerProductTables =
  for i in 0..FMax:
    innerProductTable[i] = int8(countBits32(int32(i)) - N div 2)
    if innerProductTable[i] == 0:
      if (i and 1) == 0:
        add(zeroInnerProductList, int32(i))

initInnerProductTables()

proc ror1(x: int): int {.inline.} =
  ((x shr 1) or (x shl (N-1))) and FMax

proc initEquivClasses =
  add(fTable, (0'i32, 1'i32))
  for i in 1..FMax:
    var r = i
    var found = false
    block loop:
      for j in 0..N-1:
        for m in [0, FMax]:
          if equiv[r xor m] != 0:
            fTable[equiv[r xor m]-1].weight += 1
            found = true
            break loop
        r = ror1(r)
    if not found:
      equiv[i] = int32(len(fTable)+1)
      add(fTable, (int32(i), 1'i32))

initEquivClasses()

when defined(gcc):
  const unrollDepth = 4
else:
  const unrollDepth = 4

proc search2(lz: var ZeroCounter, s0, f, w: int) =
  var s = s0
  for i in unrollDepth..M-1:
    lz[i] = lz[i] + uint64(w)
    s = s shr 1
    case innerProductTable[s xor f]
    of 0:
      # s = s + 0
    of -1:
      s = s + SStep
    else:
      return

template search(lz: var ZeroCounter, s, f, w, i: int) =
  when i < unrollDepth:
    lz[i] = lz[i] + uint64(w)
    if i < M-1:
      let s2 = s shr 1
      case innerProductTable[s2 xor f]
      of 0:
        search(lz, s2 + 0, f, w, i+1)
      of -1:
        search(lz, s2 + SStep, f, w, i+1)
      else:
        discard
  else:
    search2(lz, s, f, w)

proc worker(base: int) {.thread.} =
  var lz: ZeroCounter
  for fi in countup(base, len(fTable)-1, numThreads):
    let (fp, w) = fTable[fi]
    let f = if (fp and (FSize div 2)) == 0: fp else: fp xor FMax
    for sp in zeroInnerProductList:
      let s = f xor sp
      search(lz, s, f, w, 0)
  acquire(lock)
  for i in 0..M-1:
    let t = lz[i].toInt128 shl (M-i).toInt128
    leadingZeros[i] = leadingZeros[i] + t
  release(lock)

proc main =
  var threads: array[numThreads, ComputeThread]
  for i in 0 .. numThreads-1:
    createThread(threads[i], worker, i)
  for i in 0 .. numThreads-1:
    joinThread(threads[i])

initLock(lock)
main()
echo(@leadingZeros)
Reimer Behrends
fonte
O resultado com N = 22 é 12410090985684467712, que leva 63,42 bits e, portanto, se encaixa em um de 64 bits não assinado.
Stefan
2
Você definitivamente elevou a fasquia de maneira impressionante.
1
É bom ver alguém usando Nimrod. :)
cjfaure
@ Stefan Talvez sua magia de codificação possa obter esse método abaixo de 10 minutos para N = 22?
Eu tentei N = 22, que terminou depois de algumas horas. No entanto, dá-me [-6036653088025083904, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680], que parece ser um erro de estouro. Não conheço nimrod, mas é possível usar ints não assinados para resolver isso?
11

Java ( n=22?)

Penso que a maioria das respostas é melhor do que n=16usar uma abordagem semelhante a essa, embora elas diferem nas simetrias que exploram e na maneira como dividem a tarefa entre os threads.

Os vetores definidos na pergunta podem ser substituídos por cadeias de bits, e o produto interno com XOR na janela sobreposta e verificando se há exatamente os n/2bits definidos (e, portanto, os n/2bits limpos). Existem n! / ((n/2)!)(coeficiente binomial central) cadeias de nbits com n/2bits configurados (que eu chamo de cadeias balanceadas ); portanto, para qualquer dado dado, Fexistem muitas janelas Sque dão um produto interno nulo. Além disso, a ação de deslizar Sao longo de uma e verificar se ainda podemos encontrar um bit de entrada que dê um produto interno zero corresponde a procurar uma aresta em um gráfico cujos nós são as janelas e cujas arestas vinculam um nó ua um nó vcujos primeiros n-1bits são os últimosn-1pedaços de u.

Por exemplo, com n=6e F=001001obtemos este gráfico:

Gráfico para F = 001001

e para F=001011obtermos este gráfico:

Gráfico para F = 001011

Então precisamos contar para cada ia partir 0de nquantos caminhos de comprimento ihá, somando sobre os gráficos para cada F. Eu acho que a maioria de nós está usando a pesquisa profunda.

Observe que os gráficos são escassos: é fácil provar que cada nó possui um grau máximo de 1 e um grau máximo de um. Isso também significa que as únicas estruturas possíveis são cadeias simples e loops simples. Isso simplifica um pouco o DFS.

Exploro algumas simetrias: as seqüências balanceadas são fechadas sob bits inversos (a ~operação em vários idiomas da família ALGOL) e sob rotação de bits, para que possamos agrupar valores Frelacionados por essas operações e fazer apenas o DFS uma vez.

public class CodeGolf26459v8D implements Runnable {
    private static final int NUM_THREADS = 8;

    public static void main(String[] args) {
        v8D(22);
    }

    private static void v8D(int n) {
        int[] bk = new int[1 << n];
        int off = 0;
        for (int i = 0; i < bk.length; i++) {
            bk[i] = Integer.bitCount(i) == n/2 ? off++ : -1;
        }

        int[] fwd = new int[off];
        for (int i = 0; i < bk.length; i++) {
            if (bk[i] >= 0) fwd[bk[i]] = i;
        }

        CodeGolf26459v8D[] runners = new CodeGolf26459v8D[NUM_THREADS];
        Thread[] threads = new Thread[runners.length];
        for (int i = 0; i < runners.length; i++) {
            runners[i] = new CodeGolf26459v8D(n, i, runners.length, bk, fwd);
            threads[i] = new Thread(runners[i]);
            threads[i].start();
        }

        try {
            for (int i = 0; i < threads.length; i++) threads[i].join();
        }
        catch (InterruptedException ie) {
            throw new RuntimeException("This shouldn't be reachable", ie);
        }

        long surviving = ((long)fwd.length) << (n - 1);
        for (int i = 0; i <= n; i++) {
            for (CodeGolf26459v8D runner : runners) surviving -= runner.survival[i];
            System.out.print(i == 0 ? "[" : ", ");
            java.math.BigInteger result = new java.math.BigInteger(Long.toString(surviving));
            System.out.print(result.shiftLeft(n + 1 - i));
        }
        System.out.println("]");
    }

    public final int n;
    protected final int id;
    protected final int numRunners;
    private final int[] bk;
    private final int[] fwd;

    public long[] survival;

    public CodeGolf26459v8D(int n, int id, int numRunners, int[] bk, int[] fwd) {
        this.n = n;
        this.id = id;
        this.numRunners = numRunners;

        this.bk = bk;
        this.fwd = fwd;
    }

    private int dfs2(int[] graphShape, int flip, int i) {
        if (graphShape[i] != 0) return graphShape[i];

        int succ = flip ^ (fwd[i] << 1);
        if (succ >= bk.length) succ ^= bk.length + 1;

        int j = bk[succ];
        if (j == -1) return graphShape[i] = 1;

        graphShape[i] = n + 1; // To detect cycles
        return graphShape[i] = dfs2(graphShape, flip, j) + 1;
    }

    @Override
    public void run() {
        int n = this.n;
        int[] bk = this.bk;
        int[] fwd = this.fwd;

        // NB The initial count is approx 2^(2n - 1.33 - 0.5 lg n)
        // For n=18 we overflow 32-bit
        // 64-bit is good up to n=32.
        long[] survival = new long[n + 1];
        boolean[] visited = new boolean[1 << (n - 1)];
        int th = 0;
        for (int f = 0; f < visited.length; f++) {
            if (visited[f]) continue;

            int m = 1, g = f;
            while (true) {
                visited[g] = true;
                int ng = g << 1;
                if ((ng >> (n - 1)) != 0) ng ^= (1 << n) - 1;
                if (ng == f) break;
                m++;
                g = ng;
            }

            if (th++ % numRunners != id) continue;

            int[] graphShape = new int[fwd.length];
            int flip = (f << 1) ^ f;
            for (int i = 0; i < graphShape.length; i++) {
                int life = dfs2(graphShape, flip, i);
                if (life <= n) survival[life] += m;
            }
        }

        this.survival = survival;
    }
}

No meu Core 2 de 2,5 GHz, recebo

# n=18
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]

real    0m3.131s
user    0m10.133s
sys     0m0.380s

# n=20
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]

real    1m8.706s
user    4m20.980s
sys     0m0.564s

# n=22
$ javac CodeGolf26459v8D.java && time java CodeGolf26459v8D
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]

real    20m10.654s
user    76m53.880s
sys     0m6.852s

Como o computador de Lembik possui 8 núcleos e executou meu programa de thread único anterior duas vezes mais rápido que o meu, estou otimista de que seja executado n=22em menos de 8 minutos.

Peter Taylor
fonte
7:17! Muito agradável. Você se importaria de explicar um pouco mais o seu método?
6

C

É basicamente apenas uma implementação levemente otimizada do algoritmo na questão. Ele pode gerenciar n=12dentro do prazo.

#include <stdio.h>
#include <inttypes.h>

#define n 12
#define m (n + 1)

int main() {
    int i;
    uint64_t S, F, o[m] = {0};
    for (S = 0; S < (1LLU << (n + m - 1)); S += 2)
        for (F = 0; F < (1 << (n - 1)); F++)
            for (i = 0; i < m; i++)
                if (__builtin_popcount(((S >> i) & ((1 << n) - 1)) ^ F) == n >> 1)
                    o[i] += 4;
                else
                    break;
    for (i = 0; i < m; i++)
        printf("%" PRIu64 " ", o[i]);
    return 0;
}

Execução de teste para n=12, incluindo compilação:

$ clang -O3 -march=native -fstrict-aliasing -ftree-vectorize -Wall fast.c
$ time ./a.out 
15502147584 3497066496 792854528 179535872 41181184 9826304 2603008 883712 381952 177920 85504 42560 21280 
real    0m53.266s
user    0m53.042s
sys     0m0.068s
$

Comentário: Acabei de ligar meu cérebro e usei algumas combinatórias simples para calcular que o primeiro valor sempre será n! / ((n / 2)!)^2 * 2^(n + m - 1). Parece-me que deve haver uma solução completamente algébrica para esse problema.

Para s
fonte
Recebo muitos avisos ao compilar isso. Tente gcc -Wall -Wextra Fors.c -o Fors
Havia algumas variáveis ​​não utilizadas esquecidas de uma iteração anterior, mas eu as removi, pelo menos alguns avisos deveriam ter desaparecido. Não tenho o GCC disponível no momento (apenas Clang) e o Clang não me dá nenhum aviso no momento (depois de remover as variáveis ​​não utilizadas). E como Clang geralmente é mais rigoroso quando se trata de avisos, devo dizer que estou um pouco surpreso que você tenha recebido algum aviso.
Fors
Ele reclama de Fors.c: 13: 17: warning: sugere parênteses em torno de '-' no operando de '&' [-Wparentheses] (duas vezes) e também em aviso: format '% llu' espera argumento do tipo 'long long unsigned long int ', mas o argumento 2 tem o tipo' uint64_t '[-Wformat =]. Na verdade clang reclama da declaração printf demais para mim,
Com as alterações mais recentes, o GCC não deve emitir nenhuma mensagem de aviso.
Fors
Ele ainda reclama de Fors.c: 13: 49: aviso: sugira parênteses em torno da aritmética no operando de '^' [-Wparentheses] Mas em piores notícias ... leva mais de 10 minutos na minha máquina.
5

Java, n=16

Para qualquer valor dado de, Fexistem \binom{n}{n/2}vetores que possuem um produto interno nulo. Assim, podemos construir um gráfico cujos vértices são os vetores correspondentes e cujas bordas correspondem à mudança de S, e então precisamos contar os caminhos de comprimento até no gráfico.

Eu não tentei microoptimizar isso substituindo condicionais por operações bit a bit, mas cada incremento duplo de naumenta o tempo de execução em cerca de 16 vezes, para que isso não faça diferença suficiente, a menos que eu esteja bem próximo do limite. Na minha máquina, não estou.

public class CodeGolf26459 {

    public static void main(String[] args) {
        v3(16);
    }

    // Order of 2^(2n-1) * n ops
    private static void v3(int n) {
        long[] counts = new long[n+1];
        int mask = (1 << n) - 1;
        for (int f = 0; f < (1 << (n-1)); f++) {
            // Find adjacencies
            long[] subcounts = new long[1 << n];
            for (int g = 0; g < (1 << n); g++) {
                subcounts[g] = Integer.bitCount(f ^ g) == n/2 ? 2 : -1;
            }

            for (int round = 0; round <= n; round++) {
                long count = 0;
                // Extend one bit.
                long[] next = new long[1 << n];
                for (int i = 0; i < (1 << n); i++) {
                    long s = subcounts[i];
                    if (s == -1) next[i] = -1;
                    else {
                        count += s;
                        int j = (i << 1) & mask;
                        if (subcounts[j] >= 0) next[j] += s;
                        if (subcounts[j + 1] >= 0) next[j + 1] += s;
                    }
                }
                counts[round] += count << (n - round);
                subcounts = next;
            }
        }

        System.out.print("[");
        for (long count : counts) System.out.print(count+", ");
        System.out.println("]");
    }
}

No meu Core 2 de 2,5 GHz, recebo

$ javac CodeGolf26459.java && time java -server CodeGolf26459 
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600, ]

real    6m2.663s
user    6m4.631s
sys     0m1.580s
Peter Taylor
fonte
Pegando carona desde que eu não quero implementar minha própria solução agora. Cada vértice tem no máximo um sucessor, então você realmente não precisa da matriz. Para iterar eficientemente sobre combinações de fe vértices iniciais, itere sobre todos f_xor_gcom os n/2bits definidos exatamente . Para cada um deles, itere sobre todos fe tome g = f ^ f_xor_g.
David Eisenstat
@ David, eu sei, e minha versão 7 n = 18 em um minuto no meu netbook Atom, mas não posso publicá-lo até voltar das férias.
Peter Taylor
4

RPython, N = 22 ~ 3: 23

Multiencadeado, usando uma descida recursiva sem pilha. O programa aceita dois argumentos de linha de comando: N e o número de threads de trabalho.

from time import sleep

from rpython.rlib.rthread import start_new_thread, allocate_lock
from rpython.rlib.rarithmetic import r_int64, build_int, widen
from rpython.rlib.rbigint import rbigint

r_int8 = build_int('r_char', True, 8)

class ThreadEnv:
  __slots__ = ['n', 'counts', 'num_threads',
               'v_range', 'v_num', 'running', 'lock']

  def __init__(self):
    self.n = 0
    self.counts = [rbigint.fromint(0)]
    self.num_threads = 0
    self.v_range = [0]
    self.v_num = 0
    self.running = 0
    self.lock = None

env = ThreadEnv()

bt_bits = 12
bt_mask = (1<<bt_bits)-1
# computed compile time
bit_table = [r_int8(0)]
for i in xrange(1,1<<bt_bits):
  bit_table += [((i&1)<<1) + bit_table[i>>1]]

def main(argv):
  argc = len(argv)
  if argc < 2 or argc > 3:
    print 'Usage: %s N [NUM_THREADS=2]'%argv[0]
    return 1

  if argc == 3:
    env.num_threads = int(argv[2])
  else:
    env.num_threads = 2

  env.n = int(argv[1])
  env.counts = [rbigint.fromint(0)]*env.n
  env.lock = allocate_lock()

  v_range = []
  v_max = 1<<(env.n-1)
  v_num = 0
  v = (1<<(env.n>>1))-1
  while v < v_max:
    v_num += 1
    v_range += [v]
    if v&1:
      # special case odd v
      s = (v+1)&-v
      v ^= s|(s>>1)
    else:
      s = v&-v
      r = v+s
      # s is at least 2, skip two iterations
      i = 3
      s >>= 2
      while s:
        i += 1
        s >>= 1
      v = r|((v^r)>>i)
  env.v_range = v_range
  env.v_num = v_num

  for i in xrange(env.num_threads-1):
    start_new_thread(run,())

  # use the main process as a worker
  run()

  # wait for any laggers
  while env.running:
    sleep(0.05)

  result = []
  for i in range(env.n):
    result += [env.counts[i].lshift(env.n-i+3).str()]
  result += [env.counts[env.n-1].lshift(3).str()]
  print result
  return 0

def run():
  with env.lock:
    v_start = env.running
    env.running += 1

  n = env.n
  counts = [r_int64(0)]*n
  mask = (1<<n)-1
  v_range = env.v_range
  v_num = env.v_num
  z_count = 1<<(n-2)

  for i in xrange(v_start, v_num, env.num_threads):
    v = v_range[i]
    counts[0] += z_count
    counts[1] += v_num
    r = v^(v<<1)
    for w in v_range:
      # unroll counts[2] for speed
      # ideally, we could loop over x directly,
      # rather than over all v, only to throw the majority away
      # there's a 2x-3x speed improvement to be had here...
      x = w^r
      if widen(bit_table[x>>bt_bits]) + widen(bit_table[x&bt_mask]) == n:
        counts[2] += 1
        x, y = v, x
        o, k = 2, 3
        while k < n:
          # x = F ^ S
          # y = F ^ (S<<1)
          o = k
          z = (((x^y)<<1)^y)&mask
          # z is now F ^ (S<<2), possibly xor 1
          # what S and F actually are is of no consequence

          # the compiler hint `widen` let's the translator know
          # to store the result as a native int, rather than a signed char
          bt_high = widen(bit_table[z>>bt_bits])
          if bt_high + widen(bit_table[z&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z
            k += 1
          elif bt_high + widen(bit_table[(z^1)&bt_mask]) == n:
            counts[k] += 1
            x, y = y, z^1
            k += 1
          else: k = n

  with env.lock:
    for i in xrange(n):
      env.counts[i] = env.counts[i].add(rbigint.fromrarith_int(counts[i]))
    env.running -= 1

def target(*args):
  return main, None

Compilar

Crie um clone local do repositório PyPy usando mercurial, git ou o que você preferir. Digite o seguinte encantamento (assumindo que o script acima tenha o nome convolution-high.py):

$ pypy %PYPY_REPO%/rpython/bin/rpython --thread convolution-high.py

onde %PYPY_REPO%representa uma variável de ambiente apontando para o repositório que você acabou de clonar. A compilação leva cerca de um minuto.


Exemplo de tempos

N = 16, 4 threads:

$ timeit convolution-high-c 16 4
[55276229099520, 10855179878400, 2137070108672, 420578918400, 83074121728, 16540581888, 3394347008, 739659776, 183838720, 57447424, 23398912, 10749184, 5223040, 2584896, 1291424, 645200, 322600]
Elapsed Time:     0:00:00.109
Process Time:     0:00:00.390

N = 18, 4 threads:

$ timeit convolution-high-c 18 4
[3341140958904320, 619683355033600, 115151552380928, 21392898654208, 3982886961152, 744128512000, 141108051968, 27588886528, 5800263680, 1408761856, 438001664, 174358528, 78848000, 38050816, 18762752, 9346816, 4666496, 2333248, 1166624]
Elapsed Time:     0:00:01.250
Process Time:     0:00:04.937

N = 20, 4 threads:

$ timeit convolution-high-c 20 4
[203141370301382656, 35792910586740736, 6316057966936064, 1114358247587840, 196906665902080, 34848574013440, 6211866460160, 1125329141760, 213330821120, 44175523840, 11014471680, 3520839680, 1431592960, 655872000, 317675520, 156820480, 78077440, 39005440, 19501440, 9750080, 4875040]
Elapsed Time:     0:00:15.531
Process Time:     0:01:01.328

N = 22, 4 threads:

$ timeit convolution-high-c 22 4
[12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680]
Elapsed Time:     0:03:23.156
Process Time:     0:13:25.437
primo
fonte
9:26. Bem-vindo ao 22 tripulantes :)
Não sei por que, mas sua nova versão não é mais rápida para mim. Ainda por volta das 9h30, quando eu tiver tempo ./primo-c 22 8.
@ Lembik que faria sentido se a divisão fosse tão rápida, em média, quanto 3 turnos à direita (3 = Soma {(n + 1) / (2 ^ n)}, n = 1..infty). Para arquiteturas certian, suponho que possa ser o caso, mas na divisão de minas é notavelmente mais lenta. Obrigado por tomar o tempo para testá-lo :)
primo
3

Python 3.3, N = 20, 3.5min

Isenção de responsabilidade: minha intenção não é postar isso como minha própria resposta, pois o algoritmo que estou usando é apenas uma porta sem vergonha da solução RPython do primo . Meu objetivo aqui é apenas mostrar o que você pode fazer em Python se você combinar a mágica dos módulos Numpy e Numba .

Numba explicou resumidamente:

O Numba é um compilador especializado just-in-time que compila código Python e NumPy anotado no LLVM (através de decoradores). http://numba.pydata.org/

Atualização 1 : notei que, depois de lançar os números, podemos simplesmente pular alguns deles completamente. Então agora maxf torna-se (1 << n) // 2 e maxs torna-se maxf 2 **. Isso irá acelerar bastante o processo. n = 16 agora leva apenas ~ 48s (abaixo de 4,5min). Eu também tenho uma outra idéia que vou tentar e ver se consigo fazê-lo um pouco mais rápido.

Atualização 2: algoritmo alterado (solução do primo). Embora minha porta ainda não suporte multithreading, é bastante simples de adicionar. É ainda possível liberar o CPython GIL usando Numba e ctypes. Esta solução, no entanto, também é executada muito rapidamente em núcleo único!

import numpy as np
import numba as nb

bt_bits = 11
bt_mask = (1 << bt_bits) - 1
bit_table = np.zeros(1 << bt_bits, np.int32)

for i in range(0, 1 << bt_bits):
    bit_table[i] = ((i & 1) << 1) + bit_table[i >> 1]

@nb.njit("void(int32, int32, int32, int32, int64[:], int64[:])")
def run(n, m, start, re, counts, result):
    mask = (1 << n) - 1

    v_max = (1 << n) // 2
    rr = v_max // 2

    v = (1 << (n >> 1)) - 1
    while v < v_max:
        s = start

        while s < rr:
            f = v ^ s
            counts[0] += 8
            t = s << 1
            o, j = 0, 1

            while o < j and j < m:
                o = j
                w = (t ^ f) & mask
                bt_high = bit_table[w >> bt_bits]

                if bt_high + bit_table[w & bt_mask] == n:
                    counts[j] += 8
                    t <<= 1
                    j += 1
                elif bt_high + bit_table[(w ^ 1) & bt_mask] == n:
                    counts[j] += 8
                    t = (t | 1) << 1
                    j += 1
                    s += re

            s = v & -v
            r = v + s
            o = v ^ r
            o = (o >> 2) // s
            v = r | o

    for e in range(m):
        result[e] += counts[e] << (n - e)

E finalmente:

if __name__ == "__main__":
    n = 20
    m = n + 1

    result = np.zeros(m, np.int64)
    counts = np.zeros(m, np.int64)

    s1 = time.time() * 1000
    run(n, m, 0, 1, counts, result)
    s2 = time.time() * 1000

    print(result)
    print("{0}ms".format(s2 - s1))

Isso funciona na minha máquina em 212688ms ou ~ 3,5min.

Anna Jokela
fonte
Obrigado. Agora, que tal n = 18? :)
Já se passaram quase 20 minutos desde que iniciei o programa usando n = 18. Acho que é seguro dizer que o Python não pode resolver isso, mesmo com o Numba dentro do prazo, usando esse algoritmo específico.
Anna Jokela
Estou otimista de que existe um algoritmo melhor.
Eu tentei instalar pip numba, mas ele diz que não pode encontrar llvmpy. Eu tentei o sudo pip install llvmpy, mas ele diz que não consegue encontrar o versioneer. Eu tentei o sudo pip install versioneer, mas ele diz que já o possui.
Embora ainda não tenha o numba para trabalhar (acho que vou precisar instalar o anaconda no final), estou impressionado com isso. A questão é: você pode resolver N = 22 usando um método semelhante ao nimrod?
2

C ++ N = 16

Estou testando em um EEEPC com um átomo .. meu tempo não faz muito sentido. : D
O átomo resolve n = 14 em 34 segundos. E n = 16 em 20 minutos. Quero testar n = 16 no OP pc. Eu sou otimista.

A idéia é que toda vez que encontramos uma solução para um dado F, encontramos uma solução 2 ^ i porque podemos alterar a parte inferior de S, levando ao mesmo resultado.

#include <stdio.h>
#include <cinttypes>
#include <cstring>

int main()
{
   const int n = 16;
   const int m = n + 1;
   const uint64_t maxS = 1ULL << (2*n);
   const uint64_t maxF = 1ULL << n;
   const uint64_t mask = (1ULL << n)-1;
   uint64_t out[m]={0};
   uint64_t temp[m] = {0};
   for( uint64_t F = 0; F < maxF; ++F )
   {
      for( uint64_t S = 0; S < maxS; ++S )
      {
         int numSolution = 1;
         for( int i = n; i >= 0; --i )
         {
            const uint64_t window = S >> i;
            if( __builtin_popcount( mask & (window ^ F) ) == (n / 2) )
            {
               temp[i] += 1;
            } else {
               numSolution = 1 << i;
               S += numSolution - 1;
               break;
            }
         }
         for( int i = n; i >= 0; --i )
         {
            out[i] += temp[i]*numSolution;
            temp[i] = 0;
         }
      }
   }
   for( int i = n; i >= 0; --i )
   {
      uint64_t x = out[i];
      printf( "%lu ", x );
   }
   return 0;
}

compilar:

gcc 26459.cpp -std = c ++ 11 -O3 -march = nativo-restrito-alias--ftree-vectorize -Wall -pedantic -o 26459

ilmale
fonte
1
Isso é ótimo. Na verdade, tenho algumas idéias incompletas sobre como resolvê-lo para n maiores. Gostaria de ouvi-los ou isso poderia prejudicar a concorrência?
2

JAVASCRIPT n: 12

No meu computador, foram necessários 231,242 segundos. Na demonstração, estou usando trabalhadores da web para evitar o congelamento do navegador. Isso com certeza pode ser melhorado com trabalhadores paralelos. Eu sei que JS não tem chance nesse desafio, mas eu fiz isso por diversão!

Clique para executar a demonstração online

var n = 8;        
var m = n + 1;
var o = [];
var popCount = function(bits) {
  var SK5  = 0x55555555,
      SK3  = 0x33333333,
      SKF0 = 0x0f0f0f0f,
      SKFF = 0xff00ff;

  bits -= (bits >> 1) & SK5;
  bits  = (bits & SK3) + ((bits >> 2) & SK3);
  bits  = (bits & SKF0) + ((bits >> 4) & SKF0);
  bits += bits >> 8;

  return (bits + (bits >> 15)) & 63;
};
for(var S = 0; S < (1 << n + m - 1); S += 2){
  for(var F = 0; F < (1 << n - 1); F += 1){
    for (var i = 0; i < m; i++){
      var c = popCount(((S >> i) & ((1 << n) - 1)) ^ F);
      if(c == n >> 1){
        if(!o[i]) o[i] = 0;
        o[i] += 4;
      } else break;
    }
  }
}
return o;
rafaelcastrocouto
fonte
Que tal um desses novos mecanismos javascript (ish) rápidos? Eles poderiam ser usados?
Você quer dizer algo como dardo ?
Rafaelcastrocouto
1
Na verdade eu estou errado. Você também pode tentar o firefox e o cromo. A menos que você quiser escrever em asm.js naturalmente :)
1
desafio aceito ... vou fazer isso!
Rafaelcastrocouto
1
Tentei isso e levou meu computador 5,4 segundos para fazer n=22 [235388928,86292480,19031048,5020640,1657928,783920,545408,481256,463832,460256,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744,459744] i.imgur.com/FIJa2Ch.png
Spedwards
1

Fortran: n = 12

Acabei de fazer uma versão rápida no Fortran, sem otimizações, exceto o OpenMP. Ele deve se espremer em pouco menos de 10 minutos para n = 12 na máquina OP, leva 10:39 na minha máquina, que é levemente mais lenta.

Inteiros de 64 bits têm um impacto negativo no desempenho; acho que eu teria que repensar todo o algoritmo para que isso seja muito mais rápido. Não sei se vou me incomodar, acho que prefiro passar algum tempo pensando em um bom desafio que seja mais do meu próprio gosto. Se alguém quiser pegar isso e continuar com isso, vá em frente :)

program golf
use iso_fortran_env
implicit none
integer, parameter ::  n=12
integer :: F(n), S(2*n)
integer(int64) :: leadingzerocounts(n+1)
integer :: k
integer(int64) :: i,j,bindec,enc

leadingzerocounts=0

!$OMP parallel do private(i,enc,j,bindec,S,F,k) reduction(+:leadingzerocounts) schedule(dynamic)
do i=0,2**(2*n)-1
  enc=i
  ! Short loop to convert i into the array S with -1s and 1s
  do j=2*n,1,-1
    bindec=2**(j-1)
    if (enc-bindec .ge. 0) then
      S(j)=1
      enc=enc-bindec
    else
      S(j)=-1
    endif
  end do
  do j=0,2**(n)-1
    ! Convert j into the array F with -1s and 1s
    enc=j
    do k=n,1,-1
      bindec=2**(k-1)
      if (enc-bindec .ge. 0) then
        F(k)=1
        enc=enc-bindec
      else
        F(k)=-1
      endif
    end do
    ! Compute dot product   
    do k=1,n+1
      if (dot_product(F,S(k:k+n-1)) /= 0) exit
      leadingzerocounts(k)=leadingzerocounts(k)+1
    end do
  end do
end do
!$OMP end parallel do

print *, leadingzerocounts

end
semi-extrínseco
fonte
1

Lua: n = 16

Isenção de responsabilidade: minha intenção NÃO é postar isso como minha própria resposta, pois o algoritmo que estou usando é descaradamente roubado da resposta inteligente de Anna Jokela . que foi descaradamente roubado da resposta inteligente de ilmale .

Além disso, nem é válido - possui imprecisões causadas por números de ponto flutuante (seria melhor se Lua suportasse números inteiros de 64 bits). No entanto, ainda estou carregando, apenas para mostrar a rapidez com que esta solução é. É uma linguagem de programação dinâmica, e ainda assim eu posso calcular n = 16 em tempo razoável (1 minuto na CPU de 800 MHz).

Execute com LuaJIT, o intérprete padrão está muito lento.

local bit = require "bit"
local band = bit.band
local bor = bit.bor
local bxor = bit.bxor
local lshift = bit.lshift
local rshift = bit.rshift

-- http://stackoverflow.com/a/11283689/736054
local function pop_count(w)
    local b1 = 1431655765
    local b2 = 858993459
    local b3 = 252645135
    local b7 = 63

    w = band(rshift(w, 1), b1) + band(w, b1)
    w = band(rshift(w, 2), b2) + band(w, b2)
    w = band(w + rshift(w, 4), b3)
    return band(rshift(w, 24) + rshift(w, 16) + rshift(w, 8) + w, b7)
end

local function gen_array(n, value)
    value = value or 0
    array = {}
    for i = 1, n do
        array[i] = value
    end
    return array
end

local n = 16
local u = math.floor(n / 2)
local m = n + 1
local maxf = math.floor(lshift(1, n) / 2)
local maxs = maxf ^ 2
local mask = lshift(1, n) - 1

local out = gen_array(m, 0)
local temp = gen_array(m, 0)


for f = 0, maxf do
    local s = 0
    while s <= maxs do
        local num_solution = 1

        for i = n, 0, -1 do
            if pop_count(band(mask, bxor(rshift(s, i), f))) == u then
                temp[i + 1] = temp[i + 1] + 8
            else
                num_solution = lshift(1, i)
                s = s + num_solution - 1
                break
            end
        end

        for i = 1, m do
            out[i] = out[i] + temp[i] * num_solution
            temp[i] = 0
        end

        s = s + 1
    end
end

for i = m, 1, -1 do
    print(out[i])
end
xfix
fonte
Obrigado. Eu acho que as versões recentes da lua usam int long long, que deve ser de 64 bits em um sistema de 64 bits. Veja "lua_integer" em lua.org/work/doc/manual.html .
@Lembik: Interessante. De qualquer maneira, é Lua padrão (que já suporta, em long longvez de doublecom uma configuração de compilação), não LuaJIT.
Konrad Borowski 5/05
Eu acho que estava errado, de qualquer forma, errado. Seria necessário 5.3 que não existe. O melhor conselho que as pessoas poderiam dar era "tente 5.3-workx".