Zählen Sie die Anzahl der Hamming-Distanzsequenzen

9

Der Hamming-Abstand zwischen zwei gleich langen Saiten ist die Anzahl der Positionen, an denen sich die entsprechenden Symbole unterscheiden.

Sei Peine binäre Zeichenfolge der Länge nund Teine binäre Zeichenfolge der Länge 2n-1. Wir können die nHamming-Abstände zwischen Pund jedem nTeilstring Tin der Reihenfolge von links nach rechts berechnen und sie in ein Array (oder eine Liste) einfügen .

Beispiel Hamming-Distanzsequenz

Lass P = 101und T = 01100. Die Reihenfolge der Hamming-Entfernungen, die Sie von diesem Paar erhalten, ist 2,2,1.

Aufgabe

Berücksichtigen Sie zum Erhöhen nab n=1alle möglichen Paare von binären Zeichenfolgen Pmit Länge nund TLänge 2n-1. Es gibt 2**(n+2n-1)solche Paare und damit viele Sequenzen von Hamming-Entfernungen. Viele dieser Sequenzen sind jedoch identisch. Die Aufgabe besteht darin, herauszufinden, wie viele für jeden unterschiedlich sind n.

Ihr Code sollte eine Zahl pro Wert von ausgeben n.

Ergebnis

Ihre Punktzahl ist die höchste, die nIhr Code in 5 Minuten auf meinem Computer erreicht. Das Timing ist für die Gesamtlaufzeit, nicht nur dafür n.

Wer gewinnt

Die Person mit der höchsten Punktzahl gewinnt. Wenn zwei oder mehr Personen die gleiche Punktzahl erzielen, gewinnt die erste Antwort.

Beispielantworten

Denn nvon 1bis zu 8den optimalen Antworten sind 2, 9, 48, 297, 2040, 15425, 125232, 1070553.

Sprachen und Bibliotheken

Sie können jede verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Wenn möglich, ist es gut, wenn Sie Ihren Code ausführen können. Geben Sie daher bitte eine vollständige Erklärung an, wie Sie Ihren Code unter Linux ausführen / kompilieren können, wenn dies überhaupt möglich ist.

Mein Computer Die Timings werden auf meinem 64-Bit-Computer ausgeführt. Dies ist eine Standard-Ubuntu-Installation mit 8 GB RAM, AMD FX-8350 Eight-Core-Prozessor und Radeon HD 4250. Dies bedeutet auch, dass ich Ihren Code ausführen kann.

Führende Antworten

  • 11 in C ++ von feersum. 25 Sekunden.
  • 11 in C ++ von Andrew Epstein. 176 Sekunden.
  • 10 in Javascript von Neil. 54 Sekunden.
  • 9 in Haskell von Nimi. 4 Minuten und 59 Sekunden.
  • 8 in Javascript von fəˈnɛtɪk. 10 Sekunden.

quelle
.. irgendwelche verfügbaren freien * Sprachen?
Stewie Griffin
schnellster Code ? nicht der schnellste Algorithmus ? Wissen Sie, die Leute könnten mit einem verdammt schnellen Dolmetscher mit der Sprache arbeiten und einen signifikanten Unterschied in der Zeit machen, aber die zeitliche Komplexität ist immer gleich, also macht es sie etwas fair.
Matthew Roh
Verbunden.
Martin Ender
4
@SIGSEGV fastest-codeBlätter mehr Raum für Optimierungen durch beide Code - Ebene Optimierungen und einem guten Algorithmus. Also ich denke das faster-codeist besser als faster-algorithm.
Dada

Antworten:

3

C ++ 11 (sollte auf 11 oder 12 kommen)

Im Moment ist dies Single-Threaded.

Kompilieren:

g++ -std=c++11 -O2 -march=native feersum.cpp
#include <iostream>
#include <unordered_set>
#include <vector>
#include <unordered_map>
#include <string.h>

using seq = uint64_t;
using bitvec = uint32_t;
using seqset = std::unordered_set<seq>;
using std::vector;

#define popcount __builtin_popcount
#define MAX_N_BITS 4

bitvec leading(bitvec v, int n) {
    return v & ((1U << n) - 1);
}
bitvec trailing(bitvec v, int n, int total) {
    return v >> (total - n);
}

bitvec maxP(int n) {
    return 1 << (n - 1);  // ~P, ~T symmetry
}

