12

Recentemente fiz um teste online bastante interessante (da Codility). Infelizmente esse teste era cronometrado (30 minutos) e acabei não conseguindo chegar a uma solução satisfatória para uma das perguntas.

Contexto

Um número decimal pode ser visto como uma sequência de bits.

Exemplos:

955 = 1110111011
10 =  1010
627 = 1001110011
102 = 1100110
104 = 1101000

Essas strings de bits podem ser periódicas, ou seja, compostas por sucessivas repetições de substrings de bits.

Update

Da definição oficial do problema. Dada uma String S composta por Q bits. O período P é o menor inteiro positivo tal que:

  • P ≤ Q / 2 e
  • S[K] = S[K+P] para todo K, onde 0 ≤ K < Q − P.

Exemplos:

O binário 1010 é composto da substring 10 repetida duas vezes. O binário 1110111011 é composto pela substring 1110 repetida duas vezes e meia (pois o 11 sobra no final após duas repetições). Já o decimal 1101000 não é periódico (não existe uma substring com Q / 2 que forme um período).

O período de uma string binária nada mais é do que o tamanho da sequência de bits que se repete.

955-> 1110 (período 4)
10 ->  10  (período 2)
627 -> 10011 (período 5)
102 -> 1100 (4, mas esse não é um período válido pois `P > Q / 2`)
104 -> não tem

O problema

Dado um inteiro n, escrever um algoritmo que retorne o período da string binária de n ou -1 caso a string binária não seja periódica:

public int periodo(int n) 

Complexidade esperada

  • Pior caso temporal O(log(N)²)
  • Pior caso espacial O(log(N))

Uma possível solução subótima de força bruta

Eu perdi muito tempo nessa pergunta e nem sei se consegui chegar a uma solução naive correta (meu feeling era que essa era uma pergunta de manipulação de bits, no fim acabei usando Integer.toBinaryString(n) e indo pela força bruta).

