Экспресс курс по сортировкам или вспомнить всё

1. Пузырьком О(n^2). Два вложенных цикла, во внутреннем сравниваются пары соседних элементов, начиная с нижних. Таким образом за один проход внутреннего цикла получаем один отсортированный элемент на своем месте.

2. Выбором О(n^2). В исходном массиве ищем наименьший элемент и меняем его с первым. Далее повторяем эти шаги с подмассивом исходного, куда не входит уже отсортированный первый элемент.

3. Вставками O(n^2). Все элементы условно разделяются на готовую последовательность a1 ... ai-1 и входную ai ... an. Hа каждом шаге, начиная с i = 2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.

4. Шелла O(n log^2 n). Некая модификация сортировки вставками: здесь сначала сортируется не весь массив, а группы элементов, отстоящих друг от груга на некоторое расстояние d. Это расстояние постепенно уменьшаем и доходим до того, что сортируем опять же весь массив. Например, для массива 16 элементов разумно выбрать начальное d = 8, а потом уменьшать его в два раза. Сначала будет сортироваться 8 групп по 2 элемента, потом 4 группы по 4 и так далее.

5. Пирамидальная O(n log n). Из исходного массива сначала строится пирамида. Она является так же сбалансированным деревом и обладает свойством, что каждый элемент меньше либо равен родителю. Это дерево легко вписывается в массив, если вписывать элементы по порядку - слева направо и сверху вниз. Далее первый элемент (максимальный) меняем с последним (минимальным) и забываем его, т.е. не учитываем в пирамиде. Перестраиваем пирамиду согласно свойству, т.е. просеиваем первый элемент вниз. Повторяем шаги пока пирамида не иссякнет.

6. Быстрая O(n log n). Из массива выбирается некоторый опорный элемент a[i]. Запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо.
Теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого. Для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

7. Поразрядная O(nk). Итак, в этом алгоритме у нас есть некие вспомогательные списки, называемые карманами. Их количество равно разрядности данных, например, для человеческих чисел = 10. Вначале они пустые и в них добавляются элементы нашего массива согласно значению первого разряда. Далее полученные списки склеиваются, и операция повторяется над полученным массивом, но только со 2 разрядом. И далее вплоть до максимального разряда самого длинного числа.

Matplotlib - анимация в реальных условиях

На сайте проекта - http://matplotlib.sourceforge.net/examples/index.html - даны базовые примеры анимации с графиками, которые, как обычно бывает, плохо работают в боевых условиях. Например, у меня имеется прога на GTK, с отдельным потоком, где производятся все вычисления для графиков. По-хорошему, там же и надо вызывать функцию перерисовки, но не тут-то было!

Иксы выкатывают мне неведомую ошибку:

The program 'panel.py' received an X Window System error. This probably reflects a bug in the program. The error was 'BadDrawable (invalid Pixmap or Window parameter)'. (Details: serial 6974 error_code 9 request_code 62 minor_code 0) (Note to programmers: normally, X errors are reported asynchronously; that is, you will receive the error a while after causing it. To debug your program, run it with the --sync command line option to change this behavior. You can then get a meaningful backtrace from your debugger if you break on the gdk_x_error() function.)

Я так и не понял почему такое может происходить, поэтому начал искать другой способ запуска функции через определенный промежуток времени. В этом мне помог такой кодес:

import gobject
gobject.timeout_add(1000, self.animate)

 Такой замес тупо вызывает функцию animate каждую секунду. Все довольны!

Подключение некоторых Android 2.3 based устройств к Linux

Не знаю уж почему так делают, но на некоторых прошивках Android 2.3 при подключении к компу устройство по умолчанию распознается как модем, а не как флешка, что сопровождается подобными деферамбами dmesg:

[81405.955234] usb 2-2: new high speed USB device number 7 using ehci_hcd
[81406.098927] cdc_acm 2-2:1.0: This device cannot do calls on its own. It is not a modem.
[81406.099041] cdc_acm 2-2:1.0: ttyACM0: USB ACM device

На этом всё, то есть как флешка оно не определяется. Итак, чтобы исправить это, заходим в телефон и набираем номер *#7284#, выскочит некая PhoneUtil, где и надо выбрать в обоих случаях пункт PDA. Вот и всё, теперь андроид монтируется как в старые добрые времена.

Перепрошивка Galaxy Tab на Android 2.3

Samsung уже давно анонсировал обновление Android 2.3 для Galaxy Tab, но официально распространять его в нашей стране не торопится. Мне это надоело и я решил перепрошить свой девайс самостоятельно итальянской версией системы.
Для этого воспользуемся прогой heimdall, которая является кроссплатформенной, в отличие от остальных:

# dpkg -i heimdall_1.3.0_i386.deb

Далее нужно скачать саму прошивку, можно отсюда. После этого распаковываем tar в отдельную папку и добавляем туда файл P1_add_hidden.pit из основного архива. Потом переводим наш планшет в режим перепрошивки, для этого надо выключить его, а потом зажать кнопку включения и кнопку понижения громкости пока не появится значок с гастарбайтером. Подключаем девайс к компу через usb и вводим команду:

