How to efficiently track and store deltas between two HAMTs
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- python
- Domain
- backend-api-design
Research direction
No files or tests are named. Start by reviewing the HAMT and Map update/delete implementation, then determine whether a delta representation can preserve structural sharing without requiring the proposed scan. Done means an efficient, documented approach or a clearly scoped API change with coverage for the example.
Written by the indexing model from the issue text.
Description
Ideally, I would like to be able to do
x = Map({'a': 2, 'c': 1})
y = x.update({'b': 3: 'c': 2)
z = y - x # magic
z == Map({'b': 3, 'c': 2})
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 with y in the same way y shares its data with x. One way that comes to mind is
def diff(y, x):
z = y
for k, v in y.items():
if k in x and x[k] == v:
z = z.delete('k')
return z
But this is O(N log N) (for log N get/set). Is there a more efficient way to go about this?
- Dominant language
- C
- Stars
- 1.2k
- Forks
- 60
- PR merge metrics
- No merged PRs in 30d
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from MagicStack/immutables
-
Difficulty 3/5 1-2 days Newbie friendliness 38/100
MagicStack/immutables#121 · 6 reactions ·
-
Difficulty 5/5 Over a week Newbie friendliness 25/100
MagicStack/immutables#107 ·
-
Difficulty 3/5 1-2 days Newbie friendliness 32/100
MagicStack/immutables#102 ·
-
Difficulty 5/5 Over a week Newbie friendliness 20/100
MagicStack/immutables#82 ·
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
MagicStack/immutables#55 · 3 comments ·
All issues in MagicStack/immutables
Similar issues
-
level/task module/gcp type/bug
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
-
Difficulty 1/5 Under an hour Newbie friendliness 86/100
hapostgres/pg_auto_failover#1190 ·
-
docs
Difficulty 1/5 Under an hour Newbie friendliness 85/100
-
P3 sonic-vpp
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
sonic-net/sonic-buildimage#29662 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 94/100
spack/spack-packages#6586 ·