Wie hoch kannst du gehen? (Eine Codierung + Algorithmen Herausforderung)

34

Jetzt, da jeder seine (oft erstaunliche) Programmierkenntnisse auf niedrigem Niveau für Wie langsam ist Python wirklich? (Oder wie schnell ist deine Sprache?) Und wie langsam ist Python wirklich (Teil II)? Es ist Zeit für eine Herausforderung, die auch Ihre Fähigkeit zur Verbesserung eines Algorithmus erweitert.

Der folgende Code berechnet eine Liste der Länge 9. Die Position iin der Liste gibt an, wie oft mindestens iaufeinanderfolgende Nullen gefunden wurden, wenn die inneren Produkte zwischen Fund berechnet wurden S. Um dies genau zu tun, werden alle möglichen FLängen- nund Längenlisten Sdurchlaufen 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

Die Ausgabe ist

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

Wenn Sie mit diesem Code n auf 10,12,14,16,18,20 erhöhen, wird es sehr schnell viel zu langsam.

Regeln

  • Die Herausforderung besteht darin, die richtige Ausgabe für ein möglichst großes n zu liefern. Nur gerade Werte von n sind relevant.
  • Wenn es einen Gleichstand gibt, geht der Gewinn an den schnellsten Code auf meinem Computer für das größte n.
  • Ich behalte mir das Recht vor, keinen Code zu testen, der länger als 10 Minuten dauert.
  • Sie können den Algorithmus beliebig ändern, solange er die richtige Ausgabe liefert. Tatsächlich müssen Sie den Algorithmus ändern, um angemessene Fortschritte auf dem Weg zum Sieg zu erzielen.
  • Der Gewinner erhält eine Woche ab dem Zeitpunkt, zu dem die Frage gestellt wurde.
  • Das Kopfgeld wird bei Fälligkeit ausgezahlt, kurz danach wird der Gewinner ausgezahlt.

Mein Computer Die Timings werden auf meinem Computer ausgeführt. Dies ist eine Ubuntu-Standardinstallation auf einem AMD FX-8350 Eight-Core-Prozessor. Dies bedeutet auch, dass ich in der Lage sein muss, Ihren Code auszuführen. Verwenden Sie daher nur leicht verfügbare kostenlose Software und fügen Sie vollständige Anweisungen zum Kompilieren und Ausführen Ihres Codes bei.

Status .

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

Der Gewinner war Reimer Behrends mit einem Eintrag in Nimrod!

Zur Kontrolle sollte der Ausgang für n = 22 sein [12410090985684467712, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680].


Der Wettbewerb ist jetzt vorbei, aber ... Ich werde 200 Punkte für jede Einsendung anbieten , die n um 2 erhöht (innerhalb von 10 Minuten auf meinem Computer), bis mir die Punkte ausgehen. Dieses Angebot ist für immer offen .

Gemeinschaft
quelle
1
"Ich behalte mir das Recht vor, keinen Code zu testen, der länger als ein paar Minuten dauert." > Sie sollten eine genaue Uhrzeit auf Ihrem Computer angeben, da ansonsten für diese Frage kein objektives Gewinnkriterium vorliegt.
pastebin.com Schrägstrich 0mr8spkT
14
Ich liebe diese Herausforderungen, um meine Geschwindigkeit zu steigern. Wenn Sie ein kommerzielles Produkt damit bauen, werden Sie ein verdammt schnelles Produkt haben, und Sie sind auch ein böses Genie .
Rainbolt
1
Vielleicht würde ein informativerer Titel darauf aufmerksam machen?
TheDoctor
8
Wenn wir diese Art von Herausforderung fortsetzen, sollten wir meines Erachtens zumindest versuchen, ein anderes Problem zu lösen, um es interessant zu halten (keine Variation desselben Problems mit zusätzlichen Spezifikationen).
HainenNL
2
@Claudiu seine CPU hat 8 physische Kerne, aber die Fetch / Decode- und FPU-Einheiten werden zwischen den Kernen geteilt. Wenn sich der Engpass in einem dieser Bereiche befindet, verhält er sich eher wie ein Quadcore. Missbrauche Integer-Logik und vermeide große Code-Größen und es ist eher wie ein 8-Kern.
Stefan

Antworten:

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)

Kompilieren mit

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

(Nimrod kann hier heruntergeladen werden .)

Dies läuft in der zugewiesenen Zeit für n = 20 (und für n = 18, wenn nur ein einziger Thread verwendet wird, was im letzteren Fall ungefähr 2 Minuten dauert).

