Есть два набора записей. В каждом наборе по 5. Время, которое прошло с момента последнего обращения к каждой записи из указанных наборов, сек.:

1000 50
2 50
3 40
4 10
5 10

Кандидатом на удаление из кэша в данном случае является второй набор.
Подскажите, плиз, алгоритм расчета показателя, который может использоваться для оценки наборов записей.

Здравствуйте, Аноним, Вы писали:

А>Есть два набора записей. В каждом наборе по 5. Время, которое прошло с момента последнего обращения к каждой записи из указанных наборов, сек.:

А>1000 50
А>2 50
А>3 40
А>4 10
А>5 10

А>Кандидатом на удаление из кэша в данном случае является второй набор.
А>Подскажите, плиз, алгоритм расчета показателя, который может использоваться для оценки наборов записей.

Ну и конечно количество записей в наборе может быть разное

> Кандидатом на удаление из кэша в данном случае является второй набор.
> Подскажите, плиз, алгоритм расчета показателя, который может
> использоваться для оценки наборов записей.
>
LRU (LastRecently Used)?
А так вопрос не совсем понятен!!!

Здравствуйте, Stanky, Вы писали:

S>LRU (LastRecently Used)?
S>А так вопрос не совсем понятен!!!

Удалять можно только весь набор записей, а не по одной записи. Как для набора определить критерий LRU-зности?

> Удалять можно только весь набор записей, а не по одной записи. Как для
> набора определить критерий LRU-зности?
>
Подсчитать среднее время последнего обращения у набора, ну и набор с самым большим средним вычеркнуть!!!
Но я чую, что ты далеко не это хочешь услышать!!!

Здравствуйте, Stanky, Вы писали:

S>Но я чую, что ты далеко не это хочешь услышать!!!
Прально чуешь

1000, 2, 3, 4, 5 — среднее (арифметическое) время 202.8
50, 50, 40, 10, 10 — среднее время 32

Но в первом наборе всего одна запись имеет такое большое время последнего обращения, ко всем остальным обращаются часто, поэтому 1-й набор является, по сути, более часто используемым, чем второй.
Здесь чего-то надо поинтересней замутить. Тока я вот в алгоритмах не силен

Здравствуйте, Аноним, Вы писали:

А>Есть два набора записей. В каждом наборе по 5. Время, которое прошло с момента последнего обращения к каждой записи из указанных наборов, сек.:

А>1000 50
А>2 50
А>3 40
А>4 10
А>5 10

А>Кандидатом на удаление из кэша в данном случае является второй набор.
А>Подскажите, плиз, алгоритм расчета показателя, который может использоваться для оценки наборов записей.
Хм... Советую посмотреть в сторону книги "Техника оптимизации программ. Эффективное использование памяти" by Крис Касперски. Там описаны алгоритмы работы с кешем.

Если я все правильно понял, то память в кеш помещается/замещается/читается не записями, а блоками памяти, соотв. в строки кэша. 2 основных алгоритма: LRU & FIFO.

Здесь ниже писали, что для блоков считается среднее арифметическое. На самом же деле, я полагаю, что для блока используется LRU по минимальным значениям.

т.е. на самом деле пофиг, что в первом наборе первая запись была использована 1000 тактов назад. Считывалась она вместе с остальными и 5 и 4 и 3 и 2 такта назад.

поэтому для алгоритма LRU значения "древности" использования блоков выглядят как 2 и 10 соотв.
2й набор будет замещен.

Позвольте поинтересоваться — вы занимаетесь оптимизацией или разрабатываете архитектуру процессоров ?

> 1000, 2, 3, 4, 5 — среднее (арифметическое) время 202.8
> 50, 50, 40, 10, 10 — среднее время 32
>
Теперь всё понял!!!

А не лучше ли тогда иметь время последнего доступа к серии — ну или минимум в серии и есть, то что тебе нужно?

Здравствуйте, Stanky, Вы писали:


S>А не лучше ли тогда иметь время последнего доступа к серии — ну или минимум в серии и есть, то что тебе нужно?

Доступ производится к отдельным записям в серии, поэтому могут быть парочка позабытых записей и десяток активно используемых, т.е. так, как я показал на примере. Такую серию удалять нельзя.
Кол-во записей в наборе может со временем расти, естетсвенно динамически меняется время последнего доступа к каждой записи серии. Если весовая часть (т.е. кол-во) записей с большим временем последнего обращения преобладает — такую серию надо удалять.

Здравствуйте, xtile, Вы писали:

X>Здравствуйте, Аноним, Вы писали:

X>Хм... Советую посмотреть в сторону книги "Техника оптимизации программ. Эффективное использование памяти" by Крис Касперски. Там описаны алгоритмы работы с кешем.

Спасибо, гляну.

X>Если я все правильно понял, то память в кеш помещается/замещается/читается не записями
Нет, именно записями, просто эта группа записей характеризуется общим признаком (не важно каким)

X>Здесь ниже писали, что для блоков считается среднее арифметическое. На самом же деле, я полагаю, что для блока используется LRU по минимальным значениям.
X>т.е. на самом деле пофиг, что в первом наборе первая запись была использована 1000 тактов назад. Считывалась она вместе с остальными и 5 и 4 и 3 и 2 такта назад.

