Um pouco de conhecimento sobre Python
Python é uma ótima linguagem. Eu tentei várias línguas antes: Pascal na escola; C, C com aulas, C ++ na universidade. Os dois últimos (três) instilaram uma forte aversão à programação: em vez de resolver o problema, você mexe com alocações e destruidores (palavras assustadoras do passado), pensa em termos de primitivos de baixo nível. Minha opinião é que C não é adequado para resolver problemas educacionais e científicos (em qualquer caso, no campo da matemática). Tenho certeza de que eles vão se opor a mim, mas não estou tentando impor nada a ninguém, estou apenas expressando minha opinião.
Python já foi uma revelação. Pela primeira vez na minha vida, escrevi vários níveis de abstração mais altos do que o habitual em C. A distância entre a tarefa e o código foi reduzida como nunca antes.
Provavelmente eu teria feito isso a vida toda em Python se não tivesse que implementar de repente os testes estatísticos do NIST. Parece que a tarefa é muito simples: existe uma matriz de vários megabytes (> = 10), existe um conjunto de testes que devem ser aplicados a essa matriz.
O que é bom numpy?
Existe um bom pacote numpy em python para trabalhar com matrizes, que é essencialmente uma interface de alto nível para bibliotecas rápidas como LAPACK. Parece que todo o conjunto de cavalheiros da computação científica está disponível (Sympy, Numpy, Scipy, Matplotlib), o que mais você poderia querer?
Todo mundo que lidou com entorpecido sabe que ele é bom, mas não em tudo. Também precisamos tentar garantir que as operações sejam vetorizadas (como em R), ou seja, de certa forma, uniforme para toda a matriz. Se de repente seu problema, por algum motivo, não se encaixar nesse paradigma, então você tem problemas.
De que tipo de tarefas não vetorizadas eu estou falando? Sim, pelo menos use o mesmo NIST: calcule o comprimento do registro de deslocamento linear usando o algoritmo Berlekamp-Messi; calcule o comprimento da subsequência mais longa de unidades consecutivas e assim por diante. Não excluo a possibilidade de que exista algum tipo de solução engenhosa que reduza o problema a um vetorizado.
Astúcia?Como exemplo do mesmo NIST: era necessário calcular o número de "comutadores" da sequência, onde, por "comutação", eu significava mudar unidades consecutivas (... 1111 ...) para zeros consecutivos (... 000 ... ) e vice-versa. Para fazer isso, você pode pegar a sequência original sem o último elemento (x [: -1]) e subtrair a sequência deslocada por 1 (x [2:]) e, em seguida, calcular o número de elementos diferentes de zero na nova sequência resultante. Todos juntos terão a seguinte aparência:
np.count_nonzero(x[:-1] - x[1:])
Pode parecer um exercício divertido para a mente, mas essencialmente algo antinatural está acontecendo aqui, um truque que não será óbvio para o leitor após um curto período de tempo. Sem mencionar que isso ainda é lento - ninguém cancelou a alocação de memória.
As operações não vetorizadas em Python são demoradas. Como lidar com eles se o sono não é suficiente? Geralmente eles oferecem várias soluções:
- Numba JIT. Se ela trabalhou como descrito na página de título do Numba, acho que valeria a pena terminar a história. Eu tinha esquecido um pouco no passado que o que havia dado errado com ela; o ponto principal é que a aceleração não foi tão impressionante quanto eu esperava, infelizmente.
- Cython. OK, levante a mão daqueles que acreditam que o cython é uma solução realmente bonita e elegante que não destrói o próprio significado e espírito do Python? Eu acho que não; se você acessa o Cython, já pode parar de se enganar e mudar para algo menos sofisticado, como C ++ e C.
- Reescreva os gargalos em C e retire-os do seu amado Python. OK, mas e se eu tiver todo o programa - é tudo sobre cálculos e gargalos? Xi não oferece! Não estou falando do fato de que nesta solução você precisa conhecer não apenas uma, mas duas linguagens - Python e C.
Aí vem a JULIA!
Tendo sido contemplado com soluções existentes e não encontrado (incapaz de programar) nada de bom, decidi reescrevê-lo com algo "mais rápido". De fato, se você escrever "debulhadora de números" no século 21 com suporte normal a matrizes, operações vetorizadas "prontas para uso", etc. etc., sua escolha não é muito densa:
- Fortran . E não ria, qual de nós não tirou o BLAS / LAPACK dos nossos idiomas favoritos? O Fortran é uma linguagem realmente boa (melhor SI!) Para computação CIENTÍFICA. Não entendi pela razão de que desde o tempo do Fortran muitas coisas foram inventadas e adicionadas às linguagens de programação; Eu esperava algo mais moderno.
- R sofre dos mesmos problemas que o Python (vetorização).
- Matlab - provavelmente sim, infelizmente não tenho dinheiro para verificar.
- Julia - o cavalo está escuro, decola, não decola (e era natural até a versão estável 1.0)
Algumas vantagens óbvias de Julia
- Parece com o Python, pelo menos o mesmo de "alto nível", com a capacidade, se necessário, de reduzir os bits em números.
- Sem problemas com alocações de memória e afins.
- Sistema de tipo poderoso. Os tipos são prescritos opcionalmente e muito doseados. Um programa pode ser escrito sem especificar um único tipo - e, se você fizer, ele poderá fazê-lo rapidamente. Mas existem nuances.
- É fácil escrever tipos personalizados que serão tão rápidos quanto os tipos internos.
- Despacho múltiplo. Você pode falar sobre isso por horas, mas, na minha opinião - é o melhor que Julia tem, é a base do design de todos os programas e, em geral, a base da filosofia da linguagem.
Graças ao envio múltiplo, muitas coisas são escritas de maneira muito uniforme.
Vários exemplos de despacho rand() # 0 1 rand(10) # 10 0 1 rand(3,5) # 3 5 .... using Distributions d = Normal() # 0, 1 rand(d) # rand(d, 10) # 10 ...
Ou seja, o primeiro argumento pode ser qualquer distribuição (unidimensional) de Distribuições, mas a chamada de função permanecerá literalmente a mesma. E não apenas distribuição (é possível transmitir o RNG em si como um objeto MersenneTwister e muito mais). Outro exemplo (na minha opinião, ilustrativo) é a navegação em DataFrames sem loc / iloc.
- 6. Matrizes são nativas, internas. Vetorização fora da caixa.
Contras de ficar calado sobre o que seria um crime!
- Novo idioma. Por um lado, é claro, um sinal de menos. Em algo, talvez imaturo. Por outro lado, ele levou em conta o rake de muitas línguas passadas, está "nos ombros de gigantes", absorveu muitas coisas interessantes e novas.
- É improvável que programas imediatamente rápidos gravem. Existem algumas coisas não óbvias que são muito fáceis de lidar: você entra no rake, pede ajuda à comunidade, entra novamente ... etc. Essas são principalmente instabilidade de tipo, instabilidade de tipo e variáveis globais. Em geral, até onde eu sei, um programador que deseja escrever rapidamente em Julia passa por vários estágios: a) escreve em Python. Isso é ótimo, e também é, mas às vezes haverá problemas de desempenho. b) escreve como em C: prescrevendo manualmente tipos sempre que possível. c) entende gradualmente onde é necessário (muito medido) prescrever tipos e onde eles interferem.
- Ecossistema Alguns pacotes são brutos, no sentido de que em algum lugar constantemente algo cai; alguns são maduros, mas inconsistentes entre si (é necessária a conversão para outros tipos, por exemplo). Por um lado, isso é obviamente ruim; por outro lado, Julia tem muitas idéias interessantes e ousadas apenas porque "estamos nos ombros dos gigantes" - acumulamos uma tremenda experiência de pisar em um ancinho e "como não fazê-lo", e isso é levado em conta (parcialmente) pelos desenvolvedores de pacotes.
- Numerando matrizes de 1. Ha, brincando, é claro que isso é uma vantagem! Não, bem, sério, qual é o problema? Com que índice começa a numeração? Você se acostuma em 5 minutos. Ninguém reclama que números inteiros são chamados de número inteiro, não inteiro. Todas essas são questões de gosto. E sim, use pelo menos o mesmo Cormen de acordo com os algoritmos - tudo é numerado de um lá, e às vezes é inconveniente refazê-lo no Python, pelo contrário.
Bem, por que velocidade?
É hora de lembrar por que tudo foi iniciado.
Nota: Esqueci o Python com segurança, então escreva suas melhorias nos comentários. Tentarei executá-las no meu laptop e ver o tempo de execução.
Então, dois pequenos exemplos com marcas de micropigmentação.
Algo vetorizadoProblema: um vetor X de 0 e 1. é alimentado na entrada da função.É necessário convertê-lo em um vetor de 1 e (-1) (1 -> 1, 0 -> -1) e calcular quantos coeficientes da transformada de Fourier desse vetor são o valor absoluto excede o limite.
def process_fft(x, boundary): return np.count_nonzero(np.abs(np.fft.fft(2*x-1)) > boundary) %timeit process_fft(x, 2000) 84.1 ms ± 335 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
function process_fft(x, boundary) count(t -> t > boundary, abs.(fft(2*x.-1))) end @benchmark process_fft(x, 2000) BenchmarkTools.Trial: memory estimate: 106.81 MiB allocs estimate: 61 -------------- minimum time: 80.233 ms (4.75% GC) median time: 80.746 ms (4.70% GC) mean time: 85.000 ms (8.67% GC) maximum time: 205.831 ms (52.27% GC) -------------- samples: 59 evals/sample: 1
Não veremos nada de surpreendente aqui - mesmo assim, eles não consideram isso por si mesmos, mas o transmitem para programas fortran bem otimizados.
Algo não vetorizávelUma matriz de 0 e 1. é alimentada na entrada.Encontre o comprimento da subsequência mais longa de unidades consecutivas.
def longest(x): maxLen = 0 currLen = 0
function longest(x) maxLen = 0 currLen = 0 # This will count the number of ones in the block for bit in x if bit == 1 currLen += 1 maxLen = max(maxLen, currLen) else maxLen = max(maxLen, currLen) currLen = 0 end end return max(maxLen, currLen) end @benchmark longest(x) BenchmarkTools.Trial: memory estimate: 0 bytes allocs estimate: 0 -------------- minimum time: 9.094 ms (0.00% GC) median time: 9.248 ms (0.00% GC) mean time: 9.319 ms (0.00% GC) maximum time: 12.177 ms (0.00% GC) -------------- samples: 536 evals/sample: 1
A diferença é óbvia a olho nu. Dicas para "finalizar" e / ou vetorizar a versão numpy são bem-vindas. Eu também quero observar que os programas são quase idênticos. Por exemplo, eu não registrei um único tipo em Julia (compare com o anterior) - mesmo assim, tudo funciona rapidamente.
Também quero observar que as versões apresentadas não foram incluídas no programa final, mas foram otimizadas ainda mais; aqui eles são dados como exemplo e sem complicações desnecessárias (encaminhando memória adicional em Julia para executar rfft no local, etc.).
O que saiu no final?
Não mostrarei o código final para Python e Julia: isso é um segredo (pelo menos por enquanto). No momento em que parei para finalizar a versão python, funcionou todos os testes do NIST em uma matriz de 16 megabytes de caracteres binários em ~ 50 segundos. Na Julia no momento, todos os testes são executados no mesmo volume ~ 20 segundos. Pode ser que eu seja um tolo, e havia espaço para otimizações etc. etc. Mas este sou eu, como sou, com todas as suas vantagens e desvantagens e, na minha opinião, não é a velocidade esférica dos programas no vácuo nas linguagens de programação que deve ser considerada, mas como eu pessoalmente posso programá-lo (sem erros realmente graves).
Por que eu escrevi tudo isso?
As pessoas
aqui ficaram interessadas; Eu decidi escrever quando a hora aparecer. No futuro, acho que vou passar por Julia mais detalhadamente, com um exemplo de solução de alguns problemas típicos. Porque Mais idiomas, bons e diferentes, e permita que todos que queiram encontrar algo que lhe convém pessoalmente.