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) contains_all method #40

Closed uncomputable closed 1 week ago

uncomputable commented 3 months ago

BasePattern::contains_all has O(n^2) asymptotics although there exists a O(n) algorithm.

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

Instead you should construct a hashset of all the identifiers in self and then check that every item yielded from the iterator lands in the hashset.