Encontrar substrings numéricos matematicamente, sem comparação de string
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Este era originalmente um problema que eu tive no trabalho, mas agora é algo que eu estou tentando resolver para a minha própria curiosidade.
Eu quero saber se int 'a' contém o int 'b' da maneira mais eficiente possível. Eu escrevi algum código, mas parece que não importa o que eu escrevo, analisá-lo em uma corda e em seguida, usando indexOf é duas vezes mais rápido que fazê-lo matematicamente.
A memória não é um problema (dentro da razão), apenas a velocidade de processamento pura.
Este é o código que tenho escrito para fazê-lo matematicamente:
private static int[] exponents = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
private static boolean findMatch(int a, int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = getLength(b);
int exponent = exponents[needleLength];
int subNum;
while (a >= 1) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
private static int getLength(int b) {
int len = 0;
while (b >= 1) {
len++;
b /= 10;
}
return len;
}
Aqui está o método de corda Eu estou usando, o que parece trunfo do método matemático acima:
private static boolean findStringMatch(int a, int b) {
return String.valueOf(a).indexOf(String.valueOf(b)) != -1;
}
Assim, embora este não é realmente necessário para eu completar o meu trabalho, eu só estava me perguntando se alguém poderia pensar em alguma maneira de otimizar ainda mais a minha maneira de fazê-lo matematicamente, ou uma inteiramente nova abordagem completamente. Novamente memória é nenhum problema, estou apenas atirando para velocidade pura.
Eu estou realmente interessado em ver ou ouvir qualquer coisa que alguém tem para oferecer sobre este assunto.
EDIT: Quando digo contém quero dizer pode ser em qualquer lugar, por isso, por exemplo, findMatch (1234, 23) == true
EDIT: Para todos dizendo que essa porcaria é ilegível e desnecessário: você está faltando o ponto. O objetivo era chegar ao totó para fora em um problema interessante, não venha com uma resposta para ser usado no código de produção.
Solução
Este é ao longo da linha de Kibbee, mas eu tenho um pouco intrigado com isso antes que ele postou e trabalhou isto:
long mask ( long n ) {
long m = n % 10;
long n_d = n;
long div = 10;
int shl = 0;
while ( n_d >= 10 ) {
n_d /= 10;
long t = n_d % 10;
m |= ( t << ( shl += 4 ));
}
return m;
}
boolean findMatch( int a, int b ) {
if ( b < a ) return false;
if ( a == b ) return true;
long m_a = mask( a ); // set up mask O(n)
long m_b = mask( b ); // set up mask O(m)
while ( m_a < m_b ) {
if (( m_a & m_b ) == m_a ) return true;
m_a <<= 4; // shift - fast!
if ( m_a == m_b ) return true;
} // O(p)
return false;
}
void testContains( int a, int b ) {
print( "findMatch( " + a + ", " + b + " )=" + findMatch( a, b ));
}
testContains( 12, 120 );
testContains( 12, 125 );
testContains( 123, 551241238 );
testContains( 131, 1214124 );
testContains( 131, 1314124 );
Desde 300 caracteres é muito pouco para fazer um argumento, eu estou editando este post principal para responder a Pyrolistical.
Ao contrário do OP, eu não estava tão surpreso que um nativo compilado indexOf foi mais rápido do que o código Java com primitivos. Então, meu objetivo não era encontrar algo que eu pensei que era mais rápido do que um método nativo chamado zilhões de vezes em todo o código Java.
O OP deixou claro que este não era um problema de produção e mais ao longo das linhas de uma curiosidade, isso a minha resposta resolve essa curiosidade. Meu palpite era que a velocidade era um problema, quando ele estava tentando resolvê-lo em produção, mas como uma curiosidade: "Este método será chamado milhões e milhões de vezes" já não se aplica. Como ele teve que explicar para um cartaz, ele não é mais perseguido como código de produção, de modo a complexidade não importa mais.
Além disso, ele fornece a única implementação na página que consegue encontrar o "123" em "551241238", a menos que a correção é uma preocupação estranha, que prevê que. Além disso, o espaço de solução de "um algoritmo que resolve o problema matematicamente utilizando primitivas Java, mas batidas otimizados código nativo" pode ser vazia .
Além disso, não está claro a partir de seu comentário se está ou não em comparação maçãs com maçãs. A especificação funcional é f (int, int) -> boolean, não f (String, String) -> boolean (que é uma espécie de domínio da indexOf). Então, se você testou algo como isto (que ainda poderia bater meu, e eu não seria muito surpreso.) A sobrecarga adicional pode comer um pouco do que o excesso de 40%.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Ele faz as mesmas etapas básicas. log 10 (a) que codifica + log 10 (b) que codifica + realmente encontrar o jogo, o que é bem S (
Outras dicas
deve ser a maneira mais rápida de cordas, porque seu problema é textual, não matemática. Observe que o seu relacionamento "contains" não diz nada sobre os números, ele só diz algo sobre sua decimal representações.
Observe também que a função que você quer escrever será ilegível - outro desenvolvedor nunca vai entender o que está fazendo. (Veja o problema que você teve com isso aqui.) A versão corda, por outro lado, é perfeitamente claro.
A única otimização que eu posso pensar é para fazer a conversão para string em seus próprios e comparar dígitos (direita para a esquerda), como você faz a conversão. Primeiro converter todos os dígitos de b, em seguida, converter a partir da direita em um até encontrar uma correspondência no primeiro dígito do b (da direita). Compare até que todos B partidas ou você bater uma incompatibilidade. Se você acertar uma incompatibilidade, recuar para o ponto onde você começar combinando o primeiro dígito do b, avanço em um e começar de novo.
IndexOf terá que fazer basicamente o mesmo algoritmo de rastreamento de volta, com exceção da esquerda. Dependendo dos números reais este pode ser mais rápido. Eu acho que se os números são aleatórios, deve ser uma vez que não devem ser muitas vezes quando ele não tem que converter todos a.
Parece que sua função é realmente fazendo muito bem, mas uma pequena melhoria:
private static boolean findMatch(int a, int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = getLength(b);
int exponent = exponents[needleLength];
int subNum;
while (a > b) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
Apenas porque uma vez que uma é menor do que b, não é digno continua olhando, não é? Boa sorte e pós se você encontrar a solução!
Este é um problema interessante. Muitas das funções do String.class estão realmente fazendo nativa batendo Cordas uma proposta difícil. Mas aqui está alguns ajudantes:
Dica 1:. Diferentes operações simples inteiros têm velocidades diferentes
Por cálculos rápidos em programas de amostra mostrou:
% ~ T
* ~ 4T
/ ~ 7T
Assim que você quer usar o mínimo possível divisão em favor da multiplicação ou módulo. Não mostrado são subtração, adição e operadores de comparação porque eles explodir todos eles para fora da água. Além disso, usando "final" tanto quanto possível permite que a JVM para fazer certas otimizações. Acelerar você função "getLength":
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Isso dá uma melhoria 7x na função. Você receber uma exceção IndexOutOfBounds se b> seu máximo em expoentes. Para resolver isso, você pode ter:
private static int getLength(final int b) {
int len = 0;
final int maxLen = exponents.length;
while (len < maxLen && b > exponents[len]) {
len++;
}
return len + 1;
}
Isso é um pouco mais lento e dá-lhe um comprimento incorreto se b é muito grande, mas não lançar uma exceção.
Dica 2: de objetos desnecessários / criação primitiva e método chamadas adicionar ao tempo de execução
.Eu estou supondo que "getLength" não é chamado em qualquer outro lugar, por isso, embora possa ser bom ter uma função separada, do ponto de vista de otimização de sua uma chamada de método desnecessário e criação do objeto de "len". Podemos colocar esse direito código onde podemos usá-lo.
private static boolean findMatch(int a, final int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = 0;
while (b > exponents[len]) {
needleLength ++;
}
needleLength++;
final int exponent = exponents[needleLength];
int subNum;
while (a >= 1 && a <= b) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
Além disso, nota que eu mudei o fundo loop while para incluir também "a <= b". Eu não testei isso e não tenho certeza se a pena por iteração bate o fato de que você não perca nenhum iterações. Eu tenho certeza que há uma maneira de se livrar da divisão usando matemática inteligente, mas eu não posso pensar nisso agora.
Umm, eu estou mal-entendido provavelmente totalmente a questão, mas .....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
A menos que você quer saber se uma determinada seqüência de números é dentro de outra sequência de números.
Nesse caso, convertendo-a em uma seqüência será mais rápido do que fazer a matemática para descobrir isso.
Isso em nada responde a sua pergunta, que seja, mas é o conselho de qualquer maneira: -)
O nome do método findMatch não é muito descritivo. Neste caso, eu teria um ContainerBuilder.number(int) método estático, que retornou um ContainerBuilder, que tem a contains método nele. Desta forma o seu código torna-se:
boolean b = number(12345).contains(234);
Juts alguns conselhos para o longo prazo!
Oh sim, eu quis dizer, também, você deve definir o que você quer dizer com "contém"
Existe alguma maneira de calcular isso em binário? Obviamente, o valor binário de um inteiro que contém o inteiro binário de outro personagem não significa que o decical faz o mesmo. No entanto, existe algum tipo de trickary binário que poderia ser usado? Talvez converter um numer como 12345-0001 0010 0011 0100 0101, e, em seguida, fazer alguma bit deslocando para descobrir se 23 (0010 0011) está contida ali. Porque o seu conjunto de caracteres é de apenas 10 caracteres, você pode reduzir o tempo de computação por loja 2 valores personagens em um único byte.
Editar
Expandindo essa idéia um pouco. se você tem 2 números inteiros, A e B, e quer saber se A contém B, você verificar 2 coisas primeiro. se A é menor que B, então A não pode conter B. Se A = B então A contém B. Neste ponto, você pode convertê-los para cadeias *. Se A contém o mesmo número de números de caracteres, como B, então A não contém B, a menos que eles são iguais, mas nós não estaríamos aqui se eles são iguais, por isso, se ambas as strings são o mesmo comprimento, uma não contém b . Neste ponto, o comprimento de A será maior do que B. Então, agora você pode converter as cordas aos seus valores binários embalados como observei na primeira parte deste post. Armazenar esses valores em um array de inteiros. Agora você faz um bit a bit e os valores inteiros em sua matriz, e se o resultado é A, então A contém B. Agora você mudar o array de inteiros para B, para a esquerda 4 bits, e fazer o conparison novamente. Faça isso até que você começar a estalar pedaços fora à esquerda de B.
* Isso * nos meios de parágrafos anteriores, você pode ser capaz de ignorar esta etapa. Pode haver uma maneira de fazer isso sem usar cordas em tudo. Pode haver algum truque binário fantasia que você pode fazer para obter a representação binária embalado eu discuti no primeiro parágrafo. Deve haver algum truque binário você pode usar, ou alguma matemática rápida que irá converter um inteiro para o valor decimal eu discutimos antes.
Posso perguntar onde você estiver usando essa função em seu código? Talvez haja outra maneira de resolver o problema que está resolvendo o que seria muito mais rápido. Isso poderia ser como quando meu amigo me pediu para voltar a sintonizar completamente sua guitarra, e eu fiz isso antes de perceber que eu poderia ter apenas baixou a corda parte inferior por uma etapa inteira e obteve um resultado equivalente.
