Онлайн-алгоритм обновления списков: различия между версиями

Ранние экспериментальные исследования алгоритмов Move-To-Front, Transpose и Frequency Count были проведены Ривестом [15], а также Бентли и Макгиох [7]. Более позднее и обширное экспериментальное исследование представили Бахрах и коллеги [ ]. Они реализовали и протестировали большое количество онлайновых алгоритмов обновления списков на последовательностях запросов, сгенерированных вероятностными распределениями и цепями Маркова, а также на последовательностях, извлеченных из корпуса Calgary Corpus. Было показано, что локальность ссылок существенно влияет на абсолютную и относительную производительность алгоритмов. Бахрах и др. также проанализировали различные алгоритмы как стратегии сжатия данных.