Scala Collections: como escolher a mais adequada (artigo técnico)

Programar é compreender. Antes de escrever uma única linha de código, é necessário saber claramente com o que se está a trabalhar: o que é uma coleção, o que está por detrás dela e como pode ser utilizada. A escolha da coleção certa em Scala começa exatamente aí - nas estruturas de dados, nos tipos abstratos de dados e na notação assintótica. Estes são os instrumentos conceptuais que permitem navegar pela Scala Collections Library e tomar decisões fundamentadas.

Os blocos fundamentais: o que está por detrás de cada coleção

Uma estrutura de dados tem três componentes principais: os dados que armazena, as relações entre os elementos e as operações que suporta - como pesquisa, modificação e atualização. As operações são, na prática, a parte mais útil.

As coleções Scala são suportadas por várias estruturas de dados, entre as quais arrays, listas ligadas, tabelas de dispersão, árvores red-black, heaps binários e tries radix-balanced. Compreender estas estruturas e as suas características de desempenho é essencial para navegar pela hierarquia de coleções Scala.

Agrupar por comportamento, não por código: tipos abstratos de dados

Os tipos abstratos de dados, ou ADTs, são um mecanismo para agrupar e classificar estruturas de dados. Muitas estruturas de dados têm algo em comum - operações ou propriedades dos dados. Um ADT é a forma como as agrupamos.

Por exemplo, no caso do ADT List, tanto uma lista ligada como um array podem ser tratados como uma estrutura de dados semelhante a uma lista. São semelhantes no sentido em que representam uma sequência ordenada de elementos; é possível obter o primeiro elemento, o restante da sequência ou qualquer outra parte.

Quando falamos de ADTs, falamos sobretudo de semântica e de interfaces. Uma compreensão clara dos ADTs permite abordar qualquer biblioteca de coleções com confiança.

Uma biblioteca, várias camadas: as coleções Scala através da lente da ciência da computação

As coleções Scala estão organizadas em dois pacotes: imutáveis e mutáveis. O mesmo ADT pode ter diferentes implementações. Por exemplo, ArraySeq, ArrayBuffer e StringBuilder são tipos Scala diferentes, mas utilizam a mesma estrutura de dados subjacente e correspondem ao mesmo tipo abstrato de dados.

O ADT Map segue um padrão semelhante, com HashMap, LinkedHashMap e VectorMap a oferecerem diferentes implementações para requisitos específicos. Compreender a estrutura de dados subjacente permite selecionar a coleção mais adequada.

Antes de escolheres uma coleção, responde a estas perguntas

Para escolher uma coleção concreta, é necessário compreender primeiro os requisitos da aplicação. Seis fatores moldam essa decisão:

Propriedades dos dados do domínio: compreender as características dos dados - valores possíveis, relações, ordenação e unicidade.

Operações pretendidas: considerar os tipos de operações que serão realizadas - inserção, eliminação, recuperação e iteração.

Características de desempenho: avaliar a complexidade temporal esperada e a utilização de memória.

Paralelismo: considerar se a coleção precisa de suportar operações paralelas.

Segurança em ambientes concorrentes: avaliar se a estrutura de dados precisa de ser thread-safe para evitar corrupção de dados ou race conditions.

Outros requisitos: considerar mutabilidade, imutabilidade, escalabilidade ou compatibilidade com código existente.

Mesmo tendo as perguntas certas em mente, há dois erros que surgem frequentemente.

O primeiro é utilizar um tipo de implementação específico no código de interface - em assinaturas de funções e em traits. Usar List em todo o lado não é ideal, porque List não é a estrutura de dados mais rápida em muitos cenários, além de tornar o código menos flexível. Deve escolher-se a abstração mais adequada. Se o código deve funcionar com uma sequência, escolha Seq.

O segundo erro é confiar nas implementações por defeito. A implementação por defeito de Seq é simplesmente uma List. No entanto, se o cenário envolver pesquisa linear sobre dados que não mudam, ArraySeq é muito mais adequada. Os dados são colocados uma vez e pesquisados muitas vezes - muito mais rapidamente do que com a implementação por defeito.

E não se esqueça do Princípio da Parcimónia: o sistema deve ser tão complexo quanto necessário para resolver a tarefa. Escolha a solução mais simples que funcione.

Big O não conta a história toda

A notação assintótica é essencial para avaliar o desempenho das operações em estruturas de dados, tanto em termos de tempo de execução como de utilização de memória. A ideia por detrás desta notação é eliminar alguns detalhes e focar conceitos mais abstratos ao analisar e comparar algoritmos.

Big O representa o pior caso - a nossa função está sempre limitada superiormente por outra função. Big Omega representa o melhor caso - limitada inferiormente. Big Theta combina ambos. A documentação de Scala disponibiliza uma tabela de desempenho com esta notação. Vale a pena lê-la com atenção antes de selecionar uma implementação.

A notação Big O é bastante abstrata. Na prática, porém, o fator constante C tem um valor concreto. Depende de muitos fatores: a versão da JVM, o compilador e o hardware. Tudo isto influencia o resultado.

A pesquisa linear num array e numa lista ligada é, em ambos os casos, O(n). Mas, em 2 milhões de entradas, a versão com array é várias vezes mais rápida. Isto acontece porque o hardware moderno está otimizado para estruturas de dados baseadas em arrays. A lista é mais lenta devido a diferentes fatores constantes, e cada abordagem tem um tempo de execução diferente.

O QuickSort demonstra o mesmo princípio. Em média, tem complexidade O(n log n), o que o torna um algoritmo rápido. Mas quando o array já está ordenado e o elemento de partição é escolhido de forma ingénua, não há progresso real em cada iteração, e o tempo de execução torna-se quadrático. Esse é o pior caso.

O insertion sort também tem tempo quadrático, mas em conjuntos de dados pequenos - devido aos fatores constantes - supera o QuickSort até cerca de 200 elementos. Este facto é utilizado em muitas bibliotecas: insertion sort para entradas pequenas e QuickSort para o restante.

O Vector de Scala é um caso mais subtil. A documentação indica que Vector tem tempo efetivamente constante, mas por baixo existe uma árvore radix-balanced, pelo que o tempo é logarítmico. A altura da árvore é muito reduzida, por isso, na prática, a diferença é negligenciável. Ainda assim, não é verdadeiramente O(1).

A visão mais ampla

As coleções Scala são mais do que uma funcionalidade de biblioteca. São um modelo estruturado - uma framework para raciocinar sobre trade-offs no desenho de sistemas.

Com estes conceitos, é possível navegar pela biblioteca e tomar uma decisão sólida. Nem sempre é óbvio - mas estas são as ferramentas certas. E estes conceitos não são específicos de Scala. Não são específicos de nenhuma linguagem. São específicos da ciência da computação.

Autor: Sergii Zubovych, Senior Scala Engineer na Intellias