void prefixes(int n, int pre, int P, seqset& p) {
    p.clear();
    for (bitvec pref = 0; pref < (1U << pre); pref++) {
        seq s = 0;
        for (int i = 0; i < pre; i++) {
            seq ham = popcount(trailing(pref, pre - i, pre) ^ leading(P, pre - i));
            s |= ham << i * MAX_N_BITS;
        }
        p.insert(s);
    }
}



vector<seqset> suffixes(int n, int suf, int off) {
    vector<seqset> S(maxP(n));
    for (bitvec P = 0; P < maxP(n); P++) {
        for (bitvec suff = 0; suff < (1U << suf); suff++) {
            seq s = 0;
            for (int i = 0; i < suf; i++) {
                seq ham = popcount(leading(suff, i + 1) ^ trailing(P, i + 1, n));
                s |= ham << (off + i) * MAX_N_BITS;
            }
            S[P].insert(s);
        }
    }
    return S;
}



template<typename T> 
void mids(int n, int npre, int nsuf, int mid, bitvec P, T& S, const seqset& pre) {
    seq mask = (1ULL << (npre + 1) * MAX_N_BITS) - 1;
    for(bitvec m = 0; m < 1U << mid; m++) {
        int pc = popcount(P ^ m);
        if(pc * 2 > n) continue; // symmetry of T -> ~T : replaces x with n - x
        seq s = (seq)pc << npre * MAX_N_BITS;
        for(int i = 0; i < npre; i++)
            s |= (seq)popcount(trailing(P, n - npre + i, n) ^ leading(m, n - npre + i)) << i * MAX_N_BITS;
        for(int i = 0; i < nsuf; i++)
            s |= (seq)popcount(leading(P, mid - 1 - i) ^ trailing(m, mid - 1 - i, mid)) << (npre + 1 + i) * MAX_N_BITS;
        for(seq a: pre)
            S[(s + a) & mask].insert(P | (s + a) << n);
    }
}

uint64_t f(int n) {
    if (n >= 1 << MAX_N_BITS) {
        std::cerr << "n too big";
        exit(1);
    }
    int tlen = 2*n - 1;
    int mid = n;
    int npre = (tlen - mid) / 2;
    if(n>6) --npre;
    int nsuf = tlen - npre - mid;
    seqset preset;
    auto sufs = suffixes(n, nsuf, npre + 1);
    std::unordered_map<seq, std::unordered_set<uint64_t>> premid;
    for(bitvec P = 0; P < maxP(n); P++) {
        prefixes(n, npre, P, preset);
        mids(n, npre, nsuf, mid, P, premid, preset);
    }
    uint64_t ans = 0;
    using counter = uint8_t;
    vector<counter> found((size_t)1 << nsuf * MAX_N_BITS);
    counter iz = 0;
    for(auto& z: premid) {
        ++iz;
        if(!iz) {
            memset(&found[0], 0, found.size() * sizeof(counter));
            ++iz;
        }
        for(auto& pair: z.second) {
            seq s = pair >> n;
            uint64_t count = 0;
            bitvec P = pair & (maxP(n) - 1);
            for(seq t: sufs[P]) {
                seq suff = (s + t) >> (npre + 1) * MAX_N_BITS;
                if (found[suff] != iz) {
                    ++count;
                    found[suff] = iz;
                }
            }
            int middle = int(s >> npre * MAX_N_BITS) & ~(~0U << MAX_N_BITS);
            ans += count << (middle * 2 != n);
        }
    }

    return ans;
}

int main() {
    for (int i = 1; ; i++)
        std::cout << i << ' ' << f(i) << std::endl;
}
Feersum
quelle
In weniger als 30 Sekunden auf 11!
Falls es von Interesse ist:feersum.cpp:111:61: warning: shifting a negative signed value is undefined [-Wshift-negative-value] int middle = int(s >> npre * MAX_N_BITS) & ~(~0 << MAX_N_BITS);
5

Haskell, Punktzahl 9

import Data.Bits
import Data.List
import qualified Data.IntSet as S

main = mapM_ (print . S.size . S.fromList . hd) [1..9]