Der Algorithmus verwendet eine rekursive Suche, die den Suchbaum beschneidet, wenn ein inneres Produkt angetroffen wird, das nicht Null ist. Wir halbieren auch den Suchraum, indem (F, -F)wir beobachten, dass wir für jedes Paar von Vektoren nur einen berücksichtigen müssen, weil der andere genau die gleichen Mengen innerer Produkte erzeugt (indem wir Sauch negieren ).

Die Implementierung verwendet die Metaprogrammierungsfunktionen von Nimrod, um die ersten Ebenen der rekursiven Suche zu entrollen / inline zu schalten. Dies spart ein wenig Zeit, wenn Sie gcc 4.8 und 4.9 als Backend von Nimrod verwenden, und eine angemessene Menge für das Klingen.

Der Suchraum könnte weiter eingeschränkt werden, indem beobachtet wird, dass wir nur Werte von S berücksichtigen müssen, die sich in einer geraden Anzahl der ersten N Positionen von unserer Wahl von F unterscheiden. Die Komplexität oder der Speicherbedarf davon skalieren jedoch nicht für große Werte von N, vorausgesetzt, der Schleifenkörper wird in diesen Fällen vollständig übersprungen.

Die Tabellierung, bei der das innere Produkt Null ist, scheint schneller zu sein, als die Verwendung einer Bitzählfunktion in der Schleife. Offensichtlich hat der Zugang zum Tisch eine ziemlich gute Lokalität.

Angesichts der Funktionsweise der rekursiven Suche scheint das Problem für die dynamische Programmierung zugänglich zu sein, aber es gibt keinen offensichtlichen Weg, dies mit einer angemessenen Speicherkapazität zu tun.

Beispielausgaben:

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]

Um den Algorithmus mit anderen Implementierungen zu vergleichen, dauert N = 16 auf meinem Computer bei Verwendung eines einzelnen Threads etwa 7,9 Sekunden und bei Verwendung von vier Kernen 2,3 Sekunden.

N = 22 dauert ungefähr 15 Minuten auf einem 64-Core-Rechner mit gcc 4.4.6 als Nimrods Backend und überläuft 64-Bit-Ganzzahlen leadingZeros[0](möglicherweise nicht vorzeichenlose, habe es nicht angeschaut).


Update: Ich habe Raum für ein paar Verbesserungen gefunden. Erstens Fkönnen wir für einen gegebenen Wert von die ersten 16 Einträge der entsprechenden SVektoren genau aufzählen , da sie sich genau an den N/2Stellen unterscheiden müssen . Wir berechnen also eine Liste von Bitvektoren der Größe N, für die N/2Bits gesetzt sind, und leiten daraus den Anfangsteil von Sab F.

Zweitens können wir die rekursive Suche verbessern, indem wir beobachten, dass wir immer den Wert von kennen F[N](da das MSB in der Bitdarstellung Null ist). Auf diese Weise können wir genau vorhersagen, in welchen Zweig wir vom inneren Produkt zurückkehren. Während dies uns tatsächlich erlauben würde, die gesamte Suche in eine rekursive Schleife umzuwandeln, führt dies tatsächlich dazu, dass die Verzweigungsvorhersage ziemlich durcheinander gerät, sodass wir die obersten Ebenen in ihrer ursprünglichen Form beibehalten. Wir sparen immer noch Zeit, vor allem durch die Reduzierung der Verzweigungen.

Für einige Aufräumarbeiten verwendet der Code jetzt vorzeichenlose Ganzzahlen und korrigiert diese auf 64-Bit (nur für den Fall, dass jemand dies auf einer 32-Bit-Architektur ausführen möchte).

Die Gesamtbeschleunigung liegt zwischen einem Faktor von x3 und x4. N = 22 benötigt immer noch mehr als acht Kerne, um in weniger als 10 Minuten ausgeführt zu werden, aber auf einem 64-Kern-Computer sind es jetzt nur noch etwa vier Minuten (mit entsprechend numThreadserhöhten Werten). Ich glaube nicht, dass es ohne einen anderen Algorithmus viel mehr Raum für Verbesserungen gibt.

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]

Erneut aktualisiert, um weitere mögliche Reduzierungen des Suchraums zu nutzen. Läuft in ca. 9:49 Minuten für N = 22 auf meinem Quadcore-Rechner.

