Irmen's blog

Installing PyCrypto on Windows (or how to build installers for libraries with C-modules)

PyCrypto is a Python Cryptography Toolkit, providing various cryptological things such as hashes, encryption, and random number utilities.

It contains various files that need to be compiled as a C-module.

On Linux and Mac OS this is no problem at all because they provide a working C compiler (gcc) but on Windows you're stuck. I've found that the easiest way to get this going is by installing the MingW gcc compiler. I don't think Cygwin wil work because that will introduce a dependency on the cygwin dlls, while MingW doesn't (it produces stand-alone binaries).

More to the point: I installed the GCC/MingW compiler using the bundled installer from TDM. It contains a very up to date set of gcc and companion tools, and installs with just a few clicks.

Add the MingW bin directory to your PATH and check if you have gcc available:

F:\> set PATH=C:\MingW\bin;%PATH%

F:\> gcc --version
gcc (TDM-2 mingw32) 4.4.1
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

That's it. Python's distutils is smart enough nowadays to be able to work with the MingW compiler (if you tell it to), so I can now simply type

F:\pycrypto-2.1.0b1> python setup.py build -c mingw32
F:\pycrypto-2.1.0b1> python setup.py bdist_wininst
F:\pycrypto-2.1.0b1> dir /b dist
pycrypto-2.1.0b1.win32-py2.6.exe

There you go, a windows installation package. You can either use that to install PyCrypto or just type python setup.py install at the prompt.

You can also tell distutils to always use mingw32 as a compiler by creating the file distutils.cfg in the distutils package directory in the Python standard lib, with the following contents:

[build]
compiler = mingw32

You no longer have to manually perform the build step and provide the -c mingw32 argument because distutils can now build automatically.

I think you need at least Python 2.5 to get all this to work as described above. I am using 2.6 and it's working flawlessly so far. Haven't tried it with older versions.

Priemgetallen

Beetje aan het prutsen geweest met een algoritme dat in Python op een efficiente manier priemgetallen berekent. De beste tot nu toe is deze:

import math

def primes(largest):
    bound=(largest+1)/2 # only use space for the odd numbers
    sieve=[True]*bound
    # sieve index i = odd integer 2i+1
    sieve[0]=False
    sq=int(round(largest**0.5))
    for i in xrange(1,sq/2+1):
        if sieve[i]:
            #r=len(range(i*2*(i+1), bound, 2*i+1))
            r=int(math.ceil((bound-i*2*(i+1))/(2.0*i+1)))
            sieve[i*2*(i+1)::2*i+1]=[False]*r
    result=[2]
    for i in xrange(bound):
        if sieve[i]: result.append(i+i+1)
    return result

Zeef van Eratosthenes, gebruikt alleen geheugen voor de oneven getallen (omdat alle even getallen behalve 2 zeker geen priemgetal zijn). Toch zijn er nog 2 problemen mee:

• neemt bij grote getallen nog behoorlijk veel geheugen in. Zo veel dat hij crasht met een memoryerror bij Spoj.
• hij begint altijd bij 2. Ben er nog niet achter of er wel een handige manier is om vanaf een ander getal te beginnen (niet met dit algoritme in elk geval).

edit: Ik heb wat extra algoritmes toegevoegd: een factorisatie functie, een functie om te checken of een gegeven getal priem is, en een nieuwe functie die de priemgetallen tussen min en max berekent. Deze laatste maakt gebruik van de voorberekende sieve als de range klein genoeg is, en anders gaat hij met factorisatie aan de slag. Het is nog niet voldoende om de Spoj te halen (hij is simpelweg te traag) maar voor niet al te grote getallen volstaat het wel denk ik. Voor meer info zie bijvoorbeeld Sieve en voor een snelle generator in C: Primegen.

Code volgt hieronder...

Is x+=1 threadsafe? No it isn't...

A question that popped up on comp.lang.python the other day:

I still can not believe that +=1 is not a thread safe operation. Any clue?

Yes, indeed, the statement

x+=1

is not thread-safe (or atomic, as you wish). Why the hell is that?

Well, the statement:

x+=1

is equivalent to:

x = x.__iadd__(1)

i.e. a function call followed by an assignment. The function call may execute atomicly, but the combination of this with the second operation (rebinding of the new integer object to x) isn't atomic.

So if we want to use simple counters across threads, they also need to be synchronised by proper lock objects.

While I'm not 100% sure about var++ in Java, I'm pretty sure that in C/C++ the statement is compiled into a single atomic machine instruction (such as INC). However in a multiprocessor / shared memory environment that could still result in wrong values. Better to always use a locking mechanism, even for seemingly simple things as incrementing a single counter...

simple tab completion

Use custom tab-completion in your console programs, like this:

#from http://effbot.org/librarybook/readline.htm
#You do it like this,

class Completer:
    def __init__(self, words):
        self.words = words
        self.prefix = None
    def complete(self, prefix, index):
        if prefix != self.prefix:
            self.matching_words = [w for w in self.words if w.startswith(prefix)]
            self.prefix = prefix
        try:
            return self.matching_words[index]
        except IndexError:
            return None

import readline

# a set of more or less interesting words
validanswers = [ 'yes', 'no', 'maybe', 'tuesday', 'never' ]

completer = Completer(validanswers)

readline.parse_and_bind("tab: complete")
readline.set_completer(completer.complete)

# try it out!
while True:
    answer = raw_input("Answer the Question: ")
    if answer not in validanswers:
       print "Wrong!"
    else:
       print "Your answer is",answer

Readline on Mac OS X

There are some problems with readline support in Python on Mac OS X. It is because Apple doesn't supply a readline on the system (or a broken one, I dont remember). In any case, you need to download and install a correct readline yourself.

In my case, I use the one that comes as part of Fink. (Alternatives exist, such as darwinports or getting and building just the readline code itself). To make the Python 2.5 setup tool recognise fink's readline, I had to run the configure script like this:

~$ LDFLAGS=-L/sw/lib CPPFLAGS=-I/sw/include ./configure

otherwise the fink include- and libfiles won't be found. Note that for Python 2.4 this is not needed, the setup.py from that version knows about Fink and will find the readline lib by itself...

(more info in this message on python-dev. Also see other article about command-line tab completion and readline)

Do Design Patterns still apply in Python?

(from a thread on comp.lang.python discussing Design Patterns in Python)

Roy Smith wrote:

In article <1141394593.588174.321660@z34g2000cwc.googlegroups.com>, "msoulier" wrote:

> For example, the Factory pattern is mostly to work around the fact that it's difficult in Java and C++ to dynamically load classes.

You're over-specifying. Most of most design patterns is to work around the fact that it's difficult in Java and C++ to do many things.

I voted +1 Quote of the week for this

Frog: NOTICE: Please disable blacklist auto-updating in Frog!!!

Concerning FROG:

I just found out that the owner of the MT-blacklist file, that Frog uses as anti-spammer blacklist, has blocked my IP address. Apparently because Frog downloads that file too often (default: once per 4 hours).

I urge the users of Frog to DISABLE THE AUTO-UPDATE FEATURE !

You risk the same IP-blockage as me, or you may already be blocked. Check this by looking at the last update timestamp of the blacklist, you can see this in Frog's about page. You can disable the auto-update feature by removing the lines in Frog's __init__.py file that create a scheduled update task. It's probably safest to put a bogus URL in antispam/blacklist.py too. If you need more information, just ask. Sorry for the trouble.

Fuzzy (approximate) string compare

Met Fuzzy string compare bedoel ik het vergelijken van twee strings en dan een uitkomst krijgen die aangeeft hoe veel de strings op elkaar lijken. Dat wil zeggen, het is dus geen absolute string compare (die alleen maar aangeeft of 2 strings hetzelfde zijn of niet), maar een meer kwantitatieve string vergelijking.

Het kan gebruikt worden om bijvoorbeeld typefouten uit commando's te halen, een bepaalde vorm van spellingscontrole, of voor andere natuurlijke-taal toepassingen.

Voor Python zijn er een aantal modules beschikbaar die een fuzzy string compare functie bieden.

away with the Global Interpreter Lock

The GIL is bad for Python on multi-processor systems.

Command-line tab completion in standard Python shell

To enable 'tab-completion' on the command line of the default Python shell, put this in ~/.pythonrc, and setup the PYTHONSTARTUP environment variable to point to it: export PYTHONSTARTUP=~/.pythonrc

# ~/.pythonrc
# enable syntax completion
try:
    import readline
except ImportError:
    print "Module readline not available."
else:
    import rlcompleter
    readline.parse_and_bind("tab: complete")

It needs the GNU readline library and so probably doesn't work on Windows. On Mac OS X there are some issues with readline too, see other article.

For even fancier stuff, use the following startup file: .pystartup in your home-dir

# Add auto-completion and a stored history file of commands to your Python
# interactive interpreter. Requires Python 2.0+, readline. Autocomplete is
# bound to the Esc key by default (you can change it - see readline docs).
#
# Store the file in ~/.pystartup, and set an environment variable to point
# to it, e.g. "export PYTHONSTARTUP=/max/home/itamar/.pystartup" in bash.
#
# Note that PYTHONSTARTUP does *not* expand "~", so you have to put in the
# full path to your home directory.

import atexit
import os
import readline
import rlcompleter

historyPath = os.path.expanduser("~/.pyhistory")
historyTmp = os.path.expanduser("~/.pyhisttmp.py")

endMarkerStr= "# # # histDUMP # # #"

saveMacro= "import readline; readline.write_history_file('"+historyTmp+"'); \
    print '####>>>>>>>>>>'; print ''.join(filter(lambda lineP: \
    not lineP.strip().endswith('"+endMarkerStr+"'),  \
    open('"+historyTmp+"').readlines())[:])+'####<<<<<<<<<<'"+endMarkerStr

readline.parse_and_bind('tab: complete')
readline.parse_and_bind('\C-w: "'+saveMacro+'"')

def save_history(historyPath=historyPath, endMarkerStr=endMarkerStr):
    import readline
    readline.write_history_file(historyPath)
    # Now filter out those line containing the saveMacro
    lines= filter(lambda lineP, endMarkerStr=endMarkerStr:
                      not lineP.strip().endswith(endMarkerStr), open(historyPath).readlines())
    open(historyPath, 'w+').write(''.join(lines))

if os.path.exists(historyPath):
    readline.read_history_file(historyPath)

atexit.register(save_history)

del os, atexit, readline, rlcompleter, save_history, historyPath
del historyTmp, endMarkerStr, saveMacro

Additionaly you need to ~# export PYTHONSTARTUP=/root/.pystartup. Then you will have:

• Pressing tab completes the input like common unix-shells.
• Pressing CTRL-w gives You an python code to print the history-file (or parts of it -- there's a [:] in the command that You can replace by [-50:]; which will give you the last 50 lines)

Quicksort

Quicksort using list comprehensions:

import random

def quicksort(lst): 
     if len(lst) <= 1: return lst 
     pivot = lst[random.randrange(len(lst))]
      
     left =   [x for x in lst if x <  pivot] 
     middle = [x for x in lst if x == pivot] 
     right =  [x for x in lst if x >  pivot] 

     return quicksort(left) + middle + quicksort(right)