search

BlockstreamResearch / simfony

Rust-like high-level language that compiles down to Simplicity bytecode. Work in progress.
19 stars 6 forks source link

O(n^2) get method #39

Closed uncomputable closed 1 week ago

uncomputable commented 3 months ago

BasePattern::get has O(n^2) asymptotics although there exists an O(n) algorithm.

https://github.com/BlockstreamResearch/simfony/pull/38#discussion_r1616353544

I would suggest using verbose_pre_order_iter in contains , and returning a vector of left/right decisions which you can pop every time you hit a BasePattern::Product in this loop. I'd also make contains non-public or rename it to reflect the richer return value.