Разработка на коленке

"тут должна быть красивая цитата о программировании"

Ищу новую площадку с задачами по программированию

2013-02-01 13:52

Пробую силы в решении олимпиадных задач. Начал свои попытки с архива задач Online соревнование по программированию в МФТИ. Сама идея выполнения таких заданий показалась интересной, хоть и непривычной. Но вот эта площадка меня не устраивает, потому что на сервере код проверяется python 2.1.3, который совсем старый и забытый. Для того, чтобы у меня код прошёл проверку по задаче 027, мне пришлось модифицировать вот такой код

def search_odd_number(count_of_numbers, numbers):
    i = 0
    while i < count_of_numbers - 1:
        if numbers[i] ^ numbers[i + 1] != 0:
            break
        i += 2

    return numbers[i]

print(search_odd_number(int(input()), sorted(map(int, input().split(' ')))))

в такой:

# >>>> for python 2.1.3

from string import split

def sorted(s):
    s.sort()
    return s

def search_odd_number(count_of_numbers, numbers):
    i = 0
    while i < count_of_numbers - 1:
        if numbers[i] ^ numbers[i + 1] != 0:
            break
        i += 2

    return numbers[i]

print(search_odd_number(int(raw_input()), sorted(map(int, split(raw_input())))))

Тратить время на адаптацию кода под старый python мне не хочется, поэтому поищу новую площадку для развлечений.

Заодно открыл доступ к репозиторию с решениями (вроде бы это не запрещено) - ссылка на bitbucket.

An Introduction to Interactive Programming in Python

2013-01-21 23:23

В прошлом году я проходил курс по программированию на Python'е (An Introduction to Interactive Programming in Python). Записался на него по нескольким причинам:

  • любопытство;
  • just for fun (я надеялся, что это будет весело);
  • проверить свои знания английского "в бою";
  • научиться чему-то новому.

Любопытство

Мне было интересно, как будет проходить дистанционный курс обучения. К тому же вариант с запуском программ непосредственно в браузере меня тоже заинтересовал. Всё таки не каждый день встретишь использование python, написанного на javascript.

Just for fun

Мне нравится моя профессия, мне нравится сам python, и я всегда интересовался разработкой игр, а тут курс, который даёт возможность написать пару простых игр. Потратить на это время казалось неплохой идеей. Так оно и было. Мне было интересно наблюдать за летающим корабликом, было интересно ревьювить код других людей и видеть разницу в подходах новичков и опытных программистов.

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

Английский

В начале весны 2012 я чётко осознал, что огромное количество необходимого и интересного мне материала никогда не будет переведено на русский язык, и для нормального понимания мне недостаточно знать ряд ключевых слов, а нужно вникать в язык серьёзно. Большое количество курсов по алгоритмам, AI, ML, ANN, NLP. Всё это хотелось посмотреть, попробовать, что-то применить, но сначала это нужно понять.

С с конца весны 2012 я активно занялся изучением английского языка. Аудиокурсы, фильмы, lingualeo. Осенью решил опробовать на практике. Результатом остался доволен. Материалы курсы понимал без больших проблем. Тут стоит сделать скидку на то, что материал давался весьма доступно и дикторы старались говорить чётко. Тем не менее первый положительный результат получен.

Научиться чему-то новому

Особых надежд на расширение своих знаний python'а за счёт прохождения этого курса я не питал. Более того, я сомневался, что узнаю что-то новое о питоне вообще. Я хотел научиться пользоваться дистанционными курсами, взаимодействовать с другими студентами, посмотреть на разработку простых игр на практике. Ещё мне понравилась концепция версионируемых исходников на облаке. Довольно интересное решение для среды разработки.

Итого

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

Подсчёт уникальных значений в разных столбцах на SQL

2011-08-16 13:35

Недавно понадобилось сделать выборку из базы данных с подсчётом уникальных значений в разных колонках. Зачем это было нужно - не скажу, потому что это внутренняя информация.

Итак, есть у меня таблица documents и таблица objects.

objects
    id - primary key
    document_id - foreign key
    f_input - integer
    f_output - integer

Вот для полей f_input и f_output мне нужно было выдать количество уникальных значений для каждого документа.

    from (
        select number, f_input
            from documents
            join objects on documents.id = objects.document_id

        union all

        select number, f_output
            from documents
            join objects on documents.id = objects.document_id
        ) as x

    group by number
    order by number

Не знаю, лучший ли это способ, но он работает, а в данный момент мне больше и не нужно.

Зависимость скорости работы СУБД от индексов и ORM на примере SQLite, PostgreSQL и SQLAlchemy

2011-07-14 07:16

В моём зоопарке проектов приложения работают с SQLite3, PostgreSQL, MySql. На MySql крутится всего один проект, да и то только лишь потому, что довольно давно его делал и менять СУБД не вижу смысла. Остальные используют либо SQLite3, либо PostgreSQL.

