Elmord's Magic Valley

Software, lingüística e rock'n'roll. Às vezes em Português, sometimes in English.

Manipulando listas encadeadas: uma pequena gambiarra

2010-10-23 22:39 -0200. Tags: comp, prog, em-portugues

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]

Comentários / Comments (0)

Deixe um comentário / Leave a comment

Main menu

Posts recentes

Comentários recentes

Tags

em-portugues (213) comp (138) prog (68) in-english (51) life (47) unix (35) pldesign (35) lang (32) random (28) about (27) mind (25) lisp (23) mundane (22) fenius (20) web (18) ramble (17) img (13) rant (12) hel (12) privacy (10) scheme (10) freedom (8) bash (7) copyright (7) music (7) academia (7) lash (7) esperanto (7) home (6) mestrado (6) shell (6) conlang (5) emacs (5) misc (5) latex (4) editor (4) book (4) php (4) worldly (4) politics (4) android (4) etymology (4) wrong (3) security (3) tour-de-scheme (3) kbd (3) c (3) film (3) network (3) cook (2) poem (2) physics (2) wm (2) treta (2) philosophy (2) comic (2) lows (2) llvm (2) perl (1) en-esperanto (1) audio (1) german (1) kindle (1) old-chinese (1) pointless (1) translation (1)

Elsewhere

Quod vide


Copyright © 2010-2020 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.