Нахождение приблизительных соотношений

14

Рассмотрим двоичную строку Sдлины n. Индексируя с 1, мы можем вычислить расстояния Хэмминга между S[1..i+1]и S[n-i..n]для всех iв порядке от 0до n-1. Расстояние Хэмминга между двумя строками одинаковой длины - это количество позиций, в которых соответствующие символы различны. Например,

S = 01010

дает

[0, 2, 0, 4, 0].

Это потому , что 0совпадения имеют расстояние Хэмминга от двух до , совпадения , расстояние Хэмминга от четырех до и, наконец, совпадают.001100100100101101001010

Однако нас интересуют только результаты, в которых расстояние Хэмминга не более 1. Таким образом, в этой задаче мы сообщим, Yесли расстояние Хэмминга не больше одного, а в Nпротивном случае. Таким образом, в нашем примере выше мы получили бы

[Y, N, Y, N, Y]

Определите f(n)количество различных массивов Ys и Ns, получаемых при переборе всех 2^nвозможных битовых строк Sдлины n.

задача

Для увеличения, nначиная с 1, ваш код должен выводить f(n).

Пример ответов

Для n = 1..24, правильные ответы:

1, 1, 2, 4, 6, 8, 14, 18, 27, 36, 52, 65, 93, 113, 150, 188, 241, 279, 377, 427, 540, 632, 768, 870

счет

Ваш код должен повторяться от n = 1предоставления ответа для каждого nпо очереди. Я рассчитываю весь пробег, убив его через две минуты.

Ваш результат - самый высокий nза это время.

В случае ничьей победит первый ответ.

Где будет проверяться мой код?

Я буду запускать ваш код на моем (немного старом) ноутбуке с Windows 7 под Cygwin. В результате, пожалуйста, предоставьте любую возможную помощь, чтобы облегчить это.

Мой ноутбук имеет 8 ГБ оперативной памяти и процессор Intel i7 5600U @ 2,6 ГГц (Broadwell) с 2 ядрами и 4 потоками. Набор команд включает SSE4.2, AVX, AVX2, FMA3 и TSX.

Ведущие записи по языку

  • n = 40 в Rust с использованием CryptoMiniSat, автор Anders Kaseorg. (В гостевой виртуальной машине Lubuntu под Vbox.)
  • n = 35 в C ++ с использованием библиотеки BuDDy, автор Christian Seviers. (В гостевой виртуальной машине Lubuntu под Vbox.)
  • n = 34 в клинго Андерс Касорг. (В гостевой виртуальной машине Lubuntu под Vbox.)
  • n = 31 в Rust от Anders Kaseorg.
  • n = 29 в Clojure от NikoNyrh.
  • n = 29 в С по Bartavelle.
  • n = 27 в Хаскеле по Бартавелле
  • n = 24 в пари / гп по алефале.
  • n = 22 в Python 2 + pypy мной.
  • n = 21 в Mathematica от alephalpha. (Self сообщается)

Будущие награды

Теперь я дам 200 баллов за каждый ответ, который за две минуты достигнет n = 80 на моей машине.


источник
Вы знаете какой-нибудь трюк, который позволит кому-то найти более быстрый алгоритм, чем наивная грубая сила? Если нет, то это проблема «пожалуйста, реализуйте это в x86» (или, может быть, если мы знаем ваш GPU ...).
Джонатан Аллан
@JonathanAllan Конечно, можно ускорить очень наивный подход. Точно, как быстро вы можете получить, я не уверен. Интересно, что если мы изменили вопрос так, чтобы вы получили Y, если расстояние Хемминга не больше 0, и N в противном случае, то есть известная формула замкнутой формы.
@Lembik Мы измеряем процессорное время или реальное время?
flawr
@flawr Я измеряю реальное время, но запускаю его несколько раз и беру минимум для устранения странностей.

Ответы:

9

Rust + CryptoMiniSat , n ≈ 41

src/main.rs

extern crate cryptominisat;
extern crate itertools;

use std::iter::once;
use cryptominisat::{Lbool, Lit, Solver};
use itertools::Itertools;