$ heimdall flash --repartition --pit P1_add_hidden.pit --cache cache.rfs --dbdata dbdata.rfs --factoryfs factoryfs.rfs --kernel zImage

Всё! Перепрошивка занимает несколько минут, потом устройство само перезагрузится и можно начинать переустанавливать весь софт. =\

MySQL и Python

Итак, тут я расскажу как быстро развернуть СУБД мускуль и рулить ей из питона. Начнем. Сперва установим нужные пакеты. Мускуль:

# apt-get install mysql-server

В процессе установки спросят пароль для рута, лучше ввести что-нибудь и не забыть! Ставим модуль для питона:

# apt-get install python-mysqldb

Ну вот, после этого было бы неплохо создать базу данных и пользователя к ней. Логинимся под рутом:

$ mysql -u root -p

Создаем базу:

mysql> CREATE DATABASE testdb;

Создаем пользователя с паролем 'test', даем все права и выходим:

mysql> CREATE USER 'user'@'localhost' IDENTIFIED BY 'test';
mysql> USE testdb;
mysql> GRANT ALL ON testdb.* TO 'user'@'localhost';
mysql> quit;

Теперь небольшой пример:

import MySQLdb as mdb

conn = mdb.connect('localhost', 'user', 'test', 'testdb')
cursor = conn.cursor()
cursor.execute("SELECT VERSION()")
data = cursor.fetchone()
print data
cursor.close()
conn.close()

Здесь просто выполняется запрос "SELECT VERSION()" и соотвественно версия субд выводится на экран. Функция fetchone() возвращает одну строку. Если запрос возвращает множество строк, то чтобы их получить можно использовать fetchall(). Но если записей очень много, то это может быть расточительно для памяти. В таком случае нам поможет атрибут rowcount, где содержится количество строк, которое вернул запрос:

cursor.execute("SELECT * FROM table")
numrows = int(cursor.rowcount)
for i in xrange(numrows):
    row = cursor.fetchone()
    print row

Кстати, row представляет из себя кортеж, так что можно с легкостью получить доступ к каждому элементу выборки. Ну а дальнейшие изыскания ограничиваются только вашими знаниями языка SQL!

Python + Excel или создаем отчеты в формате XLS

Создавать экселевские файлы в питоне элементарно! Для этого есть модуль xlwt. Ставим:

# apt-get install python-xlwt

Простейший пример:

import xlwt

# тут важно поставить 'utf-8', если надо писать русские символы и так далее
wbk = xlwt.Workbook('utf-8')
# добавляем лист
sheet = wbk.add_sheet('sheet 1')
# пишем в первую строку и первый столбец
sheet.write(0, 0, 'bla bla')
# сохраняем в файл
wbk.save('test.xls')

Вот и всё! Конечно, функционал модуля этим не ограничивается, все интересующиеся могут ознакомиться с ним на страницах документации.

Установка Linux на долбаную флешку

Сегодня я закоспектирую тут, как правильно ставить НЕ live дистрибутив Linux на флешку, в моем случае Debian, а то я забываю некоторые моменты и парюсь с этим каждый раз. =\

Итак, всё начинается с форматирования флешки с помощью fdisk и mkfs. Я ставлю ФС ext2, потому что там нет журналирования, а с журналом флешка быстро загнется. Можно воспользоваться и ext3/4 с отключенным журналом, но это дополнительный гемор. Кстати, рекомедую раздел создавать именованый, потом станет понятно зачем:
# mkfs.ext2 -L TRANSCEND /dev/sdc1

Монтируем флешку:
# mount /dev/sdc1 /mnt

Ставим туда базовую систему:
# debootstrap --arch i386 lenny /mnt

Для Debian есть специальная утилита debootstrap, для других дистров может и нет, но можно и вручную залить туда из образа, например. После установки чрутимся в нашу новую системку:
# chroot /mnt /bin/bash

В этой системе уже можем делать что-нибудь, ставить пакеты например, но для начала надо апдейтнуть список, чтобы APT не ругался на не подписанные пакеты. Ну и сразу поставим GRUB и ядро:
# apt-get update
# apt-get install linux-image-2.6-686 grub

Пишем в /etc/fstab такую инфу, чтобы все правильно монтировалось:

LABEL=TRANSCEND / ext2 defaults,errors=remount-ro,noatime 0 1
proc /proc proc defaults 0 0
tmpfs /tmp tmpfs defaults,noatime 0 0
tmpfs /var/lock tmpfs defaults,noatime 0 0
tmpfs /var/log tmpfs defaults,noatime 0 0
tmpfs /var/run tmpfs defaults,noatime 0 0
tmpfs /var/tmp tmpfs defaults,noatime 0 0

И после этого начинается самая шляпа - надо сделать флешку загрузочной. Из основной системы ставим GRUB в MBR флешки:
# grub-install --root-directory=/mnt /dev/sdc

