Go deh!

Wednesday, April 29, 2009

Fight for the community you want

Someone took offence at a puerile and sexist presentation given at what is supposed to be a technical event in the Rails community. Good on them. The community is what you make of it.

"Using sex to sell spanners" doesn't make me think they are good spanners.

- Paddy.

Tuesday, April 21, 2009

Monitoring a linux process as it reads files

I am processing 20 thousand files with some proprietary software and
needed to monitor how far it got in reading the files. In my own Python
version of the utility the reading of data was ten times faster than
the subsequent processing and i wanted to find out if this proprietary
solution, which was havinfg performance problems , was equally spending
most of its time reading data.

The proprietary program took a list of 20000 files to process as its
first argument and I remembered that on Linux, the /proc
directory had info on running processes and sure enough , the
/proc/<process id>/fd directory had info on all the file
descriptors currently open by the process as links. So by opening the
list of files to in my editor and searching within it for the file name
shown on one of the file descriptors, I could gauge how many
files been read so far.

I decided to automate the checking and wrote a shell script using
cat/fgrep/gawk/... that then told me what line in the list of files to
process the program was currently at.

Now I've had time to refine things to use mainly python but to
demonstrate its use I also have to generate a test environment

First create some test files to process

style="font-family: monospace;">bash$ style="font-weight: bold;">mkdir -p /tmp/test style="font-family: monospace;">
bash$ style="font-weight: bold;">for ((i=0; i < 100; i++))
do touch /tmp/test/file$i ;done style="font-family: monospace;">
bash$ style="font-weight: bold;">/bin/ls /tmp/test/file* >
/tmp/test/all_files.lst style="font-family: monospace;">
bash$ style="font-weight: bold;">head /tmp/test/all_files.lst style="font-family: monospace;">
/tmp/test/file0 style="font-family: monospace;">
/tmp/test/file1 style="font-family: monospace;">
/tmp/test/file10 style="font-family: monospace;">
/tmp/test/file11 style="font-family: monospace;">
/tmp/test/file12 style="font-family: monospace;">
/tmp/test/file13 style="font-family: monospace;">
/tmp/test/file14 style="font-family: monospace;">
/tmp/test/file15 style="font-family: monospace;">
/tmp/test/file16 style="font-family: monospace;">
/tmp/test/file17 style="font-family: monospace;">
bash$

Now lets create a test executable to monitor

This script just holds each file open for reading for twenty seconds
before closing the file.

style="font-family: monospace;">bash$ style="font-weight: bold;">python -c ' style="color: rgb(0, 0, 153);">import sys,time style="font-family: monospace; color: rgb(0, 0, 153);">
for
name in file(sys.argv[1]): style="font-family: monospace; color: rgb(0, 0, 153);">

f = file(name.strip()) style="font-family: monospace; color: rgb(0, 0, 153);">

time.sleep(45) style="font-family: monospace; color: rgb(0, 0, 153);">

f.close()

' style="font-weight: bold;">/tmp/test/all_files.lst
& style="font-family: monospace;">
[2] style="font-weight: bold;"> style="font-family: monospace; color: rgb(0, 0, 153);"> style="font-weight: bold; color: red;">7984 style="font-family: monospace;">
bash$

here is what the fd directory looks like

style="font-family: monospace;">bash$ ls -l /proc/ style="font-family: monospace; color: rgb(0, 0, 153);"> style="font-weight: bold; color: red;">7984 style="font-family: monospace;">/fd style="font-family: monospace;">
total 0 style="font-family: monospace;">
lrwxrwxrwx 1 HP
DV8025EA None 0 Apr 21 22:17 0 -> /dev/tty1 style="font-family: monospace;">
lrwxrwxrwx 1 HP
DV8025EA None 0 Apr 21 22:17 1 -> /dev/tty1 style="font-family: monospace;">
lrwxrwxrwx 1 HP
DV8025EA None 0 Apr 21 22:17 2 -> /dev/tty1 style="font-family: monospace;">
lrwxrwxrwx 1 HP
DV8025EA None 0 Apr 21 22:17 3 -> /tmp/test/all_files.lst style="font-family: monospace;">
lrwxrwxrwx 1 HP
DV8025EA None 0 Apr 21 22:17 4 -> /tmp/test/file0 style="font-family: monospace;">
bash$

And here is a python script to monitor that fd directories
link number 4 periodically

style="font-family: monospace;">bash$ style="font-weight: bold;">python -c ' style="color: rgb(0, 0, 153);">import sys,time,os,datetime style="color: rgb(0, 0, 153);">
name2index =
dict((name.strip(), index) for index,name in
enumerate(file(sys.argv[1]))) style="color: rgb(0, 0, 153);">
all = len(name2index) style="color: rgb(0, 0, 153);">
while True: style="color: rgb(0, 0, 153);">
path =
os.path.realpath("/proc/7984/fd/ style="font-weight: bold; color: red;">4").strip() style="color: rgb(0, 0, 153);">
print
name2index[path],"/",all, path, datetime.datetime.now().isoformat() style="color: rgb(0, 0, 153);">

time.sleep(30)

' /tmp/test/all_files.lst

22 / 100 /tmp/test/file29 2009-04-21T22:34:07.817750

23 / 100 /tmp/test/file3 2009-04-21T22:34:37.820750

24 / 100 /tmp/test/file30 2009-04-21T22:35:07.825750

24 / 100 /tmp/test/file30 2009-04-21T22:35:37.834750

I watched the monitor output over the next couple of hours and found
out when file reading ended and processing of read data started.

END.

Thursday, April 16, 2009

Bimap. Bi-directional mapping/dictionary for Python?

I had a chance encounter with the boost C++ library documentation and
came across a description of their href="http://cablemodem.fibertel.com.ar/mcape/boost/libs/bimap/index.html">bimap
(that is bimap without a 't') .

It seems to be a bi-directional mapping.

In a Python dict, keys map to values. In a bimap, values would also map
to keys. It seems they put keys/values on an equal footing by renaming
them as left and right members, and having methods that work on either
the right to left or the left to right mapping.

I had just re-visited a program of mine that dealt with what I would
consider large sets of values. I was mapping test names to test
coverage where their were tens of trhousands of test names, each of
~100 characters long and for each file, I had many thousands of code
coverage points, which themselves were strings of ~150 characters each.
I new I had to work with a dict mapping test_names to sets of covered
points for each test and do a lot of set arithmatic to rank the tests
in order of contribution to the overall coverage figure, so I decided
to use indices; replacing files by negative numbers and coverage points
by positive numbers. My program works, and is very fast but I note that
I create both a testname2index mapping dict and the inverse
index2testname mapping, (and coverpoint2index and index2coverpoint
mapping dicts).

What I had been constructing, unawares, was a bimap by using two dicts.

I then spent time googling for Python bimaps to no avail, (although I
think there are haskel and Java implementations out there - and Google
'helps' by sugesting you meant bitmap with a 't').

So my questions are:

Is their a Python bimap implementation out there?

Would anyone want one? (I already code around its
absense).

What would its methods be?

Methods

On my third question, I guess you could have all the normal methods of
a dict but preceeded by either
left_ or right_
with calling of a method without those prefixes raising an exception,
as it seems important to not favour one mapping direction over another.

This would give:

style="font-family: monospace; font-weight: bold; text-decoration: underline;">
DICT      BIMOD
(LEFT) BIMOD (RIGHT) style="font-family: monospace; font-weight: bold;">
style="font-family: monospace;">
clear
left_clear right_clear


copy
left_copy right_copy


fromkeys
left_fromkeys right_fromkeys style="font-family: monospace;">

get
left_get
right_get      style="font-family: monospace;">

has_key
left_has_key right_has_key style="font-family: monospace;">

items
left_items right_items

iteritems    left_iteritems
right_iteritems


iterkeys
left_iterkeys right_iterkeys style="font-family: monospace;">
itervalues
left_itervalues right_itervalues style="font-family: monospace;">

keys
left_keys right_keys


pop
left_pop
right_pop      style="font-family: monospace;">

popitem
left_popitem right_popitem style="font-family: monospace;">
setdefault
left_setdefault right_setdefault style="font-family: monospace;">

update
left_update right_update   style="font-family: monospace;">

values
left_values right_values

The above couldn't be extended for indexing however, unless you did
something like:

style="font-family: monospace;">bimod_instance.left[leftindex]
and bimod_instance..right[rightindex]

but then wouldn't it be better to use the dotted form for all the
methods and have:

style="font-family: monospace;">
bimod_instance.left.haskey # (with a dot after left), ...

I note that their are redundancies above, for example, left_clear ==
right_clear ...

Strewth, I've only scratched the surface :-)

- Paddy.

Friday, April 10, 2009

Knapsack solution by OO Calc

