Hitung jumlah urutan jarak Hamming

9

The Hamming jarak antara dua string dengan panjang yang sama adalah jumlah posisi di mana yang sesuai simbol yang berbeda.

Membiarkan Pmenjadi string biner panjang ndan Tmenjadi string biner panjang 2n-1. Kita dapat menghitung njarak Hamming antara Pdan setiap nsubstring Tdengan panjang dari kiri ke kanan dan menempatkannya ke dalam array (atau daftar).

Contoh urutan jarak Hamming

Biarkan P = 101dan T = 01100. Urutan jarak Hamming yang Anda dapatkan dari pasangan ini adalah 2,2,1.

Tugas

Untuk meningkatkan nmulai dari n=1, pertimbangkan semua pasangan yang mungkin dari string biner Ppanjang ndan Tpanjang 2n-1. Ada 2**(n+2n-1)pasangan seperti itu dan karenanya banyak urutan jarak Hamming. Namun banyak dari sekuens tersebut akan identik. Tugasnya adalah menemukan berapa banyak yang berbeda untuk masing-masing n.

Kode Anda harus menampilkan satu nomor per nilai n.

Skor

Skor Anda adalah tertinggi yang dicapai nkode Anda di mesin saya dalam 5 menit. Waktunya adalah total waktu berjalan, bukan hanya waktu untuk itu n.

Yang menang

Orang dengan skor tertinggi menang. Jika dua orang atau lebih berakhir dengan skor yang sama maka itu adalah jawaban pertama yang menang.

Contoh jawaban

Untuk ndari 1ke 8jawaban optimal adalah 2, 9, 48, 297, 2040, 15425, 125232, 1070553.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa dan perpustakaan yang tersedia yang Anda suka. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda, jadi harap sertakan penjelasan lengkap tentang cara menjalankan / mengkompilasi kode Anda di Linux jika memungkinkan.

Mesin Saya Pengaturan waktu akan dijalankan pada mesin 64-bit saya. Ini adalah instalasi ubuntu standar dengan RAM 8GB, Prosesor Delapan-Core AMD FX-8350 dan Radeon HD 4250. Ini juga berarti saya harus dapat menjalankan kode Anda.

Memimpin jawaban

  • 11 dalam C ++ oleh feersum. 25 detik.
  • 11 dalam C ++ oleh Andrew Epstein. 176 detik.
  • 10 di Javascript oleh Neil. 54 detik.
  • 9 di Haskell oleh nimi. 4 menit dan 59 detik.
  • 8 di Javascript oleh fəˈnɛtɪk. 10 detik.

sumber
.. ada bahasa * gratis yang tersedia ?
Stewie Griffin
kode tercepat ? bukan algoritma tercepat ? Anda tahu, orang bisa menggunakan bahasa dengan penerjemah cepat dan membuat perbedaan waktu yang signifikan, tetapi kompleksitas waktu selalu sama, jadi itu membuatnya adil.
Matthew Roh
Terkait
Martin Ender
4
@SIGSEGV fastest-codemenyisakan lebih banyak ruang untuk optimasi melalui optimasi level kode dan algoritma yang baik. Jadi saya pikir itu faster-codelebih baik daripada faster-algorithm.
Dada

Jawaban:

3

C ++ 11 (harus mencapai 11 atau 12)

Saat ini single-threaded.

Untuk mengkompilasi:

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
sumber
Dapatkan hingga 11 dalam waktu kurang dari 30 detik!
Dalam hal ini menarik: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, skor 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]]

Kompilasi dengan -O3. Dibutuhkan 6min35s pada perangkat keras laptop saya yang berumur 6 tahun untuk menjalankannya n=9, jadi mungkin itu di bawah 5 menit pada perangkat keras referensi.

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

real  6m35.763s
user  6m27.690s
sys   0m5.025s
nimi
sumber
1
Laptop 6 tahun? Sial, itu beberapa teknologi yang ketinggalan jaman!
Matius Roh
@ SIGSEGV: mungkin sudah ketinggalan zaman, tetapi selain menghitung jumlah urutan jarak Hamming, ia melakukan tugasnya dengan cukup baik.
nimi
4

JavaScript, skor 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);

Penjelasan: Menghitung n=10sulit karena ada lebih dari dua miliar pasangan dan lebih dari 26 miliar urutan potensial. Untuk mempercepat, saya membagi perhitungan menjadi 121 nampan. Karena urutannya tidak berubah di bawah komplemen bitwise, saya dapat mengasumsikan tanpa kehilangan keumuman bahwa bit tengah Tadalah nol. Ini berarti bahwa saya dapat menentukan elemen pertama dan terakhir dari urutan secara terpisah dari bit atas n-1dan bawahn-1T. Setiap nampan sesuai dengan sepasang elemen pertama dan terakhir yang berbeda; Saya kemudian loop melalui semua set kemungkinan bit atas dan bawah yang sesuai dengan masing-masing bin dan menghitung elemen yang tersisa dari urutan, akhirnya menghitung urutan unik untuk setiap bin. Itu kemudian tetap total 121 sampah. Awalnya memakan waktu 45 jam, ini sekarang selesai dalam waktu kurang dari tiga setengah menit pada AMD FX-8120 saya. Sunting: Terima kasih kepada @ChristianSievers untuk kecepatan 50%. Output penuh:

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
sumber
Kode Anda tidak memberikan hasil saat ini.
felipa
@felipa Tidak yakin apa yang Anda maksud. Ini adalah fungsi anonim, jadi Anda menyebutnya (mungkin dengan menugaskannya ke variabel terlebih dahulu dan kemudian memanggil variabel seolah-olah itu fungsi) dan meneruskannya nsebagai parameter. (Maaf untuk pilihan nama parameter yang salah di sana.)
Neil
Pertanyaan itu meminta kode yang mencetak jawaban untuk n hingga nilai tertinggi yang bisa didapat dalam 5 menit. "Kode Anda harus menampilkan satu angka per nilai n."
felipa
Akan lebih bagus jika kode Anda bekerja dari n = 1 dan menghasilkan waktu pada setiap tahap. Dari pertanyaan "Waktu adalah untuk total waktu berjalan, bukan waktu hanya untuk itu n."
1
@Lembik Menambahkan kode waktu dan juga memperbaiki bug untuk n=1(tidak tahu mengapa hang).
Neil
4

C ++, skor 10 11

Ini adalah terjemahan dari jawaban @ Neil ke dalam C ++, dengan beberapa paralelisasi sederhana. n=9selesai dalam 0,4 detik, n=10dalam 4,5 detik, dan n=11dalam sekitar 1 menit pada 2015 Macbook Pro saya. Juga, terima kasih kepada @ChristianSievers. Karena komentarnya pada jawaban @ Neil, saya perhatikan beberapa simetri tambahan. Dari 121 ember asli (untuk n=10), hingga 66 ember saat menghitung pembalikan, saya turun menjadi hanya 21 ember.

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

Gunakan skrip berikut untuk menjalankan kode:

#!/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

Outputnya adalah sebagai berikut: (Formatnya adalah 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 butuh 42 menit untuk menghitung pada utas tunggal, dan memberikan hasil 7368225813.

Andrew Epstein
sumber
Bagaimana Anda mengkompilasi ini di ubuntu menggunakan dentang?
felipa
@felipa saya pikir jawabannya sudo apt-get install libiomp-dev.
Akan lebih bagus jika kode Anda bekerja dari n = 1 dan menghasilkan waktu pada setiap tahap. Dari pertanyaan "Waktu adalah untuk total waktu berjalan, bukan waktu hanya untuk itu n."
Daripada menerapkannya kembali, Anda mungkin bisa menggunakannya __builtin_popcount.
Neil
@Lembik: Saya akan melakukan perubahan hari ini. @ Neil: Fungsi popcnt hanya dievaluasi pada waktu kompilasi, dan saya tidak tahu bagaimana menggunakannya __builtin_popcountdalam konteks constexpr. Saya bisa pergi dengan implementasi naif dan itu tidak akan mempengaruhi waktu berjalan.
Andrew Epstein
2

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

Jalankan di konsol:

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

Cobalah online!

Atau sebagai Cuplikan Stack:

Kode menginisialisasi array untuk membuat menambahkan 1 ke array lebih cepat

Kode menemukan semua urutan jarak hamming dan memperlakukan mereka sebagai basis angka (input + 1), menggunakannya untuk menempatkan 1s dalam sebuah array. Sebagai hasilnya, ini menghasilkan array dengan n 1s di mana n adalah jumlah urutan jarak hamming yang unik. Akhirnya, jumlah 1s dihitung menggunakan array.reduce () untuk menjumlahkan semua nilai dalam array.

Kode ini tidak akan dapat berjalan untuk input 10 karena menyentuh batas memori

Kode ini berjalan dalam O (2 ^ 2n) waktu karena itulah berapa banyak elemen yang dihasilkannya.

fəˈnɛtɪk
sumber
1
Tidak mengherankan, mencoba membuat elemen array 26 * 10 ^ 9 tidak berfungsi
fəˈnɛtɪk
n = 9membutuhkan waktu 5 menit dan 30 detik untuk saya menggunakan node.js jadi terlalu lambat.
@Lembik n = 8awalnya membutuhkan 24 detik pada PC saya, tetapi saya dapat mengoptimalkan kode sehingga n = 8butuh 6 detik. Saya kemudian mencoba n = 9dan itu butuh 100 detik.
Neil
@Neil Anda harus mengirimkan jawaban!
Akan lebih bagus jika kode Anda bekerja dari n = 1 dan menghasilkan waktu pada setiap tahap. Dari pertanyaan "Waktu adalah untuk total waktu berjalan, bukan waktu hanya untuk itu n."