Este artigo descreve como objetos string são gerenciados internamente pelo Python e como a busca por string é feita.

Estrutura do PyStringObject

Um objeto string no Python é representado internamente pela estrutura PyStringObject. “ob_shash” é o  hash da string se calculada. “ob_sval” contém a string de tamanho “ob_size”. A string tem um terminador nulo. O tamanho inicial de “ob_sval” é 1 byte e ob_sval[0] = 0. Se você estiver se perguntando onde “ob_size é definido”, dê uma olhada no PyObject_VAR_HEAD no object.h. “ob_sstate” indica se o objeto string está no dicionário interno que iremos ver depois. 

1 typedef struct {
2     PyObject_VAR_HEAD
3     long ob_shash;
4     int ob_sstate;
5     char ob_sval[1];
6 } PyStringObject;

Novo objeto string

O que acontece quando você atribui uma nova string a uma variável como esta?

1 >>> s1 = 'abc'

A função interna C “PyString_FromString” é chamada, e o pseudo código se parece com este:

1 arguments: string object: 'abc'
2 returns: Python string object with ob_sval = 'abc'
3 PyString_FromString(string):
4     size = length of string
5     allocate string object + size for 'abc'. ob_sval will be of size: size + 1
6     copy string to ob_sval
7     return object

Cada vez que uma nova string é utilizada, um novo objeto string é alocado.

Compartilhando objetos string

Existe um bom recurso no qual pequenas strings são compartilhadas entre variáveis. Isso reduz a quantidade de memória utilizada. Strings pequenas são strings de tamanho de 0 ou 1 byte. A variável global interno é um dicionário referenciado essas strings pequenas. O array “characters” também é utilizado para referenciar as strings de comprimento de 1 byte: p.e. caracteres únicos. Iremos ver depois como o array “characters” é usado.

1 static PyStringObject *characters[UCHAR_MAX + 1];
2 static PyObject *interned;

Vamos ver o que acontece quando uma nova string pequena é atribuída a uma variável no seu script Python.

1 >>> s2 = 'a'

O objeto string contendo ‘a’ é adicionado ao dicionário interno. A chave é um ponteiro para o objeto string, e o valor é o mesmo ponteiro. Esse novo objeto string também é referenciado nos caracteres do array no offset 97 porque o valor de ‘a’ é 97 em ASCII. A variável “s2? está apontando para esse objeto string.

O que acontece quando uma variável diferente é atribuída à mesma string ‘a’?

1 >>> s3 = 'a'

O mesmo objeto string criado anteriormente é retornando, então ambas variáveis estão apontado para o mesmo objeto string. O array “characters” é usado durante o processo para verificar se a string já existe e retorna o ponteiro para o objeto string.

1 if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL)
2 {
3     ...
4     return (PyObject *)op;
5 }

Vamos criar uma string pequena contendo o caractere ‘c’.

1 >>> s4 = 'c'

Temos o seguinte:

Nós também usamos o array “characters” quando o item de uma string é solicitado como no script do Python a seguir: 

1 >>> s5 = 'abc'
2 >>> c = s5[0]
3 >>> c
4 >>> 'a'

Em vez de criar uma nova string contendo ‘a’, o ponteiro no offset 97 do array “characters” é retornado. Aqui está o código da função “string_item” que é chamada quando requeremos um caractere de uma string. O argumento “a” é o objeto string que contém ‘abc’, e o argumento “i” é o índice requerido: no nosso caso, 0. Um ponteiro para um objeto string é retornado.

01 static PyObject *
02 string_item(PyStringObject *a, register Py_ssize_t i)
03 {
04     char pchar;
05     PyObject *v;
06     ...
07     pchar = a->ob_sval[i];
08     v = (PyObject *)characters[pchar & UCHAR_MAX];
09     if (v == NULL)
10         // allocate string
11     else {
12         ...
13         Py_INCREF(v);
14     }
15     return v;
16 }

Busca por string

Vamos dar uma olhada no que acontece quando você executa uma busca de string como no código Python a seguir: 

1 >>> s = 'adcabcdbdabcabd'
2 >>> s.find('abcab')
3 >>> 11

A função “find” retorna o índice onde a string ‘abcd’ é encontrada na string “s”. Ela retorna -1 se a string não for encontrada.

Então, o que acontece internamente? A função “fastsearch” é chamada. É um mix entre algoritmos Boyer-Moore e Horspool mais alguns truques interessantes.

Vamos chamar de “s” a string na qual iremos buscar, e de “p” a string pela qual iremos buscar. s = ‘adcabcdbdabcabd’ e p = ‘abcab’. “n” é o comprimento de “s” e “m” é o comprimento de “p”. n = 18 e m = 5.

A primeira verificação no código é óbvia, se m > n, sabemos que não será possível encontrar o índice, então a função retorna -1 imediatamente, como podemos ver no código a seguir:

1 w = n - m;
2 if (w < 0)
3     return -1;

Quando m = 1, o código passa por “s” com um caractere por vez, e retorna o índice quando há correspondência. mode = FAST_SEARCH, no nosso caso, uma vez que estamos procurando pelo índice onde a string é encontrada primeiro, e não o número de vezes que a string é encontrada.

01 if (m <= 1) {
02     ...
03     if (mode == FAST_COUNT) {
04         ...
05     } else {
06         for (i = 0; i < n; i++)
07             if (s[i] == p[0])
08                 return i;
09     }
10     return -1;
11 }

Para outros casos em que m > 1. O primeiro passo é criar uma tabela comprimida boyer-moore delta 1. Duas variáveis serão atribuídas durante esse passo: “mask” e “skip”.

“mask” é uma bitmask de 32 bits, usando os 5 bits menos significantes do caractere como a chave. Ela é gerada usando a string para procurar “p”. É um filtro bloom, que é usado para testar se um caractere está presente nessa string. Ele é realmente rápido, mas existem falsos positivos. Você pode ler mais sobre filtros bloom aqui. É assim que a bitmask é gerada no nosso caso:

1 mlast = m - 1
2 /* process pattern[:-1] */
3 for (mask = i = 0; i < mlast; i++) {
4     mask |= (1 << (p[i] & 0x1F));
5 }
6 /* process pattern[-1] outside the loop */
7 mask |= (1 << (p[mlast] & 0x1F));

O primeiro caractere de “p” é ‘a’. O valor de ‘a’ é 97 = 1100001 em formato binário. Usando os 5 bits menos significantes, temos 00001, então o “mask” é primeiramente estabelecido como: 1 << 1 = 10. Uma vez que toda a string “p” é processada, o mask = 1110.

Como usamos essa bitmask? Usando o teste a seguir, em que “c” é o caractere a ser buscado na string “p”.

1 if ((mask & (1 << (c & 0x1F))))

O ‘a’ está em “p” onde p = ‘abcab’? 1110 & (1 << (‘a’ & 0X1F)) é verdadeiro? 1110 & (1 << (‘a’ & 0X1F)) = 1110 & 10 = 10. Então sim, ‘a’ está em ‘abcab’. Se testarmos com ‘d’, teremos falso, da mesma maneira com os de ‘e’ a ‘z’. Então, esse filtro funciona muito bem no nosso caso.

“skip” é usado para o índice do caractere com o mesmo valor do último caractere na primeira string que for procurada. “skip” é atribuído ao comprimento de “p” – 1 se o último caractere não for encontrado. O último caractere na string a ser procurado é ‘b’, o que significa que “skip” será determinado como 2, porque este caractere também pode ser encontrado ao usar o skip em 2 caracteres para baixo. Essa variável é usada em um método skip chamado método do ‘bad-character skip’.

No seguinte exemplo: p = ‘abcab’ e s = ‘adcabcaba’. A busca começa no índice 4 de “s” e verifica para trás se existe uma correspondência de string. O primeiro teste falha no índice = 1, onde ‘b’ é diferente de ‘d’. Sabemos que o caractere ‘b’ em “p” também é encontrado 3 caracteres para baixo começando do fim. Como ‘c’ é parte de “p”, vamos direto para o ‘b’ seguinte. Esse é o skip “bad-character“.

Em seguida, é o próprio loop de busca (o código real está em C em vez de em Python):

01 for i = 0 to n - m = 13:
02     if s[i+m-1] == p[m-1]:
03         if s[i:i+mlast] == p[0:mlast]:
04             return i
05         if s[i+m] not in p:
06             i += m
07         else:
08             i += skip
09     else:
10         if s[i+m] not in p:
11             i += m
12 return -1

O teste “s[i+m] não está em” p” é feito usando a bitmask. “i += skip” é o skip “bad-character“. “i += m” é feito quando o próximo caractere não é encontrado em “p”.

Vamos ver como esse algoritmo de busca funciona com nossas strings “p” e “s”. Os 3 primeiros passos são conhecidos. Depois disso, o caractere “d” não está na string “p”, então usamos o skip no comprimento de “p” e rapidamente encontramos uma correspondência depois disso.

Você pode dar uma olhada no código pra objetos string aqui.

Por enquanto é só. Espero que você tenha gostado deste artigo.

?

Texto original disponível em http://www.laurentluce.com/posts/python-string-objects-implementation/