На память.
https://concatenative.org/wiki/view/Exotic%20Data%20Structures
На сайте, посвящённом соединительным языкам, есть раздел про экзотические структуры данных.
Меня там особо интересует массив, разбитый на √N подмассивов, это самая первая часть раздела. На нём можно оптимально (по словам авторов) реализовать очередь с сортировкой (priority queue), а это открывает интересные возможности.
Ещё в этой структуре количество разбиений √N, что роднит её с прозрачными-для-кеша (cache-oblivious) структурами данных (некоторыми, не всеми).
PS
Твиттер мне перестал нравиться, как средство выражения мыслей. Надо больше писать сюда.
На сайте, посвящённом соединительным языкам, есть раздел про экзотические структуры данных.
Меня там особо интересует массив, разбитый на √N подмассивов, это самая первая часть раздела. На нём можно оптимально (по словам авторов) реализовать очередь с сортировкой (priority queue), а это открывает интересные возможности.
Ещё в этой структуре количество разбиений √N, что роднит её с прозрачными-для-кеша (cache-oblivious) структурами данных (некоторыми, не всеми).
PS
Твиттер мне перестал нравиться, как средство выражения мыслей. Надо больше писать сюда.
