naive graph coloring

  Coloring nodes of a graph, simple and naive approach:


Usage is very simple:

python color.py  nbNodes nbEdges dotFileName

and then use dot, neato or twopi for rendering.

Example gallery is here.

don't pay taxes for CO2 emission, just plant more red black trees

Just for fun and making plots like that [small rbtrees gallery].

And here goes the humble code...




:)

python popcnt

popcnt - count bits set ("1") in a integer, of course using python

I've implemented only four ways to do this:

• using look up table 0..255 (no iterations, oen sum and a few shifting by 8 bits)
• naive (number of iterations ==  number of bits)
• Brian Kernighan way (number of iterations == number of bits set)
• pythonic by ugly (count "1"s after calling bin()...)

All function were run on 1000 samples made by 100 random numbers:



And now testing results:

• naive (Zzzzz...)

[Wed, 05 Jun 22:07 E0][cibak@localhost:~/popcnt]> time python testNaive.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
175.885u 0.055s 2:56.35 99.7%    0+0k 0+0io 0pf+0w

• BK way (much better!)

[Wed, 05 Jun 22:04 E0][cibak@localhost:~/popcnt]> time python testBK.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
75.853u 0.028s 1:16.03 99.7%    0+0k 0+0io 0pf+0w 

• look up table (niiiice!)

[Wed, 05 Jun 22:06 E0][cibak@localhost:~/popcnt]> time python testLUT.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
42.828u 0.030s 0:42.93 99.8%    0+0k 0+0io 0pf+0w 

• ugly but pythonic (wut?)

[Wed, 05 Jun 22:04 E1][cibak@localhost:~/popcnt]> time python testUgly.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
40.880u 0.040s 0:41.06 99.6%    0+0k 0+0io 0pf+0w


And guess what? Ugly (but pythonic) won! Coincidence? I don't think so... ;)

EDIT:
And of course I can completely remove lines with lambda and all this stuff within popcntLUT  and it could be coded just like that:



But it doesn't help to much.

Also one can check say 16 bits look up table, say:



 This should run at least 2 times faster that original popcntLUT.

 

one does not simply pickle a tree

Ahrrr... It took me 5 hours to figure it out.

Python multiprocessing.Queue is using internally shelve module, which again internally is using cPickle for speed up.  But if something cannot be pickled, when calling Queue.put, you will see some cryptic error message:


File "/opt/dirac/pro/Linux_x86_64_glibc-2.5/lib/python2.6/multiprocessing/queues.py", line 242, in _feed
-    send(obj)
TypeError: expected string or Unicode object, NoneType found

Ugh! Not helping at all, but what to do except start debugging? Taking the advantage of the opportunity I had fixed also some problems here and there (un-shelvable locks or instance methods in several classes), but at the very, very end  I've got this:

pickle.PicklingError: Can't pickle : it's not found as __main__.copyelement

 Huh? What the heck? Where is this one? Find and grep fellows stayed completely  muted, so I've started to dump symbols from *.so under PYTHONPATH, and guess what? I HAVE FOUND IT!

[volhcb13] /opt/dirac/pro > nm Linux_x86_64_glibc-2.5/lib/python2.6/lib-dynload/_elementtree.so | grep copyelement
0000000000209dd8 b elementtree_copyelement_obj



This little bastard was hiding in cElementTree! I've swapped this one with its  python twin (ElementTree). Taa-daam!  Queue.put is working again, not a big deal for me,  XML fragments I'm dealing with are rather small.

5 hours! Five! FIVE HOURS lost...

So, dear children, please remember: when going multiprocessing forget about cElementTree (and perhaps several other modules rewritten in C for speed up) and use pure python implementations.

nth permutation in a lexicographical order

Problem:

Somebody is generating permutations of a given list of elements in a lexicographical order. What is the value of say nth permutation?

Brute force solution is to generate them all, but in that case you'll spend quite a lot of time generating useless permutations - O(n!). So here is the easy way:

clogged pipe

What if? Say you want to execute something in a python sub-process and you want to read and resend all output data, no matter how big they are?

The simplest solution to use pipe is BAD idea - pipe has it's own buffer and what's worse size of this buffer is constant and cannot be changed by using some smart fnctl call any more. Let's run a simple test:



On my laptop I'm not able to send more than 64kB at a time, moreover its completely hanging:



