Classificação Patológica

Seu chefe exigiu que você desenvolva um algoritmo de classificação para melhorar o desempenho do aplicativo da sua empresa. No entanto, depois de escrever o aplicativo, você sabe que é improvável que seja capaz de torná-lo significativamente mais rápido. Não querendo decepcionar seu chefe, você decidiu desenvolver um novo algoritmo que funciona ainda melhor do que * a classificação em determinados conjuntos de dados. Obviamente, você não pode deixar óbvio que o algoritmo funciona apenas em alguns casos; portanto, você deve torná-lo o mais obscuro possível.

O objetivo deste concurso é escrever uma rotina de classificação no idioma de sua escolha, com melhor desempenho em determinados conjuntos de dados do que em outros, com resultados repetíveis. Quanto mais específica a classificação que determina a velocidade, melhor. O algoritmo deve fazer uma classificação de algum tipo; portanto, um algoritmo que depende dos dados já estarem completamente classificados (como em um algoritmo que não faz nada) ou um algoritmo que depende dos dados serem classificados completamente ao contrário são ambos inválidos. O algoritmo de classificação deve classificar corretamente qualquer conjunto de dados.

Após apresentar sua rotina, inclua uma explicação do motivo pelo qual ela funciona apenas em determinados conjuntos de dados e inclua execuções de teste em pelo menos um conjunto de dados bons (rápidos) e um conjunto de dados ruins (lentos). O objetivo aqui é poder provar ao seu chefe que você encontrou uma maneira melhor de classificar, para que mais dados de teste sejam melhores. Obviamente, você só mostrará ao seu chefe os resultados dos testes dos bons dados, para que a falha nos dados de teste necessários não seja muito óbvia. Se aplicável ao seu idioma, mostre que seu algoritmo é mais rápido que o algoritmo de classificação interno do seu idioma.

Por exemplo, pode-se enviar um algoritmo de classificação por inserção, com dados bons sendo dados que já estão quase classificados e dados ruins sendo dados completamente aleatórios, uma vez que a classificação por inserção se aproxima de O (n) em dados quase classificados. No entanto, isso não é muito bom, pois meu chefe provavelmente notaria que todos os dados de teste estão quase ordenados para começar.

Este é um concurso de popularidade , por isso vence a resposta com mais votos após 7 dias (21 de maio).

Se ninguém me interessar, gostaria de enviar uma resposta wiki da comunidade que aproveite os conjuntos de dados distribuídos uniformemente.

Faz muito tempo, mas lembro que nos Algoritmos 101, aprendemos algum algoritmo de classificação que usava randomização. Eu não era um aluno muito bom, então não me lembro como foi ou porque funcionou rapidamente em média.

No entanto, decidi que esse problema exige uma solução que use a randomização, que, esperamos, funcionará a meu favor em média.

import random

def arrayIsSorted (arr) :
    for i in range(len(arr)-1) :
        if arr[i]>arr[i+1] : return False
    return True

def rSort (arr) :
    random.seed (42)
    counter = 0
    while not arrayIsSorted(arr) :
        random.shuffle (arr)
        counter+=1
    print ("Sorted in %d iterations." % counter)
    return arr

Como a verdadeira aleatorização é importante, certifico-me de semear o RNG com a resposta para a Vida, o Universo e Tudo. Depois de alguns testes, verificou-se que foi uma jogada inteligente! Confira com que rapidez essas duas listas completamente arbitrárias são classificadas:

rSort ([6,1,4,2,3,7,5])
rSort ([8,9,6,1,4,7,2,3,5])

Ambos são classificados em apenas uma iteração - você não poderia pedir uma função mais rápida do que isso!

Agora, reconhecidamente, algumas outras listas produzem resultados um pouco piores ...

rSort ([5,1,4,2,3,7,6])
rSort ([8,9,6,1,4,7,2,5,3])

Elas são classificadas em 4.176 e 94.523 iterações, respectivamente, o que leva mais de um segundo ... mas vamos manter esse fato em sigilo para não distrair ninguém do quão incrível é esse algoritmo!

Editar:

Pediram-me para provar a eficiência do meu algoritmo em uma lista de 100 itens, então aqui está:

rSort ([70, 6, 52, 97, 85, 61, 62, 48, 30, 3, 11, 88, 39, 91, 98, 8, 54, 92, 44, 65, 69, 21, 58, 41, 60, 76, 27, 82, 93, 81, 20, 94, 22, 29, 49, 95, 40, 19, 55, 42, 43, 1, 0, 67, 35, 15, 51, 31, 16, 25, 5, 53, 37, 74, 86, 12, 13, 72, 56, 32, 47, 46, 59, 33, 80, 4, 45, 63, 57, 89, 7, 77, 14, 10, 34, 87, 18, 79, 9, 66, 24, 99, 64, 26, 78, 38, 90, 28, 83, 75, 68, 2, 17, 73, 96, 71, 23, 84, 36, 50])

Mesmo essa lista longa e completamente arbitrária é classificada instantaneamente! Na verdade, devo ter encontrado o melhor algoritmo de classificação do mundo!

Se você pode criar seus próprios dados, é bastante simples - obtenha dados que pareçam aleatórios, mas incluem uma chave para uma classificação mais rápida. Todos os outros dados usam o método de classificação original, portanto os tempos médios são melhores.

Uma maneira fácil é garantir que cada item de dados tenha uma chave exclusiva e, em seguida, basta fazer o hash das chaves. Tomemos, por exemplo, uma lista com os números de 1 a 10.000, todos multiplicados por 16 e com um número aleatório de 0 a 15 adicionado a ele (consulte fillArray () abaixo). Eles parecerão aleatórios, mas cada um tem uma chave seqüencial única. Para classificar, divida por 16 (em C, o >> 4 é muito rápido) e, em seguida, basta colocar o número em uma matriz usando a chave resultante como índice. Um passe e pronto. Nos testes, descobri que o quicksort era 30 vezes mais lento em dez milhões de números.

void fillArray(int *a,int len)
{
  for (int i=0;i<len;++i)
    a[i]=(i<<4)|(rand()&0xF);
  // shuffle later
}
void sortArray(int *a,int len)
{
  int key=0;
  int *r=new int[len];
  for (int i=0;i<len;++i)
  {
    key=a[i]>>4;
    r[key]=a[i];
  }
  memcpy(a,r,len*sizeof(int));
  delete[] r;
}
void shuffleArray(int *a,int len)
{
  int swap=0, k=0;
  for (int i=0;i<len;++i)
  {
    k=rand()%len;
    swap=a[k];
    a[k]=a[i];
    a[i]=swap;
  }
}
int qCompare(const void*a,const void*b)
{
  int result=*((int*)a)-*((int*)b);
  return result;
}
void main()
{
  int aLen=10000;
  int *a=new int[aLen];
  srand (time(NULL));
  fillArray(a,aLen);
  // time them
  long t0=0, d0=0, d1=0;
  // qsort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  qsort(a,aLen,sizeof(int),&qCompare);
  d0=::GetTickCount()-t0;
  // oursort
  shuffleArray(a,aLen);
  t0=::GetTickCount();
  sortArray(a,aLen);
  d1=::GetTickCount()-t0;
  delete[] a;
}

Qualquer coisa que possua uma chave exclusiva pode ser classificada dessa maneira - se você tiver memória para armazená-la, é claro. Por exemplo, muitos bancos de dados usam uma identificação numérica exclusiva do cliente - se a lista for pequena / seqüencial o suficiente, isso poderá ser mantido na memória. Ou alguma outra maneira de converter um registro em um número único. Para mais informações, pesquise Hash Sorts, já que é isso que ...