Endgültiges Update (glaube ich). Bessere Äquivalenzklassen für die Auswahl von F, Verkürzung der Laufzeit für N = 22 auf 3:19 Minuten 57 Sekunden (Bearbeiten: Ich hatte das versehentlich mit nur einem Thread ausgeführt) auf meinem Computer.

Diese Änderung nutzt die Tatsache, dass ein Vektorpaar die gleichen führenden Nullen erzeugt, wenn eine durch Drehen in die andere transformiert werden kann. Leider erfordert eine ziemlich kritische Low-Level-Optimierung, dass das oberste Bit von F in der Bitdarstellung immer das gleiche ist, und während diese Äquivalenz verwendet wird, wird der Suchraum ziemlich stark gekürzt und die Laufzeit um etwa ein Viertel gegenüber einem anderen Zustandsraum verringert Reduzierung von F, der Overhead durch das Eliminieren der Low-Level-Optimierung mehr als kompensiert. Es stellt sich jedoch heraus, dass dieses Problem behoben werden kann, indem auch die Tatsache berücksichtigt wird, dass F, die Inverse voneinander sind, ebenfalls äquivalent sind. Dies trug zwar etwas zur Komplexität der Berechnung der Äquivalenzklassen bei, erlaubte mir jedoch auch, die oben erwähnte Optimierung auf niedriger Ebene beizubehalten, was zu einer Beschleunigung von etwa x3 führte.

Ein weiteres Update zur Unterstützung von 128-Bit-Ganzzahlen für die akkumulierten Daten. Um mit 128-Bit-Ganzzahlen zu kompilieren, müssen Sie longint.nimvon hier aus und mit kompilieren -d:use128bit. N = 24 dauert immer noch mehr als 10 Minuten, aber ich habe das Ergebnis für die Interessenten unten angegeben.

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
quelle
Das Ergebnis mit N = 22 ist 12410090985684467712, das 63,42 Bit benötigt und somit in ein 64-Bit-Bit ohne Vorzeichen passt.
Stefan
2
Sie haben die Messlatte definitiv sehr beeindruckend angehoben.
1
Schön zu sehen, dass jemand Nimrod benutzt. :)
cjfaure
@ Stefan Vielleicht könnte Ihr Programmierer diese Methode für N = 22 unter 10 Minuten bringen?
Ich habe versucht, N = 22, die nach ein paar Stunden beendet wurde. Aber es gibt mir [-6036653088025083904, 2087229562810269696, 351473149499408384, 59178309967151104, 9975110458933248, 1682628717576192, 284866824372224, 48558946385920, 8416739196928, 1518499004416, 301448822784, 71620493312, 22100246528, 8676573184, 3897278464, 1860960256, 911646720, 451520512, 224785920, 112198656, 56062720, 28031360, 14015680], was anscheinend ein Überlauffehler ist. Ich kenne keinen Nimrod, aber ist es möglich, unsignierte Ints zu verwenden, um dies zu lösen?
11

Java ( n=22?)

Ich denke, die meisten Antworten sind besser, als n=16einen ähnlichen Ansatz zu verwenden, obwohl sie sich in den Symmetrien, die sie ausnutzen, und in der Art und Weise, wie sie die Aufgabe zwischen den Threads aufteilen, unterscheiden.

Die in der Frage definierten Vektoren können durch Bitfolgen ersetzt werden, und das innere Produkt kann durch XOR-Verknüpfung des überlappenden Fensters und durch Überprüfen, ob genau n/2Bits gesetzt (und daher n/2Bits gelöscht) sind. Es gibt n! / ((n/2)!)(zentraler Binomialkoeffizient) Folgen von nBits mit n/2gesetzten Bits (die ich ausgeglichene Folgen nenne ), also Fgibt es für jede gegebene Zahl so viele Fenster, von Sdenen ein Null-Innenprodukt erhalten wird. Darüber hinaus entspricht die Aktion des Gleitens Sentlang eins und des Überprüfens, ob noch ein eingehendes Bit gefunden werden kann, das ein inneres Produkt von Null ergibt, der Suche nach einer Kante in einem Graphen, dessen Knoten die Fenster sind und dessen Kanten einen Knoten umit einem Knoten verknüpfen , vdessen erste n-1Bits sind die letztenn-1Bits von u.

Zum Beispiel erhalten wir mit n=6und F=001001diesen Graphen:

Diagramm für F = 001001

und dafür F=001011bekommen wir diese Grafik:

Diagramm für F = 001011

Dann müssen wir für jeden ivon 0bis zu der Anzahl der nPfade izählen, die es gibt, und für jeden die Diagramme aufsummieren F. Ich denke, die meisten von uns verwenden die Tiefensuche.

