anagram-generator/docs/MEMORY_TRADEOFFS.md

# Compromis Mémoire vs Déduplication

## Problématique

Lors de la génération de millions d'anagrammes en mode streaming, il existe un conflit fondamental entre deux objectifs :
1. **Mémoire constante** : Ne pas consommer de RAM proportionnellement au nombre d'anagrammes
2. **Déduplication complète** : Garantir l'unicité de tous les anagrammes générés

## Solution implémentée : Déduplication plafonnée

### Principe

Le mode streaming maintient un `HashSet<u64>` pour la déduplication, mais avec une **limite de taille à 100 000 entrées**.

```rust
let dedup_limit = 100_000; // ~800KB de mémoire
```

### Comportement

| Anagrammes générés | Déduplication | Mémoire utilisée |
|-------------------|---------------|------------------|
| 1 - 100 000 | ✅ **100% unique** | Croissante (0 → ~8MB) |
| 100 001+ | ⚠️ **Duplicatas possibles** | **Plafonnée à ~8MB** |

### Pourquoi cette limite ?

**Sans limite** (version originale problématique) :
- 1M anagrammes = 1M × 8 bytes = ~8MB + overhead HashSet = **~50MB**
- 10M anagrammes = **~500MB**
- 100M anagrammes = **~5GB**
- ❌ Mémoire qui croît indéfiniment, pas vraiment du "streaming"

**Avec limite à 100k** (version optimisée) :
- 100k hashs × 8 bytes = 800KB + overhead HashSet = **~8MB**
- Peu importe le nombre total (1M, 10M, 100M, 1B) : **Toujours ~8MB**
- ✅ Vraie mémoire constante

## Modes disponibles et leur usage

### Mode 1 : Standard (< 10k anagrammes)
```bash
cargo run --release -- --word "word" --count 5000
```

| Critère | Valeur |
|---------|--------|
| Mémoire | O(n) - ~1-10MB pour 1-10k items |
| Déduplication | ✅ 100% |
| Performance | Excellente |
| Limitation | Ne passe pas à l'échelle (> 10k) |

**Utilisation recommandée** : Génération quotidienne, développement, tests

---

### Mode 2 : Streaming (10k - 10M anagrammes, duplicatas acceptables)
```bash
cargo run --release -- --word "word" --count 5000000 --streaming --progress
```

| Critère | Valeur |
|---------|--------|
| Mémoire | **Plafonnée à ~8MB** |
| Déduplication | ✅ 100% sur premiers 100k<br>⚠️ Duplicatas possibles après |
| Performance | Excellente, résultats immédiats |
| Limitation | Duplicatas après 100k items |

**Utilisation recommandée** :
- Pipeline avec filtrage en aval (ex: `| sort -u`)
- Génération où quelques duplicatas sont acceptables
- Besoin de résultats immédiats
- Contraintes mémoire strictes

**Exemple avec élimination duplicatas en aval** :
```bash
# Générer avec streaming, puis éliminer duplicatas avec sort
cargo run --release -- --word "word" --count 10000000 --streaming \
  | sort -u > anagrams_uniques.txt
```

---

### Mode 3 : Batch (> 1M anagrammes, déduplication 100% requise)
```bash
cargo run --release -- --word "word" --count 50000000 --batch-size 100000 --progress
```

| Critère | Valeur |
|---------|--------|
| Mémoire | O(batch_size) - ~50-100MB |
| Déduplication | ✅ **100% globale** |
| Performance | Bonne, traitement par chunks |
| Limitation | Latence initiale (batch complet) |

**Utilisation recommandée** :
- Génération massive (> 1M)
- Déduplication 100% requise
- RAM suffisante pour batch (~100MB)

---

## Exemples pratiques

### Cas 1 : Génération de 500k anagrammes uniques

**Option A - Streaming (rapide, duplicatas possibles)** :
```bash
# ~8MB RAM, résultats immédiats
# 100k premiers uniques garantis, puis duplicatas possibles sur les 400k suivants
cargo run --release -- --word "algorithm" --count 500000 --streaming --progress
```

**Option B - Batch (plus lent, 100% unique)** :
```bash
# ~50MB RAM, tous uniques
cargo run --release -- --word "algorithm" --count 500000 --batch-size 50000 --progress
```

