Comfy-Org / Comfy-Org/ComfyUI_frontend
Optimize histogramToPath percentile calculation with QuickSelect algorithm
- Dominant language
- TypeScript
- Stars
- 2k
- Forks
- 699
- Avg merge
- 1d 7h
- Merged PRs (30d)
- 490
Description
## Description
Currently, the `histogramToPath` function in `src/components/curve/curveUtils.ts` sorts the entire 256-element histogram array to find the 99.5th percentile:
```typescript
const sorted = Array.from(histogram).sort((a, b) => a - b)
const max = sorted[Math.floor(255 * 0.995)]
```
This performs a full sort with O(n log n) time complexity on every call.
## Proposed Optimization
Use QuickSelect (nth-element style) algorithm to find the percentile value without sorting all elements. QuickSelect has O(n) average time complexity.
Example implementation:
```typescript
function percentile(arr: Uint32Array, p: number): number {
const copy = new Uint32Array(arr)
const k = Math.floor(arr.length * p)
return quickSelect(copy, k)
}
```
## Context
- PR: #8860
- Comment: https://github.com/Comfy-Org/ComfyUI_frontend/pull/8860#discussion_r2838864064
- Requested by: @christian-byrne
## Benefits
- Improved performance from O(n log n) to O(n) average case
- More efficient for the fixed 256-element histogram size
┆Issue is synchronized with this [Notion page](https://www.notion.so/Issue-9109-Optimize-histogramToPath-percentile-calculation-with-QuickSelect-algorithm-3106d73d3650812e8189cd0cccedf6f8) by [Unito](https://www.unito.io)
Contributor guide
Assessment
This issue has not been assessed yet.