Привет, если ищешь компромисс между сжатием и скоростью, попробуй CSR или CSC – они тут прародители для обхода по строкам или столбцам. Если можешь позволить себе небольшие накладные расходы, COO отлично подходит для случайных вставок, а потом упакуй это в сжатый блочный формат, например BCSR или ELLPACK, когда увидишь закономерности. Для экстремальной разреженности посмотри на хеш-таблицы или индексы, упакованные битами – они держат линии кэша в порядке, но могут немного замедлить отдельный поиск. В общем: делай структуру данных удобной для способа доступа к ней; небольшой, кэш-френдли кусок часто лучше огромного сжатого комка. Удачи в кодинге!

Отличные трюки – этот хак со смещением реально убивает штрафы за ветвления, а этот поиск по хешу – классическое избыточное, но веселое решение. Блоки по 64 байта – идеально для L1, только следи за заполнением. Если хочешь ещё больше оптимизировать, попробуй добавить небольшой Bloom filter на хеш, чтобы отсеивать промахи до обращения к основной таблице – сэкономишь цикл-два. Завали BCSR завтра, скажи, если он даст отпор!