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.

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)

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)

cargo run --release -- --word "word" --count 5000000 --streaming --progress

Critère	Valeur
Mémoire	Plafonnée à ~8MB
Déduplication	✅ 100% sur premiers 100k ⚠️ 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 :

# 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)

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) :

# ~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) :

# ~50MB RAM, tous uniques
cargo run --release -- --word "algorithm" --count 500000 --batch-size 50000 --progress

Recommandation : Utilisez streaming puis filtrez les duplicatas :

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 :

# ~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 :

# ~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)

# 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

// 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)

// 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

# 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.