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.

Revert words in a sentence.

Revert words in a sentence, so " The quick brown fox jumped over the lazy dog." becomes "dog. lazy the over jumped fox brown quick The" .

In C:

In C++:


In py:


52 > 27 > 4!