nyaload

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

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

Entries by tag: release

Виды связи символа с его значением
nyaload
_winnie
Модификаторы для глобальных переменных:
constexpr - для выражений вычислимых в compile-time отдельного модуля
linkexpr - для выражений вычислимых при полной сборке системы
deployexpr - для выражений вычислимых при инсталляции системы
rebootexpr - для выражений вычислимых при старте хоста
initexpr - для выражений вычислимых при старте программы
expr<component> - для выражений вычислимых при запуске определённого под-компонента системы. Топологическая сортировка по зависимостям.

Такая разбивка позволяет разным фазам сборки-деплоя-запуска-интерпретации понимать, какие выражения обязаны быть уже вычислены, и не пытаться вычислять их динамически.
А так же отлавливать ошибки в тех случаях, когда программист пытается вычислить linkexpr через rebootexpr

dobro_backup.py
nyaload
_winnie
Выкладываю питоний скрипт для бэкапов, который доделал сегодня.

Бэкап за каждую дату - выглядит просто как папка. Для того, чтобы не хранить терабайт в каждой папке по много раз при создании нового бэкапа создаются хардлинки в предыдущий бэкап. Старые папки можно смело стирать.
Для того, чтобы быстро считать md5 от файлов - в директорию сохраняется файл с посчитаными md5 и timestamps/size. Если timestamp/size файла не изменился, то верим что md5 тоже не поменялся.
Скрипт работает под Linux и Windows (под Windows даже есть оптимизированый os.walk через FindFirstFile).
Возможно, можно разобрать на запчасти для быстрого копирования директорий в production.

Cам скрипт: dobro_backup.py

Дублирую сюда usage и todoшки-недоделки:
Read more...Collapse )

packed float
nyaload
_winnie
Если допустимо округление float на ±0.1 процент, то можно хранить число как логарифм по основанию 2^(1/512). 2 байт хватит, что бы записать числа порядка 1.0e±18 (миллиард миллиардов). Деление и умножение - практически бесплатно, конверсию в double-float можно делать через таблицу с 512 элементами и битовые операции.

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

Идея хранить логарифмы вместо чисел не нова. Но хочется обратить внимание на то, что логарифм можно хранить как небольшое целое число. В контексте записи звука или освещённости в пикселах - общее место, но в big data - не распространено.

*-gramms, — сказал князь Андрей.
nyaload
_winnie
Придумал тупой алгорим, хорошо извлекающий из куска текста его частые крупные элементы. Компромисс "частый vs крупный" можно подкручивать, соль — в том, что бы не учитывать мелкие куски, которые часть крупных.

Он правда тупой-тупой и жадный, результат средненький, лингвисты и люди пишущие архиваторы будут наверное смеяться, но тем не менее работает гораздо лучше, чем «отсортировать все n-граммы». Ну какой смысл в том, что бы знать что 1-грамма "ь" встречается в «Войне и мире» чаще чем "ться", "Пьер", "опять" и "сказал князь Андрей". А этот алгоритм — выводит ближе к топу осмысленные куски текста: морфему "ться", слова "Пьер", "опять" и даже целые словосочетания со знаками препинания (", – сказал князь Андрей.")

Итак:

КУСКИ = []

for L := 50 to 1:
    for любой КУСОК длины L, который встречается в тексте K раз и K >= 2:
		выкинуть из текста вхождения этого куска
		ЭКОНОМИЯ_БУКВ = (K-1)*L #нужны твики для маленьких К
		добавить в КУСКИ пару (ЭКОНОМИЯ_БУКВ, КУСОК)
		
напечатать пары из списка КУСКИ, отсортированный по (ЭКОНОМИЯ БУКВ).



Алгоритм жует бинарники, сишные исходники. Ему пофиг на кодировку UTF-8 или urlencode, он сам выводит как из байтов составляются буквы. Правда, жадноват и часто ошибается, захватывая в кусок популярные байты D0 и D1 в UTF-8 и % в urlencode. Надо как-то избегать приклеивания к длинному куску популярных коротких n-грамм ( см. ещё пример такого приклеивания - http://dobrokot.ru/pics/i2013-03-02__20-01-14_8kb.png ). Немножко борется изменением константы 2 в K>=2.

И тем более алгоритм выше наших сомнений «как делить на слова URLы и китайские тексты».

Любопытно, может есть что-то более хорошо работающее чем этот велосипед, и не слишком сложнее (updated: Unsupervised Morpheme Segmentation)

Сформулировать формальную задачу можно так: составить словарь «кусков» текста и переписать текст, заменяя куски текста на коды кусков, так что бы минизировать общий размер словаря и текста. Код — Хаффмана, или фиксированный log2(кол-во кусков) битов, или без конкретных кодов считать его длину как (-Log2(p)). Скорее всего после такой минимизации в словаре будут осмысленные кусочки.
Tags: ,

cut fields faster in text file
nyaload
_winnie
Написал аналог утилиты cut, вырезающей столбцы из tab-delimited файла.
Работает в 2-3 раза быстрее стандартного cut и в 5-10 раз быстрей awk -F '\t' (зависит от системы), в 50 раз быстрей питона.
Как и оригинальный cut, не умеет переставлять столбцы местами, только выделяет часть из них.

http://dobrokot.ru/dump/cut_field_fast.cpp

Довольно противно на C/C++ писать то что на питоне получается в одну строку, типа sorted(set(int(x) for x in command_line.split(','))), и самое обидное что такого тупого кода парсинга командной строки - больше, и он сложней чем основной алгоритм...

Tags: , ,

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

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

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

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

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

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

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

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

Из такого лога выборку можно сделать таким скриптом: Read more...Collapse )
Tags: , ,

