Hitung OEIS A005434

10

Tugasnya adalah menghitung OEIS A005434 secepat mungkin.

Pertimbangkan Spanjang string biner n. Mengindeks dari 1, kita dapat menentukan apakah S[1..i+1]cocok S[n-i..n]untuk semua idalam urutan dari 0ke n-1. Sebagai contoh,

S = 01010

memberi

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

Ini karena 0cocok 0, 01tidak cocok 10, 010cocok 010, 0101tidak cocok 1010 dan akhirnya 01010cocok dengan sendirinya.

Tentukan f(n)jumlah array yang berbeda dari Ys dan Ns yang didapat ketika iterasi semua 2^nstring bit Spanjang yang mungkin berbeda n.

Pengamat akan memperhatikan bahwa pertanyaan ini adalah varian yang lebih sederhana dari pertanyaan saya yang lain baru-baru ini . Namun, saya berharap bahwa trik cerdas dapat membuat ini lebih cepat dan lebih mudah.

Tugas

Untuk meningkatkan nmulai dari 1, kode Anda harus ditampilkan n, f(n).

Contoh jawaban

Sebab n = 1..24, jawaban yang benar adalah:

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

Mencetak gol

Kode Anda harus iterate dari n = 1memberi jawaban untuk masing-masing npada gilirannya. Saya akan mengatur waktu seluruh pelarian, membunuhnya setelah dua menit.

Skor Anda adalah yang tertinggi yang nAnda dapatkan pada waktu itu.

Dalam kasus seri, jawaban pertama menang.

Di mana kode saya akan diuji?

Saya akan menjalankan kode Anda di bawah Virtualbox di VM tamu Lubuntu (pada host Windows 7 saya).

Laptop saya memiliki RAM 8GB dan CPU Intel i7 [email protected] GHz (Broadwell) dengan 2 core dan 4 thread. Set instruksi termasuk SSE4.2, AVX, AVX2, FMA3 dan TSX.

Entri terkemuka per bahasa

  • n = 599 di Rust bu Anders Kaseorg.
  • n = 30 dalam C oleh Grimy. Versi paralel mencapai 32 ketika dijalankan secara native di cygwin.

sumber
math.uni-bielefeld.de/~sillke/SEQUENCES/autocorrelation-range.c (ditautkan dari halaman OEIS) dijalankan dengan -O3 dapat menghitung hingga 100 dalam <0,02 detik pada mesin saya
vroomfondel
@rogaos Oh sayang. Saya harus menghapus pertanyaan tetapi sudah memiliki jawaban.
Saya pikir ini masih merupakan masalah yang keren - tetapi mungkin lebih dari 1000? Atau tanyakan jawaban untuk golf program yang cukup cepat
vroomfondel
1
@rogaos Saya baru saja menghapus batas sepenuhnya.

Jawaban:

4

Karat , 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>());
    }
}

Cobalah online!

Bagaimana itu bekerja

Ini adalah implementasi memoized dari predikat rekursif Ξ yang diberikan dalam Leo Guibas, "Periode dalam string" (1981). Fungsi f(memo, n, p, s)menemukan jumlah korelasi panjang ndengan periode terkecil pdan juga masing-masing periode dalam himpunan s.

Anders Kaseorg
sumber
Membuat Anda bertanya-tanya apakah ada solusi yang lebih cepat untuk masalah terkait lainnya. Sangat mengesankan!
Menariknya, ini sepenuhnya terbatas pada memori. Ini mempercepat hingga ~ 500 dan kemudian tiba-tiba melambat karena kehabisan RAM.
2

Hanya pencarian kasar sederhana, untuk memulai tantangan:

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

Kompilasi dengan clang -fopenmp -Weverything -O3 -march=native. Di mesin saya mencapai n = 34 dalam 2 menit.

EDIT: menaburkan beberapa arahan OMP untuk paralelisme mudah.

Grimmy
sumber
@Lembik Apakah ada jawaban yang bagus di luar SE untuk dihapus? Tidakkah Anda harus menunggu seseorang (mungkin komentator) untuk mengirimkan algoritma ini sebagai jawaban, dan menerima jawaban itu?
Grimmy
Anda membuat poin yang sangat bagus
Sayangnya saya tidak bisa benar-benar menguji kode paralel Anda di virtualbox karena saya memiliki total dua core pada CPU saya.
Saya menjalankannya di cygwin dan mencapai 32.