Acabei fazendo o seguinte:

  • Gerar cada substring candidata a ser um período de n. Começando de 1 até [tamanho da string de bits de n] / 2

     final String binaryString = Integer.toBinaryString(n);
     for (int i = 1; i < binaryString.length() / 2; i++) {
         final String period = binaryString.substring(0, i);
    
  • Para cada uma dessas substrings, verificar se a string principal poderia ser gerada a partir de repetições da substring (usando um loop e comparando caractere a caractere):

    private boolean checkSolution(String binaryString, String period) {
        boolean isPeriod = true;
        for (int i = 0; isPeriod && i < binaryString.length(); i++) {
            if (binaryString.charAt(i) != period.charAt(i % period.length())) {
                isPeriod = false;
            }
        }
    
        return isPeriod;
    }
    
  • Retornar o menor período encontrado (ou -1 que é o default se nenhum período foi encontrado).

Porém não fiquei satisfeito com essa solução... Principalmente por que ela é basicamente quadrática em relação a Q, passando bem longe da complexidade temporal esperada.

Minha pergunta é, alguém já resolveu esse problema e conhece um algoritmo melhor? Não precisa ser em Java, um pseudo-código ou implementação em qualquer linguagem está ok.

14
  • 2
    I call shenaningans! 110100 é a sequência 110100 repetida exatamente uma vez! Commented 6/05/2014 às 22:34
  • 1
    Esse problema me é vagamente familiar... Tenho certeza que existe uma solução envolvendo autômato finito, e é bem semelhante ao problema de casar uma string com uma expressão regular. Vou tentar me recordar melhor, mas já fica a dica.
    – mgibsonbr
    Commented 6/05/2014 às 22:48
  • 1
    É, também pensei em Fecho de Kleene, mas não consegui pensar em nenhum algoritmo para inferir o alfabeto dada a palavra, ainda mais por permitir casos de composição parcial como a do 905 = 1110111011. Mais tarde também esbarrei nos algoritmos de detecção de ciclos mas não consegui formular o problema exatamente conforme a proposta dos algoritmos. Commented 6/05/2014 às 23:03
  • 2
    Essa complexidade esperada está expressa em função de que? Lembre-se que, para um inteiro n, o tamanho de sua cadeia de bits é [o teto de] log2(n). Ou seja, uma solução "quadrática em relação a Q" corresponde exatamente a log2(n)^2...
    – mgibsonbr
    Commented 7/05/2014 às 16:40
  • 2
    Humm... Faz sentido @mgibsonbr. Nos meus resultados eu estourei o tempo limite de alguns testes unitários (mas meu algoritmo tinha um problema besta... Só consegui 38 dos 100 pontos). Talvez você tenha razão e eu esteja querendo otimizar uma solução já "suficientemente boa". Commented 7/05/2014 às 16:47

3 Respostas 3

4

Eu particularmente acredito que a melhor(ou a mais confiável) solução é aplicar autocorrelação, é o mesmo método usado para encontrar o período em sinais, um exemplo bem prático de autocorrelação é quando você precisa encontrar a frequência(que reciprocamente é o mesmo que o período) de um determinado sinal de áudio o principio é bem parecido com o do problema proposto, a autocorrelação pode ser definida como:

inserir a descrição da imagem aqui

Os passos para se chegar ao resultado esperado é:

  1. Aplicar autocorrelação no vetor de bits.
  2. A autocorrelação vai te retornar os pontos mais parecidos.
  3. Agora com o vetor retornado pela autocorrelação encontre todos os picos deste vetor.
  4. agora que você sabe todos os locais(picos), subtraia(ache a diferença) entre os picos.
  5. O seu período é o resultado da primeira diferença.

Eu fiz aqui rapidamente em matlab para demonstrar o conceito, segue alguns resultados dos apresentados pelo problema:


vector = [1 1 1 0 1 1 1 0 1 1];

R = xcorr(vector);

[pks,locs]=findpeaks(R);

resultado=diff(locs);

resultado(1)

ans =

     4

vector = [1 0 1 0];

R = xcorr(vector);

[pks,locs]=findpeaks(R);

resultado=diff(locs);

resultado(1)

ans =

     2

vector =[1 0 0 1 1 1 0 0 1 1];

R = xcorr(vector);

[pks,locs]=findpeaks(R);

resultado=diff(locs);

resultado(1)

ans =

     5
6
  • 1
    Muito bacana Elder (e Matemática realmente permite uma programação muito sucinta para esse tipo de problema). Você teria idéia da complexidade assintótica dessa solução? Commented 7/05/2014 às 15:28
  • 1
    @ederwander Creio que quando diz "complexidade assintótica" o OP se refere à ordem de complexidade do algoritmo.
    – mgibsonbr
    Commented 7/05/2014 às 16:20
  • 1
    Ow é verdade, eu olhei rapidamente :-) confundi, pensei que ele estava perguntando por aperiodicidade, em aplicações realmente reais isso é usado em tempo-real, ou seja afinadores de guitarra, violão, piano, etc, são usados para dar a frequência de uma nota em tempo real usando este principio... claro usamos blocos fixos ou seja 1024, 2048 de tamanho :-)
    – ederwander
    Commented 7/05/2014 às 16:32
  • 5
    "Grande-O" é como se diz em português? Sounds funny. Podia ser Ozão :-) @AnthonyAccioly
    – bfavaretto
    Commented 12/05/2014 às 3:37
  • 3
    Até a Wikipedia tem dois artigos sobre o assunto em português (Grande-O e Big-O), acho que nesses casos é melhor chamar de complexidade assintótica temporal superior (eu sei que isso é chamar vaca de animal bovino quadrupede ruminante, mas as vezes é inevitável hehehe). Commented 12/05/2014 às 15:42
3

A princípio considerei aplicar o algoritmo de detecção de ciclos de Floyd, também conhecido como o algoritmo da "tartaruga e do coelho", mas o problema parece ser mais simples do que isso.

