Do it

Under such fitting phrase is hidden a make program implementation in python. DoIt enables to create building rules with the help of python script, therefore the dependencies have not to be hardly encoded. The change of dependencies is detected according the file md5 hash and not only by last modification time.

With the help of this framework I was able to approximately 5 times speed up our server start by creating production rules for cheetah templates compilation.

Sorting according local customs in python

In the previous week I played with sorting of strings according Czech language locale. I tried to sort records according the Czech collation in our Firebird 2.1 database, but I found no way how to do it for utf-8 charset (please share if you know how). Thus I decided to sort records on the application layer.

Python provides two modules for international sorting the locale and the PyICU both depend on installed system locales (on debian based systems look for dpkg-reconfigure locales). But locale module set the the locale setting for the whole system, instead of intel library PyICU, which can set a locale only for specific function. Because in our threaded web application can be used multiple locales together, the Python locale is no way.

PyICU is a only a thin SWIG generated wrapper above C++ library therefore it's interface is not very pythonic.

I use a function for a sorting key generation because custom comparative function for sort is not supported in Python 3.0 and above. Sorting through a sorting key is also much more efficient.

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

import PyICU

def getCollate(locale):
    def getCollationKey(s):
        s = PyICU.UnicodeString(s)
        k = icuCol.getCollationKey(s)
        return k.getByteArray()

    icuLoc = PyICU.Locale(locale)
    icuCol = PyICU.Collator.createInstance(icuLoc)
    return getCollationKey

