Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Придумать метрику равномерности чтения файла / 15 сообщений из 15, страница 1 из 1
17.06.2013, 21:17
    #38300699
Alexey Kuznetsov
Alexey Kuznetsov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Есть файл. Считаем что он разбит на блоки равной длины. Минимально по 4кб.
Из файла производится считывание. Необходимо придумать метрику для отслеживания "равномерности" чтения файла.
От 0 до 1.

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

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

Можете еще что-то посоветовать для вычисления равномерности?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.06.2013, 23:00
    #38300759
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Какой такой коэффициент у тебя равен 0.9-0.7?

Есть такая штука: линейная регрессия.
Грубо говоря: Построй точечный график - номера блоков по x, количество обращений к блоку по y. Попытайся провести прямую через эти точки.
По результатам расчета такой прямой можно получить уравнение прямой и коэффициент корреляции. Последний и даст тебе "одну цифру", от 0 до 1.
http://en.wikipedia.org/wiki/Linear_regression
Но там тоже не все так просто...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.06.2013, 23:35
    #38300778
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey Kuznetsovпридумать метрику для отслеживания "равномерности" чтения файла.Так и не придумаете.
Поскольку в вашей постановке - нет как минимум одного необходимого структурного показателя (порядок считывания блока: поиск от начала; поиск по ключу/индексу,..) и минимум одного существенного показателя (сущностный состав "файла").
Примеры:
- если ваш файл представляет собой набор динамических стрингов в виде дерева, описывающего Орфографический словарь - то статистика чтения блоков будет правильно описывать только количество узлов графа путей поиска
- если ваш файл представляет собой таблицу отсортированного справочника (например, адреса или телефоны города/региона/страны) - то статистика чтения блоков будет (скорее всего!) показывать распределение запросов по расстоянию от запрашивающего до сервиса (например, в базе КЛАДР, на публичном сервисе в Ростове - максимум распределения будет на блоках Ростова и Ростовской области)

Так что либо конкретизируйте, либо...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 09:34
    #38300992
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey KuznetsovНеобходимо придумать метрику для отслеживания "равномерности" чтения файла.
Сначала дайте строгое и однозначное определение этого термина. Тогда методика сама собой вылезет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 10:03
    #38301037
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey KuznetsovКол-во блоков = k
Заводим массив счетчиков, сколько каждый блок раз был прочитан: m_i
sum(m_i)/(k*max(m_i))
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 11:25
    #38301196
Alexey Kuznetsov
Alexey Kuznetsov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
?sum(m_i)/(k*max(m_i))

Выглядит не плохо, а какой у этого выражения математический смысл?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 11:36
    #38301218
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey Kuznetsov, отношение среднего (арифм.) количества чтений одного блока к количеству чтений самого читаемого блока.
Кстати, даст абсолютно одинаковый результат как для такого распределения
Код: plaintext
5  5  5  5  5  10  5  5  5  0
, так и для такого, например
Код: plaintext
9  4  9  1  1  10  8  1  1  6
Как-то не тянет на показатель "равномерности чтения", имхо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 11:48
    #38301246
Alexey Kuznetsov
Alexey Kuznetsov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
На хабре еще посоветовали:

Сумма модулей отклонения от медианы, деленая на общее количество чтений.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 12:54
    #38301396
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey KuznetsovСумма модулей отклонения от медианы, деленая на общее количество чтений.6666554444=10010510501000
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 12:59
    #38301412
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey Kuznetsov , и всё-таки... что же, по-Вашему, есть оно такое?
Да, ещё вопрос - а для нахрена оно надо? мож, Вы зря не учитываете эффекта кэширования, например...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 13:13
    #38301467
Alexey Kuznetsov
Alexey Kuznetsov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Akina Alexey Kuznetsov , и всё-таки... что же, по-Вашему, есть оно такое?
Да, ещё вопрос - а для нахрена оно надо? мож, Вы зря не учитываете эффекта кэширования, например...
Мы тут пытаемся замутить типа прфайлер для Hadoop File System.
И есть мысль показывать пользователю что у него есть файлы в которых есть "хот споты".

Мы тут пришли к мысли что надо тупо гистограмму показывать - на ней будет видно где резкий пик, а где провал.

Еще есть мысль как-то использовать проверку гипотезы на соответсвие текущего распределения равномерному распределению (статистика хи-квадрат). Можно ли как то из проверки гипртезы не только получить да/нет, но и какую-нибудь цифру от 0 до 1 - типа степень совпадения с равномерным законом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 13:47
    #38301545
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Alexey Kuznetsovгде резкий пиккак только чётко определите, что такое "резкость" этого пика, так и алгоритм его поиска станет ясен :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 13:56
    #38301575
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
 
оффтопРавномерность чтения файла в профилировании файловой системы? Это при том, что крайне редко файл считывается целиком одним потоком от головы до задницы...

Для профилирования работы ФС с точки зрения интерфейса от логического представления к физическому устройству имхо было бы интересно двумерное распределение процента запросов по осям (размер блока) и (время доступа), но вот профилирование именно файловой системы... там же чего только нет - кэширование на устройстве, лифт чтения-записи, модификация служебных структур, включая журналирование, и т.д., и т.п... и вы всё это хотите загнать в одно число?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 15:22
    #38301771
Alexey Kuznetsov
Alexey Kuznetsov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
Akina,

Я может не совсем корректно описал про профилирование.

Задача вот такая: на хадупе ранаются таски которые обрабатывают файлы, причем файлы обычно очень большие.
И моя задача отследить такую ситуацию, когда некий большой файл читается не равномерно весь, а только его небольшая часть,
что может служить признаком неоптимальной логики работы (или даже бага) хадуповской таски или неоптимальность разбиения обрабатываемых данных на файлы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.06.2013, 15:36
    #38301802
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Придумать метрику равномерности чтения файла
ааа... вон оно как... то есть речь не о времени доступа, а (грубо говоря) о том, насколько рационально используется пространство файла?

Но тогда поневоле вопрос - а какой в том смысл? я понимаю, если ты речь шла о создании хранилова на кучу экзабайт с фреймом доступа в сотню терабайт, и разработке алгоритма оптимального сноса неиспользуемых данных из фрейма на внешние носители с высоким временем доступа (впрочем, обычный лифт на базе LRU/MRU и минимального блока предсказаний должен неплохо с этим справляться)... но для хадупы ты же не будешь гонять (а то и дублировать) данные с дальнего узла на ближний! или будешь? и именно для отработки этого момента всё и затеяно?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Придумать метрику равномерности чтения файла / 15 сообщений из 15, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 354ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1341769]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 57ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 27ms
get tp. blocked users:
 1ms
others: 234ms
total:  354ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]