A maioria algoritmo de classificação eficiente para muitas chaves idênticas?

votos
8

Qual é o algoritmo mais eficiente para agrupar itens idênticos juntos em uma matriz, dado o seguinte:

  1. Quase todos os itens são duplicados várias vezes.
  2. Os itens não são necessariamente inteiros ou qualquer outra coisa que é semelhante simples. A gama das chaves não é ainda bem definida, muito menos pequena. Na verdade, as chaves podem ser estruturas arbitrárias. Isto exclui as formas mais simples de contar espécie.
  3. Nós nos preocupamos com ambas as propriedades não-assimptóticas assintótica e, e n pode ser pequeno, às vezes. No entanto, quando n é pequeno, o desempenho ainda é importante porque esta função pode ser chamado de vários milhões de vezes em um loop de milhões de pequenos conjuntos de dados. Isto exclui qualquer função hash caro ou usando uma complexa estrutura de dados que precisa para executar lotes de alocações de memória.
  4. Os dados podem ser classificados em ordem arbitrária, desde que todos os itens idênticos são agrupados.

Se isso é confuso, aqui está um exemplo, supondo que tal função é chamada de groupIdentical:

uint[] foo = [1,2,3,2,1,5,4,5];
uint[] bar = groupIdentical(foo);
// One possibile correct value for bar:
// bar == [2,2,1,1,3,4,5,5].
// Another possible correct answer:
// bar == [1,1,2,2,5,5,4,3].

No entanto, como um lembrete, não podemos assumir que os dados é composto como inteiros.

Edit: Obrigado pelas respostas. Meu principal problema com hash foi que tabelas hash realizar alocações de memória para freqüentemente. O que eu acabei fazendo era escrever meu próprio tabela hash que usa um alocador região que eu tinha em torno de contornar este problema. Funciona bem.

Publicado 09/12/2008 em 22:00
fonte usuário
Em outras línguas...                            


9 respostas

votos
10

Eu acho que você poderia simplesmente botar os objetos, desde ordem real não importa, única agrupamento. objectos idênticos vai acabar agrupados no mesmo balde. Isso supõe que cada tipo que você está interessado tem a sua própria função hash, ou você pode definir o seu próprio e sobrecarregá-lo (tendo cada tipo como parâmetro para a definição de função hashCode diferente).

Para evitar colisões em todo tipos de dados (assim cordas não acabar no mesmo balde como duplos, para um exemplo), você precisa codificar o tipo de dados para o hash. Assim, por exemplo, se você tem um hash de 32 bits, talvez os primeiros 5 bits pode codificar o tipo de dados, assim você pode ter 32 tipos diferentes no mesmo mapa hash.

EDIT: Deixe-me apenas acrescentar que a razão que eu estou sugerindo um mapa de hash personalizado é porque eu não sei de um que expõe o suficiente de sua implementação interna para você obter os valores de cada balde. Pode haver uma implementação de tal forma que eu não saiba. Há um monte de coisas que eu não sei. :)

Respondeu 09/12/2008 em 22:04
fonte usuário

votos
4

A palavra mágica que você está procurando aqui é multiset (ou saco ). Não é realmente uma espécie em tudo, desde que você não se importa com a ordem, desde que você tem todos os elementos com chaves iguais agrupados. Existem várias implementações enlatados disponíveis, dependendo do idioma que você está usando, mas em geral a versão hash acima é assintoticamente ótimo, eu acredito: insert()é tempo constante, desde que você pode calcular um hash em O (1) e acrescentar colidindo inserções para uma lista em O (1) tempo; você pode recuperar um elemento das caixas em O (1) tempo, você simplesmente pegar o primeiro no lixo; e você pode, portanto, recolher todos eles em O (n) tempo, desde que você recuperar n elementos com O (1) para cada elemento.

Respondeu 09/12/2008 em 23:17
fonte usuário

votos
3