fn make_solver(n: usize) -> (Solver, Vec<Lit>) {
    let mut solver = Solver::new();
    let s: Vec<Lit> = (1..n).map(|_| solver.new_var()).collect();
    let d: Vec<Vec<Lit>> = (1..n - 1)
        .map(|k| {
                 (0..n - k)
                     .map(|i| (if i == 0 { s[k - 1] } else { solver.new_var() }))
                     .collect()
             })
        .collect();
    let a: Vec<Lit> = (1..n - 1).map(|_| solver.new_var()).collect();
    for k in 1..n - 1 {
        for i in 1..n - k {
            solver.add_xor_literal_clause(&[s[i - 1], s[k + i - 1], d[k - 1][i]], true);
        }
        for t in (0..n - k).combinations(2) {
            solver.add_clause(&t.iter()
                                   .map(|&i| d[k - 1][i])
                                   .chain(once(!a[k - 1]))
                                   .collect::<Vec<_>>()
                                   [..]);
        }
        for t in (0..n - k).combinations(n - k - 1) {
            solver.add_clause(&t.iter()
                                   .map(|&i| !d[k - 1][i])
                                   .chain(once(a[k - 1]))
                                   .collect::<Vec<_>>()
                                   [..]);
        }
    }
    (solver, a)
}

fn search(n: usize,
          solver: &mut Solver,
          a: &Vec<Lit>,
          assumptions: &mut Vec<Lit>,
          k: usize)
          -> usize {
    match solver.solve_with_assumptions(assumptions) {
        Lbool::True => search_sat(n, solver, a, assumptions, k),
        Lbool::False => 0,
        Lbool::Undef => panic!(),
    }
}

fn search_sat(n: usize,
              solver: &mut Solver,
              a: &Vec<Lit>,
              assumptions: &mut Vec<Lit>,
              k: usize)
              -> usize {
    if k >= n - 1 {
        1
    } else {
        let s = solver.is_true(a[k - 1]);
        assumptions.push(if s { a[k - 1] } else { !a[k - 1] });
        let c = search_sat(n, solver, a, assumptions, k + 1);
        assumptions.pop();
        assumptions.push(if s { !a[k - 1] } else { a[k - 1] });
        let c1 = search(n, solver, a, assumptions, k + 1);
        assumptions.pop();
        c + c1
    }
}

fn f(n: usize) -> usize {
    let (mut solver, proj) = make_solver(n);
    search(n, &mut solver, &proj, &mut vec![], 1)
}

fn main() {
    for n in 1.. {
        println!("{}: {}", n, f(n));
    }
}

Cargo.toml

[package]
name = "correlations-cms"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
cryptominisat = "5.0.1"
itertools = "0.6.0"

Как это устроено

Это делает рекурсивный поиск по дереву всех частичных назначений префиксов массива Y / N, используя решатель SAT, чтобы на каждом шаге проверять, является ли текущее частичное назначение последовательным, и сокращать поиск, если нет. CryptoMiniSat является подходящим решателем SAT для этой работы благодаря специальной оптимизации для предложений XOR.

Три семейства ограничений

S iS k + iD ki , для 1 ≤ kn - 2, 0 ≤ i ≤ n - k ;
D ki 1D ki 2 ∨ ¬ A k , для 1 ≤ kn - 2, 0 ≤ i 1 < i 2n - k ;
¬ Д ки 1 ∨ ⋯ ∨ ¬ Д ки п - к - 1к , для 1 ≤ KN - 2, 0 ≤ я 1 <⋯ < я п - к - 1п - к ;

за исключением того, что в качестве оптимизации S 0 принудительно устанавливается в false, так что D k 0 просто равно S k .

Андерс Касеорг
источник
2
Ооооооооо! :)
Я все еще пытаюсь скомпилировать это в Windows (используя cygwin + gcc). Я клонировал cryptominisat и скомпилировал его. Но я до сих пор не знаю, как скомпилировать код ржавчины. Когда я cargo buildполучу--- stderr CMake Error: Could not create named generator Visual Studio 14 2015 Win64
2
@ rahnema1 Спасибо, но, похоже, проблема в системе сборки CMake встроенной библиотеки C ++ в ящике криптоминизата, а не в самой Rust.
Андерс Касеорг
1
@Lembik Я получаю 404 от этой пасты.
Mego
1
@ChristianSievers Хороший вопрос. Это работает, но, кажется, немного медленнее (в 2 раза). Я не уверен, почему это не должно быть так хорошо, так что, возможно, CryptoMiniSat просто не был хорошо оптимизирован для такой дополнительной нагрузки.
Андерс Касеорг
9

Ржавчина, n ≈ 30 или 31 или 32

На моем ноутбуке (два ядра i5-6200U) это происходит через n = 1,…, 31 за 53 секунды, используя около 2,5 ГБ памяти или через n = 1,…, 32 за 105 секунд, используя около 5 ГиБ памяти. Скомпилируйте cargo build --releaseи запустите target/release/correlations.

src/main.rs

extern crate rayon;

type S = u32;
const S_BITS: u32 = 32;

fn cat(mut a: Vec<S>, mut b: Vec<S>) -> Vec<S> {
    if a.capacity() >= b.capacity() {
        a.append(&mut b);
        a
    } else {
        b.append(&mut a);
        b
    }
}

fn search(n: u32, i: u32, ss: Vec<S>) -> u32 {
    if ss.is_empty() {
        0
    } else if 2 * i + 1 > n {
        search_end(n, i, ss)
    } else if 2 * i + 1 == n {
        search2(n, i, ss.into_iter().flat_map(|s| vec![s, s | 1 << i]))
    } else {
        search2(n,
                i,
                ss.into_iter()
                    .flat_map(|s| {
                                  vec![s,
                                       s | 1 << i,
                                       s | 1 << n - i - 1,
                                       s | 1 << i | 1 << n - i - 1]
                              }))
    }
}

fn search2<SS: Iterator<Item = S>>(n: u32, i: u32, ss: SS) -> u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) << i + 1));
    let close = |s: S| {
        let x = (s ^ s >> shift) & mask;
        x & x.wrapping_sub(1) == 0
    };
    let (ssy, ssn) = ss.partition(|&s| close(s));
    let (cy, cn) = rayon::join(|| search(n, i + 1, ssy), || search(n, i + 1, ssn));
    cy + cn
}

fn search_end(n: u32, i: u32, ss: Vec<S>) -> u32 {
    if i >= n - 1 { 1 } else { search_end2(n, i, ss) }
}

fn search_end2(n: u32, i: u32, mut ss: Vec<S>) -> u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) << i + 1));
    let close = |s: S| {
        let x = (s ^ s >> shift) & mask;
        x & x.wrapping_sub(1) == 0
    };
    match ss.iter().position(|&s| close(s)) {
        Some(0) => {
            match ss.iter().position(|&s| !close(s)) {
                Some(p) => {
                    let (ssy, ssn) = ss.drain(p..).partition(|&s| close(s));
                    let (cy, cn) = rayon::join(|| search_end(n, i + 1, cat(ss, ssy)),
                                               || search_end(n, i + 1, ssn));
                    cy + cn
                }
                None => search_end(n, i + 1, ss),
            }
        }
        Some(p) => {
            let (ssy, ssn) = ss.drain(p..).partition(|&s| close(s));
            let (cy, cn) = rayon::join(|| search_end(n, i + 1, ssy),
                                       || search_end(n, i + 1, cat(ss, ssn)));
            cy + cn
        }
        None => search_end(n, i + 1, ss),
    }
}

fn main() {
    for n in 1..S_BITS + 1 {
        println!("{}: {}", n, search(n, 1, vec![0, 1]));
    }
}

Cargo.toml

[package]
name = "correlations"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rayon = "0.7.0"

Попробуйте онлайн!

У меня также есть немного более медленный вариант, использующий намного меньше памяти.