В том то и дело, что не пофиг. Если кол-во записей, к которым обращались давно больше. чем тех записей, к которым обращались недавно, то хранения такого блока в кэше становится не эффективным. Он должен быть удален и при следующей операции получения данных в этот блок попадут только более часто используемые.

X>Позвольте поинтересоваться — вы занимаетесь оптимизацией или разрабатываете архитектуру процессоров ?
Надеюсь, это не подкол
Не, все гораздо проще — это кэш для DAL-компонента. Группа записей идентифицируется названием сохр. проц. В зависимости от параметров СП наборы получаемых записей могут пересекаться, поэтому не хочется сюда приплетать еще и параметры.
Можно, конечно разрулить на уровне записей, но тогда придется кэш на клиенте реплицировать с его серверной частью — это слишком большой трафик по сети.
Надо на уровне группы. Только вот беда: раз СП может вернуть 1 000 записей, а потом все время 50, которые и будут постоянно обновляться. 950 остальных — мусор. Надо удалить весь блок и перечитать только нужные 50.
Может есть другие алгоритмы кэширования...

> Кол-во записей в наборе может со временем расти, естетсвенно
> динамически меняется время последнего доступа к каждой записи серии.
> Если весовая часть (т.е. кол-во) записей с большим временем последнего
> обращения преобладает — такую серию надо удалять.
>
Тогда считаешь среднее и если большинство элементов имееют время больше среднего, то запись подлежит удалению!!!

Попробуйте в качестве критерия использовать медиану. Это такое значение
переменной, по обе стороны которого (больше и меньше) находится
одинаковое количество объектов.

Можно вместо половины использовать любой другой процент. Для
обоснованного выбора процента необходима модель случайного процесса.

wrote:
>
> Если кол-во записей, к которым обращались давно больше. чем тех
> записей, к которым обращались недавно, то хранения такого блока в
> кэше становится не эффективным. Он должен быть удален и при следующей
> операции получения данных в этот блок попадут только более часто
> используемые.
>

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

1000 50
2 50
3 40
4 10
5 10

Медиана 4 40

подробнее — в учебнике по мат. статистике.



TheBeard wrote:

> Попробуйте в качестве критерия использовать медиану.

Здравствуйте, Аноним, Вы писали:

А>Есть два набора записей. В каждом наборе по 5. Время, которое прошло с момента последнего обращения к каждой записи из указанных наборов, сек.:

А>1000 50
А>2 50
А>3 40
А>4 10
А>5 10

А>Кандидатом на удаление из кэша в данном случае является второй набор.
А>Подскажите, плиз, алгоритм расчета показателя, который может использоваться для оценки наборов записей.
Есть 2 набора: A = {T1, T2, T3, T4, T5} и B = {T6, T7, T8, T9, T10}, 1 <= Ti < inf
Цель — минимизировать штраф за подгрузку записи не из кэша. Тогда нужно оставлять такой набор, чтобы вероятность попадания следующей записи в него была максимальна.
Пусть PA — вероятность, что следующая запись из A, а PB — из B.
PA = p1 + p2 + p3 + p4 + p5
PB = p6 + p7 + p8 + p9 + p10
, где pi — вероятность, что следующая запись такая же, как i-ая.
Нужно выбирать набор с максимальной вероятностью.

Теперь к практике Я думаю, что вероятность можно грубо заменить частотой появления. Тогда:
PA = 1/T1 + 1/T2 + 1/T3 + 1/T4 + 1/T5
PB = 1/T6 + 1/T7 + 1/T8 + 1/T9 + 1/T10
Этот критерий хорошо согласуется со "здравым смыслом".
Для вашего примера:

PA = 1/1000 + 1/2 + 1/3 + 1/4 + 1/5   = 3853 / 3000 =~ 1.3  <- выбираем этот набор
PB = 1/50 + 1/50 + 1/40 + 1/10 + 1/10 =   53 / 200  =~ 0.3

Здравствуйте, TheBeard, Вы писали:


>> Попробуйте в качестве критерия использовать медиану.
Про медиану думал, не очень точно и надо сортировать. Хотя, спасибо.

Здравствуйте, What, Вы писали:

W>

W>PA = 1/1000 + 1/2 + 1/3 + 1/4 + 1/5   = 3853 / 3000 =~ 1.3  <- выбираем этот набор
W>PB = 1/50 + 1/50 + 1/40 + 1/10 + 1/10 =   53 / 200  =~ 0.3
W>

О! Отэто примерно то, шо я пытался выразить словами

> Кол-во записей в наборе может со временем расти, естетсвенно
> динамически меняется время последнего доступа к каждой записи серии.
> Если весовая часть (т.е. кол-во) записей с большим временем последнего
> обращения преобладает — такую серию надо удалять.
>

Тогда считаешь среднее и если большинство элементов имееют время больше среднего, то запись подлежит удалению!!!
Тогда считаешь среднее квадратичное — оно не так вроде чувствительно к единичным отклонениям