nyaload

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

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

Entries by tag: soft-dev

CR LF
nyaload
_winnie
В некоторых файлах в некоторых контекстах надо байты '\r\n' интерпретировать так же, как как байт '\n' (например, чтение значения из рукописного конфига key=value). Иногда так делать ни в коем случае нельзя ("битый архив", hex-dump).

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

А когда так надо делать и в каких ситуациях - это область гуманитарных наук, а не computer science.
Tags:

полиномиальный хеш aka кольцевой хеш Рабина-Карпа aka хеш для олимпиад...
nyaload
_winnie
при использовании "естественного" модуля 2^64 ломается вот таким неожиданно красивым образом:
http://codeforces.com/blog/entry/4898
Tags: ,

строка по номеру
nyaload
_winnie
Есть такой забавный рекурсивный алгоритм перечисления всех строк (использущий yield из питона):

letters = "abcdefghijklmnopqrstuvwxyz"
def all_strings():
    yield ''
    for s in all_strings():
        for c in letters:
            yield s + c


Чтобы перечислить все строки - перечисляем все строки и добавляем варианты суффиксов a,b,c,...,z. Благодаря yield '' у вложенных вызываемых генераторов всегда есть достаточно ответов для более высокоуровневых, и поэтому функция не зависает.


Его можно механически, не думая, трансформировать в более полезную функцию "дай строку по номеру" (следующим шагом рекурсия легко заменяется на цикл). Просто заменяем все циклы на вычисление длины этого цикла.

def string_by_index(i):                  
    if i == 0:                           
        return ''                        
                                         
    i -= 1                               
                                         
    s = string_by_index(i // len(letters))  
    return s + letters[i % len(letters)] 
Tags:

Смотрим и отлаживаем трафик с iPhone
nyaload
_winnie
Научился смотреть http-трафик с мобильника. Оказалось очень просто - запустить прокси-отладчик на PC (Fiddler в моём случае, для мака - рекомендуют аналогичный Charles), а в айфоне в найстроках wifi-соединения (буква 'i' или стрелка '>' в кружочке) в закладке "Manual/Вручную" указать адрес моего прокси.

Бинарники из app-store скачивается без https, можно смотреть в ресурсы игрушек (подписаны ли они другим образом - не проверял, но странно будет, если не).

Смотреть HTTPS-трафик - тоже легко, по инструкции.
Tags:

binary search
nyaload
_winnie
В книге "жемчужины программирования" сообщается, что невозможно написать binary search с первого раза.

На самом деле его невозможно написать с первого раза, если не осознаешь что такое инвариант цикла. Если осознаёшь - то скорее всего запросто напишешь (я вот уже в третий раз за год написал).

Если не осознаёшь инвариант цикла, то с большой вероятностью будет одна из ошибок:

* mid = (lo+hi)/2 или hi/2+lo/2 ? (и нет, дело не в overflow, эти формулы просто разные (1+3)/2 != 1/2 + 3/2 ).Read more...Collapse )

Как писать двоичный поиск чтобы он не бажил:
* Выбрать инвариант "если искомый элемент существует, то он в [lo, hi)", изначально выбрать lo,hi = 0, N.
* mid = lo+(hi-lo)/2 (при этом для кода верно утверждение "промежуток длиннее 1 всегда укоротится").
* Если ищем первый среди равных - то сравнение выглядит как key<=array[mid-1], если последний - key<array[mid]
* в зависимости от сравнения присваиваем mid в lo или hi (в любом случае, не mid-1).



Двоичный поиск для равномерно распределённых ключей (хешей) ускоряется простым хаком "для каждого из 65536 двубайтовых префиксов запомнить, где он начинается", это убирает 16 начальных итераций.Read more...Collapse )
Tags:

python namedtuple memory
nyaload
_winnie
В питоне есть namedtuple, тупл к полям которого можно обращаться привычным синтаксисом object.field

namedtuple лучше обычных туплов тем, что к полям тупла можно обращаться по имени, легко добавлять к типу новые поля и удалять.
namedtuple лучше словарей/объектов тем, что не расходуют память на имена полей в каждом объекте.

Использование такое:
Read more...Collapse )
Померял сколько памяти занимает миллион пар-туплов, с несколькими вариантами - словари, объекты, обычные туплы.

Read more...Collapse )
Вывод: namedtuple - хороший выбор по умолчанию для массивов однотипных объектов, если отказываться от синтаксиса object.field и от питона не хочется, а привязка к размеру и порядку полей в тупле вызывает тошноту и проблемы поддержки программы.

Виды связи символа с его значением
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 )

Итератор: внутрь и наружу.
nyaload
_winnie
Два способа реализации итерации по последовательности:

1) internal iteration, "callback": программист передаёт в функцию типа foreach свой callback
2) external iteration, "iterator interface": программист зовёт у объекта функцию GetNext() и HasMore()

Недостатки callback видно на примере "а попробуй перечислить две последовательности через один (interleave([A1,A2,...], [B1,B2,...]) -> A1,B1,A2,B2,...)".
В случае iterator interface всё очевидно: зовём GetNext() у одного итератора, затем у другого. А если foreach зовёт callback для всех элементов - не получится.

Недостатки второго, iterator interface - видно на примере "а попробуй написать итератор для дерева". Сделать первым способом очень легко, простая рекурсивная функция
for-each(node, callback) { 
    if (node) {
        for-each(node->left, callback); 
        callback(node->value); 
        for-each(node->right, callback); 
    }
}

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

Итого, internal iterator - это иногда большая боль для пользователя библиотеки, а external iterator - иногда большая боль для писателя библиотеки.

В языках с yield, continuation и "зелёными потоками" - можно совместить преимущества обоих способов. Алгоритм (типа обхода дерева) выплевывает в какой-то "канал" текущее значение, а пользователь с другой стороны "канала" использует обычные методы GetNext() и HasMore(), интегрированые с for. Задача инструмента - реализовать этот канал. Такое встроено в Ruby, Go, Erlang. В bash с Unix-процессами. В Haskell с ленивыми списками может повезти, и вы не сделаете случайную незаметную утечку памяти (копию списка или список thunk-функций размером с входные данные).
В Питоне есть такое, но на 50%, нужна ручная работа и менять все промежуточные функции - при вызове каждой под-функции каждый раз писать цикл с yield. Python 3.3 экономит на строчке с for (yield from), но проблема "все функции переделать на генераторы" остаётся. Тем не менее, простые функции-генераторы - пишутся легко.

Источник: http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/
Tags:

poor man's profiler
nyaload
_winnie
Почему-то для меня каждый раз оказывается, что вспомнить как инсталлировать, запустить настоящий профайлер и его вьювер (без детализации по каждому кеш-промаху) - сложнее, чем позвать в цикле gdb.

while true; do gdb -p 19974 -ex "bt" --batch >> gdb.prof.txt ; sleep 0.1 ; done

valgrind --tool=callgrind подавал некоторые надежды в плане запоминаемости, но тормозит до неюзабельности. google profiler я забыл как запускать и инсталлировать. gprof - нужно пересобрать код и вспомнить как в билд-систему подсунуть -gp. Установка perf - у меня где-то косяк с репозиториями убунты, и тоже не помню как его запускать.

Вообщем, если можете - делайте тулзы удобными для тех, кто запускает их раз в год.
gdb я запускаю чаще, где-то раз в месяц, поэтому у меня с ним лучше, а вот вспомнить с каким ключами я инсталлировал/компилировал, запускал, и annotatировал - плохо.

?

Log in

No account? Create an account