Андерс Касеорг
источник
Какие оптимизации вы использовали?
1
@Lembik Самая большая оптимизация, помимо того, что все делается с побитовой арифметикой в ​​скомпилированном языке, заключается в том, чтобы использовать только столько недетерминированности, сколько необходимо для определения префикса массива Y / N. Я выполняю рекурсивный поиск возможных префиксов массива Y / N, беря вектор возможных строк, достигающих этого префикса, но только строки, неисследованная середина которых заполнена нулями. Тем не менее, это все еще экспоненциальный поиск, и эти оптимизации только ускоряют его за счет полиномиальных факторов.
Андерс Касеорг
Это хороший ответ. Спасибо. Я надеюсь, что кто-то покопается в комбинаторике, чтобы значительно ускориться.
@Lembik Я исправил ошибку траты памяти, сделал больше микрооптимизации и добавил параллелизм. Пожалуйста, проведите повторную проверку, когда у вас появится шанс - я надеюсь увеличить свой счет на 1 или 2. Есть ли у вас идеи комбинаторного подхода для увеличения скорости? Я ничего не придумал.
Андерс Касеорг
1
@Lembik Нет формул, приведенных в записи OEIS. (Код Mathematica там также, похоже, использует грубую силу.) Если вы знаете об этом, вы можете рассказать им об этом.
Кристиан Сиверс
6

C ++ с использованием библиотеки BuDDy

Другой подход: иметь двоичную формулу (в виде двоичной диаграммы принятия решений ), которая принимает биты в Sкачестве входных данных и является истинной, если она дает некоторые фиксированные значения Yили Nв определенных выбранных положениях Если эта формула не является константой false, выберите свободную позицию и выполните рекурсивный тест, пытаясь одновременно Yи N. Если свободной позиции нет, мы нашли возможное выходное значение. Если формула является константой false, вернитесь назад.

Это работает относительно разумно, потому что существует так мало возможных значений, что мы можем часто возвращаться назад. Я попробовал аналогичную идею с SAT Solver, но это оказалось менее успешным.

#include<vector>
#include<iostream>
#include<bdd.h>

// does vars[0..i-1] differ from vars[n-i..n-1] in at least two positions?
bdd cond(int i, int n, const std::vector<bdd>& vars){
  bdd x1 { bddfalse };
  bdd xs { bddfalse };
  for(int k=0; k<i; ++k){
    bdd d { vars[k] ^ vars[n-i+k] };
    xs |= d & x1;
    x1 |= d;
  }
  return xs;
}

void expand(int i, int n, int &c, const std::vector<bdd>& conds, bdd x){
  if (x==bddfalse)
    return;
  if (i==n-2){
    ++c;
    return;
  }

  expand(i+1,n,c,conds, x & conds[2*i]);
  x &= conds[2*i+1];
  expand(i+1,n,c,conds, x);
}

int count(int n){
  if (n==1)   // handle trivial case
    return 1;
  bdd_setvarnum(n-1);
  std::vector<bdd> vars {};
  vars.push_back(bddtrue); // assume first bit is 1
  for(int i=0; i<n-1; ++i)
    if (i%2==0)            // vars in mixed order
      vars.push_back(bdd_ithvar(i/2));
    else
      vars.push_back(bdd_ithvar(n-2-i/2));
  std::vector<bdd> conds {};
  for(int i=n-1; i>1; --i){ // handle long blocks first
    bdd cnd { cond(i,n,vars) };
    conds.push_back( cnd );
    conds.push_back( !cnd );
  }
  int c=0;
  expand(0,n,c,conds,bddtrue);
  return c;
}

int main(void){
  bdd_init(20000000,1000000);
  bdd_gbc_hook(nullptr); // comment out to see GC messages
  for(int n=1; ; ++n){
    std::cout << n << " " << count(n) << "\n" ;
  }
}

Чтобы скомпилировать с Debian 8 (Джесси), установите libbdd-devи сделайте g++ -std=c++11 -O3 -o hb hb.cpp -lbdd. Может быть полезно увеличить первый аргумент bdd_initеще больше.

Кристиан Сиверс
источник
Это выглядит интересно. Что вы получите с этим?
@Lembik Я получаю 31 из 100 на очень старом оборудовании, которое не позволяет мне отвечать быстрее
Кристиан Сиверс
Любая помощь, которую вы можете дать о том, как скомпилировать это в Windows (например, используя cygwin), с благодарностью получена.
@Lembik Я не знаю о Windws, но github.com/fd00/yacp/tree/master/buddy кажется полезным для cygwin
Кристиан Сиверс
1
Вау, ладно, ты убедил меня, что мне нужно добавить эту библиотеку в мой инструментарий. Отлично сработано!
Андерс Касеорг
4