Beachten Sie, dass die Grafiken spärlich sind: Es ist leicht zu beweisen, dass jeder Knoten einen In-Grad von höchstens 1 und einen Out-Grad von höchstens 1 aufweist. Das bedeutet auch, dass nur einfache Ketten und einfache Schleifen möglich sind. Dies vereinfacht die DFS ein wenig.

Ich nutze ein paar Symmetrien: Die ausgeglichenen Zeichenfolgen werden unter Bit-Inverse (die ~Operation in vielen Sprachen aus der ALGOL-Familie) und unter Bit-Rotation geschlossen, sodass wir Werte zusammenfassen können, Fdie durch diese Operationen zusammenhängen, und nur die DFS ausführen Einmal.

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

Auf meinen 2.5GHz Core 2 bekomme ich

# 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

Da Lembiks Computer über 8 Kerne verfügt und mein früheres Single-Thread-Programm doppelt so schnell ausgeführt hat wie ich, bin ich optimistisch, dass es n=22in weniger als 8 Minuten ausgeführt wird.

Peter Taylor
quelle
7:17! Sehr schön. Würde es Ihnen etwas ausmachen, Ihre Methode etwas näher zu erläutern?
6

C

Es handelt sich im Grunde genommen nur um eine leicht optimierte Implementierung des in Frage kommenden Algorithmus. Es kann n=12innerhalb der Frist verwalten.

#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;
}

Testlauf n=12inklusive Kompilierung für:

$ 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
$

Bemerkung: Ich habe gerade mein Gehirn angeschaltet und mit einfachen Kombinatoren berechnet, dass der erste Wert immer sein wird n! / ((n / 2)!)^2 * 2^(n + m - 1). Es scheint mir, dass es eine völlig algebraische Lösung für dieses Problem geben muss.

Fors
quelle
Ich bekomme viele Warnungen, wenn ich das kompiliere. Probieren Sie gcc -Wall -Wextra Fors.c -o Fors
Es gab ein paar unbenutzte Variablen, die bei einer früheren Iteration vergessen wurden, aber ich habe sie entfernt, sodass mindestens ein paar Warnungen hätten verschwinden sollen. Ich habe momentan kein GCC zur Verfügung (nur Clang), und Clang gibt mir im Moment keine Warnungen (nachdem die nicht verwendeten Variablen entfernt wurden). Und da Clang in Bezug auf Warnungen normalerweise strenger ist, muss ich sagen, dass ich ein bisschen überrascht bin, dass Sie überhaupt Warnungen erhalten haben.
Fors
Es beschwert sich über Fors.c: 13: 17: Warnung: Schlagen Sie Klammern um '-' im Operanden von '&' [-Wparentheses] (zweimal) vor und warnen Sie auch: Format '% llu' erwartet Argument vom Typ 'long long unsigned int ', aber Argument 2 hat den Typ' uint64_t '[-Wformat =]. Tatsächlich beschwert sich clang auch für mich über die printf-Anweisung,
Mit den letzten Änderungen sollte GCC keine Warnmeldungen ausgeben.
Fors
Es klagt immer noch über Fors.c: 13: 49: Warnung: Schlagen Sie Klammern um Arithmetik im Operanden '^' vor [- Klammern] Aber in schlimmeren Fällen dauert es länger als 10 Minuten auf meinem Computer.
5

Java, n=16

Für jeden gegebenen Wert von Fgibt es \binom{n}{n/2}Vektoren, die ein inneres Produkt von Null haben. So können wir ein Diagramm erstellen, dessen Eckpunkte die übereinstimmenden Vektoren sind und dessen Kanten der Verschiebung von entsprechen S, und dann müssen wir nur die Längenpfade bis zum nDiagramm zählen.

Ich habe nicht versucht, dies durch Ersetzen von Bedingungen durch bitweise Operationen zu optimieren, aber jede doppelte Erhöhung der nLaufzeit um das 16-fache. Das wird also keinen ausreichenden Unterschied bewirken, es sei denn, ich bin ziemlich nahe an der Schwelle. Auf meiner Maschine bin ich nicht.

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("]");
    }
}

Auf meinen 2.5GHz Core 2 bekomme ich