Больше всего я симпатизирую SQLite, потому что работать с ней просто, из питона доступна в любой момент, вся база лежит одним файлом на диске. И вот стало мне интересно, насколько правильно подобраны у меня СУБД к разным проектам, и насколько правильно я их использую. Ну и насколько тяжко будет сменить одну СУБД на другую, ежели понадобится.

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

  1. проекты, использующие SQLite3
  2. проекты, использующие PostgreSQL
  3. большие SQL-запросы, которые сами генерируют полезные отчёты
  4. код на скриптовых языках программирования, которые используют короткие SQL-запросы
  5. код на python с использованием ORM (sqlalchemy)

Вот всё это хозяйство я и захотел протестировать. Ещё я хотел посмотреть, насколько отличается скорость работы при использовании индексов и без них (как на вставке, так и на чтении).

Структура базы данных

Для начала нужна тестовая база данных. Пусть у нас будет база данных для хранения статей. У статьи должен быть автор, уровень сложности материала и комментарии. В итоге имеем таблицы tags (это у меня уровень сложности), authors, articles, comments. Базу я описывал при помощи sqlalchemy. Модуль dbstruct.py содержит описание таблиц, параметр withindex позволяет мне создавать базу данных как с индексами, так и без них.

from sqlalchemy import Column, Integer, String, Text, ForeignKey
from sqlalchemy.schema import Index
from sqlalchemy.ext.declarative import declarative_base

def createdb(engine, withindex):
    connection = engine.connect()
    queries = (
        'drop table if exists comments',
        'drop table if exists articles',
        'drop table if exists authors',
        'drop table if exists tags'
    )
    map(connection.execute, queries)

    Base = declarative_base(engine)

    class Tag(Base):
        __tablename__ = 'tags'

        id = Column(Integer, primary_key=True)
        tagname = Column(String)

        if withindex:
            __table_args__ = (Index('idx_tag_id', id),)

        def __init__(self, tagname):
            self.tagname = tagname

    class Author(Base):
        __tablename__ = 'authors'

        id = Column(Integer, primary_key=True)
        nickname = Column(String)
        fullname = Column(String)

        if withindex:
            __table_args__ = (Index('idx_author_id', id),)

        def __init__(self, nickname, fullname):
            self.nickname = nickname
            self.fullname = fullname

    class Article(Base):
        __tablename__ = 'articles'

        id = Column(Integer, primary_key=True)
        title = Column(String)
        body = Column(Text)
        author_id = Column(Integer, ForeignKey('authors.id'), nullable=False)
        tag_id = Column(Integer, ForeignKey('tags.id'), nullable=False)

        if withindex:
            __table_args__ = (Index('idx_article_id', id, author_id, tag_id),)

        def __init__(self, title, body, author_id, tag_id):
            self.title = title
            self.body = body
            self.tag_id = tag_id
            self.author_id = author_id

    class Comment(Base):
        __tablename__ = 'comments'

        id = Column(Integer, primary_key=True)
        body = Column(Text)
        article_id = Column(Integer, ForeignKey('articles.id'), nullable=False)

        if withindex:
            __table_args__ = (Index('idx_comment_id', id, article_id),)

        def __init__(self, body, article_id):
            self.body = body
            self.article_id = article_id

    Base.metadata.create_all(engine)

    return Tag, Author, Article, Comment

Работа с данными

Теперь нужно подготовить функции, которые будут делать вставку и выборку данных. Все функции будут лежать в модуле dbtestfunc.py.

Вставка данных в базу

Вставку я делаю с помощью sqlalchemy. Уровней сложности статей у меня 3 - junior, middle, guru. Сложность для статей просто чередуется в цикле. Имена авторов генерируются в цикле. Текст статьи сделал не очень длинным, но и не в 10 символов, примерно, как короткая заметка в блоге.

def fillDB(engine, Tag, Author, Article, Comment, authorsCount, articlesCount, commentsCount):
    session = sessionmaker(engine)()

    tags = ('junior', 'middle', 'guru')
    map(session.add, [Tag(tagname) for tagname in tags])
    session.commit()

    for authorNum in xrange(authorsCount):
        author = Author('au_%d' % authorNum, 'author %d fullname' % authorNum)
        session.add(author)
        session.commit()

        for articleNum in xrange(articlesCount):
            title = 'article %d from auhtor %d' % (articleNum, authorNum)
            body = 'some text of article ' * 200
            tagId = (articleNum % 3) + 1
            article = Article(title, body, author.id, tagId)
            session.add(article)
            session.commit()

            for commentNum in xrange(commentsCount):
                body = 'some text of comment ' * 20
                comment = Comment(body, article.id)
                session.add(comment)

    session.commit()

