списки и кортежи

Вот не могу понять, зачем Питону - языку с динамической типизацией нужны одновременно и списки и кортежи? Ведь основное различие между ними это то, что списки представляют гомомогенное множество, а кортежи - гетерогенное. К тому же часто бывает, что кортежи в отличии от списков иммутабельны.
В питоне же, что списки, что кортежи являются гетерогенными множествами, которые к тому же можно динамически изменять.
Зачем вводить лишние сущности? Может их того... бритвой товарища Оккама?

Linux комментарии

Тема конечно не новая, но просто стало интересно. Ввёл вот эту комманду в директории с исходниками линукса
grep fuck -Rn ./*

вот результат её

./arch/mips/kernel/irixelf.c:795:#if 0 /* XXX No fucking way dude... */
./arch/mips/kernel/irixioctl.c:2: * irixioctl.c: A fucking mess...
./arch/mips/pci/ops-bridge.c:43: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:63: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:72: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/pci/ops-bridge.c:105: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:126: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:135: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/pci/ops-bridge.c:176: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:200: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:207: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/pci/ops-bridge.c:244: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:268: * IOC3 is fucked fucked beyond believe ... Don't even give the
./arch/mips/pci/ops-bridge.c:275: * IOC3 is fucked fucked beyond believe ... Don't try to access
./arch/mips/sgi-ip22/ip22-setup.c:44: * fucking with the memory controller because it needs to know the
./arch/ppc/syslib/ppc405_pci.c:71: * the kernel try to remap our BAR #1 and fuck up bus
./arch/sparc/kernel/process.c:582: /* fuck me plenty */
./arch/sparc/kernel/sunos_ioctl.c:62: /* Binary compatibility is good American knowhow fuckin' up. */
./arch/x86/kernel/cpu/cpufreq/powernow-k7.c:577: * Some Athlon laptops have really fucked PST tables.
./arch/x86/kernel/cpu/mtrr/generic.c:141:/* Some BIOS's are fucked and don't set all MTRRs the same! */
./Documentation/DocBook/kernel-locking.tmpl:1408: If you don't see why, please stay the fuck away from my code.
./drivers/ide/pci/cmd640.c:16: * These chips are basically fucked by design, and getting this driver
./drivers/media/video/bt819.c:204: BUG? Why does turning the chroma comb on fuck up color?
./drivers/mtd/mtd_blkdevs.c:351: registered, to prevent the link/init ordering from fucking
./drivers/net/sunhme.c:1000:/* Only Sun can take such nice parts and fuck up the programming interface
./drivers/net/sunhme.c:2077: /* This card is _fucking_ hot... */
./drivers/scsi/NCR53C9x.c:1771: * how bad the target and/or ESP fucks things up.
./drivers/scsi/NCR53C9x.c:2691: /* Be careful, we could really get fucked during synchronous
./drivers/scsi/qlogicpti.h:64:/* Am I fucking pedantic or what? */
./drivers/watchdog/shwdt.c:116: * brain-damage, it's managed to fuck things up one step further..
./include/asm-cris/arch-v32/spinlock.h:109: * writers) in interrupt handlers someone fucked up and we'd dead-lock
./include/asm-m68k/sun3ints.h:30:/* master list of VME vectors -- don't fuck with this */
./include/asm-sparc64/system.h:195: /* If you fuck with this, update ret_from_syscall code too. */ \
./include/linux/netfilter/xt_limit.h:18: /* Ugly, ugly fucker. */
./lib/vsprintf.c:9: * Wirzenius wrote this portably, Torvalds fucked it up :-)
./net/ipv4/netfilter/nf_nat_snmp_basic.c:1015: * (And this is the fucking 'basic' method).
./net/netfilter/nf_queue.c:158: /* James M doesn't say fuck enough. */
./sound/oss/opl3.c:833: * What the fuck is going on here? We leave junk in the beginning

Линукс всё же народная ось :)

полезные инструменты

Оказалось, мне тут передали эстафету в одном интересном флешмобе. Чтож, придётся поучаствовать.

1. Yakuake. Очень удобная консоль, которая выезжает сверху как в продвинутых играх. Позволяет экономить место и время на мелких операциях в консоли. Но если нужно что-то сложное делать, типа подебажить в gdb, то предпочитаю полноэкранную konsole, благо у меня два монитора и я могу себе это позволить.

2. Subversion. Система контроля версий нужна не только команде разработчиков, но и одному человеку. Можно смело удалять большие куски кода и вносить значительные изменения, не волнуясь, что что-то сломаешь. Ведь всегда можно посмотреть на то, что было раньше. Также удобно использовать эту систему не только для своих больших проектов, но и для мелких наработок, вроде полезных скриптов, документации, тестов, демок и т.д.
Так как база данных SVN легко бекапится, то легко обеспечить сохранность всей своей интеллектуальной собственности, не боясь что твой хард диск полетит. Можно перенести все свои наработки на другую машину\платформу. Или выложить на сервер и иметь доступ к ним с любого другого места.

