Придумать метрику равномерности чтения файла?

Есть файл. Считаем что он разбит на блоки равной длины. Минимально по 4кб.

Из файла производится считывание.
Необходимо придумать метрику для отслеживания «равномерности» чтения файла.
От 0 до 1. Чем ближе к 1-це тем равномернее чтение.

Пока придумал делать так:
Кол-во блоков = k
Заводим массив счетчиков, сколько каждый блок раз был прочитан: m_i
Затем вычисляем частоту для каждого блока: p_i = m_i/n.
Затем находим матожидание: mo = 1/k
Затем находим среднеквадратичное отклонение от матожидания std_dev= sqrt([sum(p_i — mo)^2] / k)
За метрику равномерности берем 1-std_dev

В целом получается терпимо, но коэффициент меняется в не слишком больших пределах: 1.0 — 0.7

Можете еще что-то посоветовать для вычисления равномерности?

Если использовать коэффицент вариации, т.е. делить стандартное отклонение на мат. ожидание, то для некоторых значений получается число больше 1, что неприемлимо.
  • Вопрос задан
  • 3096 просмотров
Пригласить эксперта
Ответы на вопрос 5
@kuaw26 Автор вопроса
Пример использования: выявление «аномальных» файлов при обработке данных.
Если есть файл большого размера, а у него постоянно читается только небольшая его часть, такая метрика позволит его выявить.
А вообще это мы пишем профайлер для Hadoop File System.
Ответ написан
Комментировать
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
std_dev при таком определении даже при максимальной неравномерности (читается единственный блок) будет стремиться к 0 при увеличении k. Может за метрику брать 1 — (std_dev * sqrt(k))?
Ответ написан
Комментировать
EugeneOZ
@EugeneOZ
Для каждого файла создайте хэш, в который запишите список блоков.
При каждом чтении в тот блок, который прочитан, вписывайте либо единицу, либо увеличивайте содержимое на +1 (смотря что доступнее и востребованнее).
Потом, когда придёт время анализа, посмотрите в этот хэш — если более 60% хэша заполнено пустотой (или значениями близкими к нулю, в случае инкрементирования), то файл «подозрителен». По-моему так :)
Ответ написан
Комментировать
simbajoe
@simbajoe
Сумма модулей отклонения от медианы, деленая на общее количество чтений. Не уверен, правда, что получится именно от 0 до 1 (можно нормализовать), но по сути — то, что надо.
Ответ написан
youngmysteriouslight
@youngmysteriouslight
ТК, ТТ, JS, FP, WM
Нам даны m_i. Равномерность предполагает, что m_i ~ k * mo. ИМХО, удобнее сразу перейти к dp_i = abs(mo-p_i) — отклонению от среднего. Чем равномернее, тем ближе dp_i к нулю в среднем.

Если мы не хотим учитывать порядок m_i, то функция равномерности должна быть симметрична по всем аргументам.
Вы предлагаете использовать стандартное квадратичное отклонение sqrt(average(dp_i ^ 2)). simbajoe предлагает использовать average(dp_i). В общем случае можно выписать любой момент (на числа dp_i ведь можно смотреть как на выборку некоторой случайной величины) average(dp_i^t) или, приводя к той же «размерности», power(average(dp_i^t), 1/t), где t — любой натуральный параметр. std_dev соответствует t=2.

Кстати, если f(x) монотонно строго возрастает от 0 до 1 на [0,1], то какую-бы оценку не взяли (например, std_dev), всегда можно предложить оценку равномерности f(std_dev). Поэтому и average(dp_i^t), и power(average(dp_i^t), 1/t) одновременно подходят на должности оценки равномерности. Если Вас не устраивает результат, его можно подкорректировать при помощи такой функции f(x). Например, если std_dev обычно порядка 0 — 0.3, то sqrt(std_dev) порядка 0 — 0.5, а power(std_dev, 1/4) порядка 0 — 0.7, то есть занимает почти весь диапазон обычно. У нас нет Вашей статистики, под которую Вы хотите построить метрику, поэтому попробуйте поэкспериментировать, подбирая показатель степени.

Есть ещё одина доступная свобода — выбор способа усреднения average, то есть не ограничиваться средним арифметическим, но и другие варианты испробовать.

Однако есть вопрос, важен ли на порядок m_i. Зависит от задачи. Статистики [0.1, 0.2, 0.2, 0.2, 0.2, 0.1] и [0.2, 0.1, 0.1, 0.2, 0.2, 0.2] должны давать один результат или разные? Важно ли, блоки нагруженные и простаивающие идут вразброс, или они сгруппированы секциями? Для чтения файла, мне кажется, это должно учитываться. Однако, если это Вам не важно, смотрите в сторону power(std_dev, 1/t).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы