История изменений
Исправление a--, (текущая версия) :
Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.
Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w+0.1b, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт, b это случай неправильного предсказания перехода) пусть будет О(...).
Для коллекции, замещающей интрузивный список внутри LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).
По памяти, видимо ограничение «занимать не более чем в 2 раза больше, чем список».
Исправление a--, :
Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.
Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w+0.1b, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт, b это случай неправильного предсказания перехода) пусть будет О(...).
Для коллекции, замещающей интрузивный список внутри LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).
Исправление a--, :
Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.
Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w+0.1b, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт, b это вероятность неправильного предсказания перехода) пусть будет О(...).
Для коллекции, замещающей интрузивный список внутри LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).
Исправление a--, :
Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.
Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт) пусть будет О(...).
Для коллекции, замещающей интрузивный список внутри LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).
Исправление a--, :
Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.
Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт) пусть будет О(...).
Для интрузивного списка внутри LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).
Исходная версия a--, :
Мне было бы реально проще если бы Вы описали все требования (гарантии?) которые Вы к конкретной структуре предъявляете.
Требования к моей коллекции: быть быстрее интрузивного списка только на том множестве операций, которые требуются при реализации LRU (или 2Q) на интрузивном списке. Поскольку хороших таймингов нет (хорошие это было бы что-то вроде 1p+2r+2w, где p это проход по указателю, r это чтение данных в размере 4-8 байт, w это запись в размере 4-8 байт) пусть будет О(...).
Для LRU это (если не упустил что-то):
1. удаление с конца за О(1);
2. вставка в начало за О(1);
3. перенос из середины в начало за О(1).