names = [u'šárka', u'suzan', u'čech']
names.sort(key=getCollate('cs_CZ')
print names

In case of error, don't forget to check installed locales in your system.

A Python pitfall

Next day and a next error, actually in Python. And it is surprisingly close with the previous post about keyword arguments. Python as many other languages have default arguments, therefore it is possible to us default value of argument if no value for that argument is passed.

>>> def func(a=4):
>>>     print a
>>> func(1)
1
>>> func()
4

But these arguments are assign only first time as can be seen on the next example. The number values cannot be modified thus they are save from following effects.

>>> def func(a=[]):
>>>     a.append(1)
>>>     print a
>>> func()
[1]
>>> func()
[1, 1]
>>> func()
[1, 1, 1]

As you can see, the default value is assigned only for the first time and for next calls it is permanently reused. It can be dangerous if you are not aware of it. The following design pattern can be used to avoid this danger.

def func(a, b=None, c=None):
  if b is None:
      b = []
  if c is None:
      c = {}
  #the function body

The first few lines in the previous function will inicialize new empty values, which will be specific for the actual function call. When it is necessary to use more complicated default values which will be modified in function body, than these objects should be cloned immediate after function header.

It can be said that default argument values are variant of static variables for function and such property can be very surprising for many programmers.

A PHP pitfall (for a pythonist)

In python is quite natural to use keyword arguments in function calls, do not try that in PHP.
A header of PHP function function f1($a, $b, $c=3, $d=4) can lead to believe that it is allowed to address function arguments by theirs names in a function call. It is simply not true. What is worse, that following construction is in PHP in all ways correct.

f1($c=13, $d=14);

Because an assertion is an expression, the whole calling is semantic equivalent to:

$c=13
$d=14
f1(13, 14)

therefore f1 is called with $a=13, $b=14, $c=3, $d=4

Kolize a správná krajtí cesta

V rámci semináře v C++, jsem chtěl probrat algoritmus na zjišťování kolizí N stejně orientovaných kvádrů v lepším než v kvadratickém čase. Algoritmus v základu pracuje s tím, že promítne kvádry do jedné osy, zjistí jaké kvádry se promítají v jedné ose na sebe a dále řeší obdobným způsobem už jen kolizi mezi nimi. Tedy vezme ty co se promítnou na sebe a promítne je zas do jiné osy, zas rozdělí.. a ty které kolidují ve všech průmětech se protínají. Nejhorší čas O(N²), nejlepší O(N) a průměrný O(N.log(N)).

Zadání
Základem algoritmu je tedy umět vzít N intervalů a zjistit, které se překrývají. Vyzkoušel jsem různé postupy a podělím se s vámi o výsledky v pořadí od komplikovaných postupů po nejjednodušší.

Vzorky
Prvně si vygeneruji 100 náhodně rozmístěných intervalů mezi 0 a 1000, délky 10

import random

nsamples = 100
#list of (start position, length, name)
samples = [(random.randint(0,990), 10, i) for i in xrange(nsamples)]

Algoritmy založené na vkládání
Hlavní myšlenkou je rozdělit si intervaly pomocí binárního stromu a testovat kam vložit nový interval. V podstatě se jedná o 3 implementace binárního stromu. Ovšem pro usnadnění testování jsem si vytvořil pomocnou třídu interval.

class Interval:
  def __init__(self, lower, upper):
      self.upper = upper
      self.lower = lower
    
  def union(self, interval):
      '''
      self := self union interval
      '''
      self.lower = min(self.lower, interval.lower)
      self.upper = max(self.upper, interval.upper)
    
  def __cmp__(self, interval):
      if self.upper <= interval.lower:
          return -1
      elif self.lower >= interval.upper:
          return 1
      else:
          return 0

Všechny implementace binárního stromu se budou používat stejně.

tree = BTreeCluster()
for s, e, i in samples:
  tree.append(s, e, i)
tree.write()

1. Implementace
První implementace je jen jednoduše napsaný binární strom, který si vytvoří pod-uzly až teprve po přidání prvního prvku. Tento přístup bude paměťově nejnáročnější. Zato implementace v C++ by byla poměrně přímočará.

class BTreeCluster1:
   '''
   classical Binary tree with interval and intersecting objects in each node
   '''
   def __init__(self):
       #lazy inicialization
       self.left = None
       self.right = None
       self.inter = 0
       self.group = []
      
   def append(self, pos, lenght, name):
       if not self.group:
           self.group = [name]
           self.inter = Interval(pos, pos+lenght)
           self.left = BTreeCluster1()
           self.right = BTreeCluster1()
       else:
           inter = Interval(pos, pos+lenght)
           if self.inter == inter:
               self.group.append(name)
               self.inter.union(inter)
           elif self.inter > inter:
               self.right.append(pos, lenght, name)
           else:
               self.left.append(pos, lenght, name)
      
   def write(self):
       if self.left:
           self.left.write()
       if len(self.group) > 2:
           print 'collision', self.group
       if self.right:
           self.right.write()

2. Implementace
Druhá implementace se snaží více šetřit pamětí a přiřazuje uzlům indexy. Uzel s indexem n má pod-uzly 2n a 2n+1. Protože intervaly mohou do funkce přijít třeba seřazené a vzniklý strom může být značně nevyvážený používám na uložení uzlů hash tabulku (slovník) s indexy na místě klíčů. Protože ve standardní knihovně C++ není implementace hash tabulky, bylo by přepsání složitější. Stejně jako v prvním případě by bylo vhodné občas strom vyvážit, ale pro jednoduchost a lenost to vynechám.

class BTreeCluster2:
   '''
   Binary tree with interval and intersecting objects in each node
   encoded in dictionary (hash table)
   node number i has subnodes 2i, 2i+1
   hash table saves memory even for unballanced tree
   '''
   def __init__(self):
       self.groups = {} #number:interval, group
      
   def append(self, pos, lenght, name):
       inter = Interval(pos, pos+lenght)
       index = 1
       while True:
           if index not in self.groups:
               self.groups[index] = Interval(pos, pos+lenght), [name]               
               return
           iinter, igroup = self.groups[index]
           if inter == iinter:
               igroup.append(name)
               iinter.union(inter)
               return
           elif inter > iinter:
               index = 2*index + 1
           else:
               index = 2*index
      
   def write(self):
       for i,g in self.groups.values():
           if len(g) > 2:
               print 'collision', g

3. Implementace
Narozdíl od prvních dvou jsem se rozhodl strom přerovnávat v průběhu přidávání (halda by byla účinnější). Uzly jsou uloženy v poli srovnaném podle pozice intervalu a pole je prohledáváno pomocí půlení intervalu.

class BTreeCluster3:
   '''
   Binary tree with interval and intersecting objects in each node
   encoded in sorted array of disjunctive intervals
   sorted is archieved by inserting new nodes to right position   
   '''
   def __init__(self):
       self.groups = [] #number:interval, group
      
   def append(self, pos, lenght, name):
       '''
       finding the right position is archieved by iterative interval dividing
       '''
       inter = Interval(pos, pos+lenght)
       if not self.groups:
           self.groups = [(inter, [name])]
           return       
       upper = len(self.groups)-1
       lower = 0
       while True:
           ##print lower, upper
           index = (upper + lower) / 2
           iinter, igroup = self.groups[index]           
           if inter == iinter:
               #exteding existing one
               igroup.append(name)
               iinter.union(inter)
               return
           elif inter > iinter:
               if lower == upper or index == upper:
                   self.groups.insert(index+1, (inter, [name]))
                   print 'including after'
                   return
               lower = index + 1
           else:
               if lower == upper or index == lower:
                   self.groups.insert(index, (inter, [name]))
                   print 'including before'
                   return   
               upper = index - 1
                      
   def write(self):
       for i,g in self.groups:
           if len(g) > 2:
               print 'collision', g

Všechny tyto implementace jsou poměrně rozsáhlé, ale umožňují přidání nového prvku kdykoliv v průběhu programu. Následující postup je jednodušší, ale danou věc neumožňuje. Místo prvních 3 pokusů by možná stálo za to implementovat haldu.

Postupy založené na syntaktickém analyzátoru
Pokud intervaly seřadíme podle počátku lze je sekvenčně procházet, jednoduše testovat kolize a vracet intervaly, které se protínají. Je potřeba si však poradit s tím, kdy začít novou skupinu a také s přečtením posledního prvku.

1. Implementace
Je napsána jednoduše a jistě by šla snadno převést do C++, speciálně při využití knihovny <sort>.

EOF = 'EOF'

def readgroup(token, it):
   '''
   c-like parsing function
   returns last read token and group of intersecting intervals
   '''
   s, e, i = token
   end = s + e
   group = [i]
   for token in it:
       s, e, i = token
       if end <= s:
           return token, group
       else:
           group.append(i)
           end = s + e
   return EOF, group
  
samples.sort()
it = iter(samples)
token = it.next()
while token != EOF:
   token, g = readgroup(token, it)
   if len(g) > 1:
        print 'collision', g

Implementace nepočítá s prázdným vstupním seznamem. Po načtení posledního prvku signalizuje konec speciálním tokenem EOF. Protože se v průběhu funkce readgroup vrací vygenerované skupiny je potřeba vracet i naposledy přečtený token a navázat ve zpracování funkce ve stejném místě. Pokud by funkce vracela seznam seznamů, tak by její implementace byla jednodušší ale paměťově náročnější. Realizace výpisu přímo při nalezení kolize by funkci zjednodušila. Cílem však není výpis ale umožnit s nalezenými skupinami dále pracovat.

2. Implementace
Je první algoritmus přepsaný do Pythonu a využívající techniky generátorů.

def readgroup(samples):
   group = []
   for s, e, i in samples:
       if group and end <= s:
           yield group
           group = []
       group.append(i)
       end = s + e
   yield group
      
samples.sort()
for g in readgroup(samples):
   if len(g) > 1:
        print 'collision', g

Závěr
Možná se zdá, že jsem mohl napsat jen poslední příspěvek. Chtěl jsem však ukázat, jak v závislosti na požadavcích, použitých konstruktech jazyka a přijaté abstrakci lze vytvořit různé implementace, které se liší v rychlosti, použité paměti a délce zdrojového kódu. Předpokládám, že nejsnadněji by v C++ šla vytvořit předposlední implementace. A jaký je Váš názor?

Efektivní převední textu do HTML

Mnohdy je potřeba převést existující text z Microsoft Wordu, OpenOffice nebo jen neformátovaný text do HTML (např. i pro tento blog). K tomu nám může pomoci wiki.

Syntaxe HTML je jednoduchá obsahuje hodně sémantických značek a však na přímé psaní textu je trošku rozvleklá. Přenechme ji proto strojům a pišme pomocí přehlednějších značek.

Stejně tak pokud převádíte bohatě formátovaný text třeba z Microsoft Wordu nebo OpenOffice do HTML, tak narazíte na to, že tyto programy vytváří HTML zanesené co nejvíce tagy tak, aby byla zachováno stylování textu. Takto vytvořený HTML soubor je nepřehledný k editaci i stylování pomocí CSS a také několikrát větší než je nutné.

I pokud píšete příspěvek do blogu, může být výhodnější použít váš oblíbený editor textu a vytvořit prostý text, který teprve později převést do HTML.

Problém jak stylovat text, jiným způsobem než HTML již je několikrát řešen. Příkladem mohou být značky použitelné ve fóru phpBB . Jiným řešením jsou značkovací jazyky wiki. Pomocí jednoho z nich lze například editovat příspěvky na wikipedii . Jedním z takových to jazyků je i Textile, pomocí kterého vytvářím tento příspěvek.

Pomocí tohoto jazyka snadno zformátujete stránku a vytvoříte validní HTML, které vloíte do svého blogu nebo do stránky kterou vytváříte. Vytvořené HTML není problém ostylovat pomocí kaskádových stylů.

Pozn: Pokud chcete umožnit vkládání podobně formátovaných příspěvků uživatelům na svém webu, existují knihovny, které vám to umožní např. RedCloth.