Problem:list of elements, one is unique, others always in pairs, find unique

 

 Handy itertools:

• powerset
• all sublist from list

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: