Alocação de memória para matriz esparsa no awk

Question

Eu pesquisei, mas não cheguei a nenhuma conclusão de que quando eu defini um array esparso ele reserva toda a memória contígua até o índice máximo ou aloca a memória naquele índice específico somente. / p>

array[100000]="ID1"
array[1001]="ID2"

Da mesma forma, quando faço loop para um array, ele faz a varredura de todos os índices onde array [i] existe ou aponta somente índice de array definido para ex. 100000 & 1001.

for(i in array){...}

Eu tenho que armazenar algum valor em um índice específico, mas eu tenho medo de alocação de memória, então é muito importante para mim saber: como ele realmente aloca memória em caso de array esparso?

    

Answer 1

Pelo gawk manual , que é um bom Referência geral da linguagem awk :

An important aspect to remember about arrays is that array subscripts are always strings.

Ou seja, awk matrizes são sempre associativas e as teclas numéricas são stringed. Somente as chaves que estão em uso são armazenadas na matriz (e talvez algum espaço extra para o futuro). Os índices numéricos não são contíguos, portanto matrizes esparsas não ocupam mais espaço que outro array com o mesmo número de elementos.

Quanto a loops, ao usar a sintaxe for (k in array) {body} o:

loop executes body once for each index in array that the program has previously used

Novamente, apenas os índices que foram usados serão incluídos na iteração da matriz. Note que a ordem da iteração é indefinida , no entanto; não é necessariamente numérico ou a ordem de adição ao array.

    

Answer 2

Com gawk , de sua página man sobre matrizes , você pode ler uma explicação detalhada.

In most other languages, arrays must be declared before use, including a specification of how many elements or components they contain. In such languages, the declaration causes a contiguous block of memory to be allocated for that many elements. Usually, an index in the array must be a positive integer. For example, the index zero specifies the first element in the array, which is actually stored at the beginning of the block of memory. Index one specifies the second element, which is stored in memory right after the first element, and so on. It is impossible to add more elements to the array, because it has room only for as many elements as given in the declaration. (Some languages allow arbitrary starting and ending indices—e.g., ‘15 .. 27’—but the size of the array is still fixed when the array is declared.)

....

Arrays in awk are different—they are associative. This means that each array is a collection of pairs: an index and its corresponding array element value

Assim, você pode definir uma matriz sem especificar seu tamanho:

$ awk 'BEGIN{a[0]=1;a[10]=2;print length(a)}'
2

Não é como perl , que usa bloco contíguo de memória para matriz:

$ perl -le '$a[0]=1;$a[10]=1;print ~~@a'
11

E perl hash é muito semelhante a gawk array:

$ perl -le '$a{0}=1;$a{10}=1;print ~~keys %a'
2

Como gawk matrizes implementam como uma tabela de hash, então você pode acessar qualquer elemento da matriz em tempo constante, independente do tamanho da matriz.