Geekly articles weekly

Comparação de Classificação do Exchange



Algoritmos esféricos no vácuo são ótimos. No entanto, vamos descer do céu para a terra pecaminosa e ver como toda essa beleza teórica se provará na prática.

A análise da próxima classe de tipos terminará com testes para as classes. Hoje vamos executar (não no sentido de jogar fora, mas no sentido de executar em testes) trocas de classificação. Outras classes serão executadas mais tarde.

Na corrida de hoje envolvida:

Grupo mais fraco


Esses algoritmos não reivindicam nada devido à complexidade deprimente do tempo. Nós os testamos puramente para referência.

Tipo bobo
Classificação lenta
Classificação muda

É ainda mais interessante não apenas o quão bom eles são, mas o quanto eles são ruins nos negócios e qual deles é o pior.

Grupo principal


Aqui, reunimos trocas de trocas a la O ( n 2 ). Classificação de anões (e sua otimização) + todos os tipos de variações de classificação de bolhas.

Classificação dos Anões
Classificação anã (otimizada)
Classificação da bolha
Classificação de coquetéis
Tipo ímpar

Esta é a parte mais interessante das medidas de hoje. É entre os representantes do grupo principal que se espera a luta mais teimosa.

Grupo mais forte


Uma das variedades da bolha - classificando por um pente - conseguiu superar a barreira O ( n 2 ) e alcançar o O consagrado pelo tempo ( n log n ). Portanto, em nossa competição, a triagem rápida tem um rival digno. Além disso, experimente o k-sort recém-inventado , que é uma variação da classificação rápida.

Classificar escova de cabelo
Classificação rápida
K classificação

Os mais fortes, a propósito, não são apenas comparáveis ​​entre si. Em alguns conjuntos de dados, o grupo principal estará em concorrência séria.

Código fonte


Classificações do Python Exchange
def stooge_rec(data, i = 0, j = None): if j is None: j = len(data) - 1 if data[j] < data[i]: data[i], data[j] = data[j], data[i] if j - i > 1: t = (j - i + 1) // 3 stooge_rec(data, i, j - t) stooge_rec(data, i + t, j) stooge_rec(data, i, j - t) return data def stooge(data): return stooge_rec(data, 0, len(data) - 1) def slow_rec(data, i, j): if i >= j: return data m = (i + j) // 2 slow_rec(data, i, m) slow_rec(data, m + 1, j) if data[m] > data[j]: data[m], data[j] = data[j], data[m] slow_rec(data, i, j - 1) return data def slow(data): return slow_rec(data, 0, len(data) - 1) def stupid(data): i, size = 1, len(data) while i < size: if data[i - 1] > data[i]: data[i - 1], data[i] = data[i], data[i - 1] i = 1 else: i += 1 return data def gnome(data): i, size = 1, len(data) while i < size: if data[i - 1] <= data[i]: i += 1 else: data[i - 1], data[i] = data[i], data[i - 1] if i > 1: i -= 1 return data def gnome_opt(data): i, j, size = 1, 2, len(data) while i < size: if data[i - 1] <= data[i]: i, j = j, j + 1 else: data[i - 1], data[i] = data[i], data[i - 1] i -= 1 if i == 0: i, j = j, j + 1 return data def bubble(data): changed = True while changed: changed = False for i in range(len(data) - 1): if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] changed = True return data def shaker(data): up = range(len(data) - 1) while True: for indices in (up, reversed(up)): swapped = False for i in indices: if data[i] > data[i+1]: data[i], data[i+1] = data[i+1], data[i] swapped = True if not swapped: return data def odd_even(data): n = len(data) isSorted = 0 while isSorted == 0: isSorted = 1 for i in range(1, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 for i in range(0, n - 1, 2): if data[i] > data[i + 1]: data[i], data[i + 1] = data[i + 1], data[i] isSorted = 0 return data def comb(data): gap = len(data) swaps = True while gap > 1 or swaps: gap = max(1, int(gap / 1.25)) # minimum gap is 1 swaps = False for i in range(len(data) - gap): j = i + gap if data[i] > data[j]: data[i], data[j] = data[j], data[i] swaps = True return data def quick(data): less = [] pivotList = [] more = [] if len(data) <= 1: return data else: pivot = data[0] for i in data: if i < pivot: less.append(i) elif i > pivot: more.append(i) else: pivotList.append(i) less = quick(less) more = quick(more) return less + pivotList + more def k(data): return k_rec(data, 0, len(data) - 1) def k_rec(data, left, right): key = data[left] i = left j = right + 1 k = left + 1 p = left + 1 temp = False while j - i >= 2: if key <= data[p]: if p != j and j != right + 1: data[j] = data[p] elif j == right + 1: temp = data[p] j -= 1 p = j else: data[i] = data[p] i += 1 k += 1 p = k data[i] = key if temp: data[i + 1] = temp if left < i - 1: k_rec(data, left, i - 1) if right > i + 1: k_rec(data, i + 1, right) return data