$ 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
quelle
Huckepack, da ich momentan keine eigene Lösung implementieren möchte. Jeder Vertex hat höchstens einen Nachfolger, sodass Sie das Array nicht wirklich benötigen. Um Kombinationen von fund Startknoten effizient zu durchlaufen , iterieren Sie f_xor_gmit genau n/2gesetzten Bits über alle . Für jedes von diesen iteriere über alles fund nimm g = f ^ f_xor_g.
David Eisenstat
@ David, ich weiß, und meine Version 7 hat in einer Minute n = 18 auf meinem Atom-Netbook, aber ich kann es nicht posten, bis ich aus dem Urlaub zurück bin.
Peter Taylor
4

RPython, N = 22 ~ 3: 23

Multithreaded mit einem stapellosen rekursiven Abstieg. Das Programm akzeptiert zwei Befehlszeilenargumente: N und die Anzahl der Arbeitsthreads.

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

Kompilieren

Erstellen Sie einen lokalen Klon des PyPy-Repositorys mit Quecksilber, Git oder was auch immer Sie bevorzugen. Geben Sie die folgende Beschwörung ein (unter der Annahme, dass das obige Skript benannt ist convolution-high.py):

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

Hierbei handelt es sich %PYPY_REPO%um eine Umgebungsvariable, die auf das soeben geklonte Repository verweist. Die Kompilierung dauert ungefähr eine Minute.


Beispiel-Timings

N = 16, 4 Fäden:

$ 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 Fäden:

$ 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 Fäden:

$ 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 Fäden:

$ 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
quelle
9:26. Willkommen bei der 22-
Ich bin nicht sicher warum, aber Ihre neue Version ist für mich nicht schneller. Immer noch gegen 9:30, wenn ich Zeit habe ./primo-c 22 8.
@Lembik das wäre sinnvoll, wenn die Division im Durchschnitt 3 Rechtsverschiebungen (3 = Summe {(n + 1) / (2 ^ n)}, n = 1. .infty) gleich schnell wäre. Ich nehme an, dass dies bei bestimmten Architekturen der Fall ist, aber bei meinen ist die Aufteilung merklich langsamer. Vielen Dank, dass Sie sich die Zeit genommen haben, es zu testen :)
primo
3

Python 3.3, N = 20, 3,5 min

Haftungsausschluss: Ich beabsichtige NICHT , dies als meine eigene Antwort zu veröffentlichen, da der von mir verwendete Algorithmus nur ein schamloser Port aus der RPython-Lösung von primo ist . Ich möchte hier nur zeigen, was Sie in Python tun können, wenn Sie die Magie der Numpy- und Numba- Module kombinieren .

Numba erklärte kurz:

Numba ist ein Just-in-Time-Compiler, der kommentierten Python- und NumPy-Code in LLVM kompiliert (über Dekoratoren). http://numba.pydata.org/

Update 1 : Nachdem ich die Zahlen herumgeworfen habe, ist mir aufgefallen, dass wir einfach einige der Zahlen komplett überspringen können. So , jetzt maxf wird (1 << n) // 2 und maxs wird maxf 2 **. Dies beschleunigt den Prozess erheblich. n = 16 dauert jetzt nur noch ~ 48s (von 4,5min). Ich habe auch eine andere Idee, die ich versuchen werde, um zu sehen, ob ich es etwas schneller machen kann.

Update 2: Geänderter Algorithmus (primos Lösung). Mein Port unterstützt zwar noch kein Multithreading, das Hinzufügen ist jedoch ziemlich trivial. Es ist sogar möglich, CPython GIL mit Numba und ctypes freizugeben. Diese Lösung läuft aber auch auf Single Core sehr schnell!

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)

Und schlussendlich:

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))

Dies läuft auf meinem Rechner in 212688ms oder ~ 3.5min.

Anna Jokela
quelle
Vielen Dank. Wie wäre es nun mit n = 18? :)
Es sind fast 20 Minuten vergangen, seit ich das Programm mit n = 18 gestartet habe. Ich kann mit Sicherheit sagen, dass Python dies mit diesem speziellen Algorithmus auch mit Numba nicht rechtzeitig lösen kann.
Anna Jokela
Ich bin optimistisch, dass es einen besseren Algorithmus gibt.
Ich habe versucht, pip numba zu installieren, aber es heißt, llvmpy kann nicht gefunden werden. Ich habe versucht, sudo pip llvmpy zu installieren, aber es heißt, dass versioneer nicht gefunden werden kann. Ich habe versucht, sudo pip versioneer zu installieren, aber es besagt, dass ich es bereits habe.
Obwohl ich noch keine Numba zur Arbeit habe (ich denke, ich muss am Ende Anaconda installieren), bin ich davon beeindruckt. Die Frage ist, ob Sie N = 22 mit einer ähnlichen Methode wie die Nimrod-Methode lösen können.
2