I had previously solved the href="http://www.rosettacode.org/wiki/Knapsack_Problem"
target="_blank">knapsack problem in Python. I came
across the Solver function of OpenOffice Calc and so tried to use it to
solve knapsack.

A quick recap of the problem

A traveller gets diverted and has to make an unscheduled stop
in
what turns out to be Shangri La. Opting to leave, he is allowed to take
as much as he likes of the following items, so long as it will fit in
his knapsack, and he can carry it.
He knows that he can carry no more than 25 'weights' in total; and that
the capacity of his knapsack is 0.25 'cubic lengths'.

Looking just above the bar codes on the items he finds their
weights and volumes. He digs out his recent copy of a financial paper
and gets the value of each item.

cellpadding="2" cellspacing="2">

nowrap="nowrap" valign="middle">Item	nowrap="nowrap" valign="middle">Explanation	nowrap="nowrap" valign="middle">Value (each)	nowrap="nowrap" valign="middle">weight	nowrap="nowrap" valign="middle">Volume (each)
panacea (vials of)	Incredible healing properties	3000	0.3	0.025
ichor (ampules of)	Vampires blood	1800	0.2	0.015
gold (bars)	Shiney shiney	2500	2.0	0.002
align="left" nowrap="nowrap" valign="middle">Knapsack	align="left" nowrap="nowrap" valign="middle">For the carrying of	align="left" nowrap="nowrap" valign="middle">-	align="left" nowrap="nowrap" valign="middle"><=25	align="left" nowrap="nowrap" valign="middle"><=0.25

He can only take whole units of any item,, but there is much
more of any item than he could ever carry

How many of each item does he take to maximise the
value of items he is carrying away with him?

Note:

There are four solutions that maximise the value taken.
Only one need be given.

OO Calc setup

I am using version 3.0.1. I opened a new spreadsheat and literally
cut-n-pasted the above table into the sheet. The solver needs to be
able to change some cells (the variables) that affect one cell
containing the value to optimise.. I added the table in blue, at the
right of the figure below to calculate the value, weight and
volume of what is in the knapsack based on the amount of each item
chosen, so you can change what is in the style="font-weight: bold;">Number column and
get new totals calculated in the Totals
row

style="width: 914px; height: 444px;"
alt="Knapsack problem formulae" title="(Showing cell formulae)"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjSTTwTk_nEMgY1qLVv_QXSamy1aaWjm-H73uDgKHNjbvVB0QeTQR-EVT5tCoZtaWPjmLw3RwEbFD5kBXUJ31NSYXgM-JeYFub6uyU1ZIjFKXj1e6ltYRnG3beA0o7jgjED6D3i/">

I show the formulae in the cells in the image above.

The Solver

Menu Tools-> Solver shows a form for filling in. from top to
bottom:

The target cell is the cell I want to maximise, which is
the total value of all items in cell H8

I want to Maximise.

I want to change the Number
of each item i.e. vary cells G4:G6

My limiting conditions are:

The weight is <= 25

The volume is <= 0.25

The Number of each item cannot be negative.

style="width: 455px; height: 373px;" alt="Solver Menu"
title="Solver menu"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_hFwnFTntRnmBiKs5Be81nQN6-LVoVgsi94Yl6FTgi1eM3a2IijSDPcmUOdjbh2ME_jNSpWqkScBW-9KHrl952p7MXhYT8lV_csPjRzeciF1i3Qij3K3m5JAgXQQF4by_bGoH/">

You also need to click the Solvers Options
button and ensure the options are set like this:

style="width: 431px; height: 286px;" alt="Solver Options"
title="Solver Options"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjYg4BmKl0Ye99EgQ7bGvj4D_xEkf-oUNIug2hvpp9PAmjsa048nuFPSSdtMsYysNvh98NAMMpphy7jWQHRZhXWHg8fgvcUY_iH2WnsDAc5cUITezPm93HXGvNmQpx1Fj99Gxk-/">

Ok the Options, then hit Solve on the Solver window and eventually you
will get the following result:

style="width: 914px; height: 444px;"
alt="Result of Knapsack constraints problem"
title="Result of Knapsack constraints problem"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoq_CC0HfR9EzsFU6E9dXcxmLk1zXhqZxkuu2tCe1DWK-_REuVKnTHBGO9KhzvQ-cIJfskAb24DzRT8bMv2Wb5lshQw7ec5YGT6IN4VEgvR8MlCZNBM0wRJDOAgXqzn-tSZu2J/">

The solver has correctly determined that carrying no panacea, fifteen
ampules of ichor, and eleven gold bars will maximise the value, subject
to the given constraints..

Comment

Their are actually other values that give the same total value under
the same constraints but I can't find an easy way for the solver to
give them all.

END.

Memoization and stack use.

I was caught out today when investigating how to apply memoization to
allow computation of larger values of a recursive function.

Mutual Recursion

I had thought up a new task for Rosetta Code called href="http://www.rosettacode.org/wiki/Mutual_Recursion">Mutual
Recursion, as I had remembered that some languages needed
at least the signature of a function to be defined before it
could be called, and so creating mutually recursive functions would
allow you to compare the languages in an interesting way - which is
what R.C. is all about.

For the example for implementation I used href="http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences"
target="_blank">Hoffstadters Female and Male
sequences, and produced the following href="http://www.rosettacode.org/wiki/Mutual_Recursion#Python">Python
definitions:

def  color="#008080">F(n): return 1  color="#804040">if n == 0  color="#804040">else n - M(F(n-1))
 color="#804040">def  color="#008080">M(n): return 0  color="#804040">if n == 0  color="#804040">else n - F(M(n-1))

It seems that other members of R.C. liked the task and soon added many
examples in other languages.

Apart from the computation of the series for 0<=n<20, I
did try to compute F(200) but it blew the stack so I went to bed and
decided to memoize the functions another day.

target="_blank">Wot, no memoize?

Memoization came very easily to mind, so I thought that Python would
have such available as a decorator waiting to be applied. No such luck,
I would have to craft my own . I did remember correctly however that
there was some helper function that made wrapped functions
look a lot more like what had been wrapped, and so used functools.wrap:

from functools  color="#a020f0">import wraps

 color="#804040">def  color="#008080">memoize0(func):
    ' color="#ff00ff"> Adds cache as attribute to wrapped function for ease of access'
     color="#a020f0">@wraps(func)
     color="#804040">def  color="#008080">wrapper(*args):
        argsl = tuple(args)
         color="#804040">if argsl  color="#804040">in wrapper._cache:
             color="#804040">return wrapper._cache[argsl]
         color="#804040">else:
             color="#804040">return wrapper._cache.setdefault(argsl, func(*args))
    wrapper._cache = dict()
     color="#804040">return wrapper

 color="#804040">def  color="#008080">memoize(func):
    ' color="#ff00ff"> Creates closure around locally created cache'
    cache = dict()
     color="#a020f0">@wraps(func)
     color="#804040">def  color="#008080">wrapper(*args):
        argsl = tuple(args)
         color="#804040">if argsl  color="#804040">in cache:
             color="#804040">return cache[argsl]
         color="#804040">else:
             color="#804040">return cache.setdefault(argsl, func(*args))
     color="#804040">return wrapper

I haven't got over my (probably infantile) lust for attaching
attributes to functions so justified memoize0 as it allows you to look
at the contents of the cache. Combined with the fact that you cannot do
a memoization decorator without applying it to a href="http://en.wikipedia.org/wiki/Fibonacci_function">Fibonacci
number function:

if __name__ == ' color="#ff00ff">__main__':
     color="#a020f0">@memoize0
     color="#804040">def  color="#008080">fib(n): return n  color="#804040">if n  color="#804040">in (0,1)  color="#804040">else fib(n - 1) + fib(n - 2)
     color="#a020f0">@memoize0
     color="#804040">def  color="#008080">fib2(n):  color="#804040">return n  color="#804040">if n  color="#804040">in (0,1)  color="#804040">else fib2(n - 1) + fib2(n - 2)
     color="#804040">assert fib._cache  color="#804040">is  color="#804040">not fib2._cache
    fib(50); fib2(50)
     color="#804040">assert fib._cache == fib2._cache  color="#804040">and (fib._cache  color="#804040">is  color="#804040">not fib2._cache)

It is important that caches are not shared for mutually recursive
functions.

A blown stack

I had initial success with the Male and Female sequence and was easily
able to compute F(200) with:


    @ color="#008080">memoize
     color="#804040">def  color="#008080">F(n):
        ' color="#ff00ff"> Hofstadters Female Male sequences'
         color="#804040">return 1  color="#804040">if n == 0  color="#804040">else n - M(F(n-1))

     color="#a020f0">@memoize
     color="#804040">def  color="#008080">M(n):
        ' color="#ff00ff"> Hofstadters Female Male sequences'
         color="#804040">return 0  color="#804040">if n == 0  color="#804040">else n - F(M(n-1))

     color="#804040">assert F(200) == 124

