Muitas das operações envolvendo listas simplesmente encadeadas exigem que se mantenha um ponteiro para o elemento anterior ao que se está trabalhando. Quando o elemento em questão é o primeiro da lista, o ponteiro para o anterior é nulo, e deve-se tratar esse caso sempre que se precisa acessá-lo. Um exemplo:
list_t *lsremove(int num, list_t *ls) {
list_t *this, *prev, *temp;
prev=NULL, this=ls;
while (this) {
if (this->val == num) {
if (prev)
prev->next = this->next;
else
ls = this->next;
temp = this;
this = this->next;
free(temp);
}
else {
prev = this;
this = this->next;
}
}
return ls;
}
Dependendo do código e do nível de gambiarra em suas redondezas, esse teste pode ter algum impacto na performance (pequeno) e na legibilidade (considerável) do código.
Há alguns dias me dei conta de que existe uma outra alternativa: criar um elemento inicial fake, e apontar ele como elemento anterior no início da função. Assim, o primeiro elemento da lista não é um caso especial, e não há teste algum a fazer. Ficamos então com algo do tipo:
list_t *lsremove2(int num, list_t *this) {
list_t *prev, *temp;
list_t dummy;
dummy.next = this;
prev = &dummy;
while (this) {
if (this->val == num) {
prev->next = this->next;
temp = this;
this = this->next;
free(temp);
}
else {
prev = this;
this = this->next;
}
}
return dummy.next;
}
Desperdiçamos um inteiro (o campo val da estrutura), mas juntamos as variáveis ls e this. * E ficamos com um código mais legível [citation needed]. Além disso, a eliminação do teste nos dá um fantástico ganho de performance: para remover aproximadamente 10 milhões de elementos de uma lista de 20 milhões, temos um tempo de execução de 0.526922s, contra 0.538636s com a versão inicial. (Estes são os tempos de execução na minha máquina, que é um referencial absoluto.)
Só para constar nos anéis da história (sic), apliquei isto na prática pela primeira vez tentando escrever em [PLT] Scheme uma versão tail-recursiva da função filter, que recebe uma função e uma lista e retorna apenas os elementos da lista para os quais a função retorna verdadeiro. Eis a criança:
(define (filter ok? ls)
(define result (cons #f empty))
(fltr ok? ls result)
(rest result))
(define (fltr ok? ls last)
(cond ((empty? ls) #f)
((ok? (first ls)) (set-cdr! last (cons (first ls) empty))
(fltr ok? (rest ls) (rest last)))
(else (fltr ok? (rest ls) last))))
Termino aqui de compartilhar esta pequena nulidade com os leitores.
* Na verdade não; ls é apenas substituída pelo campo next da estrutura. [24/10/2010]
Copyright © 2010-2024 Vítor De Araújo
O conteúdo deste blog, a menos que de outra forma especificado, pode ser utilizado segundo os termos da licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International.
Powered by Blognir.