Comfy-Org / Comfy-Org/ComfyUI_frontend

Optimize histogramToPath percentile calculation with QuickSelect algorithm

Open
#9,109 0 comments 0 reactions 1 assignee Claimed by @christian-byrne View on GitHub
perf:speed
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

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.