ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Придумать метрику равномерности чтения файла
15 сообщений из 15, страница 1 из 1
Придумать метрику равномерности чтения файла
    #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, 21:17
| Ответить | Цитировать | Написать  
Придумать метрику равномерности чтения файла
    #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:00
| Ответить | Цитировать | Написать  
Придумать метрику равномерности чтения файла
    #38300778
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Alexey Kuznetsovпридумать метрику для отслеживания "равномерности" чтения файла.Так и не придумаете.
Поскольку в вашей постановке - нет как минимум одного необходимого структурного показателя (порядок считывания блока: поиск от начала; поиск по ключу/индексу,..) и минимум одного существенного показателя (сущностный состав "файла").
Примеры:
- если ваш файл представляет собой набор динамических стрингов в виде дерева, описывающего Орфографический словарь - то статистика чтения блоков будет правильно описывать только количество узлов графа путей поиска
- если ваш файл представляет собой таблицу отсортированного справочника (например, адреса или телефоны города/региона/страны) - то статистика чтения блоков будет (скорее всего!) показывать распределение запросов по расстоянию от запрашивающего до сервиса (например, в базе КЛАДР, на публичном сервисе в Ростове - максимум распределения будет на блоках Ростова и Ростовской области)

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

Выглядит не плохо, а какой у этого выражения математический смысл?
...
Рейтинг: 0 / 0
18.06.2013, 11:25
| Ответить | Цитировать | Написать  
Придумать метрику равномерности чтения файла
    #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:36
| Ответить | Цитировать | Написать  
Придумать метрику равномерности чтения файла
    #38301246
Alexey Kuznetsov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexey Kuznetsov
Участник
На хабре еще посоветовали:

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

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

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

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

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

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

Но тогда поневоле вопрос - а какой в том смысл? я понимаю, если ты речь шла о создании хранилова на кучу экзабайт с фреймом доступа в сотню терабайт, и разработке алгоритма оптимального сноса неиспользуемых данных из фрейма на внешние носители с высоким временем доступа (впрочем, обычный лифт на базе LRU/MRU и минимального блока предсказаний должен неплохо с этим справляться)... но для хадупы ты же не будешь гонять (а то и дублировать) данные с дальнего узла на ближний! или будешь? и именно для отработки этого момента всё и затеяно?
...
Рейтинг: 0 / 0
18.06.2013, 15:36
| Ответить | Цитировать | Написать  
15 сообщений из 15, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Придумать метрику равномерности чтения файла
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38301396&tid=1341769]:
 0ms
get settings:
 8ms
get forum list:
 13ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 404ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 30ms
get tp. blocked users:
 1ms
others: 250ms
total:  717ms
созд. / загр.: 717ms
x
x
Закрыть


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