Hmmm... So how can you send more than that? Let's say this way:



Use a simple manager, man! More info here.

There is also possibility  to use shared memory objects (read this), but those are rather for storing not so huge amount of data.

Disclaimer: Before use, read the contents of the package insert or consult your physician or pharmacist because each drug used improperly threatens your life or health.

python graph implementation

And now as I have promised in my previous post. it needs some more work, i.e. dumping to Graphviz format, but apart of that it is working quite well.

metaclass with dynamic creation of properties

Meteclass with dynamic properties creation: Written as helper class for my graph implementation (metaclass for nodes, edges and graph itself).

yet another Observer pattern in python

Observer sniffing a particular attribute from Observable class. This little spy is notified every time watched attribute is changing its value.

Observers are hold in weakref.WeakValueDictionary to avoid crashes in case they would disappear (i.e. being collected and deleted by gc). And here is the source code:

one type list in python

Handy list-like class holding only one type of items.

python multiprocessing handy template with callbacks

Here is a handy implementation of process pool I wrote a few days ago. All workers are created in pool and are running in daemonic mode, reading and executing ProcessTasks, which is made up using any python callable together with callback and exception callback definition.

The process pool is using two queues: first for tasks to be processed and second holding task results for callbacks. It could be executed in daemon mode too, processing results in a separate thread. Once you decide the job is done, you need to call ProcessPool::finalize (or ProcessPool::processAllResults), which is sending dummy assassins (in fact just a True value) to the workers (so they could return from their run method), terminating them once they are not alive any more and closing tasks and results queues. Blah, blah, blah... Code that was published below was kinda buggy. Error-free version can be found here.

SVN hooks once again, this time tags, branches, log messages etc.

This one hook I wrote quite long ago is forcing users of Subversion repository to:

• provide log message on every commit (class logChecker)
  
• block removing of "/tags", "/branches" and "/trunk" directories from repo (class pathChecker)
  
• forcing branch and tag naming convention
  
• making subdirectories under /tags read-only
  

My company is running Subversion for storing all software packages and our repo hasn't got the default structure (/tags, /trunk and /branches as a top directories) — instead of that every package has got it's own /trunk, /tags and /branches subdirectories. So the repository structure is something like this:

/Path/
      PackageA/
               trunk/ 
                     src/
                     doc/
               tags/ 
                    PackageA-00-00-00/ 
                                      src/
                                      doc/
                    ...
               branches/
                    PackageA-00-00-00-branch/ 
                                            src/
                                            doc/
                  
      PackageB/
               ...
/OtherPath/
           PackageC/
           ...                   

Looks rather complicated, but it isn't. ;)

Also we've got tags and branches naming convention. Every tag should be made of package name, then a three (or four for tags made over a branch) groups of digits, e.g.: PackageName-ii-jj-kk or PackageName-ii-jj-kk-ll.
Every branch name is very similar to tag name, except there is additional (-branch) string at the end.

So here is the hook itself:


If you want to use this one, you have to modify it a little:

• replace 'librarian' or/and 'root' account name with your own repository admin
  
• put repository admin mail to block messages - replace this fake 'librarian@mail' address
  
• change regexp ffor tags and branches to match your criteria
  
• put svn-policy.py script into your repository hook directory ($REPO/hooks)
  
• modify "$REPO/hooks/pre-commit" script to switch this one on
  

  
  #!/bin/sh
  REPOS="$1"
  TXN="$2"
  SVNPOLICY=/path/to/repo/hooks/svn-policy.py # modify this line
  #SVN policy
  $SVNPOLICY  -t "$TXN" "$REPOS" || exit 1
  # All checks passed, so allow the commit.
  exit 0
  

  
  

Maybe the code needs some cleaning and better structure but anyway happy using, comments and questions are welcome!

Cheers,
Krzysztof

eol once again

Here is another pre-commit hook I wrote for Subversion repositories. Let's assume many people (not always smart enough) accessing and committing to your Subversion repository. They don't know how to configure their svn client, but you want to be sure, that all text files have the same line endings (e.g. Unix = LF). So, to be sure that all line endings are consistent, you could run this hook, which blocks commit operation if svn:eol-style is not set to required one.

As always you should modify also your pre-commit file, usually stored in repo/hooks directory, e.g.:

And that's it! ;)