**Recommandation** : Utilisez **streaming** puis filtrez les duplicatas :
```bash
cargo run --release -- --word "algorithm" --count 500000 --streaming \
  | awk '!seen[$2]++' > uniques.txt
```
(awk filtre les duplicatas basé sur la 2ème colonne = le mot)

### Cas 2 : Génération de 10M anagrammes

**Option A - Streaming + filtrage externe** :
```bash
# ~8MB RAM pour le générateur
# Duplicatas éliminés par sort -u (utilise disque si nécessaire)
cargo run --release -- --word "programming" --count 10000000 --streaming \
  | sort -u -o uniques.txt
```

**Option B - Batch avec déduplication intégrée** :
```bash
# ~100MB RAM, déduplication garantie
cargo run --release -- --word "programming" --count 10000000 --batch-size 100000 --progress
```

**Recommandation** : **Batch** si RAM disponible, sinon streaming + sort -u

### Cas 3 : Génération infinie (pipeline)

```bash
# Génération continue jusqu'à interruption (Ctrl+C)
# Mémoire constante ~8MB
cargo run --release -- --word "word" --count 999999999 --streaming \
  | head -n 1000000 \
  | sort -u \
  > million_uniques.txt
```

## Tableau de décision

| Besoin | Quantité | Mode recommandé | Commande |
|--------|----------|-----------------|----------|
| Tests, dev | < 10k | **Standard** | `--count 5000` |
| Résultats rapides | 10k-100k | **Streaming** | `--count 50000 --streaming` |
| Dédup 100% | > 100k | **Batch** | `--count 500000 --batch-size 50000` |
| RAM limitée (<50MB) | Quelconque | **Streaming + sort** | `--streaming \| sort -u` |
| Pipeline temps réel | Quelconque | **Streaming** | `--streaming \| process` |
| Génération massive | > 10M | **Batch** | `--count 50000000 --batch-size 1000000` |

## Statistiques de duplicatas (streaming)

Estimation du taux de duplicatas en mode streaming selon le nombre d'anagrammes possibles :

| Mot source | Anagrammes possibles | Taux de duplicatas après 100k |
|------------|---------------------|-------------------------------|
| "test" (4 lettres) | ~24 | **Très élevé** (>90%) |
| "hello" (5 lettres) | ~120 | **Élevé** (~50-80%) |
| "algorithm" (9 lettres) | ~362k | **Faible** (<5%) |
| "programming" (11 lettres) | ~40M | **Très faible** (<0.1%) |

**Règle générale** : Plus le mot source est long, moins il y a de duplicatas en streaming.

## Alternatives futures

### Option 1 : Filtre de Bloom probabiliste
```rust
// Mémoire fixe (ex: 10MB), faux positifs <1%
BloomFilter::new(10_000_000, 0.01)
```
- ✅ Mémoire constante
- ✅ Déduplication ~99%
- ⚠️ Complexité d'implémentation

### Option 2 : Fenêtre glissante (LRU)
```rust
// Garde seulement les 100k derniers hashs
LruCache::new(100_000)
```
- ✅ Mémoire constante
- ⚠️ Duplicatas possibles si répétition éloignée
- ✅ Simple à implémenter

### Option 3 : Mode configurable
```bash
# L'utilisateur choisit la limite
--streaming --dedup-limit 500000  # ~40MB mais meilleure dédup
--streaming --dedup-limit 10000   # ~1MB mais plus de duplicatas
```
- ✅ Flexible
- ⚠️ Complexité interface

## Conclusion

Le compromis actuel (limite à 100k) offre un bon équilibre :
- ✅ Mémoire **vraiment constante** (~8MB)
- ✅ **100% unique** pour la majorité des cas d'usage (< 100k)
- ✅ **Mode batch disponible** pour déduplication complète si nécessaire
- ✅ **Compatible avec filtrage externe** (sort -u, awk, etc.)

Pour la plupart des utilisateurs, générer < 100k anagrammes est suffisant et bénéficie de la déduplication complète. Pour les cas extrêmes, le mode batch offre la garantie de déduplication totale.