Que é mais rápido, lookup Hash ou de busca binária?
https://stackoverflow.com/questions/360040
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Quando dado um conjunto estático de objetos (estática no sentido de que uma vez carregado que raramente ou nunca muda) no qual repetiu pesquisas simultâneas são necessários com ótimo desempenho, o que é melhor, um HashMap ou um array com uma pesquisa binária usando algum comparador personalizado?
A resposta é uma função do objeto ou struct tipo? Hash e / ou desempenho da função Equal? singularidade de hash? tamanho da lista? tamanho Hashset / size set?
O tamanho do conjunto que eu estou olhando para pode estar em qualquer lugar a partir de 500k a 10m -. Incase que a informação é útil
Enquanto eu estou procurando uma resposta C #, acho que os verdadeiros matemáticos resposta não está na língua, então eu não estou incluindo o tag. No entanto, se houver C coisas # específicas para estar ciente de que a informação é desejada.
Solução
Ok, vou tentar ser breve.
C # resposta curta:
Teste as duas abordagens diferentes.
.NET lhe dá as ferramentas para mudar a sua abordagem com uma linha de código. Caso contrário, use System.Collections.Generic.Dictionary e certifique-se inicialize-o com um grande número de capacidade inicial ou você vai passar o resto de sua vida a inserção de itens devido à GC trabalho tem que fazer para recolher matrizes balde de idade.
resposta mais longa:
Um hashtable tem tempos de pesquisa quase constante e chegar a um item em uma tabela hash no mundo real não só precisa para calcular um hash.
Para chegar a um item, o seu hashtable vai fazer algo como isto:
- Obter o hash da chave
- Obter o número de balde para esse hash (geralmente a função de mapa olhares como este balde = Hash% bucketsCount)
- Traverse a cadeia de itens (basicamente é uma lista de itens que compartilham o mesmo balde, a maioria dos hashtables usar este método de manuseamento de balde / de hash colisões) que começa em que balde e comparar cada tecla com o um dos itens que você está tentando adicionar / excluir / atualizar / seleção se contido.
vezes Lookup depender de como "bom" (como escassa é a saída) e rápido é a sua função hash, o número de baldes que você está usando e quão rápido é o comparador de chaves, nem sempre é a melhor solução.
A melhor e mais profundo explicação: http: //en.wikipedia. org / wiki / Hash_table
Outras dicas
Para muito pequenas coleções a diferença vai ser insignificante. Na extremidade baixa de sua faixa (500k itens) você vai começar a ver uma diferença se você está fazendo um monte de pesquisas. A busca binária vai ser O (log n), enquanto que uma pesquisa de hash será O (1), amortizado . Isso não é o mesmo que verdadeiramente constante, mas você ainda teria que ter uma função hash muito terrível ficar pior desempenho do que uma busca binária.
(Quando eu digo "de hash terrível", eu quero dizer algo como:
hashCode()
{
return 0;
}
Sim, é super rápido em si, mas faz com que seu mapa de hash para tornar-se uma lista ligada.)
ialiashkevich escreveu algum código C # usando uma matriz e um dicionário para comparar os dois métodos, mas é usado Valores longos para chaves. Eu queria testar algo que realmente executar uma função hash durante a pesquisa, então eu modifiquei esse código. Eu mudei para usar valores de corda, e eu reformulado a povoar e seções de pesquisa em seus próprios métodos por isso é mais fácil de ver em um profiler. Eu também deixou no código que usado Valores longos, assim como um ponto de comparação. Finalmente, eu me livrei da função personalizada busca binária e usou o um na classe Array.
Eis que o código:
class Program
{
private const long capacity = 10_000_000;
private static void Main(string[] args)
{
testLongValues();
Console.WriteLine();
testStringValues();
Console.ReadLine();
}
private static void testStringValues()
{
Dictionary<String, String> dict = new Dictionary<String, String>();
String[] arr = new String[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " String values...");
stopwatch.Start();
populateStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
Array.Sort(arr);
stopwatch.Stop();
Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringDictionary(dict, arr);
stopwatch.Stop();
Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchStringArray(arr);
stopwatch.Stop();
Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with random values. */
private static void populateStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness
}
}
/* Populate a dictionary with values from an array. */
private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(arr[i], arr[i]);
}
}
/* Search a Dictionary for each value in an array. */
private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr)
{
for (long i = 0; i < capacity; i++)
{
String value = dict[arr[i]];
}
}
/* Do a binary search for each value in an array. */
private static void searchStringArray(String[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
private static void testLongValues()
{
Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue);
long[] arr = new long[capacity];
Stopwatch stopwatch = new Stopwatch();
Console.WriteLine("" + capacity + " Long values...");
stopwatch.Start();
populateLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
populateLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongDictionary(dict);
stopwatch.Stop();
Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
searchLongArray(arr);
stopwatch.Stop();
Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds);
}
/* Populate an array with long values. */
private static void populateLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
arr[i] = i;
}
}
/* Populate a dictionary with long key/value pairs. */
private static void populateLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
dict.Add(i, i);
}
}
/* Search a Dictionary for each value in a range. */
private static void searchLongDictionary(Dictionary<long, long> dict)
{
for (long i = 0; i < capacity; i++)
{
long value = dict[i];
}
}
/* Do a binary search for each value in an array. */
private static void searchLongArray(long[] arr)
{
for (long i = 0; i < capacity; i++)
{
int index = Array.BinarySearch(arr, arr[i]);
}
}
/**
* Generate a random string of a given length.
* Implementation from https://stackoverflow.com/a/1344258/1288
*/
private static String generateRandomString(int length)
{
var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
var stringChars = new char[length];
var random = new Random();
for (int i = 0; i < stringChars.Length; i++)
{
stringChars[i] = chars[random.Next(chars.Length)];
}
return new String(stringChars);
}
}
Aqui estão os resultados com vários tamanhos diferentes de coleções. (Os tempos são em milissegundos).
500000 Valores longos ...
Preencher longo Dicionário: 26
Preencher longa série: 2 | Pesquisar Long Dicionário: 9
Pesquisar Long Matriz: 80500000 String valores ...
Preencher Cordas matriz: 1237
Preencher Cordas Dicionário: 46
Classificar Cadeia matriz: 1755
Cadeia de pesquisa Dicionário: 27
Cadeia de pesquisa Matriz: 15691000000 Valores longos ...
Preencher longo Dicionário: 58
Preencher longa série: 5
Pesquisar Long Dicionário: 23
Pesquisar Long matriz: 1361000000 valores String ...
Preencher Cordas matriz: 2070
Preencher Cordas Dicionário: 121
Classificar Cadeia matriz: 3579
Cadeia de pesquisa Dicionário: 58
Cadeia de pesquisa Matriz: 32673000000 Valores longos ...
Preencher longo Dicionário: 207
Preencher longa série: 14
Pesquisar Long Dicionário: 75
Pesquisar Long matriz: 4353000000 valores String ...
Preencher Cordas matriz: 5553
Preencher Cordas Dicionário: 449
Classificar Cadeia matriz: 11695
Cadeia de pesquisa Dicionário: 194
Cadeia de pesquisa Matriz: 1059410000000 Valores longos ...
Preencher longo Dicionário: 521
Preencher longa série: 47
Pesquisar Long Dicionário: 202
Pesquisar Long matriz: 118110000000 valores String ...
Preencher Cordas matriz: 18119
Preencher Cordas Dicionário: 1088
Classificar Cadeia matriz: 28174
Cadeia de pesquisa Dicionário: 747
Cadeia de pesquisa Matriz: 26503
E para comparação, aqui está a saída do Profiler para a última corrida do programa (10 milhões de registros e pesquisas). Eu destacou as funções relevantes. Eles bem de perto concordam com o cronômetro métricas de tempo acima.
Você pode ver que as pesquisas de dicionário são muito mais rápidos do que a busca binária, e (como esperado), a diferença é mais pronunciada quanto maior a coleção. Então, se você tem uma função hash razoável (bastante rápido com poucas colisões), uma pesquisa de hash deve bater busca binária para coleções nesta faixa.
As respostas por Bobby, Bill e Corbin estão errados. O (1) não é mais lento do que O (N log N) para uma fixo / delimitada n:
log (n) é constante, por isso depende da constante de tempo.
E para uma função hash lento, já ouviu falar de md5?
O algoritmo de hash string padrão provavelmente toca todos os caracteres, e pode ser facilmente 100 vezes mais lenta do que a média comparar para as chaves de cadeia longa. Estado lá, feito isso.
Você pode ser capaz de (parcialmente) usam uma base. Se você pode dividir-se em 256 blocos de tamanho aproximadamente igual, você está olhando para 2k a 40k de busca binária. Que é susceptível de proporcionar um desempenho muito melhor.
[Edit] Muitas pessoas votando para baixo o que eles não entendem.
Cordas compara para pesquisa binária classificadas conjuntos têm uma propriedade muito interessante: eles ficam mais lento quanto mais próximo de chegar ao alvo. Primeiro eles vão quebrar no primeiro caractere, no final, apenas no último. Assumindo um tempo constante para eles é incorreta.
A resposta razoável a esta pergunta é: depende. Depende do tamanho dos seus dados, a forma dos seus dados, a implementação de hash, a implementação de busca binária, e onde suas vidas dados (mesmo que ele não está mencionado na pergunta). Algumas outras respostas dizer o mesmo, então eu poderia simplesmente apagar este. No entanto, pode ser bom para compartilhar o que eu aprendi a partir do feedback para a minha resposta original.
- Eu escrevi, " algoritmos de hash são O (1), enquanto busca binária é O (log n) ." - Como observado nos comentários, Big O notação estima complexidade, não velocidade. Isto é absolutamente verdadeiro. pena de notar que normalmente usamos complexidade para ter uma noção de requisitos de tempo e de espaço de um algoritmo. Assim, enquanto é tolice supor complexidade é rigorosamente a mesma velocidade, estimando complexidade sem tempo ou espaço na parte de trás de sua mente é incomum. Minha recomendação:. Evitar Big O notação
- Eu escrevi, " Então, como n se aproxima do infinito ..." - Esta é a coisa mais estúpida que eu poderia ter incluído em uma resposta. Infinito tem nada a ver com seu problema. Você menciona um limite superior de 10 milhões. Ignorar o infinito. Como os comentadores apontam, um número muito grande irá criar todos os tipos de problemas com um hash. (Muito grandes números não fazem binário procurar um passeio no parque, também.) Minha recomendação:. Não mencionar o infinito, a menos que o infinito média
- Também a partir dos comentários: cuidado com hashes cadeia padrão (? Você está hashing cordas Você não menciona.), Os índices de banco de dados são muitas vezes b-árvores (alimento para o pensamento). Minha recomendação: considerar todas as opções. Considere outras estruturas de dados e abordagens ... como um antiquado trie (para armazenar e recuperar cordas) ou um R-árvore (para dados espaciais) ou um MA-FSA (Minimal acíclica Finite State Automaton - pequeno espaço de armazenamento).
Tendo em conta os comentários, você pode supor que as pessoas que usam tabelas de hash são demente. São tabelas de hash imprudente e perigoso? São essas pessoas insano?
Acontece que eles não são. Assim como árvores binárias são bons em certas coisas (na ordem de passagem de dados, eficiência de armazenamento), tabelas de hash têm o seu momento para brilhar também. Em particular, eles podem ser muito bons em reduzir o número de leituras necessárias para buscar seus dados. Um algoritmo de hash pode gerar uma localização e ir direto a ele na memória ou no disco enquanto busca binária lê dados durante cada comparação para decidir o que ler em seguida. Cada leitura tem o potencial para um erro de cache que é uma ordem de magnitude (ou mais) mais lento do que uma instrução de CPU.
Isso não quer dizer tabelas hash são melhores do que busca binária. Eles não são. Também não é para sugerir que todos haxixe e implementações de busca binária são os mesmos. Eles não são. Se eu tiver um ponto, é esta: ambas as abordagens existem para uma razão. Cabe a você decidir qual é o melhor para suas necessidades.
resposta Original:
algoritmos de hash são O (1), enquanto busca binária é O (log n). Assim como n se aproxima do infinito, o desempenho de hash melhora em relação ao binário procurar. Sua milhagem pode variar dependendo n, o haxixe implementação e sua implementação de busca binária.
interessante discussão sobre O (1) . Parafraseado:
O (1) não faz instantâneo significativo. Isso significa que o desempenho não faz mudar à medida que o tamanho de n cresce. Você pode projetar um algoritmo de hash Isso é tão lento ninguém jamais usá-lo e ele ainda seria O (1). Estou bastante certo .NET / C # não sofre de hashing custo proibitivo, no entanto;)
Se o seu conjunto de objetos é verdadeiramente estático e imutável, você pode usar um de hash perfeito para obter O (1) desempenho garantido. Eu vi gperf mencionado algumas vezes, embora eu nunca tive a oportunidade de usá-lo eu mesmo.
Hashes são tipicamente mais rápido, embora pesquisas binárias têm características melhores de pior caso. Um acesso hash é tipicamente um cálculo para obter um valor de hash para determinar qual o "balde" um registro estará em, e assim o desempenho geral vai depender de como uniformemente os registros são distribuídos, eo método usado para procurar o balde. A função hash ruim (deixando alguns baldes com um monte de registros) com uma busca linear através dos baldes irá resultar em uma pesquisa lenta. (No terceiro lado, se você está lendo um disco em vez de memória, os baldes de hash são susceptíveis de ser contíguo enquanto a árvore binária praticamente garante o acesso não-local).
Se você quiser geralmente rápido, usar o hash. Se você realmente quiser garantida desempenho limitado, você pode ir com a árvore binária.
surpreso que ninguém mencionou Cuckoo hashing, que fornece O garantida (1) e, ao contrário perfeito hashing, é capaz de usar toda a memória que aloca, onde, como perfeito hashing pode acabar com O garantida (1), mas perdendo a maior parte da sua alocação. A ressalva? tempo de inserção pode ser muito lento, especialmente quando o número de elementos aumenta, uma vez que toda a optimização é realizada durante a fase de inserção.
Eu acredito que alguma versão deste é usado em hardware router para pesquisas de IP.
dicionário / Hashtable está usando mais memória e leva mais tempo para preencher comparando a matriz. Mas pesquisa é feita mais rapidamente, dicionário, em vez de binário Buscar dentro de matriz.
Aqui estão os números para 10 Milhões de Int64 itens de pesquisa e preencher. Além de um código de exemplo que você pode executar por si mesmo.
dicionário Memória: 462.836
Memória matriz: 88376
Preencher Dicionário: 402
Preencher matriz: 23
Pesquisa Dicionário: 176
Pesquisar matriz: 680
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace BinaryVsDictionary
{
internal class Program
{
private const long Capacity = 10000000;
private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue);
private static readonly long[] Arr = new long[Capacity];
private static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Dict.Add(i, i);
}
stopwatch.Stop();
Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
Arr[i] = i;
}
stopwatch.Stop();
Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = Dict[i];
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds);
stopwatch.Reset();
stopwatch.Start();
for (long i = 0; i < Capacity; i++)
{
long value = BinarySearch(Arr, 0, Capacity, i);
// Console.WriteLine(value + " : " + RandomNumbers[i]);
}
stopwatch.Stop();
Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds);
Console.ReadLine();
}
private static long BinarySearch(long[] arr, long low, long hi, long value)
{
while (low <= hi)
{
long median = low + ((hi - low) >> 1);
if (arr[median] == value)
{
return median;
}
if (arr[median] < value)
{
low = median + 1;
}
else
{
hi = median - 1;
}
}
return ~low;
}
}
}
Eu suspeito fortemente que, em um conjunto de problemas de tamanho ~ 1M, hash seria mais rápido.
Apenas para os números:
a busca binária exigiria ~ 20 compara (2 ^ 20 == 1M)
a pesquisa de hash exigiria um cálculo de hash na chave de pesquisa e, possivelmente, um punhado de compara posteriormente para resolver possíveis colisões
Edit: os números:
for (int i = 0; i < 1000 * 1000; i++) {
c.GetHashCode();
}
for (int i = 0; i < 1000 * 1000; i++) {
for (int j = 0; j < 20; j++)
c.CompareTo(d);
}
vezes: c = "ABCDE", d = "rwerij" hashcode: 0.0012 segundos. Compare: 2,4 segundos.
IMPORTANTE: Na verdade aferição uma pesquisa de hash versus uma pesquisa binária pode ser melhor do que este teste não-inteiro-relevante. Não estou mesmo certo se GetHashCode fica memoized sob o capô
Eu diria que depende principalmente do desempenho do hash e métodos comparar. Por exemplo, quando se usa chaves de string que são muito longo, mas aleatória, a comparar sempre produzirá um resultado muito rápido, mas uma função hash padrão irá processar toda a cadeia.
Mas na maioria dos casos, o mapa de hash deve ser mais rápido.
Eu quero saber porque ninguém mencionou perfeito hashing .
É relevante apenas se o conjunto de dados é fixo por um longo tempo, mas o que ele faz isso analisar os dados e construir uma função hash perfeita que garante que não haja colisões.
Muito arrumado, se o conjunto de dados é constante e o tempo para calcular a função é pequeno comparado com o tempo de execução do aplicativo.
Depende de como você lida com duplicatas para tabelas de hash (se em tudo). Se você deseja permitir duplicados de chaves de hash (sem função hash é perfeito), continua a ser O (1) para pesquisa de chave primária, mas procurar para trás, para o valor "correto" pode ser caro. Resposta é então, teoricamente maior parte do tempo, hashes são mais rápidos. YMMV dependendo em que os dados que você colocar lá ...
Here it's described how hashes are built and because the Universe of keys is reasonably big and hash functions are built to be "very injective" so that collisions rarely happen the access time for a hash table is not O(1) actually ... it's something based on some probabilities. But,it is reasonable to say that the access time of a hash is almost always less than the time O(log_2(n))
Of course, hash is fastest for such a big dataset.
One way to speed it up even more, since the data seldom changes, is to programmatically generate ad-hoc code to do the first layer of search as a giant switch statement (if your compiler can handle it), and then branch off to search the resulting bucket.
The answer depends. Lets think that the number of elements 'n' is very large. If you are good at writing a better hash function which lesser collisions, then hashing is the best.
Note that
The hash function is being executed only once at searching and it directs to the corresponding bucket. So it is not a big overhead if n is high.
Problem in Hashtable:
But the problem in hash tables is if the hash function is not good (more collisions happens), then the searching isn't O(1). It tends to O(n) because searching in a bucket is a linear search. Can be worst than a binary tree.
problem in binary tree:
In binary tree, if the tree isn't balanced, it also tends to O(n). For example if you inserted 1,2,3,4,5 to a binary tree that would be more likely a list.
So,
If you can see a good hashing methodology, use a hashtable
If not, you better using a binary tree.
This is more a comment to Bill's answer because his answer have so many upvotes even though its wrong. So I had to post this.
I see lots of discussion about what is the worst case complexity of a lookup in hashtable, and what is considered amortized analysis / what is not. Please check the link below
Hash table runtime complexity (insert, search and delete)
worst case complexity is O(n) and not O(1) as opposed to what Bill says. And thus his O(1) complexity is not amortized since this analysis can only be used for worst cases (also his own wikipedia link says so)
This question is more complicated than the scope of pure algorithm performance. If we remove the factors that binary search algorithm is more cache friendly, the hash lookup is faster in general sense. The best way to figured out is to build a program and disable the compiler optimization options, and we could find that the hash lookup is faster given its algorithm time efficiency is O(1) in general sense.
But when you enable the compiler optimization, and try the same test with smaller count of samples say less than 10,000, the binary search outperformed the hash lookup by taking advantages of its cache-friendly data structure.
