-
Notifications
You must be signed in to change notification settings - Fork 55
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
How to efficiently track and store deltas between two HAMTs #75
Comments
This is not a HAMT specific problem. Depending on your use-case, you'd have to either pay a large computation during difference operation, or small computation for every single (or batch) change operation: Option 1: Pretty much what you wrote, module your requirements. Option 2: A wrapper class that appends every single set, delete, commit operation into a linear history list, enabling you to quickly get mutation differences as history index tuple. Differences between divergent histories from a common ancestor can be done efficiently by finding a largest common prefix of the two histories, which can be done with binary search thanks to cached hashes. But this option will not work if the two maps will not have a common ancestor map. |
Ideally, I would like to be able to do
Is there any particularly efficient way to do this in terms of memory and computational time? Ideally, I'd like
z
to share its data withy
in the same wayy
shares its data withx
. One way that comes to mind isBut this is O(N log N) (for log N get/set). Is there a more efficient way to go about this?
The text was updated successfully, but these errors were encountered: