# UNDF: UNDF-2026-000000515
# pytorch-geometric-0001: smiles.py list.index() O(L×A) per molecule → O(A) with dict lookup

## File
`torch_geometric/utils/smiles.py`

## Lines
94–118 (`from_rdmol`)

## Severity
**MEDIUM** — Dataset loading path. O(L) per `list.index()` call, called 9 times per atom and 3 times per bond, over every molecule in the dataset. For QM9 (130k molecules, ~18 atoms each) this produces ~491M list traversal operations. Converts to O(1) per lookup with pre-built dicts.

## Complexity Analysis

**Defective:** O(M × A × L_atom + M × B × L_bond)
- M = molecules, A = atoms/molecule, B = bonds/molecule
- L_atom = max list length (119 for `atomic_num`)
- L_bond = max list length (22 for `bond_type`)

**Fixed:** O(M × A + M × B) — pure dict lookup per atom/bond attribute

## Defective Snippet

```python
# Module-level (lines 7–77): x_map and e_map defined as dict-of-lists
x_map: Dict[str, List[Any]] = {
    'atomic_num': list(range(0, 119)),    # 119 elements
    'chirality': [...],                    # 9 elements
    'degree': list(range(0, 11)),          # 11 elements
    'formal_charge': list(range(-5, 7)),   # 12 elements
    'num_hs': list(range(0, 9)),           # 9 elements
    'num_radical_electrons': list(range(0, 5)),  # 5 elements
    'hybridization': [...],                # 8 elements
    'is_aromatic': [False, True],          # 2 elements
    'is_in_ring': [False, True],           # 2 elements
}

e_map: Dict[str, List[Any]] = {
    'bond_type': [...],    # 22 elements
    'stereo': [...],       # 6 elements
    'is_conjugated': [False, True],  # 2 elements
}

# from_rdmol(), lines 94-118: list.index() called per atom and per bond
for atom in mol.GetAtoms():
    row: List[int] = []
    row.append(x_map['atomic_num'].index(atom.GetAtomicNum()))        # O(119) scan
    row.append(x_map['chirality'].index(str(atom.GetChiralTag())))    # O(9) scan
    row.append(x_map['degree'].index(atom.GetTotalDegree()))          # O(11) scan
    row.append(x_map['formal_charge'].index(atom.GetFormalCharge()))  # O(12) scan
    row.append(x_map['num_hs'].index(atom.GetTotalNumHs()))           # O(9) scan
    row.append(x_map['num_radical_electrons'].index(                  # O(5) scan
        atom.GetNumRadicalElectrons()))
    row.append(x_map['hybridization'].index(str(atom.GetHybridization()))) # O(8) scan
    row.append(x_map['is_aromatic'].index(atom.GetIsAromatic()))      # O(2) scan
    row.append(x_map['is_in_ring'].index(atom.IsInRing()))            # O(2) scan
    xs.append(row)

for bond in mol.GetBonds():
    e = []
    e.append(e_map['bond_type'].index(str(bond.GetBondType())))       # O(22) scan
    e.append(e_map['stereo'].index(str(bond.GetStereo())))            # O(6) scan
    e.append(e_map['is_conjugated'].index(bond.GetIsConjugated()))    # O(2) scan
```

## Fixed Snippet

```python
# Add after the existing x_map and e_map definitions (after line 77):
# Pre-build O(1) lookup dicts from the existing list maps
x_idx: Dict[str, Dict[Any, int]] = {
    k: {v: i for i, v in enumerate(lst)} for k, lst in x_map.items()
}
e_idx: Dict[str, Dict[Any, int]] = {
    k: {v: i for i, v in enumerate(lst)} for k, lst in e_map.items()
}

# from_rdmol(), replace list.index() with dict lookup:
for atom in mol.GetAtoms():
    row: List[int] = []
    row.append(x_idx['atomic_num'][atom.GetAtomicNum()])          # O(1)
    row.append(x_idx['chirality'][str(atom.GetChiralTag())])      # O(1)
    row.append(x_idx['degree'][atom.GetTotalDegree()])            # O(1)
    row.append(x_idx['formal_charge'][atom.GetFormalCharge()])    # O(1)
    row.append(x_idx['num_hs'][atom.GetTotalNumHs()])             # O(1)
    row.append(x_idx['num_radical_electrons'][                    # O(1)
        atom.GetNumRadicalElectrons()])
    row.append(x_idx['hybridization'][str(atom.GetHybridization())]) # O(1)
    row.append(x_idx['is_aromatic'][atom.GetIsAromatic()])        # O(1)
    row.append(x_idx['is_in_ring'][atom.IsInRing()])              # O(1)
    xs.append(row)

for bond in mol.GetBonds():
    e = []
    e.append(e_idx['bond_type'][str(bond.GetBondType())])         # O(1)
    e.append(e_idx['stereo'][str(bond.GetStereo())])              # O(1)
    e.append(e_idx['is_conjugated'][bond.GetIsConjugated()])      # O(1)
```

## Notes
- `x_map` and `e_map` are module-level constants; `x_idx`/`e_idx` are built once at module load
- All existing values in the lists are hashable (ints, strings, bools) — dict keys work without change
- `list.index()` raises `ValueError` on miss; dict `[]` raises `KeyError` — same failure mode for unknown atom types
- Backward compatible: `x_map` and `e_map` remain for callers using them as ordered sequences