But I got cocky, as F(2000) ran out of stack.

A little thought made me realise that I only had a cached results for F
and M up to around 200 and so a call of F(2000) was going to eat up
huge amounts of stack before recursing down to cached values.

With that knowledge in mind I thought I might gradually jump to higher
values of n and, indeed, the following worked:

    print ([F(n)  color="#804040">for n  color="#804040">in range(0,20000+1,100)])

In real-world applicatrions, you might have to have some scheme to
reduce or limit cache size if memory rather than the stack becomes an
issue, and I have a great solution that I have just completed in the
margin :-)

- Paddy.

Thursday, April 02, 2009

(Ab)use of Pythons in-built data structures

I like to use Pythons in-built data structures quit a lot, and tend to
force myself to ask whether I should create my own classes,
which allows you to use meaningful names for fields and add
comments/docstrings to the datastructure but usually at the cost of
adding more lines of text.

After writing about Huffman codes and posting solutions to href="http://www.rosettacode.org/w/index.php?title=Huffman_codes&oldid=27804#Python">Rosetta
code and href="http://paddy3118.blogspot.com/2009/03/huffman-encoding-in-python.html">my
blog:

 29  color="#804040">def  color="#008080">codecreate(symbol2weights, tutor= False):
 color="#804040"> 30     ''' color="#ff00ff"> Huffman encode the given dict mapping symbols to weights '''
 color="#804040"> 31     global decode
 color="#804040"> 32 
 color="#804040"> 33     heap = [ [float(wt), [[sym, []]], repr(sym)]  color="#804040">for sym, wt  color="#804040">in symbol2weights.iteritems() ]
 color="#804040"> 34     heapify(heap)
 color="#804040"> 35     if tutor:  color="#804040">print " color="#ff00ff">ENCODING:", sorted(symbol2weights.iteritems())
 color="#804040"> 36     while len(heap) >1:
 color="#804040"> 37         lo = heappop(heap)
 color="#804040"> 38         hi = heappop(heap)
 color="#804040"> 39          color="#804040">if tutor:  color="#804040">print " color="#ff00ff">  COMBINING:", lo, ' color="#6a5acd">\n        AND:', hi
 color="#804040"> 40          color="#804040">for i  color="#804040">in lo[1]: i[1].insert(0, ' color="#ff00ff">0')
 color="#804040"> 41          color="#804040">for i  color="#804040">in hi[1]: i[1].insert(0, ' color="#ff00ff">1')
 color="#804040"> 42         lohi = [ lo[0] + hi[0] ] + [lo[1] + hi[1]]
 color="#804040"> 43         lohi.append(' color="#ff00ff">(%s if nextbit() else %s)' % (hi[2], lo[2]))
 color="#804040"> 44          color="#804040">if tutor:  color="#804040">print " color="#ff00ff">  PRODUCING:", lohi, ' color="#6a5acd">\n'
 color="#804040"> 45         heappush(heap, lohi)
 color="#804040"> 46     wt, codes, decoder = heappop(heap)
 color="#804040"> 47     decode = eval(' color="#ff00ff">lambda :' + decoder, globals())
 color="#804040"> 48     decode.__doc__ = decoder
 color="#804040"> 49     for i  color="#804040">in codes: i[1] = ''.join(i[1])
 color="#804040"> 50     #for i in codes: i[::] = i[:2]
 color="#804040"> 51     return sorted(codes, key= color="#804040">lambda x: (len(x[-1]), x))
 color="#804040"> 52

Someone posted a href="http://www.rosettacode.org/w/index.php?title=Huffman_codes&oldid=27804#Java">
Java solution, that was over three times as long. Instead of
just counting and comparing line counts, I took a closer
look to see what the extra code was for.

