Recently I've been looking at Povray, pyprocessing, and cfdg (version 3.0) as tools for creating digital images. I have branched two separate blogs where I mainly explore jruby + processing and processing.py

Tuesday, 15 February 2011

Grammar.py using a pseudo file alternative string buffer

Here is where I got he idea to experiment with string operations in python Efficient String Concatenation in Python. Here is my grammar.py modules with the cStringIO.StringIO() version (pseudo-file). These string operations highlight a major difference between python and java on the one hand compared with ruby. In ruby strings are mutable, so the most efficient way of doing these operations is to do the string replacement in situ, this makes for much neater code. The java language provides two classes of string buffer (which are both mutable) StringBuffer and StringBuilder (the former is synchronized and more expensive to run than the latter, so use StringBuilder unless you need synchronization, as I have in my processing lsystems library).

   1 """
   2 grammar.py module by Martin Prout
   3 A variant using cStringIO.StringIO pseudo file to store string data
   4 Supports the parsing of both stochastic and non-stochastic rules
   5 axiom/rules are evaluated by the produce function, which uses the __weightedRule function
   6 to return any stochastic rule according to the input dict, the repeat function is used to repeatedly
   7 iterate the rules in a recursive fashion.
   8 Example Rules:
   9 
  10 Non-Stochastic = { "A": "A+F", "G": "GG", "X" :"G-G"}
  11 
  12 Stochastic = {"A" : {"BCD": 5, "C+C+C":10, "ACA": 40}, "B" : {"DE-F": 5, "CCC":10, "A[C]A": 40}}
  13 
  14 The Stochastic rule may contain non stochastic elements, in the above example there are two stochastic, elements,
  15 with keys "A" and "B". The stochastic rule is detected by checking the 'value' type is dict. The dict needs to of the
  16 form "string substitution" as key with the weighting as value.  A test function is included for the test conscious or
  17 skeptic.
  18 """
  19 
  20 
  21 import random
  22 
  23 def __weightedRule(rules):
  24     """
  25     A private method used to choose a substitution rule from a dict of rules, according to its
  26     weighted probality. 'rules' is expected to be a dict where the substition string is the 'key' 
  27     and the 'value' is the rule weight
  28     """
  29     rand = random.random()
  30     prob = 0
  31     tot = sum(rules.values())     # sum probabilities
  32     for rule in rules.keys():     # iterate over rule choices
  33         prob += rules.get(rule)   # add assigned probalities
  34         if ((rand * tot) < prob): # compare running total with scaled random value
  35             return(rule)
  36             
  37 def produce(axiom, rules):
  38     import cStringIO.StringIO # Experimenting with a local import statement    
  39     """
  40     The single rule substitution utility, that uses type to check for dict or str
  41     as key value, else declares 'Unrecognized grammar'. Does not throw exception!!!
  42     """
  43     str_buf = cStringIO.StringIO()   # pseudo file as a string buffer
  44     for i in axiom:
  45         temp = rules.get(i, i)
  46         if (type(temp) is dict):
  47             str_buf.write(__weightedRule(temp))
  48         elif (type(temp) is str):
  49             str_buf.write(temp)
  50         else:
  51             error = "Unknown rule type %s\n" % type(temp)
  52             print(error)
  53     str_buf.flush()        
  54     buf = str_buf.getvalue()     
  55     str_buf.close()
  56     return  buf
  57             
  58             
  59 def repeat(rpx, axiom, rules):
  60     """
  61     Repeat rule substitution in a recursive fashion rpx times
  62     """ 
  63     production = axiom
  64     for i in range(0, rpx):
  65         production = produce(production, rules)
  66     return production
  67         
  68 def __testWeighting(rules, key, total):     
  69     """
  70     Private test function see module header for examples of rules format
  71     Takes a dict containing a stochastic rule with 'key' as key.
  72     Tests the weighted rule function a 'total' number of times.
  73     Frequency result is printed.
  74     """
  75     wordList = [] # create a big test list of replacement rules
  76     for z in range(0, total):    
  77         wordList.append(__weightedRule(rules.get(key)))
  78         
  79     # calculate each word frequency in generated list (NB: does not test the
  80     # randomness of order though)
  81     freqD2 = {}
  82     for word2 in wordList:
  83         freqD2[word2] = freqD2.get(word2, 0) + 1
  84         keyList = freqD2.keys()
  85         keyList.sort()
  86         
  87     print "Frequency of each substitution string in the word list (sorted):"
  88     for key2 in keyList:
  89         print "%-10s %d" % (key2, freqD2[key2])
  90         
  91 def toRuleString(axiom, rules):
  92     """
  93     Creates a string representing the pythonic rules in a more conventional
  94     manner
  95     """
  96     output = "Axiom:\t%s\n" % axiom 
  97     keys = rules.keys()
  98     for key in keys:
  99         temp = rules.get(key)
 100         type_temp =  type(temp)
 101         if (type_temp is dict):
 102             keys2 = temp.keys()
 103             for key2 in keys2:
 104                 output += "Rule:\t%s => %s\t%d\n" % (key, key2, temp.get(key2))
 105         elif (type_temp is str):
 106             output += "Rule:\t%s => %s\n" % (key, temp)
 107         else:
 108             output += "Key:\t%s => %s an unknown rule type\n" % (key, type_temp)
 109     return output        
 110                 
 111                 
 112                 

This version compares favorably with previous version based on late concatenation (but is expected to use more memory)

No comments:

Post a Comment

Followers

Blog Archive

About Me

My photo
Pembrokeshire, United Kingdom
I have developed JRubyArt and propane new versions of ruby-processing for JRuby-9.1.5.0 and processing-3.2.2