Classificações do Exchange PHP
  // function StoogeSort(&$arr, $i, $j) { if($arr[$j] < $arr[$i]) list($arr[$j], $arr[$i]) = array($arr[$i], $arr[$j]); if(($j - $i) > 1) { $t = ($j - $i + 1) / 3; StoogeSort($arr, $i, $j - $t); StoogeSort($arr, $i + $t, $j); StoogeSort($arr, $i, $j - $t); } return $arr; } // function SlowSort(&$arr, $i, $j) { if($i >= $j) return $arr; $m = ($i + $j) / 2; SlowSort($arr, $i, $m); SlowSort($arr, $m + 1, $j); if($arr[$m] > $arr[$j]) list($arr[$m], $arr[$j]) = array($arr[$j], $arr[$m]); SlowSort($arr, $i, $j - 1); return $arr; } // function StupidSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); $i = 1; } } return $arr; } // function GnomeSort($arr) { $i = 1; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ ++$i; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if($i > 1) --$i; } } return $arr; } // () function GnomeSort_opt($arr) { $i = 1; $j = 2; $size = count($arr); while($i < $size) { if($arr[$i - 1] <= $arr[$i]){ $i = $j; ++$j; } else { list($arr[$i - 1], $arr[$i]) = array($arr[$i], $arr[$i - 1]); if(--$i == 0){ $i = $j; $j++; } } } return $arr; } // function BubbleSort($arr) { $c = count($arr) - 1; do { $swapped = false; for ($i = 0; $i < $c; ++$i) { if ($arr[$i] > $arr[$i + 1]) { list($arr[$i + 1], $arr[$i]) = array($arr[$i], $arr[$i + 1]); $swapped = true; } } } while($swapped); return $arr; } // function ShakerSort($arr){ do{ $swapped = false; for($i = 0; $i < count($arr); $i++){ if(isset($arr[$i + 1])) { if($arr[$i] > $arr[$i+1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $swapped = true; } } } if ($swapped == false) break; $swapped = false; for($i = count($arr) - 1; $i >= 0; $i--){ if(isset($arr[$i - 1])){ if($arr[$i] < $arr[$i - 1]) { list($arr[$i], $arr[$i - 1]) = array($arr[$i - 1], $arr[$i]); $swapped = true; } } } } while($swapped); return $arr; } //- function OddEvenSort($arr){ $n = count($arr); $sorted = false; while(!$sorted) { $sorted = true; for($i = 1; $i < $n - 2; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } for($i = 0; $i < $n - 1; $i += 2) { if($arr[$i] > $arr[$i + 1]) { list($arr[$i], $arr[$i + 1]) = array($arr[$i + 1], $arr[$i]); $sorted = false; } } } } // function CombSort($arr){ $gap = count($arr); $swap = true; while($gap > 1 || $swap){ if($gap > 1) $gap /= 1.25; $swap = false; $i = 0; while($i + $gap < count($arr)){ if($arr[$i] > $arr[$i + $gap]){ list($arr[$i], $arr[$i + $gap]) = array($arr[$i + $gap], $arr[$i]); $swap = true; } ++$i; } } return $arr; } // function QuickSort($arr) { $loe = $gt = array(); if(count($arr) < 2) { return $arr; } $pivot_key = key($arr); $pivot = array_shift($arr); foreach($arr as $val){ if($val <= $pivot){ $loe[] = $val; }elseif ($val > $pivot){ $gt[] = $val; } } return array_merge(QuickSort($loe), array($pivot_key => $pivot), QuickSort($gt)); } //k- function K_Sort($arr) { K_Sort_rec($arr, 0, count($arr) - 1); return $arr; } function K_Sort_rec(&$arr, $left, $right) { $key = $arr[$left]; $i = $left; $j = $right + 1; $k = $p = $left + 1; $temp = false; while($j - $i >= 2) { if($key <= $arr[$p]) { if(($p != $j) && ($j != ($right + 1))) { $arr[$j] = $arr[$p]; } elseif($j == ($right + 1)) { $temp = $arr[$p]; } --$j; $p = $j; } else { $arr[$i] = $arr[$p]; ++$i; ++$k; $p = $k; } } $arr[$i] = $key; if($temp) $arr[$i + 1] = $temp; if($left < ($i - 1)) K_Sort_rec($arr, $left, $i - 1); if($right > ($i + 1)) K_Sort_rec($arr, $i + 1, $right); }