И можно уже попробовать загрузиться, НО! Проблема в том ,что Lenny использует GRUB 0.**, а все более-менее современные системы - GRUB 1.**, а они смотрят конфиги в разных местах, /boot/grub/menu.lst и /boot/grub/grub.cfg соотвественно. Грузимся через QEMU:
# qemu -hda /dev/sdc

Получаем консоль граба, который не нашел конфиг, вводим туда такие фразы:
set root=(hd0,msdos1)
linux /vmlinuz root=LABEL=TRANSCEND
initrd /initrd.img
boot

Все! Система загружается. Дальше логинимся под рутом без пароля и ставим нужный GRUB в MBR:
# update-grub
# grub-install /dev/hda

Последний момент, надо в /boot/grub/menu.lst задать корень через метку флешки, потому что на разных компах файлы устройства флешки могут различаться:

kernel /boot/vmlinuz-2.6.22-3-686 root=LABEL=TRANSCEND ro

Работа с COM портом в python: PyVISA или pySerial?

Для питона существует два модуля для работы с последовательными портами, я бы однозначно рекомендовал pySerial по нескольким причинам:

1. PyVISA сложен в установке, нужно дополнительно устанавливать библиотеку nivisa.
2. PyVISA не видит эмулированный через USB последовательный порт (т.е. переходник USB->COM).
3. В PyVISA нельзя задавать порт напрямую через файл устройства, например, в случае переходника USB->COM это будет /dev/ttyUSB0.

PySerial всех этих недостатков лишен, при этом очень прост в использовании. При работе с последовательным портом не надо забывать выставить одинаковые настойки на компе и собственно устройстве, в особенности это касается скорости передачи и бита четности. Все настройки могут задаваться при создании экземпляра объекта Serial или после через атрибуты.

Страница документации.

Парсим логи при помощи генераторов - 2

Дано: сотни логов веб-сервера, разбросанные по разным директориям. Возможно, заархивированные.
Требуется: понять сколько байтов было передано :)

В питоне есть замечательная функция os.walk(), позволяющая блуждать по файловой системе:

import os

for path, dirlist, filelist in os.walk(topdir):

    # path : текущая директория

    # dirlist : список поддиректорий

    # filelist : список файлов

    ...

Для достижения цели потребуется создать несколько функций:
1. Функция-генератор, возвращающая список файлов по заданному шаблону:

import os
import fnmatch
 

def gen_find(filepat,top):
    for path, dirlist, filelist in os.walk(top):
        for name in fnmatch.filter(filelist, filepat):
            yield os.path.join(path, name)

Примеры использования:

pyfiles = gen_find('*.py', '/')
logs = gen_find('access-log*', '/usr/www/')

2. Функция-генератор, которая принимает список файлов, и, если среди них есть архивы, то возвращает распакованные файлы. Если файл не архив, то просто открывает его:

import gzip

import bz2
 

def gen_open(filenames):
    for name in filenames:
        if name.endswith(".gz"):
            yield gzip.open(name)
        elif name.endswith(".bz2"):
            yield bz2.BZ2File(name)
        else:
            yield open(name)

3. Функция (разумеется генератор), которая возвращает единую последовательность результатов, принимая при этом несколько последовательностей (в нашем случае передаем открытые файлы, а получаем последовательность строк):

def gen_cat(sources):
    for s in sources:
        for item in s:
            yield item

Ну вот, после реализации всех этих функций осталось только немного подправить прошлый исходник, чтобы он теперь работал с любым количеством файлов:

filenames = gen_find('access-log*', '/usr/www')
logfiles = gen_open(filenames)
loglines = gen_cat(logfiles)
bytecolumn = (line.rsplit(None, 1)[1] for line in loglines)
bytes = (int(x) for x in bytecolumn if x != '-')
print "Total", sum(bytes)

Особые эстеты могут свернуть этот исходник вплоть до 1 строчки, благодаря тому факту, что в питоне все функции - высшего порядка.

Парсим логи при помощи генераторов

Задача: понять по логам Apache сколько байтов мы передали.
NB: файлы мб большие (несколько гигов).

Формат логов примерно следуюший:

217.168.25.4 - - [28/May/2011:14:06:27 +0400] "GET / HTTP/1.0 200 8509

Надо получать из каждой строки последнюю циферку, при этом если ничего не передавалось в запросе (например, произошла ошибка), то вместо циферки будет дефис. Как и в прошлый раз предлагаю два варианта: быдлокодерский и православный. Итак, номер один, без использования генератора:

wwwlog = open("access-log")

total = 0

for line in wwwlog:

    bytestr = line.rsplit(None,1)[1]

    if bytestr != '-':

        total += int(bytestr)

print "Total", total

И, с генератором:

wwwlog = open("access-log")

bytecolumn = (line.rsplit(None,1)[1] for line in wwwlog)

bytes = (int(x) for x in bytecolumn if x != '-')

print "Total", sum(bytes)

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