Русская Википедия:Развёрнутый связный список
Развёрнутый связный список — список, каждый физический элемент которого содержит несколько логических элементов (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам).
Позволяет значительно уменьшить расход памяти и увеличить производительность по сравнению с обычным списком. Особенно большая экономия памяти достигается при малом размере логических элементов и большом их количестве — так, односвязный список из 10 тысяч четырёхбайтных целых чисел при четырёхбайтной же адресации памяти займет 40 тысяч байт под собственно значения, плюс 40 тысяч байт под адреса, итого 80 тысяч байт; если же объединить числа в 100 массивов по 100 элементов, расход памяти на адреса упадёт до 400 байт, и суммарный расход составит 40400 байт.
Прирост производительности достигается за счёт того, что большая часть операций проводится над относительно небольшими массивами, которые обычно целиком помещаются в кэш-памяти. Благодаря этому быстродействие программы может быть даже выше, чем при работе с обычными массивами. В развёрнутый список легко добавлять новые элементы — без необходимости переписывать весь массив, что является большой проблемой при работе с обычными массивами.
При реализации необходимо тщательно выбирать размер «блока» (количество элементов в массивах). При слишком большом размере блока список начинает страдать от тех же проблем, что и обыкновенный массив: долгая вставка элементов в начало или середину, долгое удаление элементов оттуда же, и т. п. При слишком маленьком — увеличивается расход памяти.
См. также
- Кодирование CDR (en:CDR coding), сходная техника для уменьшения размеров списков и улучшения использования кешей.
- Список с пропусками (skip list), вариация связных списков с быстрым обходом, но с медленной вставкой и удалением.
- B-tree и T-tree, структуры данных, схожие с Р.с.с. (являются развернутыми бинарными деревьями)
- XOR-связный список, двусвязный список, использующий 1 ячейку памяти для хранения двух указателей.
Ссылки
- Unrolled linked lists - Краткое описание структуры, 2005
- CSCI-1200 Data Structures — Fall 2010. Homework 5 — Unrolled Linked Lists. Rensselaer Polytechnic Institute
- Practical Concurrent Unrolled Linked Lists Using Lazy Synchronization
- Реализация на Go
- Zhong Shao, John H. Reppy, Andrew W. Appel, Unrolling Lists // ACM Conference on Lisp and Functional Programming, June 1994
.PNG&action=edit&redlink=1){kind=link}
.PNG){kind=link}