Статистика по всем таблицам

Нужно получить статистику по количеству данных в каждой таблице.

def getCountByTable(engine):
    query = '''
    select 'tags' as table_name, count(id) as population from tags
    union all
    select 'authors', count(id) from authors
    union all
    select 'articles', count(id) from articles
    union all
    select 'comments', count(id) from comments
    '''

    connection = engine.connect()
    result = connection.execute(query)
    tline = '+%s+%s+' % ('-' * 15, '-' * 20)
    print tline
    for row in result:
        print '|%-15s|%20d|' % (row[0], row[1])
        print tline

Большой sql-запрос с 2 уровнями вложенности подзапросов

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

def useBigSelectQuery(engine):
    query = '''
    select nickname,
        (select count(*) from articles where author_id = authors.id and tag_id = 1),
        (select count(*) from articles where author_id = authors.id and tag_id = 2),
        (select count(*) from articles where author_id = authors.id and tag_id = 3),
        (select count(*) from comments where article_id in (
            select id from articles where author_id = authors.id and tag_id = 1)),
        (select count(*) from comments where article_id in (
            select id from articles where author_id = authors.id and tag_id = 2)),
        (select count(*) from comments where article_id in (
            select id from articles where author_id = authors.id and tag_id = 3))
    from authors
    '''

    connection = engine.connect()
    result = connection.execute(query)

    format = '|' + '|'.join(['%10s' for x in range(7)]) + '|'
    separator = '+' + '+'.join(['%s' % '-' * 10 for x in range(7)]) + '+'

    print '''
SQL query select test
+----------+----------+----------+----------+----------+----------+----------+
|          |junior    |middle    |guru      |junior    |middle    |guru      |
|nickname  |article   |article   |article   |comment   |comment   |comment   |
|          |count     |count     |count     |count     |count     |count     |
+----------+----------+----------+----------+----------+----------+----------+'''

    for row in result:
        print format % tuple(map(str, row))
    print separator

Запрос с меньшим количеством вложенностей подзапросов

Забегая вперёд, скажу, что предыдущий запрос просто насмерть вешал SQLite. Скорость работы падала до нуля, поэтому я переписал его, используя JOIN. Ну а раз он есть, то и померил скорость его работы не только на SQLite, но и на PostgreSQL.

def useJoinBigQuery(engine):
    query = '''
    select nickname,
        (select count(id) from articles where author_id = authors.id and tag_id = 1),
        (select count(id) from articles where author_id = authors.id and tag_id = 2),
        (select count(id) from articles where author_id = authors.id and tag_id = 3),

        (select count(comments.id)
            from comments
            join articles on article_id = articles.id
            where author_id = authors.id and tag_id = 1),

        (select count(comments.id)
            from comments
            join articles on article_id = articles.id
            where author_id = authors.id and tag_id = 2),

        (select count(comments.id)
            from comments
            join articles on article_id = articles.id
            where author_id = authors.id and tag_id = 3)

    from authors
    '''

    connection = engine.connect()
    result = connection.execute(query)

    format = '|' + '|'.join(['%10s' for x in range(7)]) + '|'
    separator = '+' + '+'.join(['%s' % '-' * 10 for x in range(7)]) + '+'

    print '''
SQL query select with join test
+----------+----------+----------+----------+----------+----------+----------+
|          |junior    |middle    |guru      |junior    |middle    |guru      |
|nickname  |article   |article   |article   |comment   |comment   |comment   |
|          |count     |count     |count     |count     |count     |count     |
+----------+----------+----------+----------+----------+----------+----------+'''

    for row in result:
        print format % tuple(map(str, row))
    print separator

Используем ORM для получения данных

Теперь для получения тех же данных буду использовать ORM (sqlalchemy). Тут я, по сути, написал код, подобный первому большому запросу (без join).

def useORM(engine, Tag, Author, Article, Comment):
    from sqlalchemy.orm import sessionmaker

    session = sessionmaker(engine)()

    format = '|' + '|'.join(['%10s' for x in range(7)]) + '|'
    separator = '+' + '+'.join(['%s' % '-' * 10 for x in range(7)]) + '+'

    print '''
ORM select test
+----------+----------+----------+----------+----------+----------+----------+
|          |junior    |middle    |guru      |junior    |middle    |guru      |
|nickname  |article   |article   |article   |comment   |comment   |comment   |
|          |count     |count     |count     |count     |count     |count     |
+----------+----------+----------+----------+----------+----------+----------+'''

    for author in session.query(Author):
        data = [author.nickname,
                session.query(Article).filter(
                    Article.author_id==author.id).filter(Article.tag_id==1).count(),
                session.query(Article).filter(
                    Article.author_id==author.id).filter(Article.tag_id==2).count(),
                session.query(Article).filter(
                    Article.author_id==author.id).filter(Article.tag_id==3).count(),
                session.query(Comment).filter(
                    Comment.article_id.in_(
                        session.query(Article.id).filter(
                            Article.author_id==author.id).filter(
                            Article.tag_id==1))).count(),

                session.query(Comment).filter(
                    Comment.article_id.in_(
                        session.query(Article.id).filter(
                            Article.author_id==author.id).filter(
                            Article.tag_id==2))).count(),

                session.query(Comment).filter(
                    Comment.article_id.in_(
                        session.query(Article.id).filter(
                            Article.author_id==author.id).filter(
                            Article.tag_id==3))).count()
                ]

        print format % tuple(map(str, data))
    print separator

