Cuenta el número de secuencias de distancia de Hamming

9

La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes.

Dejado Pser una cadena binaria de longitud ny Tser una cadena binaria de longitud 2n-1. Podemos calcular las ndistancias de Hamming entre Py cada nsubcadena de longitud Ten orden de izquierda a derecha y ponerlas en una matriz (o lista).

Ejemplo de secuencia de distancia de Hamming

Deje P = 101y T = 01100. La secuencia de distancias de Hamming que obtienes de este par es 2,2,1.

Tarea

Para aumentar a npartir de n=1, considere todos los pares posibles de cadenas binarias Pde longitud ny Tlongitud 2n-1. Hay 2**(n+2n-1)tales pares y, por lo tanto, muchas secuencias de distancias de Hamming. Sin embargo, muchas de esas secuencias serán idénticas. La tarea es encontrar cuántos son distintos para cada uno n.

Su código debe generar un número por valor de n.

Puntuación

Su puntaje es el más alto nque alcanza su código en mi máquina en 5 minutos. El tiempo es para el tiempo total de funcionamiento, no el tiempo solo para eso n.

Quién gana

La persona con el puntaje más alto gana. Si dos o más personas terminan con el mismo puntaje, entonces es la primera respuesta que gana.

Ejemplos de respuestas

Para nde 1a 8las respuestas óptimas son 2, 9, 48, 297, 2040, 15425, 125232, 1070553.

Idiomas y bibliotecas

Puede usar cualquier idioma y bibliotecas disponibles que desee. Siempre que sea posible, sería bueno poder ejecutar su código, por lo tanto, si es posible, incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux.

Mi máquina Los tiempos se ejecutarán en mi máquina de 64 bits. Esta es una instalación estándar de ubuntu con 8 GB de RAM, procesador AMD FX-8350 de ocho núcleos y Radeon HD 4250. Esto también significa que necesito poder ejecutar su código.

Respuestas principales

  • 11 en C ++ por feersum. 25 segundos
  • 11 en C ++ por Andrew Epstein. 176 segundos
  • 10 en Javascript por Neil. 54 segundos
  • 9 en Haskell por nimi. 4 minutos y 59 segundos.
  • 8 en Javascript por fəˈnɛtɪk. 10 segundos.

fuente
.. algún idioma disponible * gratis ?
Stewie Griffin
código más rápido ? no es el algoritmo más rápido ? Sabes, la gente podría seguir el lenguaje con un intérprete muy rápido y hacer una diferencia significativa en el tiempo, pero la complejidad del tiempo es siempre la misma, por lo que de alguna manera lo hace justo.
Matthew Roh
Relacionado.
Martin Ender
44
@SIGSEGV fastest-codedeja más espacio para optimizaciones a través de optimizaciones de nivel de código y un buen algoritmo. Así que creo que faster-codees mejor que faster-algorithm.
Dada

Respuestas:

3

C ++ 11 (debería llegar a 11 o 12)

Por el momento esto es de un solo subproceso.

Compilar:

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
fuente
¡Consigue 11 en menos de 30 segundos!
En caso de que sea de interés: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, puntaje 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]]

Compilar con -O3. Tarda 6min35s en el hardware de mi computadora portátil de 6 años para funcionar n=9, por lo que tal vez sea menos de 5min en el hardware de referencia.

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

real  6m35.763s
user  6m27.690s
sys   0m5.025s
nimi
fuente
1
Portátil de 6 años? Maldición, ¡eso es una tecnología anticuada!
Matthew Roh
@SIGSEGV: tal vez esté desactualizado, pero además de contar el número de secuencias de distancia de Hamming, hace su trabajo bastante bien.
nimi
4

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

