ApeWorX / ApeWorX/py-trie

Batch insertion application

Open
#56 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
111
Forks
54
Avg merge
27m
Merged PRs (30d)
1

Description

### What was wrong?

When a trie adds a single value, it must fix up all the nodes it touched along the way. This carries some performance cost, but is necessary for any single update. When applying a batch update, all the intermediate node fixups are wasted work. We could gain some (likely) significant performance benefits from a smarter batch-apply of a bunch of key/value pairs.

### How to fix it

Rough concept: walk through the trie with all scheduled insertions, applying them simultaneously.

For example, if two keys from the batch have the same first nibble, then follow the root node down into the extension/leaf/branch node with that nibble, keeping both of those insertions in memory. Then apply them both to the newly created node at the same time.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.