Использование нескольких маленьких запросов

Ну и функция, которая нужна для проверки эффективности использования нескольких небольших запросов, которые вызывают в цикле.

def useSimpleQueries(engine):

    format = '|' + '|'.join(['%10s' for x in range(7)]) + '|'
    separator = '+' + '+'.join(['%s' % '-' * 10 for x in range(7)]) + '+'

    print '''
Some simple SQL select test
+----------+----------+----------+----------+----------+----------+----------+
|          |junior    |middle    |guru      |junior    |middle    |guru      |
|nickname  |article   |article   |article   |comment   |comment   |comment   |
|          |count     |count     |count     |count     |count     |count     |
+----------+----------+----------+----------+----------+----------+----------+'''

    connection = engine.connect()

    selAuthors = 'select id, nickname from authors'
    rAuthors = connection.execute(selAuthors)
    for author in rAuthors:
        result = [author.nickname]
        for tagId in range(1, 4):
            selArtCount = 'select count(*) from articles where author_id = %d and tag_id = %d' %\
                        (author.id, tagId)
            result.append(map(None, connection.execute(selArtCount))[0][0])

        for tagId in range(1, 4):
            selComCount = '''select count(*) from comments where article_id in (
                select id from articles where author_id = %d and tag_id = %d)''' %\
                        (author.id, tagId)
            result.append(map(None, connection.execute(selComCount))[0][0])

        print format % tuple(map(str, result))
    print separator

Чтобы все эти функции заработали вместе, в начале модуля нужен код:

from sqlalchemy.orm import sessionmaker

Тестирование

Чтобы проверить время работы каждой функции из модуля dbtestfuncs.py, я написал модуль dbloadtest.py. Он запускается из командной строки и получает в качестве параметров тип СУБД: postgresql, sqlite, memory (sqlite в памяти), флаг использования индексов в базе и количество авторов (не обязательный параметр). На выходе табличка с результатами теста.

import sys
import dbstruct
from dbtestfuncs import *

from sqlalchemy import create_engine

def usage():
    man = '''Options:
    dbms type:
    -p - postgresql
    -s - slqite3. work with file
    -m - sqlite3. work with memory

    -i - using index in tables
    -n - using no index in tables

    -a=authors_count  - count of authors
    '''
    return man

if __name__ == '__main__':

    authorsCount = 10
    articlesCount = 10
    commentsCount = 20

    try:
        options = sys.argv[1:]

        if '-p' in options:
            dbparams = 'postgresql://user:secret@localhost:5432/_dbloadtest'
        elif '-s' in options:
            import os
            try:
                os.remove('_dbloadtest.sqlite')
            except: pass

            dbparams = 'sqlite:///_dbloadtest.sqlite'
        elif '-m' in options:
            dbparams = 'sqlite:///:memory:'
        else:
            raise IndexError

        if '-i' in options:
            withindex = True
        elif '-n' in options:
            withindex = False
        else:
            raise IndexError

        authc = [x for x in options if x.startswith('-a=')]
        if authc:
            authorsCount = int(authc[0].split('=')[1])
            print 'count of authors = ', authorsCount

    except IndexError:
        print usage()
        sys.exit(1)

    print 'options: %s' % str(options)

    engine = create_engine(dbparams, echo=False)
    Tag, Author, Article, Comment = dbstruct.createdb(engine, withindex)

    from timeit import Timer

    setup = 'from __main__ import fillDB, engine, Tag, Author, Article, Comment, ' +\
            'authorsCount, articlesCount, commentsCount'
    call = 'fillDB(engine, Tag, Author, Article, Comment, authorsCount, articlesCount, commentsCount)'
    fillTime = Timer(call, setup).timeit(1)

    setup = 'from __main__ import getCountByTable, engine'
    countByTableTime = Timer('getCountByTable(engine)', setup).timeit(1)

    setup = 'from __main__ import useBigSelectQuery, engine'
    bigSelectQTime = Timer('useBigSelectQuery(engine)', setup).timeit(1)

    setup = 'from __main__ import useJoinBigQuery, engine'
    bigJoinQTime = Timer('useJoinBigQuery(engine)', setup).timeit(1)


    setup = 'from __main__ import useORM, engine, Tag, Author, Article, Comment'
    ormUseTime = Timer('useORM(engine, Tag, Author, Article, Comment)', setup).timeit(1)

    setup = 'from __main__ import useSimpleQueries, engine'
    simpleQTime = Timer('useSimpleQueries(engine)', setup).timeit(1)

    times = (fillTime, countByTableTime, bigSelectQTime, bigJoinQTime,
            ormUseTime, simpleQTime)
    heads = ('fill', 'count by tables', 'big select', 'big select join',
            'orm use', 'simple queries')
    line = '+%s+%s+' % ('-' * 20, '-' * 20)
    print
    print line
    for i in range(len(times)):
        print '|%-20s|%20f|' % (heads[i], times[i])
        print line

    print '\ntesting ended!'

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

date

AUTH_COUNTS=(1 10 50 100 200)

ELEMENTS=${#AUTH_COUNTS[@]}

RESULT_DIR=all_test_results

if test -e $RESULT_DIR; then
    rm -rf $RESULT_DIR
fi

mkdir $RESULT_DIR

echo "*postgresql test"
i=0
while [ $i -lt $ELEMENTS ]
do
    COUNT=${AUTH_COUNTS[$i]}
    i=$[$i+1]

    echo "  iteration $i start..."
    python dbloadtest.py -p -i -a=$COUNT > $RESULT_DIR/[$i]_pg_with_index.txt
    python dbloadtest.py -p -n -a=$COUNT > $RESULT_DIR/[$i]_pg_no_index.txt
    echo "          ...done"
    echo
done

echo "*sqlite3 memory test"
i=0
while [ $i -lt $ELEMENTS ]
do
    COUNT=${AUTH_COUNTS[$i]}
    i=$[$i+1]

    echo "  iteration $i start..."
    python dbloadtest.py -m -i -a=$COUNT > $RESULT_DIR/[$i]_memory_with_index.txt
    python dbloadtest.py -m -n -a=$COUNT > $RESULT_DIR/[$i]_memory_no_index.txt
    echo "          ...done"
    echo
done

echo "*sqlite3 in file test"
i=0
while [ $i -lt $ELEMENTS ]
do
    COUNT=${AUTH_COUNTS[$i]}
    i=$[$i+1]

    echo "  iteration $i start..."
    python dbloadtest.py -s -i -a=$COUNT > $RESULT_DIR/[$i]_sqlite_with_index.txt
    python dbloadtest.py -s -n -a=$COUNT > $RESULT_DIR/[$i]_sqlite_no_index.txt
    echo "          ...done"
    echo
done

date

Обработка результатов

В результате запуска предыдущего скрипта получил кучу файлов с результатами. Тут сразу оговорюсь, что во время последнего теста я немного менял скрипт dbloadtest.py, потому что на количестве авторов больше 50 дождаться завершения теста с sqlite было невозможно.

Чтобы получить сводную табличку из всех файлов с результатами, написал ещё один скрипт

resultDirName = 'result'
patternsFileName = ('_memory_no_index.txt', '_memory_with_index.txt',
    '_pg_no_index.txt', '_pg_with_index.txt', '_sqlite_no_index.txt',
    '_sqlite_with_index.txt')

authorsCounts = (1, 10, 50, 100, 200)

heads = ('fill', 'count by tables', 'big select', 'big select join',
        'orm use', 'simple queries')


times = {}
for pattern in patternsFileName:
    times[pattern] = []
    for idxFile in range(len(authorsCounts)):
        fileName = resultDirName + '/' + ('[%d]' % (idxFile + 1)) + pattern
        with open(fileName, 'rt') as fp:
            times[pattern].append(map(lambda x: float(x.split('|')[2]),
                                    fp.readlines()[-14:-2:2]))

line = '+' + '-' * 20 + '+' + '+'.join(['-' * 10 for x in range(5)]) + '+'


for dbType in times:
    print '\n', dbType
    print line
    print ('|%-20s' % 'action/author_count') + ('|%10s|%10s|%10s|%10s|%10s|' % authorsCounts)
    print line

    for idxActionName in range(len(heads)):
        action = heads[idxActionName]
        dbTypeTimes = times[dbType]
        actionTimes = tuple([str(t[idxActionName]) for t in dbTypeTimes])
        print ('|%-20s' % action) + ('|%10s|%10s|%10s|%10s|%10s|' % actionTimes)
        print line

Результаты

Результаты сгруппировал по типу СУБД и по наличию индексов в базе. Там, где стоит -1, я просто не дождался завершения работы скрипта.

_pg_no_index.txt
+--------------------+----------+----------+----------+----------+----------+
|action/author_count |         1|        10|        50|       100|       200|
+--------------------+----------+----------+----------+----------+----------+
|fill                |  0.231285|   1.72187|  7.842117| 18.868243| 41.146092|
+--------------------+----------+----------+----------+----------+----------+
|count by tables     |  0.002108|   0.00162|  0.003346|  0.006318|  0.009838|
+--------------------+----------+----------+----------+----------+----------+
|big select          |  0.002859|  0.013254|  0.263669|  1.146801|  4.791618|
+--------------------+----------+----------+----------+----------+----------+
|big select join     |  0.002679|  0.012731|  0.260424|  1.170647|  4.940643|
+--------------------+----------+----------+----------+----------+----------+
|orm use             |  0.020962|  0.137301|  0.924065|  2.461377|  7.775531|
+--------------------+----------+----------+----------+----------+----------+
|simple queries      |  0.004852|  0.033245|  0.398083|  1.480214|  5.614259|
+--------------------+----------+----------+----------+----------+----------+

_memory_with_index.txt
+--------------------+----------+----------+----------+----------+----------+
|action/author_count |         1|        10|        50|       100|       200|
+--------------------+----------+----------+----------+----------+----------+
|fill                |  0.046558|  0.435866|  2.297696|   4.44086|  9.182301|
+--------------------+----------+----------+----------+----------+----------+
|count by tables     |  0.000232|  0.000598|  0.002518|  0.004859|  0.008582|
+--------------------+----------+----------+----------+----------+----------+
|big select          |  0.010185|  4.173265|  495.3262|      -1.0|      -1.0|
+--------------------+----------+----------+----------+----------+----------+
|big select join     |  0.000852|   0.04177|  1.102579|  4.700694|  19.02497|
+--------------------+----------+----------+----------+----------+----------+
|orm use             |  0.011013|  0.119054|  1.132743|  3.507863| 12.158737|
+--------------------+----------+----------+----------+----------+----------+
|simple queries      |  0.000809|  0.028106|  0.581097|  2.499086| 10.060157|
+--------------------+----------+----------+----------+----------+----------+

_memory_no_index.txt
+--------------------+----------+----------+----------+----------+----------+
|action/author_count |         1|        10|        50|       100|       200|
+--------------------+----------+----------+----------+----------+----------+
|fill                |   0.04515|  0.435912|  2.266461|    4.3318|  8.932379|
+--------------------+----------+----------+----------+----------+----------+
|count by tables     |  0.000238|  0.000627|  0.002452|  0.004428|  0.008911|
+--------------------+----------+----------+----------+----------+----------+
|big select          |  0.010438|  4.221292| 492.76092|      -1.0|      -1.0|
+--------------------+----------+----------+----------+----------+----------+
|big select join     |  0.000861|  0.042676|  1.035481|  4.751594| 18.770619|
+--------------------+----------+----------+----------+----------+----------+
|orm use             |  0.011256|  0.121582|  1.041038|  3.585144| 12.383719|
+--------------------+----------+----------+----------+----------+----------+
|simple queries      |  0.000857|   0.02478|  0.514296|  2.501858|  9.707688|
+--------------------+----------+----------+----------+----------+----------+

_sqlite_with_index.txt
+--------------------+----------+----------+----------+----------+----------+
|action/author_count |         1|        10|        50|       100|       200|
+--------------------+----------+----------+----------+----------+----------+
|fill                |  2.345496| 26.964783|127.245174|248.164527|485.671184|
+--------------------+----------+----------+----------+----------+----------+
|count by tables     |  0.022325|  0.023069|   0.02127|  0.037057|   0.06431|
+--------------------+----------+----------+----------+----------+----------+
|big select          |  0.030343|  4.971248| 9700.4559|      -1.0|      -1.0|
+--------------------+----------+----------+----------+----------+----------+
|big select join     |  0.023542|   0.07756|  5.236409| 22.053952| 84.810086|
+--------------------+----------+----------+----------+----------+----------+
|orm use             |  0.036379|  0.148815|  5.117857| 19.794298|  74.20158|
+--------------------+----------+----------+----------+----------+----------+
|simple queries      |  0.025443|  0.047866|  4.520323| 18.618552| 72.834561|
+--------------------+----------+----------+----------+----------+----------+

_sqlite_no_index.txt
+--------------------+----------+----------+----------+----------+----------+
|action/author_count |         1|        10|        50|       100|       200|
+--------------------+----------+----------+----------+----------+----------+
|fill                |  2.302192| 22.608962|114.141749|215.950755| 432.98446|
+--------------------+----------+----------+----------+----------+----------+
|count by tables     |  0.038948|  0.019935|  0.028326|  0.034316|  0.063907|
+--------------------+----------+----------+----------+----------+----------+
|big select          |  0.030463|  4.933617|      -1.0|      -1.0|      -1.0|
+--------------------+----------+----------+----------+----------+----------+
|big select join     |  0.024648|  0.077713|   5.32001| 20.818145| 85.383302|
+--------------------+----------+----------+----------+----------+----------+
|orm use             |  0.030698|  0.149703|   5.12185| 19.155246| 74.946809|
+--------------------+----------+----------+----------+----------+----------+
|simple queries      |  0.019438|  0.047167|  4.594021| 17.915685| 72.765067|
+--------------------+----------+----------+----------+----------+----------+

Заключение

По данным в таблице сделал для себя несколько выводов:

  1. SQLite не так плох, даже в сравнении с таким монстром, как PostgreSQL.
  2. Скорость работы PostgreSQL конечно же превосходит SQLite.
  3. PostgreSQL одинаково хорошо работает как с одним большим запросом, так и с очередью маленьких.
  4. SQLAlchemy с PostgreSQL даёт уменьшение скорости работы примерно в два раза.
  5. SQLAlchemy + SQLite уступает в производительности sql-запросам, но не намного.
  6. SQLite плохо переваривает подзапросы с уровнем вложенности больше 1.
  7. Индексы в SQLite не дают прироста производительности, в PostgreSQL скорость выборки увеличивается в 2 раза. При этом скорость вставки данных не падает (во всяком случае если и падает, то не сильно).
  8. Скорость вставки SQLite в памяти (memory) очень высока. Можно использовать при каких-нибудь тестах, чтобы выполнялось быстрее.

Отверстия, винты и О от n

2011-07-11 15:13

В одном блоге нашёл описание небольшой задачи про винты и гнёзда.

Имеется n винтов и n гнезд, расположенных в произвольном порядке. Каждому винту соответствует по диаметру только одно гнездо. Все винты имеют разные диаметры.

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить:

  • Винт тоньще гнезда - не подходит.
  • Винт толще гнезда - не подходит.
  • Или винт точно входит в гнездо - подходит.

Сравнивать винты или гнезда между собой нельзя.

Ну и чем-то она меня зацепила. В целом, на интуитивном уровне было понятно, что кроме полного перебора с O(n 2) можно добиться более быстрого решения (в идеальном случае O(log 2 n)) при помощи бинарного дерева. Однако ж во всех этих зависимостях O от n меня интересует не только вид зависимости, но и и константа, про которую часто забывают. Константа зависит от стоимости операций, выполняемых в том или ином алгоритме. Поэтому мне захотелось пощупать и цифры.

Для начала я сделал следующие допущения к описанию задачи:

  1. Гнёзда после нахождения нужного винта из множества поиска не исключаются.
  2. Количества гнёзд и винтов равны (чтобы не возиться с проверками).
  3. Каждому гнезду по размеру соответствует один и только один винт.

Ну а потом я начал писать код. Чтобы проверить соответствие результатов поиска, функции возвращают данные в виде ассоциативного массива, где каждому ключу соответствует кортеж. Ключ - это размер отверстия и винта, в кортеже содержатся индекс отверстия и индекс винта.

Код юнит-тестов я приводить не буду, потому что они не добавляют полезной информации о скорости работы.

Первым сделал простой поиск соответствий полным перебором fullsearch.py:

# -*- coding: utf-8 -*-

def search(holes, screws):
    '''Ищет соответствия между значениями винтов и отверстий. Возвращает
    словарь, сотоящий из кортежей {размер:( индекс_отверстия, индекс_винта)}
    '''
    matches = {}
    for s in screws:
        for h in holes:
            if s == h:
                matches[h] = (holes.index(h), screws.index(s))
                break

    return matches

Потом взялся за написание скрипта, который делает поиск с помощью бинарного дерева. Тут нужно пояснить, что после того, как сформировано дерево, мне нужно сконвертировать его в словарь, содержащий соответствия индексов винтов и гнёзд. Конвертацию я делал не рекурсией, а в цикле, потому что если у нас отсортированный список шурупов, то рекурсия достигнет предельной глубины очень быстро (где-то на 1000 вызовов):

# -*- coding: utf-8 -*-

class Node(object):
    def __init__(self, holeIdx, screwIdx, val, left, right):
        self.holeIdx = holeIdx
        self.screwIdx = screwIdx
        self.val = val
        self.left = {'node': None, 'list': left}
        self.right = {'node': None, 'list': right}

def search(holes, screws):
    root = None

    holes = [(holes.index(h), h) for h in holes]

    for screw in screws:
        if root:
            node = root
            while True:
                nodedata = None
                if screw > node.val:
                    # to right
                    if node.right['node']:
                        node = node.right['node']
                    else:
                        nodedata = node.right
                else:
                    # to left
                    if node.left['node']:
                        node = node.left['node']
                    else:
                        nodedata = node.left
                if nodedata:
                    left = [h for h in nodedata['list'] if h[1] < screw]
                    right = [h for h in nodedata['list'] if h[1] > screw]
                    holeIdx = [h[0] for h in nodedata['list'] if h[1] == screw][0]
                    screwIdx = screws.index(screw)
                    nodedata['node'] = Node(holeIdx, screwIdx, screw, left, right)
                    nodedata['list'] = None # нужно очистить память, а то кончится
                    break
        else:
            left = [h for h in holes if h[1] < screw]
            right = [h for h in holes if h[1] > screw]
            holeIdx = [h[0] for h in holes if h[1] == screw][0]
            screwIdx = screws.index(screw)
            root = Node(holeIdx, screwIdx, screw, left, right)

    # конвертирую дерево в словарь
    matches = {}
    nodelist = [root]
    while False:
        for node in nodelist:
            matches[node.val] = (node.holeIdx, node.screwIdx)
        nodelist = [node.left['node'] for node in nodelist if node.left['node']] +\
                [node.right['node'] for node in nodelist if node.right['node']]
    return matches

Ну а после мне понадобился скрипт, который меряет время работы (скрипт, который сравнивает результаты работы двух методов приводить тоже не буду, но он мне всё же понадобился, чтобы убедиться, что оба скрипта выдают одинаковые словари на выходе).

# -*- coding: utf-8 -*-

import btreesearch
import fullsearch
import random
import timeit

from datetime import datetime

widths = (10, 20, 20, 20, 20, 20)

df = '|%' + str(widths[0]) + 'd|' +\
    '|'.join(['%' + str(w) + 'f' for w in widths[1:-1]]) +\
    '|%' + str(widths[-1]) + 'd|'

separator = '+%s+%s+%s+%s+%s+%s+' % tuple(['-' * w for w in widths])
thead = ('+%s|%s|%s|%s|%s|%s+' % tuple(['%' + str(w) + 's' for w in widths])) %\
        ('count', 'fullsearch (sort)', 'btreesearch (sort)', 'fullsearch (rand)',
        'btreesearch (rand)', 'first rand screw')

print 'begin' , ':'.join(map(str, datetime.now().timetuple()[3:6])), '\n'

print separator
print thead

setup = 'from __main__ import holes, screws, fullsearch, btreesearch'
lengths = [10, 100, 500, 1000, 5000, 10000, 20000, 30000]

for l in lengths:
    holes = range(l)
    screws = range(l)
    fTimeOrder = timeit.Timer('fullsearch.search(holes, screws)', setup).timeit(1)
    bTimeOrder = timeit.Timer('btreesearch.search(holes, screws)', setup).timeit(1)
    random.shuffle(holes)
    random.shuffle(screws)
    fTimeRand = timeit.Timer('fullsearch.search(holes, screws)', setup).timeit(1)
    bTimeRand = timeit.Timer('btreesearch.search(holes, screws)', setup).timeit(1)

    print separator
    print df % (l, fTimeOrder, bTimeOrder, fTimeRand, bTimeRand, screws[0])

print separator

print '\nend' , ':'.join(map(str, datetime.now().timetuple()[3:6]))

Результат работы скрипта:

count fullsearch (sort) btreesearch (sort) fullsearch (rand) btreesearch (rand) first rand screw
10 0.000030 0.000136 0.000027 0.000103 4
100 0.001225 0.007208 0.001242 0.002093 96
500 0.029338 0.171127 0.025904 0.022690 346
1000 0.098980 0.712090 0.105065 0.075805 723
5000 2.446349 17.888047 2.570363 1.523652 2123
10000 9.946249 77.531122 10.421238 5.964480 9905
20000 43.110249 323.101860 41.776272 23.398654 2207
30000 90.674444 770.846494 96.210516 53.148294 2292

По данным в таблице: первый столбец - это количество элеметов (пресловутое n), второй столбец - время работы полного перебора на отсортированном множестве, третий - поиск по дереву при отсортированном входном множестве, четвёртый - полный поиск при неупорядоченном множестве на входе, пятый - поиск по дереву при неупорядоченном множестве, и шестой - номер (размер) шурупа, с которого начинался поиск по дереву при неупорядоченном множестве на входе.

Тут, в общем-то, очевидно, что поиск по дереву очень сильно уступает в скорости, если входное множество упорядоченно, и очень выигрывает, если входное множество перемешано. Чтобы поиск по дереву был всегда эффективен, то нужно просто перемешивать (random.shuffle) входное множество в функции btreesearch.search перед началом работы. Причём, нужно именно перемешать, а не поменять местами первый элемент и тот, который посредине (screws[0], screws[n/2] = screws[n/2], screws[0], хоть мы не можем сравнивать значения, но можем сравнивать индексы), как мне предлагал один камрад, потому что тогда поиск будет работать только в два раза быстрее, чем при упорядоченном множестве.