python learning map /reduce

a = [1, 2, 3]
b = [4, 5, 6, 7]
c = [8, 9, 1, 2, 3]
L = map(lambda x:len(x), [a, b, c])

# L == [3, 4, 5]
N = reduce(lambda x, y: x+y, L)
# N == 12
# Or, if we want to be fancy and do it in one line
N = reduce(lambda x, y: x+y, map(lambda x:len(x), [a, b, c]))


I am going to implement a generic MapReduce framework using Python multiprocess module. This module will exploit the multi-core environment better.
For data exchanges, I will use the tmpfiles.

how to shuffle data in out-of-core manner?

When the data is very huge and we cannot put all the data in the main
memory, the current shuffle methods that assume all the data resides in memory could no longer be used directly.

Here we use a method similar to the way in shuffling the cards ( similar to mergesort):
while( iteration < setvalue)
{
tmpfile_set = split(datafile)
datafile = merge(tmpfile_set)
delete(tmpfile_set)
iteration <= iteration + 1
}

Another way to do this is to use fopen64 function. This function is used to
open large files that could not be loaded into the memory at once. We can find
a way to shuffle the data as follows:

1. find a permutation of the [1...N], where N is the total number of records.
Suppose the permutation is [n1, n2, n3,..., nN]
2. try to put the ith record in the original file to the ni th place in the new file.

In this method, we would need to consider the following issues:

a. the fseek function is needed in step 2. If missing values exist, then the starting point of a record is difficult to find.

b. the running time of this algorithm seems a problem coz fseek may cross several blocks? I do not know how to analysis the time now.

After several days' testing and running

The backup system could work smoothly now. I made several changes to the system, including storing the filelist in the server and retrieve the filelist from the sever to the client for comparison.

python exceptions

python: try except raise
java : try catch throw finally?
The mechnisms of the exceptions are the same.

If we want to catch multiple exceptions:
A try statement may have more than one except clause, to specify handlers for different exceptions. At most one handler will be executed. Handlers only handle exceptions that occur in the corresponding try clause, not in other handlers of the same try statement. An except clause may name multiple exceptions as a parenthesized tuple, for example:
... except (RuntimeError, TypeError, NameError):
... pass

How to print the exception info inside the except statement
>>> try:... raise Exception('spam', 'eggs')
... except Exception as inst:
... print type(inst) # the exception instance
... print inst.args # arguments stored in .args
... print inst # __str__ allows args to printed directly
... x, y = inst # __getitem__ allows args to be unpacked directly
... print 'x =', x
... print 'y =', y

Two ways to get the index and the value from List in Python

There are two ways to get both the index and the value from the List.
One is :

    for index, item in enumerate(L):
      print index, item

The other is:

    for index in range(len(L)):
      print index, L[index]

Still need to work hard on research. Seems the proof is wrong.

The index method does a linear search, and stops at the first matching item. If no matching item is found, it raises a ValueError exception.

try:
i = L.index(value)
except ValueError:
i = -1 # no match

To get the index for all matching items, you can use a loop, and pass in a start index:

i = -1
try:
while 1:
i = L.index(value, i+1)
print "match at", i
except ValueError:
pass

iterating over datastructures in python

1. To iterate over a dictionary in Python:
>>> params = {"server":"mpilgrim", "database":"master", "uid":"sa", "pwd":"secret"}
>>> for (u, v) in params:
... print u+" " +v
...
pwd secret
database master
uid sa
server mpilgrim

2. To iterate over a list:

>>> params = ["server", "mpilgrim", "database", "master", "uid", "sa", "pwd", "secret"]
>>> for elem in params:
... print elem
server
mpilgrim
database
master
uid
sa
pwd
secret

To get the index of the element at the same time, use the following format:
>>> params = ["server", "mpilgrim", "database", "master", "uid", "sa", "pwd", "secret"]
>>> for i in range(len(params)):
... print (i, params[i])
...
(0, 'server')
(1, 'mpilgrim')
(2, 'database')
(3, 'master')
(4, 'uid')
(5, 'sa')
(6, 'pwd')
(7, 'secret')