A mergesort galope, tais como built-in sort (cf de python timsort ), tem o bom desempenho esperado quando há grandes séries de dados já classificados (como, no seu exemplo, objetos idênticos) - você vai pular O (log ( N)) trabalho por intercalação. Você também pode distribuir um mergesort através de várias CPUs e discos, se o conjunto de dados é extremamente grande (isso é chamado de tipo "externo"). No entanto, será pior caso ó (NLog (N)).

Os únicos tipos que são mais rápidos do que NLog (N) estão contando os tipos, que exploram alguma propriedade comum das chaves. Para usar uma espécie de tempo linear (tabela hash ou radix sort / caçamba), você vai ter que botar a estrutura de gerar algum tipo de chave numérica.

Radix tipo vai fazer várias passagens através das teclas, pelo que a sua hora prevista será mais longo do que uma abordagem hashtable; e, desde que você não se preocupam com ordem lexicográfica, a solução tabela hash soa melhor para você, se você pode dar ao luxo de botar as chaves.

Respondeu 09/12/2008 em 22:10
fonte usuário

votos
1

Eu acho que hash em baldes seria a melhor solução, assumindo que há um hash que preserva operador = mapeamento (0.0 pode não botar a mesma coisa -0.0, mas eles poderiam ser "igual"). Supondo que você só tem um igual, e menos do que operador, você poderia implementar um algoritmo de classificação rápida rudimentar de escolher o primeiro elemento como pivô, e colocando a menos do que em um grupo, e maior do que no outro grupo, e em seguida, repetindo o processo em cada grupo.

Respondeu 09/12/2008 em 22:16
fonte usuário

votos
1

3-maneira QuickSort realiza muito bem quando há grande número de duplicados.

Respondeu 09/12/2008 em 22:14
fonte usuário

votos
0

algoritmo simples com ordem de O desempenho (n (n-1) / 2) é como segue:

  1. Suponha matriz de entrada nomeado como tamanho de entrada tendo como n.
  2. Alocar uma memória para return array com mesmo tamanho nomeado como resultado
  3. Alocar uma memória para matriz booleana com mesmo tamanho nomeado como Visitou e definir tudo Visted como falsa
  4. Suponha que há uma função Equal nomeado como Igual a retornar true se os dois itens são iguais outra falsa.
  5. Suponha índice de matriz começa a partir de um an
  6. Por favor, veja o código Pseudo C abaixo:
function groupIdentical(Input) 
{
    k=1;
    for i=1 to n 
    {
        Visited[i]=false ;
    }

    for i=1 to n
    {
        if( !Visited(i) )
        {   
            Result[k++]=Input[i];
            for j= (i+1) to n
            {
                if( Equals(i,j) )
                {
                    Result[k++]=Input[j];
                    Visited[j]=true;
                }   
            }
        }
    }
    return Result;
}
Respondeu 10/12/2008 em 08:16
fonte usuário

votos
0

Talvez um R + B ou árvore AVL? Então, novamente - ele ainda seria, em última instância O (nlogn). Poderia muito bem usar heapsort - não vai ser pior e sem uso de memória extra ...

Respondeu 09/12/2008 em 22:36
fonte usuário

votos
0

Eu acho que desde que você tem objetos arbitrários que você não deseja copiar em torno de demasiado, você pode simplesmente usar referências ou ponteiros para o tipo, e, se necessário, copiar os objetos em ordem depois.

Respondeu 09/12/2008 em 22:19
fonte usuário

votos
0

Se você souber o intervalo de valores possíveis, e é pequeno, você pode fazer: (código pseudo-ish)

uint[] bucket = new int[10];
foreach(uint val in foo) {
    ++bucket[val];
}

uint bar_i = 0;
uint[] bar = new int[foo.length];
foreach(int val = 0; val < 10; val++) {
    uint occurrences = bucket[val];
    for(int i=0; i < occurrences; i++) {
        bar[bar_i++] = val;
    }
}
Respondeu 09/12/2008 em 22:16
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more