Tables de hachage utilisant VListes

Question

Phil Bagwell, dans son 2002 paper on the VList data structure, indique que vous pouvez utiliser une VList pour implémenter une table de hachage persistante. Cependant, son explication de la façon dont cela fonctionnait n'incluait pas beaucoup de détails, et je ne le comprends pas. Quelqu'un peut-il me donner une explication plus détaillée, ou même des exemples? En outre, il me semble d'après ce que je peux voir que cette structure de données, bien qu'elle puisse avoir la même complexité big-O qu'une Hashtable, sera plus lente car elle fait des recherches supplémentaires. Est-ce que quelqu'un se soucie de faire une analyse détaillée de combien plus lent, de préférence en incluant le comportement du cache? Comment la relation de performance entre les deux change-t-elle dans le cas où il n'y a pas de collisions ou beaucoup?

Answer 1

J'ai regardé ce papier, et il apparaît très préliminaire. Le fait qu'aucune version ultérieure n'ait été publiée, et que l'original est apparu dans IFL (qui est une sorte de réunion de travail en cours), suggère que vous pourriez perdre votre temps.

Answer 2

Hrmm il semble y avoir un certain nombre de problèmes avec les structures de données proposées par le document en question. En dehors de la manchette, les listes de lecture naïves mentionnées en premier semblent avoir besoin de références uniques pour obtenir quelque chose de proche des garanties de temps proposées. Vous perdez la plupart du temps à partager vos queues. Vous pouvez partager les minuscules noeuds vers l'arrière de la liste, mais vous devrez dupliquer le plus grand noeud vlist au moment où vous contrez quelque chose sur le cdr de vlist qui est toujours actif. Ce coût est proportionnel au coût de la copie de toute la liste.

Avec les modifications 2d mentionnées plus loin, cela redevient constant, mais c'est une constante assez grande, puisque vous finissez par copier au moins la tête d'une liste de pages (ou pire, une vlist) et la première page de votre liste .

Les trucs de la liste de hachage fonctionnelle là-bas ne semblaient pas avoir beaucoup de sens pour moi d'être honnête. C'était juste une brève lettre de présentation qui semblait être boulonnée sur un papier sans rapport avec le sujet, sans suffisamment de détails pour vraiment faire ressortir à quel point c'est pratique.