C ++ N = 16

Ich teste auf einem EEEPC mit einem Atom. Meine Zeit ergibt keinen Sinn. : D
Das Atom löst n = 14 in 34 Sekunden. Und n = 16 in 20 Minuten. Ich möchte n = 16 am OP-PC testen. Ich bin optimistisch.

Die Idee ist, dass wir jedes Mal, wenn wir eine Lösung für ein gegebenes F finden, eine 2 ^ i-Lösung gefunden haben, weil wir den unteren Teil von S ändern können, was zum gleichen Ergebnis führt.

#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;
}

kompilieren:

gcc 26459.cpp -std = c ++ 11 -O3 -march = native -fstrict-aliasing -ftree-vectorize -Wall -pedantic -o 26459

Ilmale
quelle
1
Das ist toll. Ich habe tatsächlich ein paar halbherzige Ideen, wie man es für größere n löst. Möchten Sie sie hören oder könnte das die Konkurrenz verderben?
2

JAVASCRIPT n: 12

In meinem Computer dauerte es 231.242 Sekunden. In der Demo verwende ich Webworker, um das Einfrieren des Browsers zu verhindern. Dies kann mit Parallelarbeitern sicher noch weiter verbessert werden. Ich weiß, dass JS bei dieser Herausforderung keine Chance hat, aber ich habe es aus Spaß gemacht!

Klicken Sie hier, um die Online-Demo auszuführen

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
quelle
Was ist mit einer dieser neuen (ish) schnellen Javascript-Engines? Könnten diese verwendet werden?
Du meinst so etwas wie Dart ?
Rafaelcastrocouto
1
Eigentlich irre ich mich. Sie können auch sowohl Firefox als auch Chrom ausprobieren. Es sei denn, Sie möchten es natürlich in asm.js schreiben :)
1
Herausforderung angenommen ... werde es tun!
Rafaelcastrocouto
1
Versuchte dies und brauchte 5,4 Sekunden, um 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

Ich habe gerade in Fortran eine 30-minütige Version erstellt, keine Optimierungen außer OpenMP. Es sollte bei n = 12 auf der OPs-Maschine knapp unter 10 Minuten einrasten, es dauert 10:39 auf meiner Maschine, die etwas langsamer ist.

64-Bit-Ganzzahlen wirken sich in der Tat negativ auf die Leistung aus. Ich denke, ich müsste den gesamten Algorithmus überdenken, damit dies viel schneller geht. Ich weiß nicht, ob ich mich darum kümmern werde, ich denke, ich werde lieber etwas Zeit damit verbringen, mir eine gute Herausforderung auszudenken, die eher meinem Geschmack entspricht. Wenn jemand anderes das nehmen und damit rennen will, mach weiter :)

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-extrinsisch
quelle
1

Lua: n = 16

Haftungsausschluss: Ich beabsichtige NICHT, dies als meine eigene Antwort zu veröffentlichen, da der Algorithmus, den ich verwende, schamlos aus Anna Jokelas cleverer Antwort gestohlen wurde . Das wurde schamlos aus Ilmeas kluger Antwort gestohlen .

Außerdem ist es nicht einmal gültig - es weist Ungenauigkeiten auf, die durch Gleitkommazahlen verursacht werden (es wäre besser, wenn Lua 64-Bit-Ganzzahlen unterstützen würde). Ich lade es jedoch immer noch hoch, um zu zeigen, wie schnell diese Lösung ist. Es ist eine dynamische Programmiersprache und dennoch kann ich n = 16 in angemessener Zeit berechnen (1 Minute bei 800 MHz CPU).

Mit LuaJIT ausführen, Standardinterpreter ist zu langsam.

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
quelle
Vielen Dank. Ich denke, die neuesten Lua-Versionen verwenden long long int, was auf einem 64-Bit-System 64-Bit sein sollte. Siehe "lua_integer" unter lua.org/work/doc/manual.html .
@Lembik: Interessant. In beiden Fällen handelt es sich um Standard-Lua (das long longanstelle doubleeiner Kompilierungseinstellung bereits unterstützt wird ), nicht um LuaJIT.
Konrad Borowski
Ich glaube, ich habe mich auf jeden Fall geirrt. Man müsste 5.3 was es nicht gibt. Der beste Rat, den Lua-Leute geben konnten, war "try 5.3-workx".