Características de complexidade logarítmicas geralmente envolvem uma comparação que vai diminuindo ao longo do tempo. Por exemplo, a busca binária, que vai dividindo o vetor sempre em dois.

O fato dela ser elevada ao quadrado também poderia estar associado a comparações entre os elementos do vetor, como ocorre com o algoritmo de ordenação bolha (bubble sort).

Considerando tudo isso, mais a definição do problema:

S[K] = S[K+P] para todo K, onde 0 ≤ K < Q − P

Pensei num algoritmo simples que funciona basicamente da seguinte forma:

  1. Calcula o maior período dividindo o tamanho da cadeia de bits por 2, fazendo P = T / 2, sendo T o tamanho da cadeia de bits.
  2. Calcula a quantidade de cadeias a comparar fazendo Q = LEN / P, arredondando-se sempre para cima

  3. Para cada K = 1..P e J = 2..K, compara cada elemento na posição K com o correspondente na posição K * J + P, somente quando K * J + P <= T

    Se encontrar um elemento diferente

    • Se P > 1, decrementa o período P e retorna ao passo 2 novamente
    • Senão, continua no passo 4
  4. Se P <= 0 retorna -1, senão, retorna P

Exemplo prático

Dado o número de exemplo 955, cujo valor binário é 1110111011, podemos calcular os valores inicias dos Passos 1 e 2 da seguinte forma:

T = 10
P = 10 / 2 = 5
Q = 10 / 5 = 2

Então a comparação no Passo 3 ocorre da seguinte forma:

K = 1: 1 1 1 0 1 | 1 1 0 1 1 (iguais)

K = 2: 1 1 1 0 1 | 1 1 0 1 1 (iguais)

K = 3: 1 1 1 0 1 | 1 1 0 1 1 (diferentes)

Ao comparar o terceiro elemento de cada período, um elemento diferente foi encontrado. Então, atualizados as variáveis assim:

P = P - 1 = 4
Q = 10 / 3 = 4 (arredondando para cima)

E continuamos a comparação:

K = 1: 1 1 1 0 | 1 1 1 0 | 1 1 (iguais)

K = 2: 1 1 1 0 | 1 1 1 0 | 1 1 (igualis)

K = 3: 1 1 1 0 | 1 1 1 0 | 1 1 (iguais)

K = 4: 1 1 1 0 | 1 1 1 0 | 1 1 (iguals)

Como não há diferença, então retornamos o valor de P, que é 4.

Implementação em Java

public static int periodo( int n ) {

  // validação inicial: precisa ser positivo e com pelo menos duas casas binárias
  if( n < 2 ) return -1;

  // inicialização de variáveis
  String s = Integer.toBinaryString( n );
  byte[ ] bytes = s.getBytes();
  int t = bytes.length;

  // período inicial
  int p = t / 2;

  // verifica se o período se repete pelo menos uma vez
  boolean diferente;
  do {
    diferente = false;
    int qp = t / p; // quantidade de períodos
    if (t % p > 0) qp++; //somar 1 para comparar os caracteres de resto no final

    // verifica se a repetição ocorre
    for2: for( int k = 0 ; k < p ; k++ ) {
      for (int j = 1; j < qp; j++) {
        if( k + p * j < t && bytes[ k ] != bytes[ k + p * j ] ) {
          diferente = true;
          break for2;
        }
      }
    }

    //se não encontrou repetição, tenta um período menor
    if( diferente ) {
      p--;
    }
  } while( diferente && p > 0 );

  return p <= 0 ? -1 : p;
}

Algumas Considerações

Não sou muito bom em julgar a complexidade de um algoritmo, mas acredito que no pior caso o algoritmo acima irá fazer N / 2 iterações e, em cada uma, ele faz iterações em períodos menores, o que leva a uma complexidade logarítmica temporal.

Quanto à complexidade especial (de memória), o algoritmo é O(1) porque não acrescenta novas estruturas de dados além da original, embora a implementação seja O(N) porque cria um vetor auxiliar do mesmo tamanho da cadeia de bits.

