search

kampersanda / poplar-trie

C++17 implementation of memory-efficient dynamic tries
MIT License
57 stars 5 forks source link

Regarding deletion. Can make complete? #4

Open superdolt opened 3 years ago

superdolt commented 3 years ago

this is not very elegant nor efficient in memory use. possible to implement something that can delete so that the memory for key used can be released?

Note: Deletion implementation
Since DynPDT cannot support garbage collection for deleted keys, Poplar-trie does not provide deletion functions. However, you can easily implement that function by setting the value associated with a deleted key to an invalid value. For example,

int* ptr = map.update(deleted_key);
*ptr = -1; // invalid value
In this approach, the memory used for deleted keys is not released, although it may be eused for keys inserted subsequently.
kampersanda commented 3 years ago

Impossible. The data structure of DynPDT does not support it. Poplar-trie would be suitable for applications where data is stored incrementally.

superdolt commented 3 years ago

this sounds a bit limited. possible to provide more use case scenarios for this? basically you are saying that key is immutable is best for this use case. I'm trying to figure out what applications are good for this. this is like marisa-trie.

kampersanda commented 3 years ago

Poplar-trie would be useful for applications that continue to store streaming data such as Web crawler. With a static data structure such as marisa-trie, it would be difficult to perform efficiently.