Re: [Chicken-users] Alist versus Hash-table

[Jörg F. Wittenberger]

Hi Loïc,

I did not look on your paste.  But a few hints:

alists are O(n) while hashtable are O(1) .

However the constant involved is larger for hashtable then alists.

Therefore alists are fast for small numbers of elements in the list.  Tables win when the number of elements becomes larger.

Another thing is about destructive updates vs. pure code. Destructive updates are usually faster because they produce little garbage, while pure code must copy the list upto the point of the update.

Am 12.11.2013 11:33, schrieb Loïc Faure-Lacroix:

For a tessellation function, I believe I should use a hash table or a alist to save the index of some points to prevent duplicates. Yesterday I felt I should test how fast would the hash-table work to index my 3d coordinates. For that reason, I wrote that small benchmark and realized that the destructive function on alist gives impressive speed agains the non destructive loop. The hash table gives results that are close to the alist (destructive).

To use the alist, I’d have to implement a hashing function which could then give results pretty similar to the hash table. But the non destructive alist scares me a little. 

To do the same job, it takes 650s for the non destructive function and 0.014s for the use of destructive “alist-update!”. Anyone can explain why is this so slow? 

http://paste2.org/ng2fbFyk

Also what is the big difference between alist and a hash-table other than alist doesn’t seem to hash objects. After testing again, I realize that “alist-update!” isn’t even adding new element to the current list.

-- 
Loïc Faure-Lacroix

_______________________________________________
Chicken-users mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/chicken-users