Tempo


O tempo é medido em qualquer lugar em segundos, com precisão de microssegundos.

Se um pacote de matrizes (de dez, cem ou até um milhão de peças) for alimentado imediatamente para o algoritmo, o tempo total será indicado.

O ferro é meu laptop fiel e velho que conhecia tempos melhores. Então, muito possivelmente, tudo funcionará para você muito mais rápido.

O pior dos piores


Lidar imediatamente com pessoas de fora. Matrizes para 40/50/60 elementos contendo números aleatórios de 0 a 9 são preparados para eles.
tipo = aleatório, único = Falso, min = 0, máx = 9, contagem = 1
tamanho
40.50.60
PythonPhpPythonPhpPythonPhp
0,0040,0010,0050,0030,0070,004
0,0070,0090,0180,0090,0180,023
0,028.266470,05320,87220,1290145.9786

A classificação estúpida é uma ordem de magnitude mais rápida que a classificação boba, e a classificação boba é uma ordem de magnitude mais rápida que a lenta. Não há mais nada para assistir.

Camponeses médios


Para verificar a média, foram gerados pacotes de cem matrizes de 100 elementos cada (números únicos de 100 a 999), bem como pacotes de dez matrizes de 1000 elementos cada (números exclusivos de 1000 a 9999).

Matrizes aleatórias, matrizes quase ordenadas e matrizes inversas são preparadas.

Peso Médio: Aleatório


tipo = aleatório, único = Verdadeiro
tamanho (mínimo a máximo) × contagem
100 (100 a 999) × 1001000 (1000 a 9999) × 10
PythonPhpPythonPhp
0,141010,189011,591091.7251
0,206010,223012.330132.09712
0,153010,229011,67112.23613
0,216010,264022.555152,73116
0,167010,334021.72513.13218

Em torno dos mesmos resultados para todos. As implementações em Python funcionam um pouco mais rápido que o PHP.

Middles: Quase ordenados


type = quase, único = True
tamanho (mínimo a máximo) × contagem
100 (100 a 999) × 1001000 (1000 a 9999) × 10
PythonPhpPythonPhp
0,0090,0050,0090,005
0,0090,0140,010,014
0,010,010,0110,008
0,0110,0080,0130,008
0,0110,0170,0130,017

Todos têm os mesmos resultados, mais ou menos. Do interessante: encomendar dados parciais dezenas de vezes melhora o desempenho de todos os algoritmos.

Meio: Reverso


tipo = reverso, único = Verdadeiro
tamanho (mínimo a máximo) × contagem
100 (100 a 999) × 1001000 (1000 a 9999) × 10
PythonPhpPythonPhp
0,268010,359023.100183.4292
0,396020,453034.497264.19524
0,227010,384022,481143.64421
0,302020,426033,34194.17524
0,304020,644043.365196.22036

Há uma conclusão interessante - a ordem inversa não afeta tanto a velocidade, que caiu apenas 2 vezes em comparação com o número aleatório.

Meio: Binário


tipo = aleatório, único = Falso, min = 0, max = 1
tamanho × contagem
100 × 1001000 × 10
PythonPhpPythonPhp
0,0730,0940,811050,86905
0,104010,113011.163071.06606
0,088010,129010,864051,18207
0,115010,150011,301071,41608
0,114010,258011.319082,44614

De mais ou menos interessante: se em vez de números de 100 a 9999 você classificar zeros e um, os indicadores de velocidade não crescerão muito.

Campeões


A principal intriga aqui é se a triagem com um pente e uma triagem k pode espremer o jejum do pedestal?

Campeões: Aleatório


Para descobrir, vamos formar pacotes de matriz aleatória: 10 peças de 10 mil elementos e 10 peças de 100 mil elementos. Eu queria dar milionários aos algoritmos de entrada, mas o laptop não puxou. Como não há RAM suficiente, a profundidade da recursão é muito grande.
tipo = aleatório, único = Falso, contagem = 10
tamanho (mínimo até máximo)
10000 (de 10000 a 99999)100000 (de 100000 a 999999)
PythonPhpPythonPhp
0,802050,6310410.45068.24647
0,477031,640096.6513826.5435
0.900052.1861315.808929.4867

A classificação do Python K é mais lenta e o PHP é mais rápido que a classificação rápida.
Classificar o pente em comparação com o rápido parece sólido, embora seja inferior a ele em todos os testes (e nestes e nos seguintes) para quaisquer conjuntos de dados.

No entanto, existem pentes e uma importante vantagem indiscutível. Não possui recursão e, portanto, diferentemente de seus colegas, processa com sucesso matrizes de milhões de elementos.

Casos especiais


Embora os campeões sejam centenas de vezes mais rápidos que os camponeses comuns, em alguns conjuntos de dados específicos as classificações mostram mais simplesmente que não são facilmente costuradas.

Casos especiais: quase ordenados


Vamos tentar matrizes quase ordenadas, basta ter um tamanho maior do que as testadas para os camponeses comuns.

Um pacote de 10 matrizes de 10 mil cada e um pacote de 10 matrizes de 100 mil elementos cada.
type = quase, único = Falso
tamanho (mínimo a máximo) × contagem
10000 (de 10000 a 99999) × 10100000 (de 100000 a 999999) × 10
PythonPhpPythonPhp
0,432020,0580,817050,58003
0,0840,0620,858050,54003
0,116010,124011.419081.36008
0,140010.119011.834111,41708
0,138010,231011,64912.56915
?122.088??
0,715041,589099.7835619.4731

A classificação rápida não está presente aqui - não havia RAM suficiente. Ao mesmo tempo, matrizes aleatórias com 10/100 mil elementos são processadas pelo quicksort com um estrondo. O k-sort teve problemas semelhantes, gerou apenas 10 milésimos em PHP. Matrizes grandes quase classificadas são um caso degenerado para classificação rápida e suas modificações. Devido a esse arranjo de elementos, a recursão divide a matriz em partes para quase todos os pares de elementos adjacentes, o que leva ao número máximo possível de chamadas de recursão.

A propósito, a situação é semelhante com grandes matrizes de ordem inversa. O mesmo problema surge com os quase ordenados - o algoritmo deve se chamar para cada par de elementos adjacentes.

Classificando por um pente, embora funcione uma vez e meia ou duas vezes mais devagar que rápido ou k (em geral), mas não possui os estouros de memória mencionados acima. Sem recursão - não há problema.

Bem, notamos que todos os camponeses do meio alcançaram os campeões em grandes arranjos quase ordenados. Então o princípio funcionou: "Indo silenciosamente - você continuará".

Casos especiais: milhões de rosas escarlates de pequenas matrizes


Pequenas matrizes - o elemento dos camponeses médios. Se você precisar processar um grande número de pequenos conjuntos de números, poderá obter um ganho de tempo adotando uma classificação "primitiva" de bolha ou gnomo. E use a classificação rápida e outras similares para tarefas maiores.
tipo = aleatório, único = Verdadeiro
tamanho (mínimo a máximo) × contagem
5 (10 a 99) × 1.000.00010 (10 a 99) × 1.000.000
PythonPhpPythonPhp
11.7726717.88824.2903933.6659
12.5187218.16529.3326835,202
15.4418817.86130.0667236.7911
14.1868119.783131.6598139,3533
13.6397824.337428.4166252.864
14.2188121.145225,8054832.5419
14.5868328.501624.8594250.3139
18.5380630.723829.664758.2493


Com as trocas, tudo fica claro. Agora, a parte realmente interessante - a classificação por inserções.

Referências


Aplicativo AlgoLab do Excel , com o qual você pode visualizar passo a passo a visualização desses tipos (e não apenas deles).

Todas as matrizes na forma de JSON também são dispostas no disco do Google .

Wiki - Parvo / Pateta , Lento , Anão / Gnomo , Bolha / Bolha , Agitador / Agitador , Ímpar / Par , Pente / Pente , Rápido / Rápido

Artigos da série


Source: https://habr.com/ru/post/pt415691/

More articles:


All Articles