import java.util.*;

 color="#2e8b57">abstract  color="#2e8b57">class HuffmanTree  color="#2e8b57">implements Comparable<HuffmanTree> {
     color="#2e8b57">public  color="#2e8b57">int frequency;  color="#0000ff">// the frequency of this tree
     color="#2e8b57">public HuffmanTree( color="#2e8b57">int freq) { frequency = freq; }

     color="#0000ff">// compares on the frequency
     color="#2e8b57">public  color="#2e8b57">int compareTo(HuffmanTree tree) {
         color="#804040">return frequency - tree.frequency;
    }
}

 color="#2e8b57">class HuffmanLeaf  color="#2e8b57">extends HuffmanTree {
     color="#2e8b57">public  color="#2e8b57">char value;  color="#0000ff">// the character this leaf represents

     color="#2e8b57">public HuffmanLeaf( color="#2e8b57">int freq,  color="#2e8b57">char val) {
         color="#2e8b57">super(freq);
        value = val;
    }
}

 color="#2e8b57">class HuffmanNode  color="#2e8b57">extends HuffmanTree {
     color="#2e8b57">public HuffmanTree left, right;  color="#0000ff">// subtrees

     color="#2e8b57">public HuffmanNode(HuffmanTree l, HuffmanTree r) {
         color="#2e8b57">super(l.frequency + r.frequency);
        left = l;
        right = r;
    }
}

 color="#2e8b57">public  color="#2e8b57">class HuffmanCode {
     color="#0000ff">// input is an array of frequencies, indexed by character code
     color="#2e8b57">public  color="#2e8b57">static HuffmanTree buildTree( color="#2e8b57">int[] charFreqs) {
        PriorityQueue<HuffmanTree> trees =  color="#804040">new PriorityQueue<HuffmanTree>();
         color="#0000ff">// initially, we have a forest of leaves
         color="#0000ff">// one for each non-empty character
         color="#804040">for ( color="#2e8b57">int i =  color="#ff00ff">0; i < charFreqs.length; i++)
             color="#804040">if (charFreqs[i] >  color="#ff00ff">0)
                trees.offer( color="#804040">new HuffmanLeaf(charFreqs[i], ( color="#2e8b57">char)i));

         color="#804040">assert trees.size() >  color="#ff00ff">0;
         color="#0000ff">// loop until there is only one tree left
         color="#804040">while (trees.size() >  color="#ff00ff">1) {
             color="#0000ff">// two trees with least frequency
            HuffmanTree a = trees.poll();
            HuffmanTree b = trees.poll();

             color="#0000ff">// put into new node and re-insert into queue
            trees.offer( color="#804040">new HuffmanNode(a, b));
        }
         color="#804040">return trees.poll();
    }

     color="#2e8b57">public  color="#2e8b57">static  color="#2e8b57">void printCodes(HuffmanTree tree, Stack<Character> prefix) {
         color="#804040">assert tree !=  color="#ff00ff">null;
         color="#804040">if (tree  color="#804040">instanceof HuffmanLeaf) {
            HuffmanLeaf leaf = (HuffmanLeaf)tree;

             color="#0000ff">// print out character and frequency
            System.out.print(leaf.value +  color="#ff00ff">"\t color="#ff00ff">" + leaf.frequency +  color="#ff00ff">"\t color="#ff00ff">");

             color="#0000ff">// print out code for this leaf, which is just the prefix
             color="#804040">for ( color="#2e8b57">char bit : prefix)
                System.out.print(bit);
            System.out.println();

        }  color="#804040">else  color="#804040">if (tree  color="#804040">instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;

             color="#0000ff">// traverse left
            prefix.push( color="#ff00ff">'0');
            printCodes(node.left, prefix);
            prefix.pop();

             color="#0000ff">// traverse right
            prefix.push( color="#ff00ff">'1');
            printCodes(node.right, prefix);
            prefix.pop();
        }
    }

     color="#2e8b57">public  color="#2e8b57">static  color="#2e8b57">void main(String[] args) {
        String test =  color="#ff00ff">"this is an example for huffman encoding";

         color="#0000ff">// we will assume that all our characters will have
         color="#0000ff">// code less than 256, for simplicity
         color="#2e8b57">int[] charFreqs =  color="#804040">new  color="#2e8b57">int[ color="#ff00ff">256];
         color="#0000ff">// read each character and record the frequencies
         color="#804040">for ( color="#2e8b57">char c : test.toCharArray())
            charFreqs[c]++;

         color="#0000ff">// build tree
        HuffmanTree tree = buildTree(charFreqs);

         color="#0000ff">// print out results
        System.out.println( color="#ff00ff">"SYMBOL\t color="#ff00ff">WEIGHT\t color="#ff00ff">HUFFMAN CODE");
        printCodes(tree,  color="#804040">new Stack<Character>());
    }
}

I
noticed that the Java was tidy, and that they had defined their own
classes for a HuffmanLeaf structure used when constructing a
HuffmanTree.

In my original Python, I used a nested list as
the equivalent to the HuffmanLeaf of the Java example. It worked, but I
had to introduce 'magic constants' to access the fields of the Python
leaf , which is also un-named as a structure in the program (lline 33
of
the Python code creates a list of Leaf structures):

33  heap = [ [float(wt), [sym, []]]  color="#804040">for sym, wt  color="#804040">in symbol2weights.iteritems() ]

Now I didn't want to go to the trouble of creating my own
classes, but that's were the new href="http://docs.python.org/dev/py3k/library/collections.html#collections.namedtuple">namedtuple
class factory of Python 2.6 came to the rescue.

namedtuple

namedtuple
will generate a subtype of the tuple class that allows the fields of
the tuple to be named and accessed via subscription, [], or as if the
fields are instance variable names.

I modified my Python program to use two named tuples:

For the Leaf structure as a whole in line 3.

For a component of the Leaf structure that holds the symbol
and the Huffman code (accumulated so far), in line 4.

 1  color="#a020f0">from collections  color="#a020f0">import namedtuple
 color="#804040"> 2 
 color="#804040"> 3 Leaf = namedtuple(' color="#ff00ff">Leaf', 'weight, symbols')
 color="#804040"> 4 SH = namedtuple(' color="#ff00ff">SH', 'sym, huff')
 color="#804040"> 5 
 color="#804040"> 6 def  color="#008080">codecreate2(symbol2weights, tutor= False):
 color="#804040"> 7     ''' color="#ff00ff"> Huffman codecreate2 the given dict mapping symbols to weights '''
 color="#804040"> 8     heap = [ Leaf(weight=float(wt), symbols=[ SH(sym, []) ])
 color="#804040"> 9               color="#804040">for sym, wt  color="#804040">in symbol2weights.iteritems() ]
 color="#804040">10     heapify(heap)
 color="#804040">11     if tutor:  color="#804040">print " color="#ff00ff">ENCODING:", sorted(symbol2weights.iteritems())
 color="#804040">12     while len(heap) >1:
 color="#804040">13         lo = heappop(heap)
 color="#804040">14         hi = heappop(heap)
 color="#804040">15          color="#804040">if tutor:  color="#804040">print " color="#ff00ff">  COMBINING:", lo, ' color="#6a5acd">\n        AND:', hi
 color="#804040">16          color="#804040">for sh  color="#804040">in lo.symbols: sh.huff.insert(0, ' color="#ff00ff">0')
 color="#804040">17          color="#804040">for sh  color="#804040">in hi.symbols: sh.huff.insert(0, ' color="#ff00ff">1')
 color="#804040">18         lohi = Leaf(weight  = lo.weight + hi.weight,
 color="#804040">19                     symbols = lo.symbols + hi.symbols)
 color="#804040">20          color="#804040">if tutor:  color="#804040">print " color="#ff00ff">  PRODUCING:", lohi, ' color="#6a5acd">\n'
 color="#804040">21         heappush(heap, lohi)
 color="#804040">22     symbols = heappop(heap).symbols
 color="#804040">23     symbols = [SH(sym, ''.join(huff))  color="#804040">for sym, huff  color="#804040">in symbols]
 color="#804040">24     return sorted(symbols, key= color="#804040">lambda sh: (len(sh.huff), sh))
 color="#804040">25

The
class generation is succinct in lines 3 and 4, and I use the field
names for clarity for example when creating the original list of Leaves
that will form the heap in line 8

Printing namedtuples

The print statements stay the same, but before you got output like this:

style="font-family: monospace;"> style="font-family: monospace;">...

COMBINING: [2.5, ['C', []]] style="font-family: monospace;">

AND: [5.0, ['A', []]]

PRODUCING: [7.5, ['C', ['0']], ['A', ['1']]] style="font-family: monospace;">
...

Now you get the clearer:

style="font-family: monospace;"> ENCODING:
[('A', '5'), ('B', '25'), ('C', '2.5'), ('D', '12.5')]

COMBINING: Leaf(weight=2.5, symbols=[SH(sym='C', huff=[])])


AND: Leaf(weight=5.0, symbols=[SH(sym='A', huff=[])])

PRODUCING: Leaf(weight=7.5, symbols=[SH(sym='C',
huff=['0']), SH(sym='A', huff=['1'])])

COMBINING: Leaf(weight=7.5, symbols=[SH(sym='C',
huff=['0']), SH(sym='A', huff=['1'])])


AND: Leaf(weight=12.5, symbols=[SH(sym='D', huff=[])])

PRODUCING: Leaf(weight=20.0, symbols=[SH(sym='C', huff=['0', '0']),
SH(sym='A', huff=['0', '1']), SH(sym='D', huff=['1'])])

COMBINING: Leaf(weight=20.0, symbols=[SH(sym='C', huff=['0', '0']),
SH(sym='A', huff=['0', '1']), SH(sym='D', huff=['1'])])


AND: Leaf(weight=25.0, symbols=[SH(sym='B', huff=[])])

PRODUCING: Leaf(weight=45.0, symbols=[SH(sym='C', huff=['0', '0',
'0']), SH(sym='A', huff=['0', '0', '1']), SH(sym='D', huff=['0', '1']),
SH(sym='B', huff=['1'])])

Conclusion

Although
you can do so much with Python lists, if each position in the list has
a fixed meaning then you might be best to use tuples, and if you should
be using tuples, then namedtuples can make your code more readable
without bloating it with long class definitions.

- Paddy.

Saturday, March 28, 2009

Huffman Encoding in Python

Huffman encoding came up on Rosetta Code.
Huffman encoding is a way to assign binary codes to symbols that reduces the overall number of bits used to encode a typical string of of those symbols.
For example, if you use letters as symbols and have details of the frequency of occurence of those letters in typical strings, then you could just encode each letter with a fixed number of bits, such as in ASCII codes. You can do better than this by encoding more frequently occurring letters such as e and a, with smaller bit strings; and less frequently occurring letters such as q and x with longer bit strings.
Any string of letters will be encoded as a string of bits that are no-longer of the same length per letter. To successfully decode such as string, the smaller codes assigned to letters such as 'e' cannot occur as a prefix in the larger codes such as that for 'x'.

If you were to assign a code 01 for 'e' and code 011 for 'x', then if the bits to decode started as 011... then you would not know iif you should decode an 'e' or an 'x'.

The Huffman coding scheme takes each symbol and its weight (or frequency of occurrence), and generates proper encodings for each symbol taking account of the weights of each symbol, so that higher weighted symbols have less bits in their encoding. (See the WP article for more information).
A Huffman encoding can be computed by first creating a tree of nodes:

Create a leaf node for each symbol and add it to the priority queue.
While there is more than one node in the queue:
1. Remove the node of highest priority (lowest probability) twice to get two nodes.
2. Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
3. Add the new node to the queue.
The remaining node is the root node and the tree is complete.

Traverse the constructed binary tree from root to leaves assigning and accumulating a '0' for one branch and a '1' for the other at each node. The accumulated zeroes and ones at each leaf constitute a Huffman encoding for those symbols and weights.

In Python

I orginally gave an an example that matched a definition that was later found to be insufficient, so substituted my own definition above.. My first Python solution on RC to the wrong definition, did have the advantage, (as I saw it), of not having to traverse a tree.
My 'true' Huffman code creator assembles each symbol and its weight into the following structure initially (the leaf structure):

[ weight, [ symbol, []]]

The weight applies to every (in this case only one), of the [symbol, []] pairs after it in the same list.
The empty list is used to accumulate the Huffman code for the symbol as we manipulate the heap, without having to walk a constructed tree structure.

There are two types of input to the program that I am running examples with:

A string of space separated symbol, weight pairs, as used in small examples.
A sample of text for which letters and letter frequencies are extracted.

The if statement at line 23 allows me to switch between the two types of input whilst exploring the algorithm.
The tutor argument to the encode function shows what is happening in the loop around the heap pops

 1 
 2 from heapq import heappush, heappop, heapify
 3 
 4 def codecreate(symbol2weights, tutor= False):
 5     ''' Huffman encode the given dict mapping symbols to weights '''
 6     heap = [ [float(wt), [sym, []]] for sym, wt in symbol2weights.iteritems() ]
 7     heapify(heap)
 8     if tutor: print "ENCODING:", sorted(symbol2weights.iteritems())
 9     while len(heap) >1:
10         lo = heappop(heap)
11         hi = heappop(heap)
12         if tutor: print "  COMBINING:", lo, '\n        AND:', hi
13         for i in lo[1:]: i[1].insert(0, '0')
14         for i in hi[1:]: i[1].insert(0, '1')
15         lohi = [ lo[0] + hi[0] ] + lo[1:] + hi[1:]
16         if tutor: print "  PRODUCING:", lohi, '\n'
17         heappush(heap, lohi)
18     codes = heappop(heap)[1:]
19     for i in codes: i[1] = ''.join(i[1])
20     return sorted(codes, key=lambda x: (len(x[-1]), x))
21 
22 # Input types
23 if 1:
24     readin = "B 25   C 2.5 D  12.5 A 5 \n"
25     #readin = "a .1 b .15 c .3 d .16 e .29" # Wikipedia sample
26     #readin = "a1 .4 a2 .35 a3 .2 a4 .05" # Wikipedia sample
27     #readin = "A 50 B 25 C 12.5 D 12.5" # RC example
28 
29     cleaned = readin.strip().split()
30     symbol2weights = dict((symbol, wt)
31                          for symbol, wt in zip(cleaned[0::2], cleaned[1::2]) )
32 else:
33     astring = "this is an example for huffman encoding"
34     symbol2weights = dict((ch, astring.count(ch)) for ch in set(astring)) # for astring
35 
36 huff = codecreate(symbol2weights, True)
37 print "\nSYMBOL\tWEIGHT\tHUFFMAN CODE"
38 for h in huff:
39     print "%s\t%s\t%s" % (h[0], symbol2weights[h[0]], h[1])

A run, with the tutor enabled gives the following output:

ENCODING: [('A', '5'), ('B', '25'), ('C', '2.5'), ('D', '12.5')]
COMBINING: [2.5, ['C', []]]
        AND: [5.0, ['A', []]]
PRODUCING: [7.5, ['C', ['0']], ['A', ['1']]]

COMBINING: [7.5, ['C', ['0']], ['A', ['1']]]
        AND: [12.5, ['D', []]]
PRODUCING: [20.0, ['C', ['0', '0']], ['A', ['0', '1']], ['D', ['1']]]

COMBINING: [20.0, ['C', ['0', '0']], ['A', ['0', '1']], ['D', ['1']]]
        AND: [25.0, ['B', []]]
PRODUCING: [45.0, ['C', ['0', '0', '0']], ['A', ['0', '0', '1']], ['D', ['0', '1']], ['B', ['1']]]

SYMBOL    WEIGHT    HUFFMAN CODE
B    25    1
D    12.5    01
A    5    001
C    2.5    000

Encode/Decode Round-tripping

I realised that I could use a method similar to how I accumulate the codes in the heap loop, to generate a single function that can recognise a single symbol from the beginning of the encoded symbols. By using the function in a loop, I could regenerate the symbol list.

In the codecreate function, the leaf structure is modified:

[weight, [ [symbol, []] ], repr(sym)]

Their is an extra level of list around the [symbol, code accumulation list pair] as well as a new item: 'repr(sym)' it is the third item in the outer list and will always be the function to generate the item as accumulated so far.. This function starts off by returning just the symbol and an outer if/then/else expression is added as we go around the heap loop (see line 43)

After the outer expression is accumulated, it is turned into a lambda expression, the string eval'd, and assigned to a global variable (see line 47)

I use function probchoice (from earlier RC work), to create an arbitrary sequence of symbols to in the given weighting then encode and decode it as well as giving some stats on space saving.

  1 
  2 from heapq import heappush, heappop, heapify
  3 import random, bisect
  4 
  5 
  6 # Helper routine for generating test sequences
  7 def probchoice(items, probs):
  8   '''\
  9   Splits the interval 0.0-1.0 in proportion to probs
 10   then finds where each random.random() choice lies
 11   (This routine, probchoice, was released under the
 12   GNU Free Documentation License 1.2)
 13   '''
 14 
 15   prob_accumulator = 0
 16   accumulator = []
 17   for p in probs:
 18     prob_accumulator += p
 19     accumulator.append(prob_accumulator)
 20 
 21   while True:
 22     r = random.random()
 23     yield items[bisect.bisect(accumulator, r)]
 24 
 25 
 26 # placeholder
 27 decode = lambda : None
 28 
 29 def codecreate(symbol2weights, tutor= False):
 30     ''' Huffman encode the given dict mapping symbols to weights '''
 31     global decode
 32 
 33     heap = [ [float(wt), [[sym, []]], repr(sym)] for sym, wt in symbol2weights.iteritems() ]
 34     heapify(heap)
 35     if tutor: print "ENCODING:", sorted(symbol2weights.iteritems())
 36     while len(heap) >1:
 37         lo = heappop(heap)
 38         hi = heappop(heap)
 39         if tutor: print "  COMBINING:", lo, '\n        AND:', hi
 40         for i in lo[1]: i[1].insert(0, '0')
 41         for i in hi[1]: i[1].insert(0, '1')
 42         lohi = [ lo[0] + hi[0] ] + [lo[1] + hi[1]]
 43         lohi.append('(%s if nextbit() else %s)' % (hi[2], lo[2]))
 44         if tutor: print "  PRODUCING:", lohi, '\n'
 45         heappush(heap, lohi)
 46     wt, codes, decoder = heappop(heap)
 47     decode = eval('lambda :' + decoder, globals())
 48     decode.__doc__ = decoder
 49     for i in codes: i[1] = ''.join(i[1])
 50     #for i in codes: i[::] = i[:2]
 51     return sorted(codes, key=lambda x: (len(x[-1]), x))
 52 
 53 # Input types
 54 if 1:
 55     tutor = True
 56     sequencecount = 50
 57     readin = "B 25   C 2.5 D  12.5 A 5 \n"
 58     #readin = "a .1 b .15 c .3 d .16 e .29" # Wikipedia sample
 59     #readin = "a1 .4 a2 .35 a3 .2 a4 .05" # Wikipedia sample
 60     #readin = "A 50 B 25 C 12.5 D 12.5" # RC example
 61 
 62     cleaned = readin.strip().split()
 63     symbol2weights = dict((symbol, wt)
 64                          for symbol, wt in zip(cleaned[0::2], cleaned[1::2]) )
 65 else:
 66     tutor = False
 67     sequencecount = 500
 68     astring = "this is an example for huffman encoding"
 69     symbol2weights = dict((ch, astring.count(ch)) for ch in set(astring)) # for astring
 70 
 71 huff = codecreate(symbol2weights, tutor= tutor)
 72 print "\nSYMBOL\tWEIGHT\tHUFFMAN CODE"
 73 for h in huff:
 74     print "%s\t%s\t%s" % (h[0], symbol2weights[h[0]], h[1])
 75 
 76 ##
 77 ## encode-decode check
 78 ##
 79 symbol2code = dict(huff)
 80 symbols, weights = zip(*symbol2weights.iteritems())
 81 # normalize weights
 82 weights = [float(wt) for wt in weights]
 83 tot = sum(weights)
 84 weights = [wt/tot for wt in weights]
 85 # Generate a sequence
 86 nxt = probchoice(symbols, weights).next
 87 symbolsequence = [nxt() for i in range(sequencecount)]
 88 # encode it
 89 bitsequence = ''.join(symbol2code[sym] for sym in symbolsequence)
 90 
 91 sslen, slen, blen = len(symbolsequence), len(symbols), len(bitsequence)
 92 countlen = len(bin(slen-1)[2:])
 93 print '''
 94 
 95 
 96 ROUND-TRIPPING
 97 ==============
 98 I have generated a random sequence of %i symbols to the given weights.
 99 If I use a binary count to encode each of the %i symbols I would need
100 %i * %i = %i bits to encode the sequence.
101 Using the Huffman code, I need only %i bits.
102 ''' % (sslen, slen, sslen, countlen, sslen * countlen, blen )
103 
104 ## decoding
105 nextbit = (bit=='1' for bit in bitsequence).next
106 
107 decoded = []
108 try:
109     while 1:
110         decoded.append(decode())
111 except StopIteration:
112     pass
113 
114 print "Comparing the decoded sequence with the original I get:", decoded == symbolsequence

This short run is in tutor mode, so you can track the accumulation of the decode function:

ENCODING: [('A', '5'), ('B', '25'), ('C', '2.5'), ('D', '12.5')]
COMBINING: [2.5, [['C', []]], "'C'"]
        AND: [5.0, [['A', []]], "'A'"]
PRODUCING: [7.5, [['C', ['0']], ['A', ['1']]], "('A' if nextbit() else 'C')"]

COMBINING: [7.5, [['C', ['0']], ['A', ['1']]], "('A' if nextbit() else 'C')"]
        AND: [12.5, [['D', []]], "'D'"]
PRODUCING: [20.0, [['C', ['0', '0']], ['A', ['0', '1']], ['D', ['1']]], "('D' if nextbit() else ('A' if nextbit() else 'C'))"]

COMBINING: [20.0, [['C', ['0', '0']], ['A', ['0', '1']], ['D', ['1']]], "('D' if nextbit() else ('A' if nextbit() else 'C'))"]
        AND: [25.0, [['B', []]], "'B'"]
PRODUCING: [45.0, [['C', ['0', '0', '0']], ['A', ['0', '0', '1']], ['D', ['0', '1']], ['B', ['1']]], "('B' if nextbit() else ('D' if nextbit() else ('A' if nextbit() else 'C')))"]

SYMBOL    WEIGHT    HUFFMAN CODE
B    25      1
D    12.5      01
A    5    001
C    2.5    000

ROUND-TRIPPING
==============
I have generated a random sequence of 50 symbols to the given weights.
If I use a binary count to encode each of the 4 symbols I would need
50 * 2 = 100 bits to encode the sequence.
Using the Huffman code, I need only 90 bits.

Comparing the decoded sequence with the original I get: True

And if I change line 54 to be False, I get the following:

SYMBOL    WEIGHT    HUFFMAN CODE
     6    101
n    4    010
a    3    1001
e    3    1100
f    3    1101
h    2    0001
i    3    1110
m    2    0010
o    2    0011
s    2    0111
g    1    00000
l    1    00001
p    1    01100
r    1    01101
t    1    10000
u    1    10001
x    1    11110
c    1    111110
d    1    111111

ROUND-TRIPPING
==============
I have generated a random sequence of 500 symbols to the given weights.
If I use a binary count to encode each of the 19 symbols I would need
500 * 5 = 2500 bits to encode the sequence.
Using the Huffman code, I need only 2012 bits.

Comparing the decoded sequence with the original I get: True

Note: The purpose of the program is to teach me more about Huffman coding and is not an exercise in speed!

I am the author of all the Python on this page. The diagram is from Wikipedia. Please refrain from passing-off my code as your own (that one is mainly for students).

Saturday, March 21, 2009

Batch Process Runner in bash shell - Forgotten Enhancements

A comment on an href="http://paddy3118.blogspot.com/2007/12/batch-process-runner-in-bash-shell.html">earlier
post caused me to dig out this enhancement to my original
batch process runner.

What you do is create a file of one-liner commands that you would enter
at a command prompt, for example, this is file style="font-weight: bold;">process_list.txt :

1  color="#0000ff"># (Comments have '#' at the left margin)
 color="#804040">2 sleep 4; echo slept for 4 at line 2; csdf_sdf_sd; exit 19
 color="#804040">3 sleep 1; cause-an-error; echo slept for 1 at line 3
 color="#804040">4 sleep 3; echo  color="#ff00ff">'slept for 3 at line 4'
 color="#804040">5 sleep 7; echo  color="#ff00ff">"slept for 7 at line 5"
 color="#804040">6 # Whee!
 color="#804040">7 sleep 9; another-erro; echo slept for 9 at line 7
 color="#804040">8 sleep 5; echo  color="#ff00ff">'slept "for 5" at line 8'

A bit of warning, bash returns the exit code of this laast command it
executes, earlier exit codes won't be seen.

Give my script the number of processes to run in parallel, N, followed
by the above file, and it will create N '.job' files out of
the non-comment lines of process_list.txt and execute them as
background jobs, with their output sent to '.n' files.:

bash$ ./process_list_runner.sh 2 process_list.txt

## STARTING 6 Processes from file: process_list.txt, 2 at a time with id plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP

# 2 Jobs in background. 6/6 started. 2009-03-21-05:36:36

## FINISHED, (stats in plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.csv)

bash$  style="font-weight: bold;">ls -1 plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.*
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.1
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.2
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.3
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.4
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.5
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.6
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.csv
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.job_0
plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP.job_1
bash$

The script does what it can to create a csv file of run stats, which,
with a bit of tidying up in calc produces the following:

frame="void" rules="none">
width="340"> width="110"> width="115"> width="73">

width="1409">## STARTING 6 Processes from file: process_list.txt
size="4">2 at a time with id plr_HPDV8025EA_2009-03-21-05_36_19_PADDYS-HPLAPTOP

align="center" bgcolor="#ccffff" height="123" valign="middle">JOB	align="right" bgcolor="#ccffff" valign="middle">LINE	align="center" bgcolor="#ccffff" valign="middle">Command being timed	align="center" bgcolor="#ccffff" valign="middle">User time (seconds)	align="center" bgcolor="#ccffff" valign="middle">System time (seconds)	align="center" bgcolor="#ccffff" valign="middle">Percent of CPU this job got	align="center" bgcolor="#ccffff" valign="middle">Elapsed (wall clock) time (h:mm:ss or m:ss)	align="center" bgcolor="#ccffff" valign="middle">Maximum resident set size (kbytes)	align="center" bgcolor="#ccffff" valign="middle">Major (requiring I/O) page faults	align="center" bgcolor="#ccffff" valign="middle">Signals delivered	align="center" bgcolor="#ccffff" valign="middle">Page size (bytes)	align="center" bgcolor="#ccffff" valign="middle">Exit status
sdnum="2057;" align="center" bgcolor="#ffffcc" height="18">1	sdnum="2057;" align="center" bgcolor="#ffffcc">2	bgcolor="#ffffcc">sleep 4; echo slept for 4 at line 2; csdf_sdf_sd; exit 19	sdnum="2057;" align="center" bgcolor="#ffffcc">0.13	sdnum="2057;" align="center" bgcolor="#ffffcc">0.15	sdnum="2057;0;0.00%" align="center" bgcolor="#ffffcc">6.00%	sdval="0.0000503472222222222" sdnum="2057;0;MM:SS.00" align="center" bgcolor="#ffffcc">00:04.35	sdval="760832" sdnum="2057;" align="center" bgcolor="#ffffcc">760832	sdnum="2057;" align="center" bgcolor="#ffffcc">3277	sdnum="2057;" align="center" bgcolor="#ffffcc">6	sdval="65536" sdnum="2057;" align="center" bgcolor="#ffffcc">65536	sdnum="2057;" align="center" bgcolor="#ffffcc">19
sdnum="2057;" align="center" bgcolor="#ccccff" height="17">2	sdnum="2057;" align="center" bgcolor="#ccccff">3	bgcolor="#ccccff">sleep 1; cause-an-error; echo slept for 1 at line 3	sdnum="2057;" align="center" bgcolor="#ccccff">0.12	sdnum="2057;" align="center" bgcolor="#ccccff">0.09	sdnum="2057;0;0.00%" align="center" bgcolor="#ccccff">16.00%	sdval="0.0000152777777777778" sdnum="2057;0;MM:SS.00" align="center" bgcolor="#ccccff">00:01.32	sdval="761088" sdnum="2057;" align="center" bgcolor="#ccccff">761088	sdnum="2057;" align="center" bgcolor="#ccccff">3273	sdnum="2057;" align="center" bgcolor="#ccccff">6	sdval="65536" sdnum="2057;" align="center" bgcolor="#ccccff">65536	sdnum="2057;" align="center" bgcolor="#ccccff">0
sdnum="2057;" align="center" bgcolor="#ffffcc" height="17">3	sdnum="2057;" align="center" bgcolor="#ffffcc">4	bgcolor="#ffffcc">sleep 3; echo 'slept for 3 at line 4'	sdnum="2057;" align="center" bgcolor="#ffffcc">0.07	sdnum="2057;" align="center" bgcolor="#ffffcc">0.06	sdnum="2057;0;0.00%" align="center" bgcolor="#ffffcc">4.00%	sdval="0.0000377314814814815" sdnum="2057;0;MM:SS.00" align="center" bgcolor="#ffffcc">00:03.26	sdval="617216" sdnum="2057;" align="center" bgcolor="#ffffcc">617216	sdnum="2057;" align="center" bgcolor="#ffffcc">2639	sdnum="2057;" align="center" bgcolor="#ffffcc">3	sdval="65536" sdnum="2057;" align="center" bgcolor="#ffffcc">65536	sdnum="2057;" align="center" bgcolor="#ffffcc">0
sdnum="2057;" align="center" bgcolor="#ccccff" height="17">4	sdnum="2057;" align="center" bgcolor="#ccccff">5	bgcolor="#ccccff">sleep 7; echo "slept for 7 at line 5"	sdnum="2057;" align="center" bgcolor="#ccccff">0.07	sdnum="2057;" align="center" bgcolor="#ccccff">0.07	sdnum="2057;0;0.00%" align="center" bgcolor="#ccccff">2.00%	sdval="0.000084837962962963" sdnum="2057;0;MM:SS.00" align="center" bgcolor="#ccccff">00:07.33	sdval="617216" sdnum="2057;" align="center" bgcolor="#ccccff">617216	sdnum="2057;" align="center" bgcolor="#ccccff">2644	sdnum="2057;" align="center" bgcolor="#ccccff">3	sdval="65536" sdnum="2057;" align="center" bgcolor="#ccccff">65536	sdnum="2057;" align="center" bgcolor="#ccccff">0
sdnum="2057;" align="center" bgcolor="#ffffcc" height="18">5	sdnum="2057;" align="center" bgcolor="#ffffcc">7	bgcolor="#ffffcc">sleep 9; another-erro; echo slept for 9 at line 7	sdnum="2057;" align="center" bgcolor="#ffffcc">0.09	sdnum="2057;" align="center" bgcolor="#ffffcc">0.13	sdnum="2057;0;0.00%" align="center" bgcolor="#ffffcc">2.00%	sdval="0.000106597222222222" sdnum="2057;0;MM:SS.00" align="center" bgcolor="#ffffcc">00:09.21	sdval="760064" sdnum="2057;" align="center" bgcolor="#ffffcc">760064	sdnum="2057;" align="center" bgcolor="#ffffcc">3274	sdnum="2057;" align="center" bgcolor="#ffffcc">6	sdval="65536" sdnum="2057;" align="center" bgcolor="#ffffcc">65536	sdnum="2057;" align="center" bgcolor="#ffffcc">0
sdnum="2057;" align="center" bgcolor="#ccccff" height="17">6	sdnum="2057;" align="center" bgcolor="#ccccff">8	bgcolor="#ccccff">sleep 5; echo 'slept "for 5" at line 8'	sdnum="2057;" align="center" bgcolor="#ccccff">0.1	sdnum="2057;" align="center" bgcolor="#ccccff">0.06	sdnum="2057;" align="center" bgcolor="#ccccff">0.03	sdval="0.0000622685185185185" sdnum="2057;0;MM:SS.00" align="center" bgcolor="#ccccff">00:05.38	sdval="617216" sdnum="2057;" align="center" bgcolor="#ccccff">617216	sdnum="2057;" align="center" bgcolor="#ccccff">2639	sdnum="2057;" align="center" bgcolor="#ccccff">3	sdval="65536" sdnum="2057;" align="center" bgcolor="#ccccff">65536	sdnum="2057;" align="center" bgcolor="#ccccff">0

The script itself is:

 1  color="#0000ff">#!/bin/bash 
 color="#804040"> 2 #!/opt/TWWfsw/bin/bash -
 color="#804040"> 3 
 color="#804040"> 4 set  color="#008080">-u
 color="#804040"> 5 
 color="#804040"> 6 ##
 color="#804040"> 7 ## process_runner.sh <concurrent> <total procs>
 color="#804040"> 8 ##
 color="#804040"> 9 ## Example script given the maximum number of processes to
 color="#804040"> 10 ## run concurrently, c, and the total number of processes, n
 color="#804040"> 11 ## runs at most c, processes in the background until all n
 color="#804040"> 12 ## Have been run.
 color="#804040"> 13 ##
 color="#804040"> 14 ## Author Donald 'Paddy' McCarthy Dec. 17 2007
 color="#804040"> 15 ##
 color="#804040"> 16 
 color="#804040"> 17 # how many processes to run in parallel
 color="#804040"> 18 concurrent= color="#a020f0">$1
 color="#804040"> 19 # File of commands
 color="#804040"> 20 proclist= color="#804040">" color="#a020f0">$2"
 color="#804040"> 21 
 color="#804040"> 22 ##
 color="#804040"> 23 ##
 color="#804040"> 24 
 color="#804040"> 25 # main loop wait time between checking background procs.
 color="#804040"> 26 tick= color="#ff00ff">1
 color="#804040"> 27 # Unique_id for process files of this run
 color="#804040"> 28 unique_id=plr_ color="#6a5acd">`date +${ color="#a020f0">USER//  color="#804040">/ color="#a020f0">}_%F-%T_ color="#a020f0">${HOSTNAME color="#804040">//  color="#804040">/ color="#a020f0">}`
 color="#804040"> 29 unique_id= color="#a020f0">${unique_id color="#804040">//: color="#804040">/_ color="#a020f0">}
 color="#804040"> 30 
 color="#804040"> 31 function read_proclistfile  color="#6a5acd">{
 color="#804040"> 32  # read processes from file ignoring comment lines
 color="#804040"> 33  maxprocs= color="#ff00ff">0
 color="#804040"> 34  local -i  color="#008080">linenumber= color="#ff00ff">0
 color="#804040"> 35  while color="#804040">  color="#804040">read color="#804040">; color="#804040">  color="#804040">do
 color="#804040"> 36  (( color="#008080">linenumber+= color="#ff00ff">1))
 color="#804040"> 37  # echo [ "${REPLY:0:1}" == "#" ] $maxprocs $REPLY
 color="#804040"> 38  if  color="#804040">[  color="#804040">" color="#a020f0">${REPLY color="#804040">: color="#ff00ff">0: color="#ff00ff">1} color="#804040">"  color="#804040">!=  color="#804040">" color="#ff00ff">#"  color="#804040">]  color="#804040">;  color="#804040">then
 color="#804040"> 39  ((maxprocs+ color="#804040">= color="#ff00ff">1))
 color="#804040"> 40  allprocs color="#804040">[ color="#a020f0">$maxprocs color="#804040">] color="#804040">= color="#804040">" color="#a020f0">$REPLY"
 color="#804040"> 41  allprocline color="#804040">[ color="#a020f0">$maxprocs color="#804040">] color="#804040">= color="#a020f0">$linenumber
 color="#804040"> 42  # echo $linenumber $maxprocs $REPLY
 color="#804040"> 43  fi
 color="#804040"> 44  done  color="#804040"><  color="#a020f0">$proclist
 color="#804040"> 45 }
 color="#804040"> 46 
 color="#804040"> 47 read_proclistfile
 color="#804040"> 48 
 color="#804040"> 49 printf  color="#804040">" color="#6a5acd">\n## STARTING %i Processes from file: %s, %i at a time with id %s color="#6a5acd">\n\n" \
 color="#804040"> 50  $maxprocs  color="#a020f0">$proclist  color="#a020f0">$concurrent  color="#a020f0">$unique_id
 color="#804040"> 51 
 color="#804040"> 52 
 color="#804040"> 53 
 color="#804040"> 54 function assemble_job  color="#6a5acd">{
 color="#804040"> 55  #
 color="#804040"> 56  local  color="#008080">plr_unique_id= color="#804040">" color="#a020f0">$1"; color="#804040">local  color="#008080">plr_ran=" color="#a020f0">$2"; color="#804040">local  color="#008080">plr_proc= color="#804040">" color="#a020f0">$3"; color="#804040">local  color="#008080">plr_procline= color="#804040">" color="#a020f0">$4"; color="#804040">local  color="#008080">plr_proclist= color="#804040">" color="#a020f0">$5"
 color="#804040"> 57  cat  color="#804040"><<!
 color="#804040"> 58 
 color="#804040"> 59 #  color="#a020f0">$plr_unique_id color="#ff00ff"> $plr_ran color="#ff00ff"> 
 color="#804040"> 60 ` color="#804040">local color="#6a5acd">`
 color="#804040"> 61 
 color="#804040"> 62 trap 'error= color="#6a5acd">\$?;printf " color="#6a5acd">\n\n##STATISTICS For Job %i color="#6a5acd">\n"  color="#a020f0">$plr_ran; printf "# Line %i of file %s color="#6a5acd">\n\n"  color="#a020f0">$plr_procline color="#ff00ff"> $plr_proclist color="#ff00ff">; exit \$ color="#ff00ff">error' EXIT
 color="#804040"> 63 
 color="#804040"> 64 
 color="#804040"> 65 $plr_proc
 color="#804040"> 66 
 color="#804040"> 67 !
 color="#804040"> 68 }
 color="#804040"> 69 
 color="#804040"> 70 function print_runstats  color="#6a5acd">{
 color="#804040"> 71  printf  color="#804040">' color="#ff00ff"># %i Jobs in background. %i/%i started. %s\r color="#804040">' \
 color="#804040"> 72  ` color="#804040">jobs color="#6a5acd"> -r color="#804040">| color="#6a5acd">wc -l` $ran  color="#a020f0">$maxprocs  color="#804040">" color="#6a5acd">`date +%F-%T` color="#804040">"
 color="#804040"> 73 }
 color="#804040"> 74 
 color="#804040"> 75 # Bash array running keeps track of the background process numbers
 color="#804040"> 76 # Start with nothing running (sentinel value will not be a process number
 color="#804040"> 77 for  color="#6a5acd">((i= color="#ff00ff">0; i color="#804040">< color="#a020f0">$concurrent color="#804040">; i+ color="#804040">= color="#ff00ff">1 )) color="#804040">;  color="#804040">do running color="#804040">[ color="#a020f0">$i] color="#804040">= color="#ff00ff">123456789 color="#804040">;  color="#804040">done
 color="#804040"> 78 
 color="#804040"> 79 ran= color="#ff00ff">0
 color="#804040"> 80 until
 color="#804040"> 81  while  color="#804040">[  color="#a020f0">$ran -lt  color="#a020f0">$maxprocs  color="#804040">] color="#804040">;  color="#804040">do
 color="#804040"> 82  for  color="#6a5acd">((p= color="#ff00ff">0; p color="#804040">< color="#a020f0">$concurrent color="#804040">; p+ color="#804040">= color="#ff00ff">1 )) color="#804040">;  color="#804040">do
 color="#804040"> 83  proc= color="#a020f0">${running color="#a020f0">[$p color="#a020f0">]}
 color="#804040"> 84  # Over all running processes...
 color="#804040"> 85  # $proc still running?
 color="#804040"> 86  ps -p  color="#a020f0">$proc |  color="#804040">fgrep  color="#a020f0">$proc >/dev/null
 color="#804040"> 87  if  color="#804040">[  color="#a020f0">$? -ne  color="#804040">' color="#ff00ff">0'  color="#804040">]  color="#804040">;  color="#804040">then
 color="#804040"> 88  # Not found i.e. its finished
 color="#804040"> 89  # So start the next
 color="#804040"> 90  ((ran+ color="#804040">= color="#ff00ff">1))
 color="#804040"> 91  #(assemble_job ) >$unique_id.job_$p
 color="#804040"> 92  ( assemble_job  color="#804040">" color="#a020f0">$unique_id color="#804040">"  color="#804040">" color="#a020f0">$ran"  color="#804040">" color="#a020f0">${allprocs color="#a020f0">[$ran color="#a020f0">]} color="#804040">" \
 color="#804040"> 93  ${ color="#a020f0">allprocline color="#a020f0">[$ran color="#a020f0">]}  color="#a020f0">$proclist  color="#804040">)  color="#804040">>  color="#a020f0">$unique_id.job_ color="#a020f0">$p
 color="#804040"> 94  chmod +x  color="#a020f0">$unique_id.job_ color="#a020f0">$p
 color="#804040"> 95  # run one job in background collecting run stats
 color="#804040"> 96  (/bin/ color="#804040">time -v -a -o  color="#a020f0">$unique_id. color="#a020f0">$ran < /dev/null  color="#a020f0">$unique_id.job_ color="#a020f0">$p 2>&1  color="#804040">)  color="#804040">>  color="#a020f0">$unique_id. color="#a020f0">$ran &
 color="#804040"> 97  running color="#804040">[ color="#a020f0">$p] color="#804040">= color="#a020f0">$!
 color="#804040"> 98  runningprocnum color="#804040">[ color="#a020f0">$p] color="#804040">= color="#a020f0">$ran
 color="#804040"> 99  if  color="#804040">[  color="#a020f0">$ran -ge  color="#a020f0">$maxprocs  color="#804040">] color="#804040">;  color="#804040">then  color="#804040">break  color="#ff00ff">1;  color="#804040">fi
 color="#804040">100  #exit
 color="#804040">101  fi
 color="#804040">102  done
 color="#804040">103  sleep  color="#a020f0">$tick
 color="#804040">104  # Status
 color="#804040">105  print_runstats
 color="#804040">106  done
 color="#804040">107 
 color="#804040">108  ## break 1 gets us here!
 color="#804040">109 
 color="#804040">110  # Keep on printing status while there are background processes 
 color="#804040">111  # even though there are no more to start.
 color="#804040">112  sleep  color="#a020f0">$tick
 color="#804040">113  # Status
 color="#804040">114  print_runstats
 color="#804040">115 do  color="#804040">[  color="#6a5acd">`jobs color="#6a5acd"> -r color="#804040">| color="#6a5acd">wc -l` -eq  color="#ff00ff">0 ]
 color="#804040">116 done
 color="#804040">117 wait
 color="#804040">118 
 color="#804040">119 function stats2csv  color="#6a5acd">{
 color="#804040">120  # Gather overall stats in csv file
 color="#804040">121 
 color="#804040">122  # CSV Heading
 color="#804040">123  printf  color="#804040">" color="#6a5acd">\n## STARTING %i Processes from file: %s color="#6a5acd">\n%i at a time with id %s color="#6a5acd">\n\n" \
 color="#804040">124  $maxprocs  color="#a020f0">$proclist  color="#a020f0">$concurrent  color="#a020f0">$unique_id  color="#804040">>  color="#a020f0">$unique_id.csv
 color="#804040">125  # CSV Column labels 
 color="#804040">126  gawk  color="#804040">' color="#ff00ff">/^##STATISTICS For Job/{s++}
 color="#804040">127  s&&/^# Line .*of file/{printf "JOB,LINE";next}
 color="#804040">128  s&&/: /{l=$0;sub(/: .*/,"");$1=$1;printf",%s",$0}
 color="#804040">129  s&&l~/Exit status:/{s=0;print"";l="";exit}
 color="#804040">130   color="#804040">'  color="#a020f0">$unique_id. color="#804040">[ color="#ff00ff">0-9]*  color="#804040">>>  color="#a020f0">$unique_id.csv
 color="#804040">131 
 color="#804040">132  # Stick allprocs into env for later gawk substitution of command
 color="#804040">133  for i  color="#804040">in  color="#a020f0">${!allprocs color="#a020f0">[@] color="#a020f0">};  color="#804040">do
 color="#804040">134  declare  color="#008080">-x _ap color="#a020f0">$i= color="#804040">" color="#a020f0">${allprocs color="#a020f0">[$i color="#a020f0">]} color="#804040">"
 color="#804040">135  done
 color="#804040">136  #env|grep '_ap.=' ; debug
 color="#804040">137  # CSV Rows
 color="#804040">138  gawk  color="#804040">' color="#ff00ff">/^##STATISTICS For Job/{s++;j=$NF}
 color="#804040">139  s&&/^# Line .*of file/{printf "%s,%s",j,$3;next}
 color="#804040">140  s&&/Command [^:]*: /{printf",%s",ENVIRON["_ap" j]; next}
 color="#804040">141  s&&/: /{l=$0;sub(/.*: /,"");printf",%s",$0}
 color="#804040">142  s&&l~/Exit status:/{s=0;print"";l="";nextfile}
 color="#804040">143   color="#804040">'  color="#a020f0">$unique_id. color="#804040">[ color="#ff00ff">0-9]*  color="#804040">>>  color="#a020f0">$unique_id.csv
 color="#804040">144 }
 color="#804040">145 
 color="#804040">146 stats2csv
 color="#804040">147 
 color="#804040">148 printf  color="#804040">" color="#6a5acd">\n## FINISHED, (stats in %s) color="#6a5acd">\n\n"  color="#a020f0">$unique_id.csv
 color="#804040">149 
 color="#804040">150 exit  color="#ff00ff">0
 color="#804040">151 
 color="#804040">152 
 color="#804040">153 
 color="#804040">154

I remember writing this with the help of the advanced bash tutorial
which is great, and looking back at this program, I would need the
tutorials help if I needed to extend it!

Why not in Python?

Of course I thought of doing it in Python, but bash's job
control features were used to flesh out the initial idea and it grew to
become the finished article. Looking back at this program as it's over
a year old, I find that I like bash's job control, and gawk one-liners
(but not the readability) :-)

- Paddy.

href="http://kompozer.net/"> alt="Document made with KompoZer"
src="http://kompozer.sourceforge.net/images/kompozer_80x15.png"
border="0">

Go deh!

Wednesday, April 29, 2009

Fight for the community you want

Tuesday, April 21, 2009

Monitoring a linux process as it reads files

First create some test files to process

Now lets create a test executable to monitor

here is what the fd directory looks like

And here is a python script to monitor that fd directories
link number 4 periodically

Thursday, April 16, 2009

Bimap. Bi-directional mapping/dictionary for Python?

Friday, April 10, 2009

Knapsack solution by OO Calc

A quick recap of the problem

OO Calc setup

The Solver

Comment

Memoization and stack use.

Mutual Recursion

target="_blank">Wot, no memoize?

A blown stack

Thursday, April 02, 2009

(Ab)use of Pythons in-built data structures

namedtuple

Printing namedtuples

Conclusion

Saturday, March 28, 2009

Huffman Encoding in Python

In Python

Encode/Decode Round-tripping

Saturday, March 21, 2009

Batch Process Runner in bash shell - Forgotten Enhancements

Why not in Python?

About Me

Followers

Subscribe Now: google

Go deh too!

whos.amung.us

Blog Archive

Wednesday, April 29, 2009

Tuesday, April 21, 2009

First create some test files to process

Now lets create a test executable to monitor

here is what the fd directory looks like

And here is a python script to monitor that fd directorieslink number 4 periodically

Thursday, April 16, 2009

Friday, April 10, 2009

A quick recap of the problem

OO Calc setup

The Solver

Comment

Mutual Recursion

target="_blank">Wot, no memoize?

A blown stack

Thursday, April 02, 2009

namedtuple

Printing namedtuples

Conclusion

Saturday, March 28, 2009

In Python

Encode/Decode Round-tripping

Saturday, March 21, 2009

Why not in Python?

About Me

Followers

Subscribe Now: google

Go deh too!

whos.amung.us

Blog Archive

And here is a python script to monitor that fd directories
link number 4 periodically