Não Existe Plain Text: Uma breve explicação sobre encodings

Nesse post eu vou falar de um ponto que muitas vezes parece não ser importante pelo motivo de (quase) sempre desenvolvermos aplicações em português e inglês, deixando de lado algumas línguas mais complicadas como grego, hebraico, chinês, japonês, e outras línguas asiáticas.

Inicialmente vamos entender um pouco mais o que exatamente é o encoding, e para que ele serve.

Encodings são códigos (geralmente números) que representam um determinado caractere em uma determinada língua/plataforma. A primeira forma de representação desses caracteres foi o tão conhecido Ascii (American Standard Code for Information Interchange), que representa um caractere em questão em forma de bits, mais precisamente 7 bits (depois completaram os 8 bits). O problema é que o universo de caracteres representados no Ascii era muito pequeno, somente 128 caracteres (por conta do seu tamanho). Não precisa nem dizer que os alfabetos pelo mundo a fora possuem muito mais do que 128 caracteres somente (e a china é o nosso principal representante desse leque). O Ascii foi o primeiro, mas diversos outros encodings surgiram depois disso: ISO 8859-1 , GB 2312, etc.

Também é fácil de concluir que com os diversos encodings que surgiram, muitos caracteres conflitavam os seus códigos com outros encodings. Isso é, dois encodings usando o mesmo código para representar o mesmo caractere. Por conta desses problemas foi criado o Unicode, que NÃO É UM ENCODING, mas padroniza a representação de caracteres dos encodings. Então começaram a surgir os encodings que basearam seus representações de caracteres em códigos sugeridos pelo unicode, e aí entra um dos primeiros encodings famosos unicode, que foi o UCS-2.

UCS-2 (Universal Character Set) utiliza 2 bytes para representar caracteres, e é claro que por conta desse espaço maior de armazenamento foram acrescentadas “muitas e muitas” línguas nesse encoding. Infelizmente “muitas e muitas” é diferente de TODAS. Ou seja, o povo decidiu criar encodings ainda maiores, com 16 e 32 bits (sendo este último não muito utilizado).

O UCS-2 teve um problema, basicamente com sistemas linux-like (que por ser um sistema antigo, se baseava completamente no encoding Ascii). Podemos exemplificar o problema com a linguagem C, que tem a convenção de representar uma string como um array de caracteres (representação ascii) terminando em zero. Exemplo: C vai armazenar a string HELLO como 72 69 76 76 79 0, num mais puro Ascii. Na maior parte dos lugares dentro dos sistemas linux-like  vão entender que essa é uma palavra de 5 letras porque ela termina com zero (null). Quando utilizamos o UCS-2, o mesmo HELLO é armazenado em 2 bytes da seguinte forma: 72 0 69 0 76 0 76 0 79 0 0 0. Praticamente todos os lugares vão interpretar isso como uma palavra de uma só letra “H”. Isso não é bom.

Foi aí que surgiram os encodings UTF (Unicode Transformation Format), uma vez que os sitemas linux (baseados em ascii 8 bits, não conseguiam se entender muito bem com os encodings 16 bits como o UCS-2). Esses UTF conseguem fazer os sistemas 8 e 16 bits se entenderem normalmente. O formato UTF mais utilizado é o UTF-8, que utiliza de até 4 bytes para representar um caractere. Como são utilizados esses bytes?

– 1 byte para a representação do caractere Ascii e

– 2 bytes para a representação de caracteres latinos, sírios, hebraicos, gregos, etc. ou 3 bytes para o restante de um plano multilingual que existe.

Com isso nós chegamos até o conceito mais utilizado hoje em termos de encoding, que é o UTF-8, que está se tornando cada vez mais um padrão para páginas, emails, e qualquer outro lugar onde caracteres sejam armazenados.

Linked lists e Dynamic arrays

Voltei 😛  Depois de um longo recesso do blog, estou de volta (e espero permanecer na ativa durante todo esse ano).

