## Friday, January 23, 2009

### Higher Order Perl (Python Style) : Chapter 3 - Caching and Memoization

`### 3.1 Caching Fixes Recursion# sub RGB_to_CMYK {#   my (\$r, \$g, \$b) = @_;#   my (\$c, \$m, \$y) = (255-\$r, 255-\$g, 255-\$b);#   my \$k = \$c < \$m ? (\$c < \$y ? \$c : \$y)#                   : (\$m < \$y ? \$m : \$y);  # Minimum#   for (\$c, \$m, \$y) { \$_ -= \$k }#   [\$c, \$m, \$y, \$k];# }def rgb_to_cmyk(r,g,b):   c, m, y = 255-r, 255-g, 255-b   k = min([c,m,y])   c, m, y = c - k, m - k, y - k   return c, m, y, k# my %cache;# sub RGB_to_CMYK {#   my (\$r, \$g, \$b) = @_;#   my \$key = join ',', \$r, \$g, \$b;#   return \$cache{\$key} if exists \$cache{\$key};#   my (\$c, \$m, \$y) = (255-\$r, 255-\$g, 255-\$b);#   my \$k = \$c < \$m ? (\$c < \$y ? \$c : \$y)#                   : (\$m < \$y ? \$m : \$y);  # Minimum#   for (\$c, \$m, \$y) { \$_ -= \$k }#   return \$cache{\$key} = [\$c, \$m, \$y, \$k];# }CACHE = {}def rgb_to_cmyk(r,g,b):   if (r,g,b) not in CACHE:       c, m, y = 255-r, 255-g, 255-b       k = min([c,m,y])       c, m, y = c - k, m - k, y - k       CACHE[(r,g,b)] = (c,m,y,k)   return CACHE[(r,g,b)]# Compute the number of pairs of rabbits alive in month n# sub fib {#    my (\$month) = @_;#    if (\$month < 2) { 1 }#    else {#        fib(\$month-1) + fib(\$month-2);#    }# }def fib(month):   if month < 2:       return 1   else:       return fib(month - 1) + fib(month - 2)### 3.2 Inline Caching# # Compute the number of pairs of rabbits alive in month n# { my %cache;#   sub fib {#     my (\$month) = @_;#     unless (exists \$cache{\$month}) {#       if (\$month < 2) { \$cache{\$month} = 1 }#       else {#         \$cache{\$month} = fib(\$month-1) + fib(\$month-2);#       }#     }#     return \$cache{\$month};#   }# }# NOTE: we include the function itself as part of#       the hash key since python can't do the#       scoping technique above w/o hackery (AFAIK).#       Of course the more natural python way#       would probably be just to use a decoratorCACHE = {}def fib(month):   if (fib, month) not in CACHE:       if month < 2:           CACHE[(fib, month)] = 1       else:           CACHE[(fib, month)] = fib(month - 1) + fib(month - 2)   return CACHE[(fib, month)]# sub fib {#   my %cache;#   ...# }def fib(month):   CACHE = {}   ...### 3.3 Good Ideas# sub some_function {#   \$result = some computation involving @_;#   return \$result;# }def some_function(*x):   result = some computation involving x   return result# { my %cache;#   sub some_function_with_caching {#     my \$key = join ',', @_;#     return \$cache{\$key} if exists \$cache{\$key};#     \$result = the same computation involving @_;#     return \$cache{\$key} = \$result;#   }# }CACHE = {}def some_function_with_caching(*x):   key = (some_function_with_caching, x)   if key not in CACHE:       CACHE[key] = the same computation involving *x   return CACHE[key]### 3.4 Memoization# use Memoize;# memoize 'fib';# # Compute the number of pairs of rabbits alive in month n# sub fib {#   my (\$month) = @_;#   if (\$month < 2) { 1 }#   else {#       fib(\$month-1) + fib(\$month-2);#   }# }# Just for sake of argument let's pretend we have a "memoize"# module that provides a memoize decorator@memoizedef fib(month):   if month < 2:       return 1   else:       return fib(month - 1) + fib(month - 2)### 3.5 The Memoize Module# sub memoize {#   my (\$func) = @_;#   my %cache;#   my \$stub = sub {#     my \$key = join ',', @_;#     \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#     return \$cache{\$key};#   };#   return \$stub;# }# One reasonable way to do this in python is as a decorator.  To keep# things simple we'll leave out **kwargs since we can't (simply) use# dicts as parts of keys.  We also assume for now that args contains# only things that can be in a dict keydef memoize(func):   CACHE = {}   def memoized_func(*args):       if args not in CACHE:           CACHE[args] = func(*args)       return CACHE[args]   return memoized_func# NOTE: running the above with fib actually gave# "RuntimeError: maximum recursion depth exceeded"# for month = 1000.  But if you do some smaller# values first to "seed" it it will handle the# larger values.#\$fastfib = memoize(\&fib);@memoizedef fib(month):   ....# or# fastfib = memoize(fib)# sub make_counter {#   my \$n = shift;#   return sub { print "n is ", \$n++ };# }# my \$x = make_counter(7);# my \$y = make_counter(20);# We cheat a little here since python's scoping# won't let's us work with the n directlydef make_counter(n):   x = [n]   def counter():       print "n is", x       x += 1   return counterx = make_counter(7)y = make_counter(20)### 3.6 Caveats# use Memoize;# sub iota {#   my \$n = shift;#   return [1 .. \$n];# }# memoize 'iota';# \$i10 = iota(10);# \$j10 = iota(10);# pop @\$i10;# print @\$j10;@memoizedef iota(n):   return range(n)i10 = iota(10)j10 = iota(10)i10.pop()print j10# package Octopus;# sub new {#   my (\$class, %args) = @_;#   \$args{tentacles} = 8;#   bless \%args => \$class;# }# sub name {#   my \$self = shift;#   if (@_) { \$self->{name} = shift }#   \$self->{name};# }# my \$junko = Octopus->new(favorite_food => "crab cakes");# \$junko->name("Junko");# my \$fenchurch = Octopus->new(favorite_food => "crab cakes");# \$fenchurch->name("Fenchurch");# # This prints "Fenchurch" -- oops!# print "The name of the FIRST octopus is ", \$junko->name, "\n";class Octopus(object):   def __init__(self, **kwargs):       self.tentacles = 8       self.__dict__.update(kwargs)   def name(self, new_name=None):       if new_name != None:           self.name = new_name       return self.name# OK, this one has me stumped.  The text says# that "new" was memoized, but I'm not seeing it# Either a typo on the books part or a thinko on mine# But the lesson about caching mutable items is well taken#@result = sort { -M \$a <=> -M \$b } @files;result = sorted(files, key=(lambda x: os.path.getmtime(x)))### 3.7 Key Generation#my \$key = join ',', @_;key = ",".join([str(x) for x in key_list])# or just use a tuple and avoid problems in the first placekey = tuple(key_list)# my @args = @_;# s/([\\,])/\\\$1/g for @args;# my \$key = join ",", @args;key = ",".join([str(x).replace(",","\,").replace("\\","\\\\") for x in key_list])# sub memoize {#   my (\$func, \$keygen) = @_;#   my %cache;#   my \$stub = sub {#     my \$key = \$keygen ? \$keygen->(@_) : join ',', @_;#     \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#     return \$cache{\$key};#   };#   return \$stub;# }# There are other ways to do this, but we want# to stay close to the perl version.  Now# memoize will need to be invoked as#@memoize() # need the "()" here#@memoize(keygen_func)def memoize(keygen=None):   CACHE = {}   def outer_func(func):       def inner_func(*args):           key = args           if keygen:               key = keygen(args)           if key not in CACHE:               CACHE[key] = func(*args)           return CACHE[key]       return inner_func   return outer_func# sub memoize {#   my (\$func, \$keygen) = @_;#   my %cache;#   my \$stub = \$keygen ?#     sub { my \$key = \$keygen->(@_);#           \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#           return \$cache{\$key};#         }#   :#     sub { my \$key = join ',', @_;#           \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#           return \$cache{\$key};#         }#   ;#   return \$stub;# }def memoize(keygen=None):   CACHE = {}   def outer_func(func):       def inner_func_no_keygen(*args):           key = args           if key not in CACHE:               CACHE[key] = func(*args)           return CACHE[key]       def inner_func_with_keygen(*args):           key = keygen(args)           if key not in CACHE:               CACHE[key] = func(*args)           return CACHE[key]       return keygen and inner_func_with_keygen or inner_func_no_keygen   return outer_func# \$memoized = memoize(\&fib, q{my @args = @_;#                              s/([\\,])/\\\$1/g for @args;#                              join ',', @args;#                             });# sub memoize {#   my (\$func, \$keygen) = @_;#   \$keygen ||= q{join ',', @_};#   my %cache;#   my \$newcode = q{#     sub { my \$key = do { KEYGEN };#           \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#           return \$cache{\$key};#         }#   };#   \$newcode =~ s/KEYGEN/\$keygen/g;#   return eval \$newcode;# }# \$keygen ||= 'join \',\', @_';# my \$newcode = "#   sub { my \\$key = do { \$keygen };#         \\$cache{\\$key} = \\$func->(\@_) unless exists \\$cache{\\$key};#         return \\$cache{\\$key};#       }# ";# sub memoize {#   my (\$func, \$keygen) = @_;#   my \$keyfunc;#   if (\$keygen eq '') {#     \$keygen = q{join ',', @_}#   } elsif (UNIVERSAL::isa(\$keygen, 'CODE')) {#     \$keyfunc = \$keygen;#     \$keygen = q{\$keyfunc->(@_)};#   }#   my %cache;#   my \$newcode = q{#     sub { my \$key = do { KEYGEN };#           \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#           return \$cache{\$key};#         }#   };#   \$newcode = ̃ s/KEYGEN/\$keygen/g;#   return eval \$newcode;# }# if (ref(\$keygen) eq 'CODE') { ... }"""UNCLE!  This seems too far off the path for a sane python translation.Actually I can think of a way to do it, you just wouldn't, so unlessthere is a great public outcry, I will just skip trying to force thisdown the python's throat."""# sub example {#   my %args = @_;#   \$args{A} = 32 unless defined \$args{A};#   \$args{B} = 17 unless defined \$args{B};#   # ...# }def example(**args):   args.setdefault("A", 32)   args.setdefault("B", 17)   ## example(C => 99);# example(C => 99, A => 32);# example(A => 32, C => 99);# example(B => 17, C => 99);# example(C => 99, B => 17);# example(A => 32, C => 99, B => 17);# example(B => 17, A => 32, C => 99);# (etc.)example(C=99)example(C=99, A=32)example(A=32, C=99)example(B=17, C=99)example(C=99, B=17)example(A=32, C=99, B=17)example(B=17, A=32, C=99)(etc.)# NOTE: the problem in python is that#       we just can't use dicts as a hash#       otherwise this would be a no brainer# sub {#   my %h = @_;#   \$h{A} = 32 unless defined \$h{A};#   \$h{B} = 17 unless defined \$h{B};#   join ",", @h{'A','B','C'};# }# we give this function a name so that we don't# have to work around python's lambda limitationsdef _keygen(a, h):   h.setdefault("A", 32)   h.setdefault("B", 17)   # a tuple key is probably more natural   return tuple([x for x in sorted(h.items())])   # but we can make a string just as simply   # return ','.join([str(x) for x in sorted(args.items())])# keygen only has to work over the set of expected values so we can go ahead and# do something like: # have the key be a tuple of (args, kwargs)# where kwargs has been adapted to a tuple of key,value pair tuples# BUT now our keygen needs to handle *Both* types of inputsdef memoize(keygen=None):   CACHE = {}   def outer_func(func):       def inner_func(*args, **kwargs):           kwargs_ = tuple(sorted(kwargs.items()))           key = (args, kwargs_)           if keygen:               key = keygen(args, kwargs)           if key not in CACHE:               print "updating cache:", key               CACHE[key] = func(*args, **kwargs)           return CACHE[key]       return inner_func   return outer_func# sub example {#   my (\$a, \$b, \$c) = @_;#   \$a = 32 unless defined \$a;#   \$b = 17 unless defined \$b;#   # more calculation here ...# }def example(a=32, b=17,c=None):   # more calculation here ...# my (\$a, \$b, \$c) = @_;# \$a = 32 unless defined \$a;# \$b = 17 unless defined \$b;# join ',', \$a, \$b, \$c;# first three lines handled by machinery of argument passing in pythonreturn ",".join([str(x) for x in (a,b,c)])# sub { my \$key = do { \$_ = 32 unless defined \$_;#                      \$_ = 17 unless defined \$_;#                      join ',', @_;#                    };#       \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#       return \$cache{\$key};#     }# Hmm... very likely I'm missing a sublety here but# is seems that python's default args already handles# this case.  Plus the fact that (if I'm understanding# correctly), python doesn't map well to the "do { }"# syntax.  I'll punt for now.# sub set_to_57 {#   \$_ = 57;# }# my \$x = 119;# set_to_57(\$x);# you can't take advantage of this (or get bit by, depending# on your perspective) in python, but cause the args are pass# by value.# sub safe_function {#    my (\$n) = @_;#    \$n = 57; # does *not* set \$x to 57# }# my \$x = 119;# safe_function(\$x);def safe_function(n):   n = 57x = 119safe_function(x)# memoize(\&example, q{#   my (\$a, \$b, \$c) = @_;#   \$a = 32 unless defined \$a;#   \$b = 17 unless defined \$b;#   @_ = (\$a, \$b, \$c);         # line 5#   join ',', @_;# });# We avoid sending the keygen function as a string# since it is too unpythonic.# Here we are assuming that the arguments are positional# and "None" if not available.  Usually we would use# key word args in this situationdef _keygen(args, kwargs):   print "args=",args,"kwargs=",kwargs   a = args == None and 32 or args   b = args == None and 17 or args   c = args   return (a,b,c)   # or return ",".join([str(x) for x in (a,b,c)])@memoize(_keygen)def exercise(*args):   a,b,c = (args + [None]*3)[:3]   ...# sub is_in {#   my (\$needle, \$haystack) = @_;#   for my \$item (@\$haystack) {#     return 1 if \$item == \$needle;#   }#   return;# }def is_in(needle, haystack):   for item in haystack:       if item == needle:           return True   return False# if (is_in(\$my_id, \@employee_ids)) { ... }if is_in(my_id, employee_ids):   ...#sub { join ",", \$_, @{\$_} }# In python the most obvious solution here# is again to just use tuple()# sub find_share {#   my (\$target, \$treasures) = @_;#   return [] if \$target == 0;#   return    if \$target < 0 || @\$treasures == 0;#   my (\$first, @rest) = @\$treasures;#   my \$solution = find_share(\$target-\$first, \@rest);#   return [\$first, @\$solution] if \$solution;#   return         find_share(\$target       , \@rest);# }def find_share(target, treasures):   if target == 0:       return []   if target < 0 or len(treasures) == 0:       return   first, rest = treasures, treasures[1:]   solution = find_share(target-first, rest)   if solution != None:       return [first] + solution   return find_share(target, rest)# sub delivery_charge {#   my (\$quantity_ordered) = @_;#   my (\$hour, \$day_of_week) = (localtime)[2,6];#   # perform complex computation involving \$weight, \$gross_cost,#   #     \$hour, \$day_of_week, and \$quantity_ordered#   # ...#   return \$delivery_charge;# }import timedef delivery_charge(quantity_ordered):   localtime = time.localtime()   hour, day_of_week = localtime, localtime   # perform complex computation involving \$weight, \$gross_cost,   #     \$hour, \$day_of_week, and \$quantity_ordered   # ...   return delivery_charge# sub delivery_charge_key {#   join ',', @_, (localtime)[2,6];# }def delivery_charge_key(quantity_ordered):   localtime = time.localtime()   return ",".join([str(x) for x in (quantity_ordered,localtime, localtime)])   ## or just return (quantity_ordered,localtime, localtime)# sub delivery_charge_key {#   my (\$hour, \$day_of_week) = (localtime)[2,6];#   my \$weekend = \$day_of_week == 0 || \$day_of_week == 6;#   join ',', @_, \$hour, \$weekend;# }def delivery_charge_key(quantity_ordered):   localtime = time.localtime()   hour, day_of_week = localtime, localtime   weekend = day_of_week in (0,6)   return ",".join([str(x) for x in (quantity_ordered, hour, weekend)])   ## or just return (quantity_ordered, hour, weekend)### 3.8 Caching in Object Methods# package Investor;# # Compute total amount currently invested# sub total {#   my \$self = shift;#   # ... complex computation performed here ...#   return \$total;# }class Investor(object):   def total(self):       # ... complex computation performed here ...       return total# # Compute total amount currently invested# { my %cache;#   sub total {#     my \$self = shift;#     return \$cache{\$self} if exists \$cache{\$self};#     # ... complex computation performed here ...#     return \$cache{\$self} = \$total;#   }# }# One way to simulate this in python would be to# have a cache "class" variableclass Investor(object):   _cache = {}   def total(self):       # ... complex computation performed here ...\       key = (self, Investor.total)       if key not in Investor._cache:           # ... complex computation performed here ...           Investor._cache[key] = total       return Investor._cache[key]# # here 90,000 is returned from the cache# \$old_total = \$old_object->total();# undef \$old_object;# \$new_object = Investor->new();# \$new_total = \$new_object->total();old_total = old_object.total()del old_objectnew_object = Investor()new_total = new_object.total()# NOTE: in addition to manually invoked "destroy"# method recommended in the text, we could# also have __del__ method, though that might not be# reliable.  Also could just stick in a unix timestamp# as part of the key so new objects with same memory location# won't be confusing# # Compute total amount currently invested# sub total {#   my \$self = shift;#   return \$self->{cached_total} if exists \$self->{cached_total};#   # ... complex computation performed here ...#   return \$self->{cached_total} = \$total;# }def total(self):   if self.cached_total == None:       # ... complex computation performed here ...       self.cached_total = total   return self.cached_total# # Compute total amount currently invested# { my %cache;#   sub total {#     my \$self = shift;#     return \$cache{\$self} if exists \$cache{\$self};#     # ... complex computation performed here ...#     return \$cache{\$self} = \$total;#   }#   sub expire_total {#     my \$self = shift;#     delete \$cache{\$self};#   }# }# sub invest {#   my (\$self, \$amount, ...) = @_;#   \$self->expire_total;#   ...# }class Investor(object):   _cache = {}   def total(self):       # ... complex computation performed here ...\       key = (self, Investor.total)       if key not in Investor._cache:           # ... complex computation performed here ...           Investor._cache[key] = total       return Investor._cache[key]   def expire_total(self):       key = (self, Investor.total)       del Investor._cache[key]   def invest(self, ammount, ...):       self.expire_total()       ...# # Compute total amount currently invested# sub total {#   my \$self = shift;#   return \$self->{cached_total} if exists \$self->{cached_total};#   # ... complex computation performed here ...#   return \$self->{cached_total} = \$total;# }# sub invest {#   my (\$self, \$amount, ...) = @_;#   delete \$self->{cached_total};#   ...# }def total(self):   if self.cached_total == None:       # ... complex computation performed here ...       self.cached_total = total   return self.cached_totaldef invest(self, amount, ...):   self.cached_total = None   ...# sub memoize_method {#   my (\$method, \$key) = @_;#   return sub {#     my \$self = shift;#     return \$self->{\$key} if exists \$self->{\$key};#     return \$self->{\$key} = \$method->(\$self, @_);#   };# }# As a decoratordef memoize_method(key):   def outter(method):       def inner(self):           if self.__dict__.get(key) == None:               print "cache miss:", method, key, self               self.__dict__[key] = method(self)           return self.__dict__[key]       return inner   return outter#*Investor::total = memoize_method(\&Investor::total, 'cached_total');#\$investor_bob->total;@memoize_method("cached_total")def total(self):   ...investor_bob.total()# \$memoized_total = memoize_method(\&Investor::total, 'cached_total');# \$investor_bob->\$memoized_total;# I suppose you could also use the pre-decorator syntax:def total(self):   ...total = memoize_method("cached_total")(total)investor_bob.total()### 3.9 Persistent Caches# use DB_File;# sub memoize {#   my (\$func, \$keygen, \$file) = @_;#   my %cache;#   if (defined \$file) {#     tie %cache => 'DB_File', \$file, O_RDWR|O_CREAT, 0666#       or die "Couldn’t access cache file \$file: \$!; aborting";#   }#   my \$stub = sub {#     my \$key = \$keygen ? \$keygen->(@_) : join ',', @_;#     \$cache{\$key} = \$func->(@_) unless exists \$cache{\$key};#     return \$cache{\$key};#   };#   return \$stub;# }import anydbmdef memoize(keygen=None, cache_file=None):   if cache_file:       cache = anydbm.open(cache_file, 'c')   else:       cache = {}   def outer_func(func):       def inner_func(*args):           key = str(args)           if keygen:               key = keygen(args)           if key not in cache:               cache[key] = func(*args)           return cache[key]       return inner_func   return outer_func# sub memoize {#     my (\$func, \$keygen, \$cache) = @_;#     \$cache = {} unless defined \$cache;#     my \$stub = sub {#        my \$key = \$keygen ? \$keygen->(@_) : join ',', @_;#        \$cache->{\$key} = \$func->(@_) unless exists \$cache->{\$key};#        return \$cache->{\$key};#     };#     return \$stub;# }def memoize(keygen=None, cache=None):   if cache == None:       cache = {}   def outer_func(func):       def inner_func(*args):           key = str(args)           if keygen:               key = keygen(args)           if key not in cache:               cache[key] = func(*args)           return cache[key]       return inner_func   return outer_func### 3.10 Alternatives To Memoization# @sorted_numbers = sort { \$a <=> \$b } @numbers;# This is default behavior for sortsorted_numbers = sorted(numbers)# @sorted_numbers = sort numerically @numbers;# sub numerically { \$a <=> \$b }sorted_numbers = sorted(numbers, cmp=numerically)def numerically(a,b):   return cmp(a,b)# @sorted_dates = sort chronologically @dates;# %m2n =#    ( jan =>  1, feb =>  2, mar =>  3,#      apr =>  4, may =>  5, jun =>  6,#      jul =>  7, aug =>  8, sep =>  9,#      oct => 10, nov => 11, dec => 12, );# sub chronologically {#   my (\$am, \$ad, \$ay) =#     (\$a =~ /(\w{3}) (\d+), (\d+)/);#   my (\$bm, \$bd, \$by) =#     (\$b =~ /(\w{3}) (\d+), (\d+)/);#              \$ay  <=>         \$by#   || \$m2n{lc \$am} <=> \$m2n{lc \$bm}#   ||         \$ad  <=>         \$bd;# }sorted_dates = sorted(dates, chronologically)m2n = {   "jan" : 1,  "feb" : 2,  "mar" : 3,   "apr" : 4,  "may" : 5,  "jun" : 6,   "jul" : 7,  "aug" : 8,  "sep" : 9,   "oct" : 10, "nov" : 11, "dec" : 12   }def chronologically(a,b):   am, ad, ay = re.search("(\w{3}) (\d+), (\d+)", a).groups()   bm, bd, by = re.search("(\w{3}) (\d+), (\d+)", b).groups()   return (cmp(int(ay), int(by)) or           cmp(m2n[am.lower()],  m2n[bm.lower()]) or           cmp(int(ad), int(bd)))#     ## or more simply#     return cmp((int(ay), m2n[am.lower()], int(ad)),#                (int(by), m2n[bm.lower()], int(bd)))# @sorted_dates = sort chronologically @dates;# %m2n =#    ( jan =>  1, feb =>  2, mar =>  3,#      apr =>  4, may =>  5, jun =>  6,#      jul =>  7, aug =>  8, sep =>  9,#      oct => 10, nov => 11, dec => 12, );# sub chronologically {#   my (\$am, \$ad, \$ay) = split_date(\$a);#   my (\$bm, \$bd, \$by) = split_date(\$b);#              \$ay  <=>         \$by#   || \$m2n{lc \$am} <=> \$m2n{lc \$bm}#   ||         \$ad  <=>         \$bd;# }# sub split_date {#   \$_ =~ /(\w{3}) (\d+), (\d+)/;# }sorted_dates = sorted(dates, chronologically)m2n = {   "jan" : 1,  "feb" : 2,  "mar" : 3,   "apr" : 4,  "may" : 5,  "jun" : 6,   "jul" : 7,  "aug" : 8,  "sep" : 9,   "oct" : 10, "nov" : 11, "dec" : 12   }def chronologically(a,b):   am, ad, ay = split_date(a)   bm, bd, by = split_date(b)   return (cmp(int(ay), int(by)) or           cmp(m2n[am.lower()],  m2n[bm.lower()]) or           cmp(int(ad), int(bd)))def split_date(dt):   return re.search("(\w{3}) (\d+), (\d+)", dt).groups()@sorted_dates = sort chronologically @dates;  COD E L IB RARY                                            chrono-3# %m2n =#    ( jan =>  1, feb =>  2, mar =>  3,#      apr =>  4, may =>  5, jun =>  6,#      jul =>  7, aug =>  8, sep =>  9,#      oct => 10, nov => 11, dec => 12, );# sub chronologically {#   date_to_string(\$a) cmp date_to_string(\$b)# }# sub date_to_string {#   my (\$m, \$d, \$y) = (\$_ =~ /(\w{3}) (\d+), (\d+)/);#   sprintf "%04d%02d%02d", \$y, \$m2n{lc \$m}, \$d;# }m2n = {   "jan" : 1,  "feb" : 2,  "mar" : 3,   "apr" : 4,  "may" : 5,  "jun" : 6,   "jul" : 7,  "aug" : 8,  "sep" : 9,   "oct" : 10, "nov" : 11, "dec" : 12   }def chronologically(a,b):   return cmp(date_to_string(a), date_to_string(b))def date_to_string(dt):   m, d, y = re.search("(\w{3}) (\d+), (\d+)", dt).groups()   return "%04d%02d%02d" % (int(y), m2n[m.lower()], int(d))# { my %cache;#   sub chronologically {#     (\$cache{\$a} ||= date_to_string(\$a))#        cmp#     (\$cache{\$b} ||= date_to_string(\$b))#   }# }# In python we can't do the scope trick with cache# but we ignore that for nowCACHE = {}def chronologically(a, b):   if a not in CACHE:       CACHE[a] = date_to_string(a)   if b not in CACHE:       CACHE[b] = date_to_string(b)   return cmp(CACHE[a], CACHE[b])# { my %cache;#   sub by_total_invested {#     (\$cache{\$a} ||= total_invested(\$a))#        <=>#     (\$cache{\$b} ||= total_invested(\$b))#   }# }CACHE = {}def by_total_invested(a,b):   if not CACHE.get(a):       CACHE[a] = total_invested(a)   if not CACHE.get(b):       CACHE[b] = total_invested(b)   return cmp(CACHE[a], CACHE[b])# { my %cache;#   sub by_total_invested {#    (exists \$cache{\$a} ? \$cache{\$a} : (\$cache{\$a} = total_invested(\$a)))#        <=>#    (exists \$cache{\$b} ? \$cache{\$b} : (\$cache{\$b} = total_invested(\$b)))#   }# }CACHE = {}def by_total_invested(a,b):   if a not in CACHE:       CACHE[a] = total_invested(a)   if b not in CACHE:       CACHE[b] = total_invested(b)   return cmp(CACHE[a], CACHE[b])# { my %cache;#   sub by_total_invested {#     (\$cache{\$a} ||= total_invested(\$a) || "0e0")#        <=>#     (\$cache{\$b} ||= total_invested(\$b) || "0e0")#   }# }# I can't think of a reason to try to emulate this trick# (or how, frankly)### 3.11 Evangelism### 3.12 The Benefits of Speed# sub function {#   if (++\$CALLS == 100) { memoize 'function'}#   ...# }def function():   CALL += 1   if CALLS == 100:       function = memoize(function)   ...# use Time::HiRes 'time';# my (%time, %calls);# sub profile {#   my (\$func, \$name) = @_;#   my \$stub = sub {#     my \$start = time;#     my \$return = \$func->(@_);#     my \$end = time;#     my \$elapsed = \$end - \$start;#     \$calls{\$name} += 1;#     \$time{\$name} += \$elapsed;#     return \$return;#   };#   return \$stub;# }# This is another good case for a decoratorimport timetime_ = {}calls = {}def profile(func):   calls.setdefault(func.__name__, 0)   time_.setdefault(func.__name__, 0)   def stub(*args):       start = time.time()       return_ = func(*args)       end = time.time()       elapsed = end - start       calls[func.__name__] += 1       time_[func.__name__] += elapsed       return return_   return stub@profiledef foo(x):   return x# END {#   printf STDERR "%-12s %9s %6s\n", "Function", "# calls", "Elapsed";#   for my \$name (sort {\$time{\$b} <=> \$time{\$a}} (keys %time)) {#     printf STDERR "%-12s %9d %6.2f\n", \$name, \$calls{\$name}, \$time{\$name};#   }# }print >>sys.stderr, "%-12s %9s %6s\n" % ("Function", "# calls", "Elapsed")for name, _time in sorted(time_.items(), key=lambda x: x):   print >>sys.stderr, "%-12s %9d %6.2f\n" % (name, calls[name], time_[name])`