Algo que me deixa com uma pulga atrás da orelha é que o problema sugeriu uma complexidade especial também logarítmica, então talvez haja alguma estrutura de dados que possa otimizar a complexidade temporal da solução.

Uma solução que pensei com complexidade temporal logarítmica é dividir a cadeia de bits em várias Strings e então comparar para ver se elas possuem o mesmo conteúdo. Porém, suspeito que essa solução seria bem menos eficiente, já que executar vários substrings me parece algo desnecessário, além do que a comparação de Strings também ocorreria caractere a caractere.

Outra ideia é recuperar o trecho binário de cada período e comparar o equivalente em seu formato numérico. Talvez ainda com operações binárias o algoritmo pudesse ser muito eficiente. Mas não analisei a complexidade da conversão de cada período do formato binário para o decimal.

Ainda outra ideia para otimizar isso ainda mais seria fazer toda essa comparação usando operadores binários para verificar a igualdade dos períodos, por exemplo, usando cadeias de bits assim: 1000010000, 1000100010, 1001001001, 1010101010. É uma ideia.

Enfim, não sei se a solução que propus atende ao requisito da pergunta, mas espero ter ajudado pelo menos com algumas ideias.

E, antes de concluir, só um alerta: cuidado com o desempenho da linguagem ao participar de um desafio online. Já resolvi alguns desses problemas usando Java e Python. Infelizmente, muitas vezes obtive um timeout mesmo com um bom algoritmo. Alguns sites adicionam multiplicadores de velocidade, por exemplo, Java 1,5 e Python 2,5 para tentar igualar a eficiência do algoritmo com linguagens mais velozes como C++. Porém, isso nem sempre é justo e basta olhar o ranking para ver quais linguagens estão sempre no topo.


Atualização

Baseado no gist do Anthony Accioly, fiz uma tentativa de otimizar ainda mais o código usando somente manipulação em bits. Segue o código:

public class BitPeriod5 {

    public int solution(int n) {

        // validação inicial: precisa ser positivo e com pelo menos duas casas binárias
        if (n < 2) {
            return -1;
        }

        // inicialização de variáveis
        final int t = 32 - Integer.numberOfLeadingZeros(n);

        // descarta bits não significantes
        final int s = n >>> Integer.numberOfTrailingZeros(n);

        // período inicial
        int p = 1;
        int maxp = t / 2;
        int vp = 0;

        // verifica se o período se repete pelo menos uma vez
        boolean diferente;
        do {
            diferente = false;
            int qp = t / p + 1;
            if (t != p * qp) {
                qp++; //somar 1 para comparar os caracteres de resto no final
            }

            vp = vp << 1 | 1;
            int vi = n & vp;
            for (int i = 1; i < qp; i++) {
                if (((n >> (i*p)) & vp) != (vi & vp)) {
                    diferente = true;
                }
            }

             //se não encontrou repetição, tenta um período menor
            if (diferente) {
                p++;
            }
        } while (diferente && p <= maxp);

        return p > maxp ? -1 : p;

    }

    public static void main(String[] args) {
        final BitPeriod5 bitPeriod = new BitPeriod5();
        for (int i = 0; i < 100; i++) {
            long nano = System.nanoTime();
            for (int j = 0; j < 100000; j++) {
                bitPeriod.solution(10);
                bitPeriod.solution(187);
                bitPeriod.solution(955);
                bitPeriod.solution(1000000000);
                bitPeriod.solution(0b10101000001010100000);
            }
            System.out.printf("%.2f\n", ((double) (System.nanoTime()) - nano) * 1e-6);
        }
    }

}

Entretanto, notei que essa solução acaba sendo mais lenta que a que a anterior, mesmo tendo um for a menos.

Lição 1

Manipular bits é mais "caro" que acessar elementos do vetor e comparar o seu valor.

Também notei que retirando a operação de módulo, o desempenho do código melhora bastante.

Alterando o trecho:

