search

Yomguithereal / mnemonist

Curated collection of data structures for the JavaScript/TypeScript language.
https://yomguithereal.github.io/mnemonist
MIT License
2.26k stars 92 forks source link

Tips for implementing HashedArrayTree#insert, #remove, and #forEach? #178

Closed lancejpollard closed 2 years ago

lancejpollard commented 2 years ago

Can you point in the right direction how to implement these sorts of 3 methods in the HashedArrayTree? I would like to use this for a dynamic array implementation, but I think it would need to have these methods as well. Thanks!

Yomguithereal commented 2 years ago

Hello @lancejpollard,

.forEach should not be difficult as it is just a matter of iterating over the structure's blocks, and each block's items, until you reach length.

.insert and #.remove are more tricky because they have to be O(n) since you need to reindex everything that comes after. So my question is more: what is your use case here? Why are you using a HAT in the first place?

lancejpollard commented 2 years ago

Cool, thanks. I am just exploring, playing around with the idea of using something like this for a dynamic array in a custom programming language. I am new to these sorts of data structure implementations though.

Yomguithereal commented 2 years ago

HATs are usually used for very specific scenario were their theoretical performance can match real-life one. People usually rely on growing arrays such as mnemonist's Vector for generic implementation as they remain very efficient because of contiguous memory allocation and cache reasons, in spite of the amortized cost being theoretically worse that HATs.

lancejpollard commented 2 years ago

Thanks for the helpful info!

lancejpollard commented 2 years ago

Oh I didn't realize how many data structures you had! Could you briefly list out what the best use cases are for a few? I am working on implementing the primitives and core "data structures" I guess for that programming language, and it would be awesome to know what could be used where.

For a long time I was thinking of making the generic structure a B+tree, as databases are implemented using it. But in-memory databases (like PebbleDB) also use SkipLists instead. But you and others have hinted recently that dynamic arrays would be better, and perhaps a hash table. But I'm curious to learn more use cases for these things in practicality.