?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
Кусочек голограммы. Обработка логов.
nyaload
_winnie
Закон больших чисел - какое-то волшебство.

Взять две московские школы - в обоих будет 2% Александров и 2% Маш, плюс-минус несколько человек. Хотя школы разные! Что бы узнать сотношение мнений толпы людей - достаточно опросить случайную сотню из толпы. Причем сотни будут каждый раз разные, а пропорции мнений - одинаковые!

При обработке логов - не обязательно использовать мега-кластер что бы обработать логи. Достаточно взять случайную выборку в 1млн элементов, и все события которые происходят хотя бы раз на тысячу - там будут. Можно с точностью до долей процентов получить разбиение на типы событий. Если интересует бинарный признак, можно вообще только 100 записей выдернуть.

Случайная выборка - очень мощный инструмент в обработке данных. Можно взять кусочек голограммы, и в ней будет полное изображение, только более размытое. Что бы посчитать количество рук и ног - достаточно фотографии человека 20x15 пикселей, а не 1024x768. Точно так же можно взять кусочек логов в 1000, 1млн записей - и часто этого достаточно что бы посчитать нужную статистику. Причем на локальном компьютере, любым скриптом, в любой програме и операционной системе без лагов доступа к общему кластеру. При социологическом опросе страны с населением в сотню миллионов человеков - этот инструмент использутся постоянно, а иначе никак. А вот при обработке данных из логов - почему-то часто обрабатываются целиком все логи, вместо малой части.

Сражу скажу когда такой способ работает неправильно - когда ищем соотношение каких-то двух редких событий, настолько редких что при случайной выборке - будет деление нуля на ноль. Или если мы считаем то, что портится при случайной выборке (напр. доля уникальных записей).

Рассмотрим два типа логов:
1) события в логах не сгруппированы, одно событие - одна запись:

Выборку можно сделать так: awk 'rand() < 0.0001'

2) события сгруппированы по признаку, и посчитаны, напр.
Маш: 3 штуки
Александров: 2 штуки
Степанов: 1 штука
Зинаид: 1 штука
Алексеев: 1 штука

Из такого лога выборку можно сделать таким скриптом:
awk -F '\t' -f sample_by_field.awk

BEGIN{
#srand()
SAMPLE_FREQ = 1e-6; #какую часть логов оставить.
SAMPLE_FIELD=2; #номер поля со штуками
OFS="\t";
}

{
if ($SAMPLE_FIELD == "1") { #оптимизация под самый частый случай
if (rand() < SAMPLE_FREQ)
print $0;
} else {
N = $SAMPLE_FIELD + 0;
sum = 0;
for (i = 0; i < N; ++i) {
if (rand() < SAMPLE_FREQ)
sum += 1;
}
if (sum) {
$SAMPLE_FIELD = sum;
print $0;
}
}
}
_Winnie C++ Colorizer


Суммирование rand() вместо использования биноминального распределения может показаться неоптимизированным, но у меня на событие которое происходит миллион раз - так же есть и миллион уникальных событий, поэтому нет смысла оптимизировать.

Tags: , ,


  • 1
Да, школы неудачный пример, именно потому что район не является случайной выборкой...

  • 1