Клинго, n ≈ 30 или 31 34

Я был немного удивлен, увидев, что пять строк кода Clingo обогнали моё решение Rust методом «грубой силы» и подошли очень близко к решению Кристиана BuDDy - похоже, оно тоже побеждает с более высоким ограничением по времени.

corr.lp

{s(2..n)}.
d(K,I) :- K=1..n-2, I=1..n-K, s(I), not s(K+I).
d(K,I) :- K=1..n-2, I=1..n-K, not s(I), s(K+I).
a(K) :- K=1..n-2, {d(K,1..n-K)} 1.
#show a/1.

corr.sh

#!/bin/bash
for ((n=1;;n++)); do
    echo "$n $(clingo corr.lp --project -q -n 0 -c n=$n | sed -n 's/Models *: //p')"
done

участок

Андерс Касеорг
источник
Это круто! Из вашего графика видно, что решение BuDDy внезапно ухудшается. Есть идеи почему?
@Lembik Я недостаточно изучил BuDDy, чтобы быть уверенным, но, возможно, в этот момент у него заканчивается кеш?
Андерс Касеорг
Вот это да! Я думаю, что bdd_initможет помочь более высокое первое значение , или позволяющее увеличить таблицу узлов, вызвав bdd_setmaxincreaseзначение, значительно превышающее значение по умолчанию 50000. - Используете ли вы измененную версию моей программы?
Кристиан Сиверс
2
Я люблю твой график.
1
Вы получаете потрясающий прирост производительности, используя опцию --configuration=crafty( jumpyи trendyдайте аналогичные результаты).
Кристиан Сиверс
2

Пари / ГП , 23

По умолчанию Par / GP ограничивает размер стека до 8 МБ. Первая строка кода default(parisize, "4g")устанавливает это ограничение в 4 ГБ. Если он все еще дает стек переполнения, вы можете установить его на 8 ГБ.

default(parisize, "4g")
f(n) = #vecsort([[2 > hammingweight(bitxor(s >> (n-i) , s % 2^i)) | i <- [2..n-1]] | s <- [0..2^(n-1)]], , 8)
for(n = 1, 100, print(n " -> " f(n)))
alephalpha
источник
Достигает 22, а затем дает стеке потока.
Получает до 24 сейчас.
2

Clojure, 29 в 75 38 секунд, 30 в 80 и 31 в 165

Время работы от Intel i7 6700K , использование памяти менее 200 МБ.

project.clj (использует многопоточность com.climate / claypoole ):

(defproject tests "0.0.1-SNAPSHOT"
  :description "FIXME: write description"
  :dependencies [[org.clojure/clojure "1.8.0"]
                 [com.climate/claypoole "1.1.4"]]
  :javac-options ["-target" "1.6" "-source" "1.6" "-Xlint:-options"]
  :aot [tests.core]
  :main tests.core)

Исходный код:

(ns tests.core
  (:require [com.climate.claypoole :as cp]
            [clojure.set])
  (:gen-class))