3. locate. Индексирует файловую систему и позволяет осуществлять быстрый поиск файлов в своей базе данных. Это очень удобно. В среднем на моих 500+ гигабайтах дискового пространства поиск конкретного файла занимает менее 1 секунды. Раньше пользовался для этих целей утилитой find, но locate позволяет сократить время на несколько порядков. Ну и find всё-таки довольно сложная утилита. Для простого поиска файла по имени надо написать find / -name 'blabla', куда лаконичнее писать locate 'blabla'

4. vixie-cron. Как я жил без шедулера раньше - не представляю. Теперь мой компьютер делает 80% рутинных действий за меня. Он и создаёт бекапы SVN репозитория с записью на болванки раз в 2 недели, и индексирует базу для locate каждый день в 12 часов ночи, и синхронизирует portage для gentoo каждое воскресенье. Вообщем, если у вас есть какой-то набор действий, которые вам надо повторять периодечески, лучше их прописать в крон и тем самым сэкономить своё время и силы.

5. gVim. vim, как оказалось, очень мощный и удобный редактор. Да, порог вхождения в него весьма высок. Сначала надо читать туториалы и мануалы, запоминать многочисленные клавиатурные комбинации. Но зато потом эффективность работы с текстом повышается на порядки. После vim`а работать в Microsoft Visual Studio это всё равно, что рубить деревья топором, после того, как ты это делал бензопилой.

6. bash, find, grep, sed, wget, etc. жизнь свою без этого уже не представляю. unix way работы с системой очень удобен и комфортен, особенно для программиста. Вместо того, что бы тыкать мышкой в ограниченное по функциональности гуи, я просто пишу то, что мне надо сделать и система это делает.

Шрифты

Наткнулся на очень интересную статью Максима Шемарёва, автора замечательной библиотеки двухмерной растеризации antigrain.

В ней автор раскрывает вопросы различия субпиксельной растеризации шрифтов у MS, Apple и под линуксом.

Выводы неутешительные.
MS использует очень грубый метод растеризации. Они отказываются от субпиксельной точности и с помощью агрессивного хинтинга вбивают символы в жёсткие границы пикселей. В результате шрифты очень чёткие, но эта чёткость даётся ценой отказа от масштабируемости. В результате все приложения под MS хорошо выглядят лишь при одном DPI - 96. Если у нас монитор имеет больший DPI, например 300. То мы не сможем смасштабировать весь интерфейс под него и придётся ломать глаза на очень маленьких элементах интерфейса и шрифтах.

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

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

Под линуксом шрифты выглядят ужасно. Это не секрет. Во всём виноват опять же хинтинг. Причём проприетарный хинтинг основанный на TT байтовом интерпретаторе.
Но библиотека freetype позволяет достичь качественного и корректного рендеринга шрифтов, даже без использования патентованных технологий. Как это сделать, описывается в статье.

Хотелось бы всё же, что бы MS встали на путь истинный и начали бы поддерживать нормальную масштабируемость шрифтов и элементов GUI. Но в висте пока этого нет
Если пипл хавает помои, то зачем его кормить деликатесами? Стандартный подход монополиста.

MotionX приготовление к релизу.

Вообщем написание библиотеки MotionX на текущий момент закончено. Проект на sf.net зарегистрирован. В ближайшие выходные буду комментировать интерфейсы в формате doxygen и генерировать документацию. Настрою системы сборки, к текущей Scons добавлю CMake. Проведу серию тестов, что бы выявить стабильность системы, утечки памяти и прочие ошибки. И если всё будет благополучно, то выложу первый релиз на sf.net.

Кстати, оказалось, что xmmintrin.h это не только MS-specific, оно есть и под GCC на x86 платформе. А значит и под линуксом библиотека сможет использовать SSE.

Я вчера запустил анимацию 50 персонажей, с 50-ти костями на каждом. С SSE фпс было в районе 700, а без SSE - 30.
То есть SSE даёт, в моём случае, более чем двадцати кратное увеличение производительности! Я сам такого не ожидал.
Так что польза от этой технологии иногда может быть весьма ощутимой.
Хотя отключить применение SSE всегда можно флагами компиляции.

рефакторинг в motionx

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

Было:

template<>
    motionx::FrameSetCPtr   Create<motionx::FrameSet>(const std::string& file)
    {
        motionx::FrameSetPtr    anim(new motionx::FrameSet);
        std::ifstream   in;
        in.open(file.c_str(), std::ios_base::in | std::ios_base::binary);

        if (io::get<int>(in) != anim_file_magic_number)
            throw   motionx::bad_resource("Wrong file type.", file);
        if (io::get<int>(in) != anim_file_version)
            throw   motionx::bad_resource("Wrong file version.", file);

        int frames_count = io::get<int>(in);
        int frame_size   = io::get<int>(in);

        for (int i = 0; i < frames_count; ++i)
        {
            float   time = io::get<float>(in);
            motionx::Frame  frame;
            frame.resize(frame_size);
            frame.Pivot = io::get<mtl::rigid_tm>(in);
            std::generate(frame.begin(), frame.end(), boost::bind(io::get<mtl::rigid_tm>, boost::ref(in)));
            anim->AddFrame(frame, time);
        }

        return  anim;
    }Syhi-подсветка кода

Стало:

Animation*  LoadBinaryAnimation(MotionXLib* lib, const char* filename)
    {           
        IFileSystem*   fs = lib->FileSystem();
        AutoFileHandle f = (fs->Open(filename, "r+b"), fs);
        if (!f)
        {
            OnError(IOError(filename));
            return;
        }

        size_t  fileSize = fs->Size(f);
        int magicNumber = 0;
        int version     = 0;
        fs->Read(f, (char*)&magicNumber, 4);
        fs->Read(f, (char*)&version, 4);

        if (magicNumber != anim_file_magic_number || version != anim_file_version)
        {
            OnError(BadResource(filename));
            return;
        }

        InplaceAnimation* animData = AllocateMemory(fileSize - 8);
        fs->Read(f, animData, fileSize - 8);
        return new Animation(animData);
    }Syhi-подсветка кода

В результате вместо N+1 аллокаций памяти на один файл анимации, получил всего лишь 2.
Где N - количество кадров. Учитывая то, что анимации могут занимать весьма ощутимое количество памяти, это неплохой выигрышь. Причём тут куда важнее не скорость загрузки, хотя и она сильно возрасла, а то, что память меньше фрагментируется таким образом.

топологическая сортировка

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

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

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

Допустим есть следующие модули: filesystem, logging, render, audio, scene manager, game

filesystem не зависит ни от какого модуля
logging зависит от filesystem
render -> filesystem, logging
audio -> filesystem, logging
scene manager -> filesystem, logging, render, audio
game -> scene manager, filesystem, logging

Тут мы имеем сложный граф зависимостей. Который не является деревом. Этот граф надо преобразовать в список, проходя по которому можно будет последовательно запустить или остановить модули.
Например вот такой: filesystem -> logging -> audio -> render -> scene manager -> game
Хотя различных списков может быть много.
Также надо как-то проверять наличие циклов в графе зависимостей, иначе построить такой список будет невозможно.

Вообщем, я уже почти сам построил нужный алгоритм, как нашёл у себя в сундуке древний манускрипт, называется он "C++ Boost Graph Library", открыв его я узнал, что моя проблема является довольно тривиальной и очень общей. Мне просто надо пройти граф зависимостей по алгоритму depth first search, а построение списков зависимостей является, так называемой, топологической сортировкой. Ну в принципе я тоже самое и придумал, только не знал как называть.

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

#include    <iostream>
#include    <utility>
#include    <algorithm>
#include    <list>
#include    <vector>
#include    <boost/graph/vector_as_graph.hpp>
#include    <boost/graph/topological_sort.hpp>

using   namespace   boost;
int main()
{
    const char* modules[] = {
        "render",
        "filesystem",     
        "scene manager",
        "game",
        "audio",
        "physics"
    };
    const int nModules = sizeof(modules)/sizeof(char*);

    std::vector<std::list<int> >    modulesGraph(nModules);
    modulesGraph[0].push_back(1); // render -> filesystem

    modulesGraph[2].push_back(0); // scene manager -> render
    modulesGraph[2].push_back(1); // scene manager -> filesystem
    modulesGraph[2].push_back(4); // scene manager -> audio
    modulesGraph[2].push_back(5); // scene manager -> physics

    modulesGraph[3].push_back(2); // game -> scene manager
    modulesGraph[3].push_back(1); // game -> filesystem
    modulesGraph[3].push_back(0); // game -> render

    modulesGraph[4].push_back(1); // audio -> filesystem
    modulesGraph[5].push_back(1); // physics -> filesystem

    std::vector<int>    modulesOrder;
    topological_sort(modulesGraph, std::back_inserter(modulesOrder), vertex_index_map(identity_property_map()));

    for (std::vector<int>::iterator it = modulesOrder.begin(); it != modulesOrder.end(); ++it)
        std::cout << modules[*it] << std::endl;
    return  EXIT_SUCCESS;
}Syhi-подсветка кода

на выходе получим следующее:
filesystem
render
audio
physics
scene manager
game

XNE

Некоторое время назад решил собрать воедино все свои наработки и организовать их в виде рабочего игрового движка.

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

Проект будет кроссплатформенным, но без фанатизма. Пока ориентация только на POSIX и Windows. Графический API - OpenGL. Мультиапи не планируется.

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

Так же вплотную займусь организацией проекта. Документация, системы сборки, вспомогательные утилиты, code standart и т.д. Это у меня слабое место. Из-за отсутствии чёткой организации всё никак не могу выпустить свою анимационную библиотеку. Надо практиковаться в этом.

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

Проект будет c открытыми исходниками, лицензия, скорее всего, BSD или другая либеральная. А может быть и GPL. Я пока не определился окончательно.

Называется он XNE, расшифровывается как "XNE is Not Engine". Люблю акронимы :)

Ход разработки буду описывать тут, хотя может быть и заведу специальный блог.