hd :: Int -> [Int]
hd n = [foldl' (\s e->s*m+e) 0 [popCount $ xor p (shiftR t i .&. m)|i<-[(0::Int)..n-1]] | let m=2^n-1,p<-[(0::Int)..2^n-1],t<-[(0::Int)..2^(2*n-1)-1]]

Kompilieren mit -O3. Auf meiner 6 Jahre alten Laptop-Hardware dauert es 6 Minuten 35 Sekunden, bis n=9sie ausgeführt wird. Auf der Referenzhardware sind es vielleicht weniger als 5 Minuten .

> time ./113785
2
9
48
297
2040
15425
125232
1070553
9530752

real  6m35.763s
user  6m27.690s
sys   0m5.025s
Nimi
quelle
1
6 Jahre Laptop? Verdammt, das ist eine veraltete Technologie!
Matthew Roh
@SIGSEGV: Vielleicht ist es veraltet, aber abgesehen von der Anzahl der Hamming-Distanzsequenzen macht es seine Arbeit ganz gut.
Nimi
4

JavaScript, Punktzahl 10

findHamming = m => { 
    if (m < 2) return 2;
    let popcnt = x => x && (x & 1) + popcnt(x >> 1);
    let a = [...Array(1 << m)].map((_,i) => popcnt(i));
    let t = 0;
    let n = (1 << m) - 1;
    for (let c = 0; c <= m; c++) {
        for (let g = 0; g <= c; g++) {
            let s = new Set;
            for (let i = 1 << m; i--; ) {
                for (let j = 1 << (m - 1); j--; ) {
                    if (a[i ^ j + j] != c) continue;
                    for (let k = 1 << m - 1; k--; ) {
                        if (a[i ^ k] != g) continue;
                        let f = j << m | k;
                        let h = 0;
                        for (l = m - 1; --l; ) h = h * (m + 1) + a[i ^ f >> l & n];
                        s.add(h);
                    }
                }
            }
            t += s.size * (g < c ? 2 : 1);
        }
    }
    return t;
};
let d = Date.now(); for (let m = 1; m < 11; m++) console.log(m, findHamming(m), Date.now() - d);

Erklärung: Die Berechnung n=10ist schwierig, da es über zwei Milliarden Paare und über 26 Milliarden mögliche Sequenzen gibt. Um die Sache zu beschleunigen, habe ich die Berechnung in 121 Fächer aufgeteilt. Da die Sequenzen unter bitweisem Komplement invariant sind, kann ich ohne Verlust der Allgemeinheit annehmen, dass das mittlere Bit von TNull ist. Dies bedeutet, dass ich das erste und das letzte Element der Sequenz unabhängig von den oberen n-1und unteren n-1Bits von bestimmen kannT. Jeder Behälter entspricht einem anderen Paar von ersten und letzten Elementen; Ich durchlaufe dann alle möglichen Sätze von oberen und unteren Bits, die jedem Bin entsprechen, und berechne die verbleibenden Elemente der Sequenz, wobei ich schließlich die eindeutigen Sequenzen für jeden Bin zähle. Es bleiben dann insgesamt 121 Behälter. Ursprünglich dauerte es 45 Stunden, jetzt war es auf meinem AMD FX-8120 in etwas weniger als dreieinhalb Minuten erledigt. Bearbeiten: Vielen Dank an @ChristianSievers für eine 50% ige Beschleunigung. Volle Ausgabe:

1 2 0
2 9 1
3 48 1
4 297 2
5 2040 7
6 15425 45
7 125232 391
8 1070553 1844
9 9530752 15364
10 86526701 153699
Neil
quelle
Ihr Code gibt derzeit keine Ausgabe aus.
Felipa
@felipa Nicht sicher, was du meinst. Da es sich um eine anonyme Funktion handelt, rufen Sie sie auf (möglicherweise indem Sie sie zuerst einer Variablen zuweisen und dann die Variable aufrufen, als wäre sie eine Funktion) und übergeben sie nals Parameter. (Entschuldigung für die schlechte Wahl des Parameternamens dort.)
Neil
In der Frage wird nach einem Code gefragt, der die Antwort für n bis zu dem höchsten Wert ausgibt, den es in 5 Minuten erreichen kann. "Ihr Code sollte eine Zahl pro Wert von n ausgeben."
Felipa
Es wäre großartig, wenn Ihr Code von n = 1 aufgearbeitet und das Timing in jeder Phase ausgegeben würde. Aus der Frage "Das Timing ist für die Gesamtlaufzeit, nicht die Zeit nur für das n."
1
@Lembik Timing-Code hinzugefügt und auch Fehler n=1umgangen (weiß nicht ohne weiteres, warum es hängt).
Neil
4

C ++, Punktzahl 10 11

Dies ist eine Übersetzung von @ Neils Antwort in C ++ mit einer einfachen Parallelisierung. n=9Fertigstellung in 0,4 Sekunden, n=10in 4,5 Sekunden und n=11in ungefähr 1 Minute auf meinem 2015 Macbook Pro. Vielen Dank auch an @ChristianSievers. Aufgrund seiner Kommentare zu @ Neils Antwort bemerkte ich einige zusätzliche Symmetrien. Von den ursprünglichen 121 Eimern (für n=10) bis zu 66 Eimern, wenn die Umkehrung berücksichtigt wird, habe ich nur noch 21 Eimer.

#include <iostream>
#include <cstdint>
#include <unordered_set>
#include <thread>
#include <future>
#include <vector>

using namespace std;

constexpr uint32_t popcnt( uint32_t v ) {
    uint32_t c = v - ( ( v >> 1 ) & 0x55555555 );
    c = ( ( c >> 2 ) & 0x33333333 ) + ( c & 0x33333333 );
    c = ( ( c >> 4 ) + c ) & 0x0F0F0F0F;
    c = ( ( c >> 8 ) + c ) & 0x00FF00FF;
    c = ( ( c >> 16 ) + c ) & 0x0000FFFF;
    return c;
}

template<uint32_t N>
struct A {
    constexpr A() : arr() {
        for( auto i = 0; i != N; ++i ) {
            arr[i] = popcnt( i );
        }
    }
    uint8_t arr[N];
};

uint32_t n = ( 1 << M ) - 1;
constexpr auto a = A < 1 << M > ();

uint32_t work( uint32_t c, uint32_t g, uint32_t mult ) {
    unordered_set<uint64_t> s;
    // Empirically derived "optimal" value
    s.reserve( static_cast<uint32_t>( pow( 5, M ) ) );

    for( int i = ( 1 << M ) - 1; i >= 0; i-- ) {
        for( uint32_t j = 1 << ( M - 1 ); j--; ) {
            if( a.arr[i ^ j + j] != c ) {
                continue;
            }

            for( uint32_t k = 1 << ( M - 1 ); k--; ) {
                if( a.arr[i ^ k] != g ) {
                    continue;
                }

                uint64_t f = j << M | k;
                uint64_t h = 0;

                for( uint32_t l = M - 1; --l; ) {
                    h = h * ( M + 1 ) + a.arr[i ^ ( f >> l & n )];
                }

                s.insert( h );
            }
        }
    }

    return s.size() * mult;

}

int main() {
    auto t1 = std::chrono::high_resolution_clock::now();

    if( M == 1 ) {
        auto t2 = std::chrono::high_resolution_clock::now();
        auto seconds = chrono::duration_cast<chrono::milliseconds>( t2 - t1 ).count() / 1000.0;
        cout << M << ": " << 2 << ", " << seconds << endl;
        return 0;
    }

    uint64_t t = 0;
    vector<future<uint32_t>> my_vector;

    if( ( M & 1 ) == 0 ) {
        for( uint32_t c = 0; c <= M / 2; ++c ) {
            for( uint32_t g = c; g <= M / 2; ++g ) {
                uint32_t mult = 8;

                if( c == M / 2 && g == M / 2 ) {
                    mult = 1;
                } else if( g == c || g == M / 2 ) {
                    mult = 4;
                }

                my_vector.push_back( async( work, c, g, mult ) );
            }

        }

        for( auto && f : my_vector ) {
            t += f.get();
        }

    } else {
        for( uint32_t c = 0; c <= ( M - 1 ) / 2; ++c ) {
            for( uint32_t g = c; g <= M - c; ++g ) {
                uint32_t mult = 4;

                if( g == c || g + c == M ) {
                    mult = 2;
                }

                my_vector.push_back( async( work, c, g, mult ) );
            }

        }

        for( auto && f : my_vector ) {
            t += f.get();
        }

    }

    auto t2 = std::chrono::high_resolution_clock::now();
    auto seconds = chrono::duration_cast<chrono::milliseconds>( t2 - t1 ).count() / 1000.0;
    cout << M << ": " << t << ", " << seconds << endl;
    return 0;
}

Verwenden Sie das folgende Skript, um den Code auszuführen:

#!/usr/bin/env bash

for i in {1..10}
do
    clang++ -std=c++14 -march=native -mtune=native -Ofast -fno-exceptions -DM=$i hamming3.cpp -o hamming
    ./hamming
done

Die Ausgabe war wie folgt: (Das Format ist M: result, seconds)

1: 2, 0
2: 9, 0
3: 48, 0
4: 297, 0
5: 2040, 0
6: 15425, 0.001
7: 125232, 0.004
8: 1070553, 0.029
9: 9530752, 0.419
10: 86526701, 4.459
11: 800164636, 58.865

n=12 Die Berechnung eines einzelnen Threads dauerte 42 Minuten und ergab ein Ergebnis von 7368225813.

Andrew Epstein
quelle
Wie würden Sie dies in Ubuntu mit clang kompilieren?
Felipa
@felipa Ich denke die Antwort ist sudo apt-get install libiomp-dev.
Es wäre großartig, wenn Ihr Code von n = 1 aufgearbeitet und das Timing in jeder Phase ausgegeben würde. Aus der Frage "Das Timing ist für die Gesamtlaufzeit, nicht die Zeit nur für das n."
Anstatt es erneut zu implementieren, könnten Sie es wahrscheinlich nur verwenden __builtin_popcount.
Neil
@Lembik: Ich werde die Änderungen später heute vornehmen. @Neil: Die popcnt-Funktion wird nur zur Kompilierungszeit ausgewertet, und ich weiß nicht, wie sie __builtin_popcountin einem constexpr-Kontext verwendet werden soll. Ich könnte mit der naiven Implementierung gehen und es würde die Laufzeit nicht beeinflussen.
Andrew Epstein
2

JavaScript 2,9,48,297,2040,15425,125232,1070553,9530752

In der Konsole ausführen:

console.time("test");
h=(w,x,y,z)=>{retVal=0;while(x||y){if(x%2!=y%2)retVal++;x>>=1;y>>=1}return retVal*Math.pow(w+1,z)};
sum=(x,y)=>x+y;
for(input=1;input<10;input++){
  hammings=new Array(Math.pow(input+1,input));
  for(i=1<<(input-1);i<1<<input;i++){
    for(j=0;j<1<<(2*input);j++){
      hamming=0;
      for(k=0;k<input;k++){
        hamming+=(h(input,(j>>k)%(1<<input),i,k));
      }
      hammings[hamming]=1;
    }
  }
  console.log(hammings.reduce(sum));
}
console.timeEnd("test");

Probieren Sie es online aus!

Oder als Stack-Snippet:

Der Code initialisiert das Array vor, um das Hinzufügen von Einsen zum Array erheblich zu beschleunigen

Der Code findet alle Hamming-Distanzsequenzen und behandelt sie als Zahlenbasis (Eingabe + 1). Er verwendet sie, um 1s in einem Array zu platzieren. Infolgedessen wird ein Array mit den n 1s erzeugt, wobei n die Anzahl der eindeutigen Hamming-Distanzsequenzen ist. Schließlich wird die Anzahl der Einsen mit array.reduce () gezählt, um alle Werte im Array zu summieren.

Dieser Code kann nicht für die Eingabe von 10 ausgeführt werden, da er die Speichergrenzen erreicht

Dieser Code wird in O (2 ^ 2n) ausgeführt, da so viele Elemente generiert werden.

fəˈnɛtɪk
quelle
1
Es ist nicht überraschend, dass der Versuch, ein 26 * 10 ^ 9-Elementarray zu erstellen, nicht funktioniert
fəˈnɛtɪk
n = 9Die Verwendung von node.js dauert 5 Minuten und 30 Sekunden, ist also einfach zu langsam.
@Lembik dauerte n = 8ursprünglich 24 Sekunden auf meinem PC, aber ich konnte den Code so optimieren, dass es n = 86 Sekunden dauerte. Ich habe es dann versucht n = 9und das hat 100 Sekunden gedauert.
Neil
@Neil Du solltest eine Antwort einreichen!
Es wäre großartig, wenn Ihr Code von n = 1 aufgearbeitet und das Timing in jeder Phase ausgegeben würde. Aus der Frage "Das Timing ist für die Gesamtlaufzeit, nicht die Zeit nur für das n."