Improve powerSet performance
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- haskell
- Domain
- performance
Research direction
Start by locating the powerSet implementation and the insertMin path it uses. Compare the current O(2^n log n) approach with the proposed singleton-tree optimization, then determine whether a better bound or a tighter lower-bound argument is possible. Done means a justified performance improvement or proof, with supporting tests or analysis.
Written by the indexing model from the issue text.
Description
Obviously, there's only so much we can do, but we can do some. The most obvious optimization is to use a version of insertMin that takes a singleton tree as an argument instead of an element. But I can't help wondering if we can do better. The problem is obviously $\Omega(2^n)$, and our solution is $O(2^n\log n)$. Can we close that gap by either improving our solution or proving a tight(er) lower bound?
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 2d 12h
- Merged PRs (30d)
- 6
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
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 haskell/containers
-
major-release strictness Tree
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
haskell/containers#1260 ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1261 · 9 comments ·
-
IntSet low-hanging-fruit performance
Difficulty 3/5 1-2 days Newbie friendliness 58/100
haskell/containers#1251 ·
-
maintainability major-release
Difficulty 3/5 1-2 days Newbie friendliness 70/100
haskell/containers#1250 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 50/100
haskell/containers#1242 ·
All issues in haskell/containers
Similar issues
-
bug good-title pdd
Difficulty 2/5 Under an hour Newbie friendliness 82/100
objectionary/phino#1630 ·
Maintainers usually reply within 1 day