Explicación: Calcular n=10es difícil porque hay más de dos mil millones de pares y más de 26 mil millones de secuencias potenciales. Para acelerar las cosas, dividí el cálculo en 121 contenedores. Debido a que las secuencias son invariantes bajo el complemento bit a bit, puedo suponer sin pérdida de generalidad que el bit medio de Tes cero. Esto significa que puedo determinar el primer y el último elemento de la secuencia independientemente de los bits superior n-1e inferior n-1deT. Cada contenedor corresponde a un par diferente de primer y último elemento; Luego recorro todos los conjuntos posibles de bits superiores e inferiores que corresponden a cada bin y calculo los elementos restantes de la secuencia, finalmente contando las secuencias únicas para cada bin. Luego queda totalizar los 121 contenedores. Originalmente tardaba 45 horas, esto ahora se completó en poco menos de tres minutos y medio en mi AMD FX-8120. Editar: Gracias a @ChristianSievers por una aceleración del 50%. Salida completa:

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
fuente
Su código no da salida actualmente.
felipa
@felipa No estoy seguro de lo que quieres decir. Es una función anónima, por lo que la llama (quizás asignándola primero a una variable y luego llamando a la variable como si fuera una función) y la pasa ncomo parámetro. (Perdón por la mala elección del nombre del parámetro allí.)
Neil
La pregunta solicita un código que imprima la respuesta para n hasta el valor más alto que pueda obtener en 5 minutos. "Su código debería generar un número por valor de n".
felipa
Sería genial si su código funcionara desde n = 1 y generara el tiempo en cada etapa. De la pregunta "El tiempo es para el tiempo total de ejecución, no solo para ese n".
1
@Lembik Agregó un código de tiempo y también evitó el error n=1(no sé por qué se cuelga).
Neil
4

C ++, puntaje 10 11

Esta es una traducción de la respuesta de @ Neil a C ++, con una simple paralelización. n=9se completa en 0.4 segundos, n=10en 4.5 segundos y n=11en aproximadamente 1 minuto en mi Macbook Pro 2015. Además, gracias a @ChristianSievers. Debido a sus comentarios sobre la respuesta de @ Neil, noté algunas simetrías adicionales. Desde los 121 cubos originales (para n=10), hasta 66 cubos cuando se tiene en cuenta la reversión, he llegado a solo 21 cubos.

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

Use el siguiente script para ejecutar el código:

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

El resultado fue el siguiente: (El formato es 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 Tardó 42 minutos en calcular en un solo hilo, y dio un resultado de 7368225813.

Andrew Epstein
fuente
¿Cómo compilarías esto en ubuntu usando clang?
felipa
@felipa Creo que la respuesta es sudo apt-get install libiomp-dev.
Sería genial si su código funcionara desde n = 1 y generara el tiempo en cada etapa. De la pregunta "El tiempo es para el tiempo total de ejecución, no solo para ese n".
En lugar de volver a implementarlo, probablemente podría usarlo __builtin_popcount.
Neil
@Lembik: Haré los cambios más tarde hoy. @Neil: La función popcnt solo se evalúa en tiempo de compilación, y no sé cómo usarla __builtin_popcounten un contexto constexpr. Podría ir con la implementación ingenua y no afectaría el tiempo de ejecución.
Andrew Epstein
2

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

Ejecutar en la consola:

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

Pruébalo en línea!

O como un fragmento de pila:

El código preinicializa la matriz para hacer que sumar 1s a la matriz sea mucho más rápido

El código encuentra todas las secuencias de distancia de hamming y las trata como una base de números (entrada + 1), las usa para colocar 1s en una matriz. Como resultado, esto genera una matriz con n 1s donde n es el número de secuencias únicas de distancia de hamming. Finalmente, el número de 1s se cuenta usando array.reduce () para sumar todos los valores de la matriz.

Este código no podrá ejecutarse para una entrada de 10 cuando alcance los límites de memoria

Este código se ejecuta en tiempo O (2 ^ 2n) porque esa es la cantidad de elementos que genera.

fəˈnɛtɪk
fuente
1
Como era de esperar, intentar crear una matriz de elementos de 26 * 10 ^ 9 no funciona
fəˈnɛtɪk
n = 9Me lleva 5 minutos y 30 segundos usar node.js, por lo que es demasiado lento.
@Lembik n = 8originalmente tardó 24 segundos en mi PC, pero pude optimizar el código, por lo que n = 8tardó 6 segundos. Luego lo intenté n = 9y eso tomó 100 segundos.
Neil
@Neil ¡Deberías enviar una respuesta!
Sería genial si su código funcionara desde n = 1 y generara el tiempo en cada etapa. De la pregunta "El tiempo es para el tiempo total de ejecución, no solo para ese n".