Оптимизация random guess. Всегда да.
nyaload
_winnie
Пусть имеется какая-нибудь machine learning задача, где нужно угадывать бинарный y - true или false, например тест наличия болезни по симптомам. Пусть мы используем метод random guess, когда мы с вероятностью p говорим "да".
Тогда:

precision от p не зависит, доля правильных результатов среди позитивных всегда одинакова.
recall растёт в завимости от p, чем больше p - тем больше доля правильных позитивных среди всех y=1.

Таким образом, наилучший random guess по F-score - это тот, который говорит "всегда да", даже если положительных примеров очень мало.
Отдельный случай, когда в выборке нет ни одного положительного экземпляра - тогда F-score не определён.

Результат забавный, но на шнобелевку боюсь не тянет, слишком простой. Впрочем, данный пример показывает, что с F-score надо быть осторожным. Даже если положительные примеры всего лишь среди 0.0001% популяции, по метрике F-score выгодней говорить что они все положительные, а не что они почти все отрицательные. А если вдруг метод "всегда отрицательный" адекватен задаче, то F-score для него вообще не определён (деление 0 на 0).

F-score, precision, recall: http://en.wikipedia.org/wiki/Precision_and_recall
Шнобелевская премия: http://ru.wikipedia.org/wiki/Шнобелевская_премия

Альтернативы:
Коррелляция - http://en.wikipedia.org/wiki/Phi_coefficient
Matthews correlation coefficient (MCC) - http://en.wikipedia.org/wiki/Matthews_correlation_coefficient
Площадь под ROC-кривой (AUC) - http://horicky.blogspot.com/2011/03/compare-machine-learning-models-with.html

Лучше использовать реальную метрику, выраженную в долларах. Например для стоматологической клиники она может быть такой:
True negative: 0 баксов, клиент уходит не заплатив.
True positive: доход в 500 баксов
False negative: 0 баксов, клиент уходит не заплатив, расход на риск потери репутации
False positive: доход в 500 баксов, расход на риск судебного преследования за неправильное лечение и потери репутации
Tags: , ,

numbers sort, lexicographic order
nyaload
_winnie
Лексикографическая("алфавитная") сортировка чисел расставляет их в неправильном порядке:
1000000
20
21
3
3.14159
4

Миллион стоит перед 20 потому что первая цифра 1 меньше 2.

Что бы лексикографическая сортировка для строковых представлений положительных чисел была правильной, можно дописать перед числом достаточно много нулей, напр. 20 нулей (коллега расказал про хак: использовать пробелы вместо нулей).
00000000000000000003
00000000000000000003.14159
00000000000000000004
00000000000000000020
00000000000000000021
00000000000001000000


Придумал ещё способ. Для сохранения зрения и места в файлах - дописать перед числом количество цифр в нем, а не нули. Двумя цифрами, 01, 02, 03, .. 99. Числа с 10-ю цифрами иногда попадаются в измерениях (миллиарды), а с сотней - уже нет.
01|3
01|3.14159
01|4
02|20
02|21
07|1000000


Можно заменить на букву, от а до z, ещё более сжато получается:
b 3
b 3.14159
b 4
c 20
c 21
h 1000000


Ну и оставить от второго числа только нужные значащие цифры, напр. 3.

b3
b314
b4
c2
c21
h1


Что бы не слишком сильно шокировать окружающих, можно писать в виде, похожем на стандартный экспоненциальный:
e06*1.0
e00*3.14

Открыть пластиковую упаковку
nyaload
_winnie
Научился открывать пластиковую упаковку (для флешек и тп) руками без ножа, ножниц и без травм. Надо бы заснять видео для ютуба, а то по запросу "how to open plastic packaging" только унылые видео с ножницами-ножами.

Сначала делаем острый сгиб твердого края, много раз сгибая в разные стороны туда-сюда. Он белеет, начинает вонять, а затем рвётся. Дальше тонкий пластик легко разрывается.

почему зеркало меняет право и лево, а верх и низ нет
nyaload
_winnie
Совершил диверсию: предложил коллегам на кухне задачку "почему зеркало меняет право-лево, но не верх и низ".

Мои мысли по этому поводу: фотки прилагаются!Collapse )
Tags: , ,

?

Log in