3. To iterate over a tuple:
the same as the list

4. To iterate over a set:
The same as the list

The python debugger

Python has a debugging tool very similar to the gdb. This post would show how to start the debugger and the basic commands.

Starting the debugger
There are mainly two ways to start the debugger.
One is in the Python interpreter:

The debugger’s prompt is (Pdb). Typical usage to run a program under control of the debugger is:

>>> import pdb
>>> import mymodule
>>> pdb.run('mymodule.test()')
> (0)?()
(Pdb) continue
> (1)?()
(Pdb) continue
NameError: 'spam'
> (1)?()
(Pdb)

The other is from the command lines:

pdb.py can also be invoked as a script to debug other scripts. 
For example:python -m pdb myscript.py

Some basic commands include:
1. Setting and removing breakpoints:
break(b) + line no, clear (cl) + break + breakid
2. checking all the breakpoints:
break
3. step into:
step(s)
4. step over:
next (n)
5. go to next breakpoint:
continue(c)
6. go to the end of the function:
r
7. jump to certain place
jump(j)
8. list the current code
list(l)
9. change the variable value of the code:
as Python is a script language, the value can be changed in the running time. just assign a new value to the language!

10. printing
p
how to print the lists, dictionares, sets?
print is a statement in the Python, not in the pdb module.

11. How to inspect the statement inside a loop?
Using conditions
condition bpnumber. Here condition is any expression that could be evaluated. It must be evaluated as true if the breakpoint takes effect.

list comprehensions and looping techniques

List Comprehensions
Each list comprehension consists of an expression followed by a for clause, then zero or more for or if clauses. The result will be a list resulting from evaluating the expression in the context of the for and if clauses which follow it. If the expression would evaluate to a tuple, it must be parenthesized.

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
#the format is [ (exp) for ... in ...]
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x <>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec] # error - parens required for tuples
File "", line 1, in ?
[x, x**2 for x in vec]
^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

The looping on the dictionary and the sequences

When looping through dictionaries, the key and corresponding value can be retrieved at the same time using the iteritems() method.

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.iteritems():
...     print k, v
...
gallahad the pure
robin the brave

When looping through a sequence, the position index and corresponding value can be retrieved at the same time using the enumerate() function.

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print i, v
...
0 tic
1 tac
2 toe

To loop over a sequence in sorted order, use the sorted() function which returns a new sorted list while leaving the source unaltered.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print f
...
apple
banana
orange
pear

python regular expression-Grouping

Metacharacters are not active inside classes. For example, [akm$] will match any of the characters "a", "k", "m", or "$"; "$" is usually a metacharacter, but inside a character class it's stripped of its special nature.

The python provides very powerful grouping facilities. When you get a matching object,
you can apply the group(index) or groups() method on it.
The groups() is the same as {group(1), group(2), ...}

The syntax for a named group is one of the Python-specific extensions: (?P...). name is, obviously, the name of the group. Except for associating a name with a group, named groups also behave identically to capturing groups. The MatchObject methods that deal with capturing groups all accept either integers, to refer to groups by number, or a string containing the group name. Named groups are still given numbers, so you can retrieve information about a group in two ways:

>>> p = re.compile(r'(?P\b\w+\b)')
>>> m = p.search( '(((( Lots of punctuation )))' )
>>> m.group('word')
'Lots'
>>> m.group(1)
'Lots'
You can refer to the previous named groups by their names:
>>> p = re.compile(r'(?P\b\w+)\s+(?P=word)')
>>> p.search('Paris in the the spring').group()
'the the'

p.s.:
Be noted that both match and search will stop once they find ONE substring that fits the pattern.

One example about the grouping:
This is an example I met in the recovery and backup system.
Suppose we want to split the filename
2009-07-22-23-09.tar.gz (year-month-day-hour-minute.tar.gz)
We want to get the year, month, day, hour and minute when this file was created. How to write the regular expression?
the pattern should be

?P\d{4})-(?P\d{2})-(?P\d{2})-(?P\d{2})-(?P\d{2})\.tar\.gz
The file name is grouped into five parts, and we can retrieve each part by invoking the group(name) function.

A better example using VERBOSE:
pat = re.compile(r"""
\s* # Skip leading whitespace
(?P

[^:]+) # Header name
\s* : # Whitespace, and a colon
(?P.*?) # The header's value -- *? used to
# lose the following trailing whitespace
\s*$ # Trailing whitespace to end-of-line
""", re.VERBOSE)

plan 4.29

I had some free time today and watched the soccer game. MU was really good and Arsenal did not make it today. I still insist Arsenal will win in the semifinals. Go Arsenal! Goal! Goal!

Here are about some interesting posts in kdnuggets. List several here.
One is about the performance comparison between the mapreduce and the parallel database. The paper indicated that parallel databases has a better performance than mapreduce. I have not look into that paper, but I guess mapreduce may achieve a better reliability and fault tolerance, and this is the main reason Google deployed it. I will go on to look at this topic.

The other is about a interesting application about the cloud computing. This is about Google again. I have to say I am not a fan of Google, but some of its applications are really interesting and worth trying. Google presented a platform called Google App Engine, where developers can build their own apps on this. If you need more resources (hard disks, cpu cycles...), you can pay Google and get things you need. Current two languages, java and Python are supported. Interesting.

Will cloud computing be the next hotspot in the data mining communities? It might be true when we are talking about the pegabytes of data, where large amount of computing resources are needed. Privacy preservation is an issue in cloud computing. Any way, this trends is worth tracing in the future.

Python substitution

>>> re.sub(r'def\s+([a-zA-Z_][a-zA-Z_0-9]*)\s*\(\s*\):',
... r'static PyObject*\npy_\1(void)\n{',
... 'def myfunc():')
The answer is : 'static PyObject*\npy_myfunc(void)\n{'

re.sub(pattern, repl, string):
The substitution has two steps:
a. Using pattern to match the string; find the left-most occurance of the pattern. If no substring matches the pattern, the sub func returns the orginal string without modification.

b. Replace the matched substring with the repl. The \number is replaced accordingly.

The use of re.VERBOSE to make the regular exp look nicer.
Whitespace within the pattern is ignored, except when in a character class or preceded by an unescaped backslash, and, when a line contains a '#' neither in a character class or preceded by an unescaped backslash, all characters from the leftmost such '#' through the end of the line are ignored.
That means that the two following regular expression objects that match a decimal number are functionally equal:
a = re.compile(r"""\d + # the integral part
\. # the decimal point
\d * # some fractional digits""", re.X)

b = re.compile(r"\d+\.\d*")

More about regular expression: http://docs.activestate.com/komodo/4.4/regex-intro.html

Python again!

\s means the white spaces. It is the same as [ \t\n\r\f\v].
re.sub(pattern, replace_string, original_string)

>>> re.sub(r'def\s+([a-zA-Z_][a-zA-Z_0-9]*)\s*\(\s*\):',
...r'static PyObject*\npy_\1(void)\n{',
...'def myfunc():')

The result is 'static PyObject*\npy_myfunc(void)\n{'

using raw stirng to simplify the problem.
'\\\\section' = r'\\section'
'\\section' =r'\section'

The matching for the phone numbers:

>>> phonePattern = re.compile(r'''
# don't match beginning of string, number can start anywhere
(\d{3}) # area code is 3 digits (e.g. '800')
\D* # optional separator is any number of non-digits
(\d{3}) # trunk is 3 digits (e.g. '555')
\D* # optional separator
(\d{4}) # rest of number is 4 digits (e.g. '1212')
\D* # optional separator
(\d*) # extension is optional and can be any number of digits
$ # end of string
''', re.VERBOSE)
>>> phonePattern.search('work 1-(800) 555.1212 #1234').groups()
('800', '555', '1212', '1234')
>>> phonePattern.search('800-555-1212')
('800', '555', '1212', '')

>>> po = re.compile(r'\w*?e') #nongreedy matching
>>> mo = re.search(po, r'the the')
>>> re.findall(po, r'the the')
result: ['the', 'the']