Metraipolis › archive › dc_7b20c47ea615
Memoization Without Keys: Compact, Out-of-Core Tables for Functions of Sorted Arguments — arXiv:2609.20276
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.20276
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T04:09:21.847Z
- SHA-256 of the archived text
ddccc250f8b2fac86bbfba3e77a8410524612f0079f8a5e97e276abc2d7dc00f- Stable URL of this page
https://metraipolis.com/documento/dc_7b20c47ea615
How to cite
Memoization Without Keys: Compact, Out-of-Core Tables for Functions of Sorted Arguments — arXiv:2609.20276 — arXiv (en), https://arxiv.org/abs/2609.20276 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7b20c47ea615 (Metraipolis archive dc_7b20c47ea615, sha256 ddccc250f8b2fac86bbfba3e77a8410524612f0079f8a5e97e276abc2d7dc00f)
BibTeX
@misc{dc7b20c47ea615,
title = {Memoization Without Keys: Compact, Out-of-Core Tables for Functions of Sorted Arguments — arXiv:2609.20276},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.20276},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7b20c47ea615; sha256 ddccc250f8b2fac86bbfba3e77a8410524612f0079f8a5e97e276abc2d7dc00f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20276. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Memoizing an expensive function of a sorted score vector is a data-structure problem before it is a numerical one: at a billion gridpoints, a hash map or a search tree spends most of its space on keys the grid already determines. We describe an implemented memo table that stores none. An entry's address is computed in closed form from the sorted argument itself, so $N$ values occupy $N$ slots, the argument is recoverable from the index, and the table can be memory-mapped and served from a file larger than RAM. Against a chained hash map it uses $5.7\times$ less memory at $37$M entries and $10.2\times$ less at $1.9$B, answers queries up to $2.9\times$ faster and builds up to $250\times$ faster; on 64 threads its construction needs no coordination; a sharded hash gains only $1.17\times$. Against an open-addressing table with inline keys it is $4$--$7\times$ smaller and $100\times$ faster to build but $1.5\times$ slower to query, a deficit we trace to the $O(d)$ index arithmetic. At $22$ GB on a $16$ GB desktop it serves each query in one disk access, where no key-storing container can be built; and its order-preserving addressing keeps a perturbation workload on the same pages that a hashed layout scatters. The closed form exists because the key set is the multiset combinations, whose index is the combinatorial number system. Memoizing Plackett--Luce normalization runs $25$--$55\times$ faster than Newton's method; memoizing $\alpha$-entmax thresholds does not pay. The contrast says when this structure is worthwhile. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-18 in cs.LG). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2609.20276 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-10T03:48:18.438Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).