# UNDF: (pending)
# scipy-0001: SHGO minimizers() — xl_maps list scan ignores xl_maps_set O(V×L)

## CWE-407 — Algorithmic Complexity: O(V×L) list scan despite O(1) set already present

| Field | Value |
|-------|-------|
| ID | scipy-0001 |
| Severity | MEDIUM |
| Ecosystem | scipy |
| Package | `scipy.optimize` |
| File | `scipy/optimize/_shgo.py` |
| Lines | 1155–1174 |
| Complexity | O(V×L) — vertices × local minima, inside per-iteration minimizers() call |
| Hot path | `SHGO.minimizers()` — called every iteration of the SHGO optimizer |

## Background

SHGO (Simplicial Homology Global Optimization) is scipy's global optimizer for
non-convex problems.  Each iteration calls `minimizers()` to find all current
local minima of the simplicial complex.  It iterates all vertices in `HC.V.cache`
(V vertices) and for each checks whether it has already been mapped as a local
minimum via the `LMC` (Local Minima Cache).

## Defect

```python
# scipy/optimize/_shgo.py  lines 1155–1174
def minimizers(self):
    self.minimizer_pool = []
    for x in self.HC.V.cache:           # V vertices
        in_LMC = False
        if len(self.LMC.xl_maps) > 0:
            for xlmi in self.LMC.xl_maps:           # DEFECT: O(L) list scan
                if np.all(np.array(x) == np.array(xlmi)):
                    in_LMC = True
        if in_LMC:
            continue

        if self.HC.V[x].minimiser():
            if self.HC.V[x] not in self.minimizer_pool:  # DEFECT: O(M) list scan
                self.minimizer_pool.append(self.HC.V[x])
```

`LMapCache` already maintains `xl_maps_set` — a set of tuples for O(1) lookup:

```python
# scipy/optimize/_shgo.py  lines 1560–1595
class LMapCache:
    def __init__(self):
        self.xl_maps = []
        self.xl_maps_set = set()        # ← already exists, not used here
        ...
    def add_res(self, v, lres, bounds=None):
        ...
        self.xl_maps.append(lres.x)
        self.xl_maps_set.add(tuple(lres.x))   # maintained on every insert
```

The set is populated on every `add_res()` call but never consulted in
`minimizers()` — the code uses the slower list instead.

### Total cost per optimization run

`minimizers()` is called once per SHGO iteration (line 885).  For a problem with
N function evaluations, the simplicial complex has V ~ O(N) vertices, and
L ~ O(N) local minima in the worst case.  The loop is O(V×L) = O(N²) per
iteration × I iterations = O(I×N²).

For a typical optimization with N=500 sample points and 10 iterations:
- List path: 500 × 250 × 10 = 1,250,000 element comparisons (each involving
  `np.all(np.array(x) == np.array(xlmi))` — not just a Python int comparison)
- Set path: 500 × 10 = 5,000 set probes

## Complexity table

| Vertices (V) | Local minima (L) | Iterations (I) | list np.all ops | set ops | Speedup |
|-------------|-----------------|---------------|----------------|---------|---------|
| 100 | 20 | 5 | 10,000 | 500 | 20× |
| 500 | 100 | 10 | 500,000 | 5,000 | 100× |
| 1,000 | 300 | 20 | 6,000,000 | 20,000 | 300× |
| 2,000 | 500 | 30 | 30,000,000 | 60,000 | 500× |

## Fix

Use `xl_maps_set` for the LMC membership check, and drop the redundant
`minimizer_pool` dedup (safe because the cache iteration visits each key once):

```python
def minimizers(self):
    self.minimizer_pool = []
    for x in self.HC.V.cache:
        # FIX: O(1) set lookup instead of O(L) list scan
        if tuple(x) in self.LMC.xl_maps_set:
            continue

        if self.HC.V[x].minimiser():
            # No need for not-in check: each x is a unique cache key
            self.minimizer_pool.append(self.HC.V[x])
```

`tuple(x)` is already the native key type (cache keys are tuples of coordinates),
matching the `tuple(lres.x)` stored by `add_res()`.  `set.__contains__` is O(1)
amortised.

Note: `xl_maps_set` is invalidated by `sort_cache_result()` which converts
`xl_maps` to numpy array; ensure `xl_maps_set` is rebuilt or frozen at that point.