(defn f [N]
  (let [n-threads   (.. Runtime getRuntime availableProcessors)
        mask-offset (- 31 N)
        half-N      (quot N 2)
        mid-idx     (bit-shift-left 1 half-N)
        end-idx     (bit-shift-left 1 (dec N))
        lower-half  (bit-shift-right 0x7FFFFFFF mask-offset)
        step        (bit-shift-left 1 12)
        bitcount
          (fn [n]
            (loop [i 0 result 0]
              (if (= i N)
                result
                (recur
                  (inc i)
                  (-> n
                      (bit-xor (bit-shift-right n i))
                      (bit-and (bit-shift-right 0x7FFFFFFF (+ mask-offset i)))
                      Integer/bitCount
                      (< 2)
                      (if (+ result (bit-shift-left 1 i))
                          result))))))]
    (->>
      (cp/upfor n-threads [start (range 0 end-idx step)]
        (->> (for [i      (range start (min (+ start step) end-idx))
                   :when  (<= (Integer/bitCount (bit-shift-right i mid-idx))
                              (Integer/bitCount (bit-and         i lower-half)))]
               (bitcount i))
             (into #{})))
      (reduce clojure.set/union)
      count)))

(defn -main [n]
  (let [n-iters 5]
    (println "Calculating f(n) from 1 to" n "(inclusive)" n-iters "times")
    (doseq [i (range n-iters)]
      (->> n read-string inc (range 1) (map f) doall println time)))
  (shutdown-agents)
  (System/exit 0))

Решение грубой силы, каждый поток проходит через подмножество диапазона (2 ^ 12 элементов) и создает набор целочисленных значений, которые указывают на обнаруженные шаблоны. Затем они «объединяются» вместе и, таким образом, рассчитывается различное количество. Я надеюсь, что код не слишком сложен, чтобы следовать даже при использовании макросы многопоточности . Я mainзапускаю тест несколько раз, чтобы разогреть JVM.

Обновление: перебирает только половину целых чисел, получает тот же результат из-за симметрии. Также пропускаются числа с большим количеством битов в нижней половине числа, поскольку они также создают дубликаты.

Готовый Uberjar ( v1 ) (3,7 МБ):

$ wget https://s3-eu-west-1.amazonaws.com/nikonyrh-public/misc/so-124424-v2.jar
$ java -jar so-124424-v2.jar 29
Calculating f(n) from 1 to 29 (inclusive) 5 times
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 41341.863703 msecs"
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 37752.118265 msecs"
(1 1 2 4 6 8 14 18 27 36 52 65 93 113 150 188 241 279 377 427 540 632 768 870 1082 1210 1455 1656 1974)
"Elapsed time: 38568.406528 msecs"
[ctrl+c]

Результаты на разных аппаратных средствах, ожидаемое время выполнения O(n * 2^n)?

i7-6700K  desktop: 1 to 29 in  38 seconds
i7-6820HQ laptop:  1 to 29 in  43 seconds
i5-3570K  desktop: 1 to 29 in 114 seconds

Вы можете легко сделать это однопоточным и избежать зависимости от третьих сторон, используя стандарт для:

(for [start (range 0 end-idx step)]
  ... )

Хорошо, встроенный pmap также существует, но у claypoole больше возможностей и настраиваемость.

NikoNyrh
источник
Да, это очень просто распространять. Если бы у вас было время переоценить мое решение, я уверен, что вы получите его до 30 сейчас. У меня нет дальнейших оптимизаций в поле зрения.
NikoNyrh
К сожалению, это не для 30. Истекшее время: 217150.87386 msecs
Ахаа, спасибо, что попробовали: D Возможно, было бы лучше подогнать кривую на этом и интерполировать ту, при которой десятичное значение затрачивается 120 секунд, но даже если это так, это хороший вызов.
NikoNyrh
1

Mathematica, n = 19

нажмите alt +. прервать и результат будет напечатан

k = 0;
For[n = 1, n < 1000, n++,
Z = Table[HammingDistance[#[[;; i]], #[[-i ;;]]], {i, Length@#}] & /@
Tuples[{0, 1}, n];
Table[If[Z[[i, j]] < 2, Z[[i, j]] = 0, Z[[i, j]] = 1], {i, 
Length@Z}, {j, n}];
k = Length@Union@Z]
Print["f(", n, ")=", k]
J42161217
источник
Я не могу запустить это, поэтому не могли бы вы объяснить, как избежать экспоненциального времени? 2 ^ 241 - это очень большое число!
Можете ли вы показать вывод кода?
1
Я имел ввиду f (n) ... исправлено
J42161217
1

Математика, 21

f [n_]: = длина @
     DeleteDuplicates @
      Транспонирование @
       Таблица [2> Tr @ IntegerDigits [#, 2] & / @ 
         BitXor [BitShiftRight [#, n - i], Mod [#, 2 ^ i]], {i, 1, 
         n - 1}] & @ Range [0, 2 ^ (n - 1)];
Do [Print [n -> f @ n], {n, Infinity}]

Для сравнения ответ Jenny_mathy дает n = 19на моем компьютере.

Самая медленная часть Tr@IntegerDigits[#, 2] &. Жаль, что Mathematica не имеет встроенного веса Хэмминга.


Если вы хотите проверить мой код, вы можете загрузить бесплатную пробную версию Mathematica .

alephalpha
источник
1

AC версия, используя встроенный popcount

Работает лучше clang -O3, но также работает, если у вас есть gcc.

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

unsigned long pairs(unsigned int n, unsigned long s) { 
  unsigned long result = 0;

  for(int d=1;d<=n;d++) { 
    unsigned long mx = 1 << d;
    unsigned long mask = mx - 1;

    unsigned long diff = (s >> (n - d)) ^ (s & mask);
    if (__builtin_popcountl(diff) <= 1)
      result |= mx;
  } 
  return result;

}

unsigned long f(unsigned long  n) { 
  unsigned long max = 1 << (n - 1);
#define BLEN (max / 2)
  unsigned char * buf = malloc(BLEN);
  memset(buf, 0, BLEN);
  unsigned long long * bufll = (void *) buf;

  for(unsigned long i=0;i<=max;i++) { 
    unsigned int r = pairs(n, i);
    buf[r / 8] |= 1 << (r % 8);
  } 

  unsigned long result = 0;

  for(unsigned long i=0;i<= max / 2 / sizeof(unsigned long long); i++) { 
    result += __builtin_popcountll(bufll[i]);
  } 

  free(buf);

  return result;
}

int main(int argc, char ** argv) { 
  unsigned int n = 1;

  while(1) { 
    printf("%d %ld\n", n, f(n));
    n++;
  } 
  return 0;
}
bartavelle
источник
Очень быстро доходит до 24, а затем заканчивается. Вам нужно увеличить лимит.
О боже, я забыл удалить код теста! Я
уберу
@Lembik должен быть исправлен сейчас
bartavelle
1

Haskell, (неофициальное n = 20)

Это просто наивный подход - пока без каких-либо оптимизаций. Я задавался вопросом, насколько хорошо это будет против других языков.

Как это использовать (если у вас есть платформа haskell ):

  • Вставьте код в один файл approx_corr.hs(или любое другое имя, соответственно измените следующие шаги)
  • Перейдите к файлу и выполните ghc approx_corr.hs
  • Бегать approx_corr.exe
  • Введите максимальный n
  • Отображается результат каждого вычисления, а также кумулятивное реальное время (в мс) до этой точки.

Код:

import Data.List
import Data.Time
import Data.Time.Clock.POSIX

num2bin :: Int -> Int -> [Int]
num2bin 0 _ = []
num2bin n k| k >= 2^(n-1) = 1 : num2bin (n-1)( k-2^(n-1))
           | otherwise  = 0: num2bin (n-1) k

genBinNum :: Int -> [[Int]]
genBinNum n = map (num2bin n) [0..2^n-1]

pairs :: [a] -> [([a],[a])]
pairs xs = zip (prefixes xs) (suffixes xs)
   where prefixes = tail . init . inits 
         suffixes = map reverse . prefixes . reverse 

hammingDist :: (Num b, Eq a) => ([a],[a]) -> b     
hammingDist (a,b) = sum $ zipWith (\u v -> if u /= v then 1 else 0) a b

f :: Int -> Int
f n = length $ nub $ map (map ((<=1).hammingDist) . pairs) $ genBinNum n
--f n = sum [1..n]

--time in milliseconds
getTime = getCurrentTime >>= pure . (1000*) . utcTimeToPOSIXSeconds >>= pure . round


main :: IO()
main = do 
    maxns <- getLine 
    let maxn = (read maxns)::Int
    t0 <- getTime 
    loop 1 maxn t0
     where loop n maxn t0|n==maxn = return ()
           loop n maxn t0
             = do 
                 putStrLn $ "fun eval: " ++ (show n) ++ ", " ++ (show $ (f n)) 
                 t <- getTime
                 putStrLn $ "time: " ++ show (t-t0); 
                 loop (n+1) maxn t0
flawr
источник
Код, по-видимому, не дает выходных данных во время работы. Это делает его немного сложным для тестирования.
Странно, компилируется без ошибок? Что произойдет, если вы попытаетесь скомпилировать программу main = putStrLn "Hello World!"?
flawr
Data.BitsМодуль может быть полезным. Для вашего основного цикла вы можете использовать что-то вроде main = do maxn <- getmax; t0 <- gettime; loop 1где loop n|n==maxn = return ()и loop n = do printresult n (f n); t <- gettime; printtime (t-t0); loop (n+1). getmaxНапример, getArgsможно использовать аргументы программы.
Кристиан Сиверс
@ChristianSievers Большое спасибо !!! Я задал этот вопрос на stackoverflow, я думаю, было бы здорово, если бы вы могли добавить это и туда!
flawr
Я не вижу, как ответить там. У вас уже есть подобная петля, и я ничего не сказал о том, чтобы потратить время: что у вас уже было здесь.
Кристиан Сиверс
1

Решение Haskell, использующее popCount и управляемый вручную параллелизм

Обобщение: ghc -rtsopts -threaded -O2 -fllvm -Wall foo.hs

(бросьте -llvm если это не работает)

Бегать : ./foo +RTS -N

module Main (main) where

import Data.Bits
import Data.Word
import Data.List
import qualified Data.IntSet as S 
import System.IO
import Control.Monad
import Control.Concurrent
import Control.Exception.Base (evaluate)

pairs' :: Int -> Word64 -> Int
pairs' n s = fromIntegral $ foldl' (.|.) 0 $ map mk [1..n]
  where mk d = let mask = 1 `shiftL` d - 1 
                   pc = popCount $! xor (s `shiftR` (n - d)) (s .&. mask)
               in  if pc <= 1 
                     then mask + 1 
                     else 0 

mkSet :: Int -> Word64 -> Word64 -> S.IntSet
mkSet n a b = S.fromList $ map (pairs' n) [a .. b]

f :: Int -> IO Int
f n 
   | n < 4 = return $ S.size $ mkSet n 0 mxbound
   | otherwise = do
        mvs <- replicateM 4 newEmptyMVar
        forM_ (zip mvs cpairs) $ \(mv,(mi,ma)) -> forkIO $ do
          evaluate (mkSet n mi ma) >>= putMVar mv
        set <- foldl' S.union S.empty <$> mapM readMVar mvs
        return $! S.size set
   where
     mxbound = 1 `shiftL` (n - 1)
     bounds = [0,1 `shiftL` (n - 3) .. mxbound]
     cpairs = zip bounds (drop 1 bounds)

main :: IO()
main = do
    hSetBuffering stdout LineBuffering
    mapM_ (f >=> print) [1..]
bartavelle
источник
Есть проблема с буферизацией, которая заключается в том, что я вообще не получаю вывод, если запускаю его из командной строки cygwim.
Я только что обновил свое решение, но я не знаю, сильно ли оно поможет.
bartavelle
@Lembik Не уверен, если это очевидно, но это должно быть скомпилировано -O3, и может быть быстрее с -O3 -fllvm...
bartavelle
(И все файлы сборки должны быть удалены перед перекомпиляцией, если не произошло изменение исходного кода)
bartavelle
@Lembik: я ввел параллелизм. Это должно быть немного быстрее.
Bartavelle
0

Python 2 + pypy, n = 22

Вот действительно простое решение Python в качестве своего рода базового теста.

import itertools
def hamming(A, B):
    n = len(A)
    assert(len(B) == n)
    return n-sum([A[i] == B[i] for i in xrange(n)])

def prefsufflist(P):
    n = len(P)
    return [hamming(P[:i], P[n-i:n]) for i in xrange(1,n+1)]

bound = 1
for n in xrange(1,25):
    booleans = set()
    for P in itertools.product([0,1], repeat = n):
        booleans.add(tuple(int(HD <= bound) for HD in prefsufflist(P)))
    print "n = ", n, len(booleans)

источник