Problem:list of elements, one is unique, others always in pairs, find unique
niedziela, 21 lutego 2021
środa, 19 czerwca 2013
naive graph coloring
Coloring nodes of a graph, simple and naive approach:
Usage is very simple:
and then use dot, neato or twopi for rendering.
Example gallery is here.
Usage is very simple:
python color.py nbNodes nbEdges dotFileName
and then use dot, neato or twopi for rendering.
Example gallery is here.
środa, 12 czerwca 2013
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...
:)
And here goes the humble code...
:)
środa, 5 czerwca 2013
python popcnt
popcnt - count bits set ("1") in a integer, of course using python
I've implemented only four ways to do this:
All function were run on 1000 samples made by 100 random numbers:
And now testing results:
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
175.885u 0.055s 2:56.35 99.7% 0+0k 0+0io 0pf+0w
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
75.853u 0.028s 1:16.03 99.7% 0+0k 0+0io 0pf+0w
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
42.828u 0.030s 0:42.93 99.8% 0+0k 0+0io 0pf+0w
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
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.
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...)
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
175.885u 0.055s 2:56.35 99.7% 0+0k 0+0io 0pf+0w
- BK way (much better!)
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
75.853u 0.028s 1:16.03 99.7% 0+0k 0+0io 0pf+0w
- look up table (niiiice!)
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
42.828u 0.030s 0:42.93 99.8% 0+0k 0+0io 0pf+0w
- ugly but pythonic (wut?)
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
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.
środa, 17 kwietnia 2013
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.
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
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.
poniedziałek, 25 marca 2013
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:
wtorek, 19 lutego 2013
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.
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.
środa, 6 lutego 2013
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!
poniedziałek, 8 października 2012
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.
poniedziałek, 1 października 2012
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).
środa, 26 września 2012
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:
środa, 8 sierpnia 2012
python traced class
With metaclass programming in python you can easily created a class tracing all updates to its attributes:
All objects using Traced metaclass are able to tell you which attributes have been changed. To get list of updated attributes (or keys when using TracedDict or indexes in case of TracedList) just call updated member function.
There is only one shortage: attributes defined and set inside __init__ (real instance attributes like instanceAttribute in TracedTest class) will be put into updated list when calling constructor. To avoid this behavior and trace changed during lifetime of object you need at call at ther very last line in constructor self.updated( reset = True ) (or uncomment last line in above example).
sobota, 14 lipca 2012
multiprocessing process pool again
Final implementation is quite different and much more smart:
And here is the source code:
wtorek, 24 stycznia 2012
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.
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.
piątek, 4 listopada 2011
Dear Python, can I create global variables in functions or methods?
Yeeee... no. Global variables in python are global on module level only. So, the answer is noooo... yes, you can.
Having a problem of a sub-process that has to execute just a callable (function, lambda or class with __call__ defined), and following DRY, I've put common functionality in base class and then created a set of children. As this code is part of much bigger project, DIRAC, where have to follow conventions and use everywhere a set of of global variables (references to services, clients, some global functions, etc.). Of course I was going to import them in a base class, but then what?
Globals are visible at the module level, so if I put them to base class, I would be able to use them in base class module (all functions and methods over there). But what I really want, was to use them in inherited classes to.
No problem, you can always store them as a member of base... Yuck! But then instead of just calling "gGlobalVar.doSomethingForMe()" I have to call it by "self.gGlobalVar.doSomethingForMe()". Awkward! Ugly! Bad!
What come to my mind is a python sequence for looking up symbols. There is always __builtins__ module, right? And this one is first in a line of r lookup, right? So what about storing them over there?
So here is an example:
Dear Python, if you knew how to cook and clean...
Having a problem of a sub-process that has to execute just a callable (function, lambda or class with __call__ defined), and following DRY, I've put common functionality in base class and then created a set of children. As this code is part of much bigger project, DIRAC, where have to follow conventions and use everywhere a set of of global variables (references to services, clients, some global functions, etc.). Of course I was going to import them in a base class, but then what?
Globals are visible at the module level, so if I put them to base class, I would be able to use them in base class module (all functions and methods over there). But what I really want, was to use them in inherited classes to.
No problem, you can always store them as a member of base... Yuck! But then instead of just calling "gGlobalVar.doSomethingForMe()" I have to call it by "self.gGlobalVar.doSomethingForMe()". Awkward! Ugly! Bad!
What come to my mind is a python sequence for looking up symbols. There is always __builtins__ module, right? And this one is first in a line of r lookup, right? So what about storing them over there?
So here is an example:
- let's say this is our module storing "globals", say testGlobals.py:
- and here is a base class, say testBase.py:
Notice, we can't put there anything outside baseClass, as it wouldn't be visible in inherited classes at all. I'm using built-in setattr or __builtins__.__setattr__, cause in pure python __builtins__ is visible as module, but when you import baseClass elsewhere, it would be just a dictionary. If you don't believe just execute this one:
once in interactive session:
and then in batch: - and here it is, a testChild.py
- at least some testing:
- and its output:
Dear Python, if you knew how to cook and clean...
czwartek, 7 października 2010
subversion checksum failed
Well, it happens occasionally that in process of committing changes to the repository some weird problem with bad checksum is reported and the whole commit is blocked:
Commit failed (details below):
svn: Checksum mismatch for '/home/userdir/devel/RTTWeb-etree-branch/cherry/sql/.svn/text-base/Job.py.svn-base', expected: '947e06aeba5bd534250ad1124e3f60d6', actual:' a226478ea1900a7aebdb3bb0cb2d42d1'
How to fix it and don't lost your precious changes? Two ways:
Now guess which way to choose and why I'm so smart now? ;)
Commit failed (details below):
svn: Checksum mismatch for '/home/userdir/devel/RTTWeb-etree-branch/cherry/sql/.svn/text-base/Job.py.svn-base', expected: '947e06aeba5bd534250ad1124e3f60d6', actual:' a226478ea1900a7aebdb3bb0cb2d42d1'
How to fix it and don't lost your precious changes? Two ways:
- VERY, VERY, VERRRY BAD:
- go to the .svn subdirectory, in above example /home/userdir/devel/RTTWeb-etree-branch/cherry/sql/.svn/
- add yourself write right to entries file and open it for editing
- now very curious find and replace 'actual' checksum with 'expected' one, but don't touch any other line/word/character in that file
- save & commit again
- go to the .svn subdirectory, in above example /home/userdir/devel/RTTWeb-etree-branch/cherry/sql/.svn/
- SAFE, CORRECT & ONLY WAY:
- make a copy of working copy somewhere:
cp -R /home/userdir/devel/RTTWeb-etree-branch/cherry/sql /home/userdir/backup - remove wrong file from working copy:
rm /home/userdir/devel/RTTWeb-etree-branch/cherry/sql/Job.py - update working copy from server:
svn up - copy back 'wrong checksum' file to working copy:
cp //home/userdir/backup/Job.py /home/userdir/devel/RTTWeb-etree-branch/cherry/sql - commit:
svn ci -m "recovered from checksum error"
- make a copy of working copy somewhere:
Now guess which way to choose and why I'm so smart now? ;)
czwartek, 23 września 2010
Compiz, whay not?
A few years ago my colleague had shown me Beryl window manager with all this super-duper spinning workspaces, 3D shaking transparent windows on rotating cubes. It sank deeply into my memory. I've tried several times to install it on MBP running Fedora, unfortunately w/o success. Up to now. This what I did:
installation
reboot to load new graphic adapter drivers
switch compiz on from top-level gnome menu "System -> Preferences -> Desktop Effects"
let is auotstart at boot "System->Preferences->Startup Applications->New" and put there:
and save
Ta-dam! It's there. It's 5 minutes job, everything works out of the box.
sudo yum install yum install mesa-dri-drivers-experimental xorg-x11-drv-nouveau \
compiz-fusion compiz-fusion-extras compiz-fusion-extras-gnome \
compizconfig-backend-gconf compizconfig-python \
emerald emerald-themes fusion-icon fusion-icon-qt \
libcompizconfig protobuf
Name: whatever, Fusion Icon
Application: fusion-icon --force
and save
Ta-dam! It's there. It's 5 minutes job, everything works out of the box.
środa, 30 czerwca 2010
Subversion server running on Fedora 13
Running subversion server using apache daemon should be an easy task, except you're security n00b like me.
- Installing required binaries:
sudo yum install subversion httpd mod_dav_svn - mod_dav_svn creates scratch configuration file subversion.conf for httpd daemon in
/etc/httpd/conf.d/. Unfortunately in this file there is a bug in comments dealing with new repository creation:
#
# Example configuration to enable HTTP access for a directory
# containing Subversion repositories, "/var/www/svn". Each repository
# must be both:
#
# a) readable and writable by the 'apache' user, and
#
# b) labelled with the 'http_sys_content_rw_t' context if using
# SELinux
#
#
# To create a new repository "http://localhost/repos/stuff" using
# this configuration, run as root:
#
# # cd /var/www/svn
# # svnadmin create stuff
# # chown -R apache.apache stuff
# # chcon -R -t http_sys_content_t stuff
Last line should rather set SELinux context to http_sys_content_rw_t:
chcon -R -t http_sys_content_rw_t stuff
But anyway let's set our httpd configuration to be:- path for all repositories /var/www/svn
- for apache authentication I choose the simplest one Basic with password file stored in /var/svn/passwd
- finally I choose to store global svn authorization file in /var/svn/svnauth
so using above presettings our subversion.conf would look like:
LoadModule dav_svn_module modules/mod_dav_svn.so
LoadModule authz_svn_module modules/mod_authz_svn.so
<Location /repos>
DAV svn
SVNParentPath /var/www/svn
AuthzSVNAccessFile /var/svn/svnauth
SSLRequireSSL
Order deny,allow
AuthType Basic
AuthName "Subversion repository"
AuthUserFile /var/svn/passwd
Require valid-user
</Location>
## logger for svn: /var/log/httpd/svn_log
CustomLog logs/svn_log "%t %u %{SVN-ACTION}e" env=SVN-ACTION - apache authentication file is of course produced using htpasswd command:
# for 1st user we're creating a file (-c) and choose MD5 encryption (-m)
sudo htpasswd -cm /var/svn/passwd cibak
New password: xxxxx
Retype new password: xxxxx
Adding password for user cibak
# all the others users only added with the same encryption
sudo htpasswd -m /var/svn/passwd jack
...
...
Once this file is ready we have to set correct SELinux policy:
sudo chcon -t httpd_sys_content_t /var/svn/passwd - creation of a new repository:
sudo svnadmin create /var/www/svn/myrepo
sudo chown -R apache:apache /var/www/svn/myrepo
sudo chcon -R -t http_sys_content_rw_t /var/www/svn/myrepo - creation of subversion authorization file /var/svn/svnauth in what ever you choose editor (I prefer emacs):
# cibak has read-write rights to the whole repository, jack could only read
[myrepo:/]
cibak = rw
jack = r
# but jack is able to write in his own directory
[myrepo:/jack]
jack = rw
Syntax of this file is better described in the Subversion bible.
Of course ones again we should remember to set correct SELinux policy context:
sudo chcon -t httpd_sys_content_t /var/svn/svnauth - restarting of httpd deamon is a last step to switch our repo on:
sudo /etc/init.d/./httpd restart
et voila, our repository is accessible under https://localhost/repos/myrepo URL.
Subskrybuj:
Posty (Atom)