Estruturas de dados e algoritmos em Python: tudo o que você precisa saber

Estruturas de dados e algoritmos em Python são dois dos conceitos mais fundamentais em ciência da computação. São ferramentas indispensáveis ​​para qualquer programador. As estruturas de dados em Python lidam com a organização e armazenamento de dados na memória enquanto um programa os processa. Por outro lado, os algoritmos Python referem-se ao conjunto detalhado de instruções que auxiliam no processamento de dados para uma finalidade específica.

Alternativamente, pode-se dizer que diferentes estruturas de dados são logicamente utilizadas por algoritmos para resolver um problema particular de análise de dados. Seja um problema do mundo real ou uma pergunta típica relacionada à codificação, uma compreensão das estruturas de dados e algoritmos em Python é crucial se você deseja encontrar uma solução precisa. Neste artigo, você encontrará uma discussão detalhada de diferentes algoritmos e estruturas de dados Python. Se você estiver interessado em aprender mais sobre Python, confira nossos cursos de ciência de dados .

Saiba mais: As seis estruturas de dados mais usadas em R

O que são estruturas de dados em Python?

As estruturas de dados são uma forma de organizar e armazenar dados; eles explicam a relação entre os dados e várias operações lógicas que podem ser executadas nos dados. Há muitas maneiras pelas quais as estruturas de dados podem ser classificadas. Uma maneira é categorizá-los em tipos de dados primitivos e não primitivos.

Enquanto os tipos de dados primitivos incluem Integers, Float, Strings e Boolean, os tipos de dados não primitivos são Array, List, Tuples, Dictionary, Sets e Files. Alguns desses tipos de dados não primitivos, como Lista, Tuplas, Dicionários e Conjuntos, são incorporados ao Python. Há outra categoria de estruturas de dados em Python que é definida pelo usuário; ou seja, os usuários os definem. Estes incluem Stack, Queue, Linked List, Tree, Graph e HashMap.

Estruturas de dados primitivas

Essas são as estruturas de dados básicas em Python contendo valores de dados puros e simples e servem como blocos de construção para manipulação de dados. Vamos falar sobre os quatro tipos primitivos de variáveis ​​em Python:

• Inteiros – Este tipo de dados é usado para representar dados numéricos, ou seja, números inteiros positivos ou negativos sem um ponto decimal. Digamos, -1, 3 ou 6.
• Float – Float significa 'número real de ponto flutuante'. É usado para representar números racionais, geralmente contendo um ponto decimal como 2,0 ou 5,77. Como Python é uma linguagem de programação tipada dinamicamente, o tipo de dados que um objeto armazena é mutável e não há necessidade de declarar explicitamente o tipo de sua variável.
• String – Este tipo de dados denota uma coleção de alfabetos, palavras ou caracteres alfanuméricos. Ele é criado incluindo uma série de caracteres dentro de um par de aspas duplas ou simples. Para concatenar duas ou mais Strings, a operação '+' pode ser aplicada a elas. Repetir, emendar, capitalizar e recuperar são algumas das outras operações de String em Python. Exemplo: 'azul', 'vermelho', etc.
• Boolean – Este tipo de dado é útil em expressões condicionais e de comparação e pode assumir os valores TRUE ou FALSE.

Saiba mais: Data Frames em Python

Estruturas de dados não primitivas incorporadas

Em contraste com as estruturas de dados primitivas, os tipos de dados não primitivos não apenas armazenam valores, mas uma coleção de valores em diferentes formatos. Vamos dar uma olhada nas estruturas de dados não primitivas em Python:

• • Listas – Esta é a estrutura de dados mais versátil em Python e é escrita como uma lista de elementos separados por vírgulas entre colchetes. Uma Lista pode consistir em elementos heterogêneos e homogêneos. Alguns dos métodos aplicáveis ​​em uma lista são index(), append(), extend(), insert(), remove(), pop(), etc. As listas são mutáveis; ou seja, seu conteúdo pode ser alterado, mantendo a identidade intacta.

Fonte

• Tuplas – Tuplas são semelhantes a Listas, mas são imutáveis. Além disso, ao contrário das Listas, as Tuplas são declaradas entre parênteses em vez de colchetes. O recurso de imutabilidade denota que uma vez que um elemento foi definido em uma Tupla, ele não pode ser excluído, reatribuído ou editado. Ele garante que os valores declarados da estrutura de dados não sejam manipulados ou substituídos.

Fonte

• Dicionários – Os dicionários consistem em pares chave-valor. A 'chave' identifica um item e o 'valor' armazena o valor do item. Dois pontos separa a chave de seu valor. Os itens são separados por vírgulas, com tudo entre colchetes. Enquanto as chaves são imutáveis ​​(números, Strings ou Tuplas), os valores podem ser de qualquer tipo.

Fonte

• Conjuntos – Conjuntos são uma coleção não ordenada de elementos únicos. Assim como as Listas, os Conjuntos são mutáveis ​​e escritos entre colchetes, mas dois valores não podem ser iguais. Alguns métodos Set incluem count(), index(), any(), all(), etc.

Fonte

• Lists vs. Arrays – Não existe um conceito embutido de Arrays em Python. Os arrays podem ser importados usando o pacote NumPy antes de inicializá-los. Para saber mais sobre o NumPy, você pode conferir nosso tutorial do python NumPy . Listas e Arrays são em sua maioria semelhantes, exceto por uma diferença – enquanto Arrays são coleções de apenas elementos homogêneos, Listas incluem itens homogêneos e heterogêneos.

Checkout: Tipos de Árvore Binária

Estruturas de dados definidas pelo usuário em Python

A seguir, em nossa discussão sobre estruturas de dados e algoritmos em Python, há uma breve visão geral das diferentes estruturas de dados definidas pelo usuário:

• Pilhas – Pilhas são estruturas de dados lineares em Python. O armazenamento de itens em Stacks é baseado nos princípios de First-In/Last-Out (FILO) ou Last-In/First-Out (LIFO). Em Stacks, a adição de um novo elemento em uma extremidade é acompanhada pela remoção de um elemento da mesma extremidade. As operações 'push' e 'pop' são usadas para inserções e exclusões, respectivamente. Outras funções relacionadas ao Stack são empty(), size() e top(). As pilhas podem ser implementadas usando módulos e estruturas de dados da biblioteca Python – list, collections.deque e queue.LifoQueue.
• Queue – Semelhante às pilhas, as filas são estruturas de dados lineares. No entanto, os itens são armazenados com base no princípio First-In/First-Out (FIFO). Em uma Fila, o item adicionado menos recentemente é removido primeiro. As operações relacionadas ao Queue incluem Enqueue (adicionando elementos), Dequeue (excluindo elementos), Front e Rear. Assim como as pilhas, as filas podem ser implementadas usando módulos e estruturas de dados da biblioteca Python – list, collections.deque e queue.
• Árvore – Árvores são estruturas de dados não lineares em Python e consistem em nós conectados por arestas. As propriedades de uma Árvore são: um nó é designado como nó raiz, exceto a raiz, todos os outros nós têm um nó pai associado e cada nó pode ter um número arbitrário de nós filhos. Uma estrutura de dados de árvore binária é aquela cujos elementos não têm mais de dois filhos.
• Lista Vinculada – Uma série de elementos de dados unidos por meio de links é chamada de Lista Vinculada em Python. É também uma estrutura de dados linear. Cada elemento de dados em uma lista vinculada é conectado a outro usando ponteiro. Como a biblioteca Python não contém Listas Vinculadas, elas são implementadas usando o conceito de nós. Linked Lists tem vantagem sobre Arrays por ter um tamanho dinâmico, com facilidade de inserção/exclusão de elementos.
• Graph – Um Graph em Python representa pictoricamente um conjunto de objetos, com alguns pares de objetos conectados por links. Os vértices representam os objetos que estão interconectados e os links que unem os vértices são chamados de arestas. O tipo de dados do dicionário Python pode ser usado para apresentar gráficos. Em essência, as 'chaves' do dicionário representam os vértices, e os 'valores' indicam as conexões ou arestas entre os vértices.
• HashMaps/Tabelas de Hash – Neste tipo de estrutura de dados, uma função Hash gera o endereço ou valor de índice do elemento de dados. O valor do índice serve como chave para o valor dos dados, permitindo acesso mais rápido aos dados. Assim como no tipo de dados do dicionário, as Tabelas de Hash possuem pares chave-valor, mas uma função de hash gera a chave.

O que são algoritmos em Python?

Algoritmos Python são um conjunto de instruções que são executadas para obter a solução para um determinado problema. Como os algoritmos não são específicos da linguagem, eles podem ser implementados em várias linguagens de programação. Nenhuma regra padrão orienta a escrita de algoritmos. Eles são dependentes de recursos e problemas, mas compartilham algumas construções de código comuns, como controle de fluxo (if-else) e loops (do, while, for). Nas seções a seguir, discutiremos brevemente algoritmos de travessia de árvore, classificação, pesquisa e gráfico.

Algoritmos de travessia de árvore

Traversal é um processo de visitar todos os nós de uma Árvore, começando pelo nó raiz. Uma árvore pode ser percorrida de três maneiras diferentes:

– A travessia em ordem envolve visitar a subárvore à esquerda primeiro, seguida pela raiz e depois a subárvore direita.

– Na travessia de pré-ordem, o primeiro a ser visitado é o nó raiz, seguido pela subárvore esquerda e, finalmente, a subárvore direita.

– No algoritmo de travessia pós-ordem, a subárvore esquerda é visitada primeiro, depois a subárvore direita é visitada, com o nó raiz sendo visitado por último.

Saiba mais: Como criar uma árvore de decisão perfeita

Algoritmos de classificação

Os algoritmos de classificação denotam as maneiras de organizar os dados em um formato específico. A classificação garante que a pesquisa de dados seja otimizada em alto nível e que os dados sejam apresentados em um formato legível. Vejamos os cinco tipos diferentes de algoritmos de classificação em Python:

• Bubble Sort – Este algoritmo é baseado em comparação em que há trocas repetidas de elementos adjacentes se estiverem em uma ordem incorreta.
• Merge Sort – Com base no algoritmo de divisão e conquista, Merge sort divide o Array em duas metades, classifica-os e depois os combina.
• Ordenação por Inserção – Esta ordenação começa com a comparação e ordenação dos dois primeiros elementos. Em seguida, o terceiro elemento é comparado com os dois elementos classificados anteriormente e assim por diante.
• Shell Sort – É uma forma de ordenação por Inserção, mas aqui, elementos distantes são ordenados. Uma grande sublista de uma determinada lista é classificada e o tamanho da lista é progressivamente reduzido até que todos os elementos sejam classificados.
• Ordenação por Seleção – Este algoritmo começa encontrando o valor mínimo de uma lista de elementos e o coloca em uma lista ordenada. O processo é então repetido para cada um dos elementos restantes na lista não ordenada. O novo elemento que entra na lista ordenada é comparado com seus elementos existentes e colocado na posição correta. O processo continua até que todos os elementos sejam classificados.

Algoritmos de Pesquisa

Os algoritmos de pesquisa ajudam a verificar e recuperar um elemento de diferentes estruturas de dados. Um tipo de algoritmo de busca aplica o método de busca sequencial onde a lista é percorrida sequencialmente e cada elemento é verificado (busca linear). Em outro tipo, a pesquisa por intervalo, os elementos são pesquisados ​​em estruturas de dados classificadas (pesquisa binária). Vejamos alguns dos exemplos:

• Pesquisa Linear – Neste algoritmo, cada item é pesquisado sequencialmente um por um.
• Pesquisa Binária – O intervalo de pesquisa é repetidamente dividido pela metade. Se o elemento a ser pesquisado for inferior ao componente central do intervalo, o intervalo será reduzido à metade inferior. Caso contrário, é reduzido para a metade superior. O processo é repetido até que o valor seja encontrado.

Algoritmos Gráficos

Existem dois métodos de percorrer grafos usando suas arestas. Estes são:

• Depth-first Traversal (DFS) – Neste algoritmo, um gráfico é percorrido em um movimento de profundidade. Quando qualquer iteração enfrenta um beco sem saída, uma pilha é usada para ir para o próximo vértice e iniciar uma pesquisa. O DFS é implementado em Python usando os tipos de dados definidos.
• Breadth-first Traversal (BFS) – Neste algoritmo, um gráfico é percorrido em um movimento de largura. Quando qualquer iteração enfrenta um beco sem saída, uma fila é usada para ir para o próximo vértice e iniciar uma pesquisa. O BFS é implementado em Python usando a estrutura de dados da fila.

Análise de algoritmo

• A Priori Analysis – Representa uma análise teórica do algoritmo antes de sua implementação. A eficiência de um algoritmo é medida presumindo-se que fatores, como a velocidade do processador, sejam constantes e não tenham consequências no algoritmo.
• Uma Análise Posterior – Refere-se à análise empírica do algoritmo após sua implementação. Uma linguagem de programação é usada para implementar o algoritmo selecionado, seguido de sua execução em um computador. Essa análise coleta estatísticas, como o tempo e o espaço necessários para a execução do algoritmo.

Conclusão

Se você é um veterano em programação ou novo, você não pode ignorar estruturas de dados e algoritmos em Python . Esses conceitos são cruciais quando você está executando operações em dados e precisa otimizar o processamento de dados. Enquanto as estruturas de dados ajudam na organização das informações, os algoritmos fornecem as diretrizes para resolver o problema da análise de dados. Juntos, eles fornecem uma maneira para os cientistas da computação processarem as informações fornecidas como dados de entrada.

Se você está curioso para aprender sobre ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1 -on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.