June 25th, 2020

with Cat The Cat

На память.

https://concatenative.org/wiki/view/Exotic%20Data%20Structures

На сайте, посвящённом соединительным языкам, есть раздел про экзотические структуры данных.

Меня там особо интересует массив, разбитый на √N подмассивов, это самая первая часть раздела. На нём можно оптимально (по словам авторов) реализовать очередь с сортировкой (priority queue), а это открывает интересные возможности.

Ещё в этой структуре количество разбиений √N, что роднит её с прозрачными-для-кеша (cache-oblivious) структурами данных (некоторыми, не всеми).

PS
Твиттер мне перестал нравиться, как средство выражения мыслей. Надо больше писать сюда.