[MÚSICA] Olá, eu gostaria de falar para vocês pouco sobre comparação de desempenho, mas hoje eu vim aqui homenageando o primeiro programador da história. Na verdade, o primeiro programador da história foi uma programadora, não foi programador. Foi uma mulher, a Ada Augusta King depois chamada Condessa de Lovelace. E ela fez contribuições importantes, principalmente no estabelecimento dos primeiros algoritmos, muito antes de existir o computador eletrônico si. Ela trabalhava encima de uma máquina que Charles Babbage tinha definido matematicamente e escreveu os primeiros algoritmos para essa máquina. E uma coisa interessante que ela disse, ela falou quanto mais estudo mais sinto que minha mente nisso é insaciável. Computação a gente precisa está estudando a todo momento. Se você for ser profissional de informática, profissional de desenvolvimento de software, todo ano você tem que aprender arcabouços novos, linguagens novas, várias tecnologias novas. Isso é uma coisa muito instigante, muito prazerosa de se fazer. A gente não pode ficar estagnado. Então, a gente vê que, também, é uma profissão muito interessante para mulheres. E o fato da primeira programadora ser mulher já é indício disso. Então, vamos agora vir aqui e falar para vocês sobre comparação de desempenho. A gente viu diferentes algoritmos de ordenação. Agora como será que a gente pode avaliar qual algoritmo é mais eficiente particular para cada situação diferente? Qual algoritmo é mais rápido? Tem duas formas que a gente pode fazer. A gente pode fazer uma análise matemática da complexidade do algoritmo. Isso vai dar uma ideia, muitas vezes, de quanto aquele algoritmo demora, mas particular se não tiver uma grande diferença ali na complexidade vai ser difícil saber no mundo real mesmo qual a diferença entre os algoritmos. E o único jeito de fazer isso é medindo. Executando o programa e cronometrando quanto tempo ele demora. Agora, como medir o desempenho de programa Python? Eu falei cronometrando, mas a gente não vai ficar na mão com cronômetro. Existem formas mais apropriadas de se fazer isso. Python existem várias formas e eu vou explicar aqui uma delas, que é usando esse módulo time que já vem embutido aí na linguagem de programação Python. Se a gente fizer o import time a gente já tem acesso as funções desse módulo. Particular, uma das funções é essa função time, que não recebe nenhum parâmetro, o que é que ela devolve? Ela devolve o tempo decorrido segundos desde o início dos tempos. Agora, o quê que é o início dos tempo? Quando Deus criou o mundo, ou quando Python foi criado? Não. É quando Unix considera que é o início dos tempos, se você está numa máquina Unix, e daí, a data é primeiro de janeiro de 1970, ou se você está numa máquina Windows é uma outra data, mas a ideia é a mesma. É o número de segundos percorridos desde aquela data. A maior parte dos sistemas operacionais sólidos utilizados hoje dia, como Linux, Android ou Mac IOS são baseados no Unix, então pelo menos nesses três sistemas operacionais é o número de segundos decorridos desde primeiro de janeiro de 1970. E ele fala segundos e também tem quatro casas depois da vírgula, então tem uma precisão bem grande. Agora, como é que a gente pode medir o intervalo de tempo decorrido para executar determinado algoritmo? A gente primeiro começa fazendo esse import time, e daí, a gente primeiro, antes de começar, a gente dispara o cronômetro. Como é que a gente faz isso? Por exemplo, escrevendo aqui, antes recebe time ponto time. Tem time duas vezes porque uma vez é o nome do módulo e a outra vez é o nome da função. Daí a gente executa o algoritmo que a gente quer cronometrar. E daí, a gente termina o cronômetro, ou seja, a gente mede de novo guardando, por exemplo, você grava depois, aquele número de segundos decorridos. Então, você tem o início e o fim. E daí, a gente já consegue calcular quanto tempo demorou. Por exemplo, eu posso falar que a execução do algoritmo demorou daí, quanto tempo demorou? A gente tem que calcular o delta T, né. Então, é o valor do depois que o algoritmo terminou, menos o valor de antes dele começar. Esse é o valor aqui segundos, tá. Então, com essas quatro linhas muito simples, a gente consegue medir o tempo, calcular o tempo que demorou para executar algoritmo e imprimir esse valor. Vamos, então, agora criar aqui programa para calcular os tempos que demoram para executar aqueles dois algoritmos de ordenação que a gente viu agora há pouco. O algorimo da bolha, o BubbleSort, e o algoritmo da seleção direta. Então, para medir esses dois algoritmos aqui, vamos criar uma classe, eu vou chamar ela de contatempos, e daí, eu vou querer analisar quanto tempo demora esses algoritmos para ordenar vetor bem grande de números aleatórios. Então, vamos gerar uma lista aleatória, eu vou ter uma função aqui chamada lista aleatória que vai receber como parâmetro o número n, que vai ser o número de elementos dessa lista e eu vou começar com essa lista aqui. Vou começar com ela zerada. Então, fazendo isso aqui este comandinho aqui vai gerar uma lista zerada de n posições. Quer ver como funciona? Zero, esse zero aqui está dizendo que vai ser zerada, e eu vou colocar, por exemplo, uma lista de 100 elementos. Olha, gera uma lista de 100 elementos todos zerado. Então, a minha lista começa com n elementos, aqui zerados, e agora eu quero preencher ela com números aleatórios. Como é que eu vou fazer isso? Eu vou percorrer toda a lista e daí para cada elemento da lista, eu vou colocar número aleatório. Como é que eu consigo gerar número aleatório? Bem, Python tem módulo chamado random e dentro deste módulo tem uma função chamada randrange que dado determinado valor, por exemplo, 1000, eu coloquei 1000? Ele vai gerar inteiros positivos entre zero e 1000 menos. Então, ele vai gerar inteiros aleatórios aqui entre zero e 999. E a lista vai ficar completamente preenchida com números aleatórios. E daí, eu posso devolver aqui a minha lista. Então, eu vou usar essas listas aleatórias para analisar quanto tempo demora. Eu vou salvar isso aqui num arquivo, deixa eu ver aqui no diretório, certo. Nas minhas aulas da parte três e eu vou chamar isso aqui de contaTempos. Pronto, salvamos. Agora, vamos fazer uma função compara propriamente dito. Que vai comparar o desempenho desses dois algoritmos de ordenação do BubbleSort e da seleção direta vetores de tamanho n. Então, primeiro vamos criar uma lista aí. Vou chamar de lista1 recebe lista aleatória, de tamanho n, tá. Note que eu vou precisar de duas listas. Porquê? Porque eu vou pegar, gerar uma lista, por exemplo, de 1000 elementos e pedir para o BubbleSort ordenar. Depois, eu preciso de uma outra lista para o seleção direta ordenar, porque se eu usasse a mesma lista, o seleção direta já ia receber a lista já pré-ordenada, daí não seria justo. Então, eu vou criar duas listas aqui, só que eu quero que elas sejam idênticas. Então, para isso na verdade eu vou clonar nessa lista2, clonar a lista1. Python é muito fácil clonar uma lista simplesmente fazendo assim. Esse colchete, dois pontos, colchete a gente está clonando, na verdade, ele está criando uma segunda lista mas o conteúdo é igual. Agora, vou precisar criar uma instância aí da minha classe ordenador. Deixa eu colocar, fazer o import aqui da classe ordenador, então. Import ordenador. Aliás, eu tinha esquecido o import do random que também vai ser necessário. E aqui, então, ordenador ponto ordenador. Pronto, criei uma nova instância dessa classe ordenador, agora eu posso começar a ordenar. Então, vamos usar aquele padrãozinho que eu mostrei. Antes vai ser time ponto time, aí lembrar que eu preciso, então, importar aqui o módulo time. Daí, eu vou executar. O.bolha. E eu preciso passar como parâmetro a lista. E daí, depois, recebe time ponto time. E daí, eu posso dizer que o algoritmo da bolha demorou, vai ser depois menos antes, segundos. Pronto. Então, daí para a seleção direta, eu posso fazer algo bem semelhante. Então, antes, isso aqui agora é lista2. E eu vou chamar o seleção direta. E aqui é o seleção direta. Então, eu acho que está certo. Vamos ver. Vamos salvar aqui. Vamos tentar executar, se der algum erro. Deu algum erro. No madule named ordenador, eu acho que eu já sei o que aconteceu. Eu acho que eu acabei mudando a localização aqui do ordenador. Eu tinha colocado aqui, eu vou trazer de volta. Ordenador, isso. Eu tinha colocado ele outro diretório, vamos ver se agora dá certo. [SEM ÁUDIO] Agora deu certo. Então, vamos criar uma instância dessa classe contaTempos. ContaTempos. E agora vou fazer o c.compara para executar o algoritmo que vai comparar, vamos ver se ele.. o compara tem que passar como parâmetro, né. Aqui o tamanho do vetor, vamos começar com vetores de tamanho 1000. Uma lista de tamanho 1000. O bolha demorou 0.14 segundos e o seleção direta demorou 0.58, 0.058. Aliás, ele foi quase aproximadamente três vezes mais rápido. Vamos fazer uma outra comparação aqui, com vetores de tamanho 5000. A gente vê que está até demorando bastante para imprimir. O bolha demorou 3.46 segundos e o seleção direta demorou aí segundo e meio, mais ou menos. Então, a gente está vendo que o seleção direta aqui está sendo aproximadamente três vezes mais rápido. Então, a gente viu aqui uma forma de comparar o desempenho de dois algoritmos. Agora, a gente está vendo que o seleção direta está sendo bem melhor que a bolha. Só que o algoritmo da bolha, ele tem uma forma relativamente simples da gente melhorar o desempenho dele alguns casos. Vamos pensar pouco. Como que a gente poderia melhorar o desempenho da bolha, particular? Ele funciona bem quando a lista já está quase ordenada. Vamos pensar pouco como que a gente poderia melhorar o desempenho dele quando a lista está quase ordenada. Pensa pouco você olhando para o algoritmo da bolha e a gente volta daqui a pouco. [MÚSICA] [MÚSICA] [MÚSICA]
