Die Aufgabe besteht darin, OEIS A005434 so schnell wie möglich zu berechnen .

Betrachten Sie eine binäre Zeichenfolge mit Seiner Länge n. Indizierung von 1, können wir bestimmen, ob S[1..i+1]Übereinstimmungen S[n-i..n]genau für alle iin der Reihenfolge von 0bis übereinstimmen n-1. Zum Beispiel,

S = 01010

gibt

[Y, N, Y, N, Y].

Dies liegt daran, dass 0Übereinstimmungen 0, 01nicht übereinstimmen 10, 010übereinstimmen 010, 0101nicht übereinstimmen 1010 und schließlich 01010selbst übereinstimmen.

Definieren Sie f(n)die Anzahl der unterschiedlichen Arrays von Ys und Ns, die Sie erhalten, wenn Sie über alle 2^nmöglichen Bitfolgen Sder Länge iterieren n.

Der Beobachter wird feststellen, dass diese Frage eine einfachere Variante einer anderen meiner jüngsten Fragen ist . Ich gehe jedoch davon aus, dass clevere Tricks dies viel schneller und einfacher machen können.

Aufgabe

Zum Erhöhen nab 1sollte Ihr Code ausgegeben werden n, f(n).

Beispielantworten

Denn n = 1..24die richtigen Antworten sind:

1, 2, 3, 4, 6, 8, 10, 13, 17, 21, 27, 30, 37, 47, 57, 62, 75, 87, 102, 116, 135, 155, 180, 194

Wertung

Ihr Code sollte sich wiederholen, wenn Sie nacheinander n = 1die Antwort geben n. Ich werde den gesamten Lauf zeitlich festlegen und ihn nach zwei Minuten beenden.

Ihre Punktzahl ist die höchste, die nSie in dieser Zeit erreichen.

Bei einem Unentschieden gewinnt die erste Antwort.

Wo wird mein Code getestet?

Ich werde Ihren Code unter Virtualbox in einer Lubuntu- Gast-VM (auf meinem Windows 7-Host) ausführen .

Mein Laptop verfügt über 8 GB RAM und eine Intel i7 [email protected] GHz (Broadwell) CPU mit 2 Kernen und 4 Threads. Der Befehlssatz enthält SSE4.2, AVX, AVX2, FMA3 und TSX.

Führende Einträge pro Sprache

• n = 599 in Rust bu Anders Kaseorg.
• n = 30 in C von Grimy. Die parallele Version erreicht 32, wenn sie nativ in Cygwin ausgeführt wird.

Rust , n ≈ 660

use std::collections::HashMap;
use std::iter::once;
use std::rc::Rc;

type Memo = HashMap<(u32, u32, Rc<Vec<u32>>), u64>;

fn f(memo: &mut Memo, mut n: u32, p: u32, mut s: Rc<Vec<u32>>) -> u64 {
    debug_assert!(p != 0);
    let d = n / p;
    debug_assert!(d >= 1);
    let r = n - p * if d >= 2 { d - 1 } else { 1 };

    let k = s.binary_search(&(n - r + 1)).unwrap_or_else(|i| i);
    for &i in &s[..k] {
        if i % p != 0 {
            return 0;
        }
    }

    if d >= 3 {
        let o = n - (p + r);
        n = p + r;
        s = Rc::new(s[k..].iter().map(|i| i - o).collect());
    } else if n == p {
        return 1;
    } else if k != 0 {
        s = Rc::new(s[k..].to_vec());
    }

    let query = (n, p, s);
    if let Some(&c) = memo.get(&query) {
        return c;
    }
    let (n, p, s) = query;

    let t = Rc::new(s.iter().map(|i| i - p).collect::<Vec<_>>());
    let c = if d < 2 {
        (1..r + 1).map(|q| f(memo, r, q, t.clone())).sum()
    } else if r == p {
        (1..p + 1)
            .filter(|&q| p % q != 0 || q == p)
            .map(|q| f(memo, r, q, t.clone()))
            .sum()
    } else {
        let t = match t.binary_search(&p) {
            Ok(_) => t,
            Err(k) => {
                Rc::new(t[..k]
                            .iter()
                            .cloned()
                            .chain(once(p))
                            .chain(t[k..].iter().cloned())
                            .collect::<Vec<_>>())
            }
        };
        (1..t.first().unwrap() + 1)
            .filter(|&q| p % q != 0 || q == p)
            .map(|q| f(memo, r, q, t.clone()))
            .sum()
    };
    memo.insert((n, p, s), c);
    c
}

fn main() {
    let mut memo = HashMap::new();
    let s = Rc::new(Vec::new());
    for n in 1.. {
        println!("{} {}",
                 n,
                 (1..n + 1)
                     .map(|p| f(&mut memo, n, p, s.clone()))
                     .sum::<u64>());
    }
}

Probieren Sie es online aus!

Wie es funktioniert

Dies ist eine auswendig gelernte Implementierung des rekursiven Prädikats Ξ, das in Leo Guibas, „Perioden in Strings“ (1981) angegeben ist. Die Funktion ermittelt f(memo, n, p, s)die Anzahl der Längenkorrelationen nmit der kleinsten Periode pund auch jede der Perioden in der Menge s.

Nur eine einfache Brute-Force-Suche, um die Herausforderung zu starten:

#include <stdio.h>
#include <stdint.h>
#include <string.h>

typedef uint16_t u16;
typedef uint64_t u64;

static u64 map[1<<16];

int main(void)
{
    for (u64 n = 1;; ++n) {
        u64 result = 1;
        u64 mask = (1ul << n) - 1;
        memset(map, 0, sizeof(map));

        #pragma omp parallel
        #pragma omp for
        for (u64 x = 1ul << (n - 1); x < 1ul << n; ++x) {

            u64 r = 0;
            for (u64 i = 1; i < n; ++i)
                r |= (u64) (x >> i == (x & (mask >> i))) << i;
            if (!r)
                continue;

            u16 h = (u16) (r ^ r >> 13 ^ r >> 27);
            while (map[h] && map[h] != r)
                ++h;

            if (!map[h]) {
                #pragma omp critical
                if (!map[h]) {
                    map[h] = r;
                    ++result;
                }
            }
        }

        printf("%ld\n", result);
    }
}

Kompilieren mit clang -fopenmp -Weverything -O3 -march=native. Auf meiner Maschine erreicht es in 2 Minuten n = 34.

BEARBEITEN: Einige OMP-Anweisungen wurden für eine einfache Parallelität gestreut.