Decidi começar esse ano falando sobre um tópico muito importante para todos os que se dizem desenvolvedores de software: Estrutura de Dados!  Na verdade vou falar sobre um ponto muito específico de estrutura de dados, mas antes vamos dar uma geral sobre estrutura de dados em si.

Primeiro de tudo, o que é estrutura de dados? Uma estrutura de dados é uma forma de organizar e armazenar dados, de forma que eles possam (os dados) ser usados de forma eficiente. Atenção para a palavrinha EFICIENTE, daqui a pouco retornaremos a ela.

Como sabemos (ou deveríamos saber), existem diversas formas de estrutura de dados, cada uma com suas particularidades, pontos positivos e negativos. Se você conhece as estruturas de dados existentes, saiba que não é suficiente saber isso. É obrigação nossa saber qual a melhor estrutura de dados para ser utilizada em cada momento e para cada tipo de situação ou cenário. E é exatamente aí que a palavra EFICIENTE entra. Você precisa saber qual a mais eficiente para determinadas situações. Isso que vai diferenciar você de um programados comum.

Nesse post eu queria falar sobre duas estruturas muito usadas: as LinkedLists e os Arrays Dinâmicos.

Linked List é uma estrutura de dados onde os registros de dados estão organizados de forma que um elemento tem uma referência para o próximo elemento (ou uma referência para o nó de anterior e também para o nó posterior no caso das listas duplamente ligadas). Essa estrutura é importantíssima, e ela que provê uma implementação simples para outras estruturas de dados abstratas como fila, pilha e outras.

Já os arrays dinâmicos são arrays que possuem tamanho variável, e que assim como os arrays, possibilitam o acesso aleatório a qualquer elemento desse array. Um exemplo de array dinâmico é o nosso ArrayList de Java.

Bom, vamos agora ao que interessa, qual dos dois é mais eficiente? Quais pontos positivos de cada um deles? Quais os pontos negativos deles?

Um Array dinâmico é uma estrutura de dados que aloca os elementos continuamente na memória, e guarda o número atual de elementos. Se o espaço reservado for excedido, ele é realocado (e possivelmente copiado), o que é uma operação custosa.

As Linked Lists possuem algumas vantagens sobre os arrays dinâmicos. A inserção de um elemento em uma posição aleatória é uma operação de tempo constante, enquanto que uma inserção em uma posição aleatória em um array dinâmico vai demandar em média mover metade do array, e no pior caso (inserir na primeira posição) vai demandar mover o array inteiro.

Outra vantagem das Linked Lists é que vários elementos podem ser inseridos ao mesmo tempo (só dependendo da memória disponível), enquanto que o array dinâmico possivelmente iria ultrapassar o espaço reservado para ele (e aí teria o custo adicional de mover o array) e poderia até não ser possível realizar a operação caso a memória estivesse muito fragmentada e não fosse possível alocar o espaço do array dinâmico.

Por outro lado, arrays dinâmicos (e arrays normais) possibilitam o acesso a qualquer elemento com um tempo constante, enquanto que as LinkedLists possbilitam o acesso sequencial (e no caso das listas simples encadeadas só possibilita a navegação na lista em uma direção).  Isso faz com que as linked lists não sejam tão adequadas para aplicações onde é preciso acessar elementos pelo índice rapidamente.

Uma outra desvantagem das Linked Lists é o espaço extra de memória que tem que ser alocada para as referências, por isso que não justifica criar linked lists para tipos pequenos e simples como character ou valores booleanos (porque o tamanho do espaço da referência é maior que o do próprio elemento), e os arrays por outro lado só gastam o espaço de memória do próprio array, sem ter o overhead de armazenar referências.

Nesse tempo de fartura de hardware, talvez nem precisemos nos preocupar com questões de baixo nível como essas, mas é importante conhecer e ficar atento pois talvez você esbarre em um cenário onde você precise utilizar a estrutura de dados mais eficiente!

No final das contas, cada situação que vai dizer qual a estrutura de dados mais adequada para o momento.

(PS. pretendo escrever mais alguns posts ainda sobre alguns tópicos importantes de estrutura de dados)