Ответ 1
Эти результаты являются разумными с учетом вашей текущей реализации. Обоснование этого, однако, имеет некоторое обсуждение.
При рассмотрении алгоритмов в целом наиболее важно учитывать свойства проверяемых алгоритмов. В частности, обратите внимание на их угловые случаи и лучшие и худшие условия. Вероятно, вы уже знакомы с этим сложным методом оценки, так что это в основном для тех, кто читает здесь, у кого может не быть алгоритмического фона.
Позвольте сломать ваш вопрос по алгоритму и изучить его свойства компонента в контексте:
-
FIFO показывает увеличение ошибок страницы по мере увеличения размера рабочего набора (оси длины).
Это правильное поведение, соответствующее аномалии Bélády для замены FIFO. По мере увеличения размера вашей рабочей страницы число страниц также должно увеличиваться.
-
FIFO показывает увеличение ошибок страницы, так как стабильность системы (1 - глубина оси) уменьшается.
Отмечая ваш алгоритм стабильности посева (
if random.random() < stability), ваши результаты становятся менее стабильными по мере приближения стабильности (S) 1. При резком увеличении entropy в ваших данных количество ошибок страницы также резко увеличивается и распространяется на аномалию Белади.До сих пор так хорошо.
-
LRU показывает согласованность с FIFO. Почему?
Обратите внимание на свой алгоритм посева. Стандартный LRU является наиболее оптимальным, если у вас есть поисковые запросы, которые структурированы в меньших операционных кадрах. Для упорядоченного, предсказуемого поиска он улучшает FIFO путем старения результатов, которые больше не существуют в текущем кадре выполнения, что является очень полезным свойством для поэтапного выполнения и инкапсулированной модальной операции. Опять же, до сих пор, так хорошо.
Однако вспомните, как вы высевали свои входные данные: используя
random.random, тем самым предоставляя вам равномерное распределение данных с контролируемым уровнем энтропии. Из-за этого все значения одинаково вероятны, и поскольку вы построили это в пространстве с плавающей запятой, повторения очень маловероятны.В результате ваш LRU воспринимает каждый элемент на наличие небольшого количества раз, а затем полностью отбрасывается при вычислении следующего значения. Таким образом, он правильно отображает каждое значение, когда оно выпадает из окна, что дает вам производительность, точно сравнимую с FIFO. Если ваша система должным образом учитывает повторяемость или сжатое пространство символов, вы увидите значительно разные результаты.
-
Для случайного периода стабильности и размера рабочего набора, похоже, вообще не влияет на производительность. Почему мы видим эту надпись по всему графику вместо того, чтобы давать нам гладкий манифольд?
В случае случайной схемы поискового вызова вы стареете с каждой записью стохастически. Предположительно, это должно дать нам некоторую форму многообразия, связанного с энтропией и размером нашего рабочего набора... right?
Или это должно быть? Для каждого набора записей вы произвольно присваиваете подмножество странице как функцию времени. Это должно давать относительно ровную производительность подкачки, независимо от стабильности и независимо от вашего рабочего набора, если ваш профиль доступа снова равномерно случайен.
Итак, на основе условий, которые вы проверяете, это абсолютно правильное поведение в соответствии с тем, что мы ожидаем. Вы получаете ровную производительность подкачки, которая не деградирует с другими факторами (но, наоборот, не улучшается ими), что подходит для высокой нагрузки, эффективной работы. Неплохо, просто не то, что вы могли бы интуитивно ожидать.
Итак, вкратце, что разбивка по вашему проекту в настоящее время реализована.
Как упражнение в дальнейшем изучении свойств этих алгоритмов в контексте различных расположений и распределений входных данных, я настоятельно рекомендую копать в scipy.stats, чтобы увидеть что, например, может иметь гауссовское или логическое распределение для каждого графика. Затем я вернусь к документально подтвержденным ожиданиям каждого алгоритма, а также к проектам, в которых каждый из них является самым большим и наименее подходящим.
В целом, я думаю, ваш учитель будет гордиться.:)