if (t % qp > 0) ...

Por isso:

if (t != p * qp) ...

O ganho de desempenho foi na faixa dos 25%. É muito interessante ver como cada operação a mais afeta drasticamente o desempenho.

Lição 2

A operação de módulo da divisão é muito "cara" do ponto de vista de desempenho.

12
  • 1
    Obrigado utluiz, a sua solução executa bem mais rápido do que a minha (mesmo que a complexidade assintótica pareça ser igual). Quanto a complexidade de espaço log(N), vou pela teoria do mgibsonbr, acredito que log(N) =~ Q, ou seja que você pode usar uma estrutura qualquer extra para conter os bits da cadeia. Não sei porque, mas ainda tenho a impressão que com um BitSet ou mesmo manipulações / operações lógicas de bits seria possível resolver esse problema de maneira mais eficiente. Talvez parte dos passos possam ser reescritos com shits binários e operação XOR / AND NOT. Commented 12/05/2014 às 17:59
  • 1
    E obrigado pela dica do timeout também, gostaria de poder executar esse teste de novo :). Commented 12/05/2014 às 18:04
  • 1
    Criei um gist com seu algoritmo ligeiramente modificado (começando com p=1 e indo até p == t / 2, de forma a retornar sempre o menor período possível). Conforme meu flawed microbenchmark sua solução consegue rodar 500.000 testes em torno de 3 vezes mais rápido que a minha. Ainda vou perseguir a questão de bits, mas para todos os fins a sua resposta está correta. Commented 13/05/2014 às 16:24
  • 1
    utluiz, para fechar o assunto de vez, atualizei o Gist acima com uma versão de força bruta e uma versão do seu algoritmo usando apenas manipulação de bits :). Também acho que na linha if (t % q > 0) qp++; você provavelmente quis dizer if (t % **qp** > 0) qp++; né? Commented 13/05/2014 às 21:17
  • 1
    @AnthonyAccioly Acabei de descobrir o quanto a operação de módulo e a manipulação de bits em java pode ser cara. Tentei de forma frustrada fazer uma otimização maior com manipulação de bits, mas nada feito. Vou atualizar a resposta com essas informações.
    – utluiz
    Commented 14/05/2014 às 1:42
2

Uma semana depois do "exercício de 30 minutos" finalmente consegui chegar a uma solução usando manipulação de bits.

Esse algoritmo continua sendo de força bruta; mas conseguiu os melhores tempos conforme meus testes (em média 6 vezes mais rápido do que o algoritmo original).

O algoritmo

  1. Para todo candidato a período P entre 1 e Q / 2
    1. Inicialize K: P bits de ordem superior em N.
    2. Encontre S: uma cadeia de Q bits utilizando sucessivas repetições de K ("restos" devem ser considerados).
    3. Se S == N, o período é P
  2. Se nenhum período foi encontrado, retorna -1.

Implementação

public int periodo(int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("n precisa ser positivo");
    }
    int result = - 1;
    // tamanho da cadeia de bits
    final int q = 32 - Integer.numberOfLeadingZeros(n);
    // cada periodo entre p 1 e tamanho da cadeia / 2
    for (int p = 1; p <= q / 2 && result == -1; p++) {
        // primeiros p bits
        final int k = n >> q - p;
        if (n == constroiPeriodo(k, p, q)) {
            result = p;
        }
    }
    return result;
}

Onde o método constroiPeriodo pode ser implementado da seguinte maneira:

private int constroiPeriodo(int k, int p, int q) {
    int result = 0;
    // periodos inteiros
    for (int i = 0; i < q; i += p) {
        result = result << p | k;
    }
    // ultimo periodo parcial
    final int mod = q % p;
    if (mod != 0) {
        result = result >> p - mod;
    }

    return result;
}

P.S. Enquanto minha adaptação do algoritmo do utluiz não conseguiu alcançar a performance dessa implementação naive, o algoritmo dele é bem mais inteligente e deve ser preferido.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .