Faça o download do AlgoLab de uma unidade do Google ( arquivos AlgoLab (Excel 2007-2013) .xlsm e AlgoLab (Excel 97-2003) .xls ).O que os bolcheviques vêm falando há tanto tempo e o que venho perseguindo há vários anos em um ritmo diferente finalmente aconteceu. Alguns anos atrás, ele escreveu uma pequena macro para criar animações gif algorítmicas para habrastaty. Com o tempo, meu humilde instrumento cresceu para um tamanho impressionante, o que não é uma vergonha agora para mostrar ao mundo.
Então conheça.
O AlgoLab é um aplicativo do Excel (ou seja, um arquivo do Excel com macros) no qual você pode se familiarizar passo a passo com os algoritmos de classificação. E também há a oportunidade de preparar gif-animação.
Exemplos de animação geradaClassificação de árvore binária
Classificação de espaguete
Tipo de dormir
Apenas 4 folhas - 2 principais e 2, informativas. Aqui estão elas:
Clicar em uma imagem abrirá uma imagem em tamanho real- Classificar folha. Nesta planilha, você pode formar rapidamente uma matriz e selecionar um algoritmo de classificação.
- Processo de folha. Aqui observamos passo a passo como esse ou aquele algoritmo funciona.
- Classificar folha. Aqui está um resumo dos algoritmos.
- Gráfico de folha. Há também um cronograma de lançamento planejado para artigos sobre classificação.
Vamos nos familiarizar com essas folhas com mais detalhes.
Classificar folha
A parte superior da planilha é dedicada à geração de uma matriz não classificada (para que haja algo para alimentar o algoritmo), além de salvar a visualização na forma de imagens no seu computador:
Na primeira linha está a própria matriz. Se necessário, você pode alterar manualmente os valores de elementos individuais:
No canto superior esquerdo, você precisa especificar as principais características da matriz gerada:
O tamanho, se os valores na matriz devem ser não repetitivos (0 - não, 1 - sim), que são iguais aos elementos mínimo e máximo da matriz. As macros VBA incluem resistência a vandalismo para inserir dados, para que você possa inserir alguns valores incorretos. Nesse caso, o aplicativo determinará a que essa ou aquela característica deve ser igual.
E também uma opção para determinar se é necessário executar o algoritmo passo a passo (= 1) ou se é possível aplicar a classificação à estrutura e mostrar apenas o resultado final (= 0). Obviamente, o próprio aplicativo Excel foi criado para observar todo o processo no modo passo a passo; portanto, o valor aqui é geralmente igual a um. Mas, às vezes, ao testar, anulo essa opção para verificar se o novo algoritmo adicionado ao AlgoLab.xlsm funciona (ou seja, primeiro preciso verificar se a matriz classificada é o resultado final, sem perder tempo visualizando a visualização) )
Um pouco à direita está a área na qual você pode especificar como exatamente os elementos na matriz não classificada gerada não são classificados.
Gerar matriz mista aleatória? Ou talvez organize os elementos em ordem decrescente? Ou faça a matriz quase classificada (e também especifique o coeficiente da quase classificação)?
Para selecionar qualquer um desses métodos, basta clicar na célula com o item. Como resultado, a matriz é regenerada na primeira linha. A célula selecionada ficará azul.
À esquerda está o território que será necessário se você precisar não apenas admirar a visualização, mas também salvar todo o processo quadro a quadro como imagens.
Primeiro, você precisa especificar se deseja exportar as etapas de classificação em geral para imagens (= 0, se não, = 1 se sim, e esta opção é "única", ou seja, é redefinida para zero após a classificação ser concluída). Em segundo lugar, você precisa especificar o formato da imagem (apenas quatro opções são possíveis: GIF, JPG, PNG e BMP. A última opção fornece o resultado da mais alta qualidade, por isso recomendo). Em terceiro lugar, você precisa especificar o caminho para a pasta onde salvar as imagens (clique nesta célula e uma caixa de diálogo será aberta para selecionar um diretório). Em seguida, vem a célula que a própria macro preenche - o identificador da sessão (necessário para o nome exclusivo da subpasta para salvar os quadros desse aplicativo de classificação específico). E também é necessário especificar a área de captura corretamente (coordenadas das células superior esquerda e inferior direita, serão os quadros que serão limitados a elas - não copie a folha inteira?)
Bem, na parte correta, você encontrará a célula "Classificar" (que funciona como um botão para iniciar o processo, ao escolher a classificação e gerar uma matriz, basta clicar nela).
Mesmo ao lado deste botão, existem vários caracteres especiais que podem ser usados na visualização. Essas células não precisam ser tocadas.
No fundo, o mais importante é a escolha do algoritmo. Você só precisa clicar no nome do tipo, após o qual a célula com ele ficará azul.
Dos mais de 80 algoritmos, aproximadamente metade deles está disponível hoje. Até agora, os não realizados têm uma aparência pálida em comparação com os já implementados. Ainda não consegui fazer algumas (e nem comecei a implementação). Alguns estão em desenvolvimento. Algumas delas foram escritas e testadas e estarão disponíveis muito em breve (em particular, quase todas as classificações por inserções estão prontas para mim, no entanto, as adicionarei ao aplicativo assim que habrastats forem lançadas para essas classificações nas próximas semanas e compartilharemos o AlgoLab.xlsm atualizado - e o que fazer, não quero estragar novos episódios da minha série).
Planejo modificar algumas das classificações já implementadas. A visualização não me satisfaz em todos os lugares.
Mas nesta área, ao escolher um algoritmo, são carregadas informações resumidas sobre ele. As informações são obtidas da planilha "Classificar", são automaticamente recolhidas com uma macro. A propósito, se você alterar o texto nesta área, na folha original ele também será alterado.
Classifique, como você pode ver muito. Para não se confundirem em todo esse esplendor, eles são divididos em classes, dependendo do método fundamental de organização dos dados. O que são essas classes?
- Classificação aleatória. Os elementos da matriz são misturados aleatoriamente e isso continua até que a estrutura seja ordenada subitamente.
- Classifica trocas. Uma comparação total em pares (e troca) de elementos da matriz é organizada.
- Classificar inserções. Os elementos são selecionados e cada um é inserido em seu lugar.
- Classifique por escolha. Na sub-matriz, o elemento máximo é selecionado, que é inserido no final da sub-matriz. Em seguida, para a parte não classificada restante, o mesmo procedimento é repetido.
- Mesclar classificações. Subarrays ordenados pesquisados que se conectam.
- Classificar por distribuição. Os elementos são divididos em classes até que isso leve ao resultado desejado.
- Classificação híbrida. Os métodos de troca, inserção, seleção, mesclagem e algoritmos de distribuição são combinados.
- Classificação paralela. Algoritmos em que o processamento paralelo de diferentes partes da matriz é fornecido.
- Classificação de redes. A matriz é passada pela rede de classificação e, na saída, é solicitada.
- Outras classificações. Pseudo-algoritmos, classificação cômica e simplesmente extravagante.
Nos próximos assaltos, nuances detalhadas para cada classe serão destacadas. Bem, passamos à próxima página.
Folha de processo
Na verdade, ao gerar uma matriz, escolhendo um algoritmo e clicando no botão "Classificar", a macro é lançada nesta planilha. É aqui que o mistério da organização de dados ocorre.
Durante todo o processo acima, você será acompanhado por esta maravilhosa janela:
Como o modo de visualização é passo a passo, para avançar para o próximo passo, é necessário
pressionar o botão "Novo Passo" . Não é muito conveniente fazer isso com o mouse; portanto, o foco da entrada da janela está sempre nesse botão. Ou seja, para prosseguir com as próximas etapas, você não precisa ter preguiça de pressionar Enter teclado (nenhum outro gesto será necessário).
O botão "Concluir" exibe o processo em uma exibição passo a passo. O algoritmo silenciosamente concluirá seu trabalho e mostrará apenas o resultado final. Você não verá o estágio final da operação de classificação.
O botão "Abortar" interrompe completamente o trabalho das macros nesta etapa.
O botão "Instantâneo" permite salvar uma captura de tela desta etapa específica. Você encontrará a imagem na pasta especificada nas configurações da folha de classificação.
Classificar folha
Uma tabela enorme com todo tipo de conhecimento sobre esse tipo é armazenada aqui. Como você se lembra, as informações são extraídas daqui ao escolher a classificação na folha de classificação. Me arrependo, embora a qualidade do preenchimento seja tão positiva, não havia perseverança suficiente para introduzir meticulosamente a quantidade máxima de dados corretos. Espero recuperar o atraso em um futuro muito próximo.
Gráfico de folha
Nesta folha, você pode se familiarizar com minhas fantasias sobre as datas dos lançamentos habrastáticos mais próximos.
Vou falar sobre algoritmos nesta ordem.
Trocas → Inserções → Seleção → Mesclar → Distribuição →
→ Híbridos → Paralela → Rede → Aleatório
As classes gerais são listadas, mas, em geral, várias opções que obedecem a esse esquema geral serão dedicadas a cada classe.
- Descrição da classe de classificação. Nuanças básicas e introdutórias inerentes a todos os tipos de classe, tipos de classe básica. Normalmente, esses artigos introdutórios conterão informações bastante conhecidas. Mas ainda assim, tentarei não ficar entediado.
- Algumas classes pouco conhecidas. Aqui vou deliciar você com material novo, sobre o qual praticamente não há informações em russo. E você não encontrará nada, mesmo em inglês. Os artigos separados não serão apenas sobre classificação de trocas, porque não há tempo para um exclusivo interessante.
- Comparação prática de tipos de classe entre si. Para cada grupo de algoritmos, haverá um artigo final dedicado ao teste de classificações em diferentes conjuntos de dados. Aqui prometo muitas descobertas incríveis!
Comparação prática de classificação
Foi planejado comparar apenas a implementação python de algoritmos. No entanto, tendo visto os primeiros resultados no exemplo da classificação de gnomos, cheguei à conclusão de que eles fornecerão um equívoco sobre a velocidade relativa.
O Python possui seu próprio sistema de acesso à memória de variáveis (especialmente se essas variáveis são atribuídas umas às outras), e é por isso que algoritmos otimizados podem ficar mais lentos.
Uma situação semelhante com Shaker / Bubble. Ao contrário das expectativas, a classificação por bolhas funciona mais rapidamente que a classificação por shaker (embora a Classificação por Shaker seja uma classificação por bolhas aprimorada).
Para controle, também testei as classificações em PHP (trabalho principalmente nessa linguagem, portanto, um teste alternativo foi mais rápido e fácil de criar). A situação já é "normal" - o "gnome" otimizado em todos os conjuntos de dados funciona claramente mais rápido que o normal.
No entanto, o PHP também tem uma reputação de ser "imperfeito" e uma ferramenta lenta, então decidi que também não era adequado para conclusões globais. Para minimizar possíveis censuras [na escolha da linguagem errada para testar a velocidade real], decidi minimizar os principais testes também em Java. No entanto, tive uma escassez de conhecimento para esse idioma. Infelizmente, não cresceu juntos.
Assim, o teste será realizado imediatamente em
três dois idiomas:
- Python Primeiro de tudo, essa linguagem é mais adequada para descrever o algoritmo. Como existem funções corretas funcionando, mediremos o tempo para elas. Mas os resultados serão um tanto duvidosos.
- PHP Inicialmente, eu não usaria esse idioma de nenhuma maneira em uma série de artigos. Mas como eu escrevi um ambiente para testar as classificações e as próprias implementações neste PL estão disponíveis, por que não? Os resultados práticos pelos quais se pode julgar a eficácia relativa dos algoritmos são mais adequados em comparação com o Python.
Java É com base nos resultados em Java que tiraremos as principais conclusões.
Obviamente, todas as opções em todos os idiomas serão compartilhadas.
Perguntas frequentes
Já prevejo algumas perguntas da platéia, responderei imediatamente.
Por que o programa para visualizar algoritmos é implementado no Excel?
Então, ao mesmo tempo, era mais rápido e fácil (para mim). O espaço de treliça das planilhas acabou sendo uma solução turnkey muito, muito conveniente para visualizar o trabalho com matrizes.
Ok, vamos dar uma olhada em todos esses tipos. O que vem a seguir?
Baseado no AlgoLab, farei visualizações de árvores, gráficos. Toalha de mesa de Ulam, formiga de Langton, só isso. Ainda existem espaços em branco para 2048 (a IA é reproduzida usando o método minimax e Monte Carlo - é necessário finalizá-lo). Obras são muitas terras.
Referências
Faça o download do AlgoLab de uma unidade do Google ( arquivos AlgoLab (Excel 2007-2013) .xlsm e AlgoLab (Excel 97-2003) .xls ).Artigos da série