Mapper speed-up? about ponyge2 HOT 12 CLOSED

From 5263e124d119401b6664cc1df1db627ead78c98d Mon Sep 17 00:00:00 2001
From: Erik Hemberg <[email protected]>
Date: Wed, 27 Jul 2016 09:44:49 -0400
Subject: [PATCH] Mapper speed-up. Change list to collections.deque and used
 list comprehension

---
 src/algorithm/mapper.py | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/src/algorithm/mapper.py b/src/algorithm/mapper.py
index c08e186..f652f29 100644
--- a/src/algorithm/mapper.py
+++ b/src/algorithm/mapper.py
@@ -1,6 +1,7 @@
 from algorithm.parameters import params
 from random import choice, randrange
 from representation.tree import Tree
+from collections import deque


 def genome_map(_input, max_wraps=0):
@@ -10,8 +11,9 @@ def genome_map(_input, max_wraps=0):
     from utilities.helper_methods import python_filter
     # Depth, max_depth, and nodes start from 1 to account for starting root
     used_input, current_depth, current_max_depth, nodes = 0, 1, 1, 1
-    wraps, output, production_choices = -1, [], []
-    unexpanded_symbols = [(params['BNF_GRAMMAR'].start_rule, 1)]
+    wraps, output, production_choices = -1, deque(), []
+    unexpanded_symbols = deque([(params['BNF_GRAMMAR'].start_rule,
+                                            1)])

     while (wraps < max_wraps) and \
             (len(unexpanded_symbols) > 0) and \
@@ -23,7 +25,7 @@ def genome_map(_input, max_wraps=0):
             wraps += 1

         # Expand a production
-        current_item = unexpanded_symbols.pop(0)
+        current_item = unexpanded_symbols.popleft()
         current_symbol, current_depth = current_item[0], current_item[1]
         if current_max_depth < current_depth:
             current_max_depth = current_depth
@@ -38,9 +40,8 @@ def genome_map(_input, max_wraps=0):
             # Use an input
             used_input += 1
             # Derviation order is left to right(depth-first)
-            children = []
-            for prod in production_choices[current_production]:
-                children.append([prod, current_depth + 1])
+            children = deque()
+            (children.append([prod, current_depth + 1]) for prod in production_choices[current_production])

             NT_kids = [child for child in children if child[0][1] == "NT"]
             if any(NT_kids):
-- 
2.6.2

Best:
  Training fitness:  0.0365482543342
  Test fitness:      0.036653738832
  Phenotype: pdiv(psqrt(plog(x[3])),psqrt(x[3]))
  Genome: [85893, 92194, 74513, 73017, 63589, 30507, 92194, 38003, 63589, 79238, 87248, 63589, 41194, 74513, 59409, 57668, 46150, 81787, 36062, 63589, 83727, 48642, 20342, 45171, 95339, 22517, 63384, 52185, 88222, 57483, 82017, 20942, 61799, 35711, 93112, 96904, 72173, 92678, 49489, 87226, 82670, 9250, 25621, 97673, 44985, 12689, 61981, 79552, 16847, 44030, 67758]
  ave_fitness :      4.80576498914e+17
  ave_genome_length :    51.875751503006015
  ave_tree_depth :   9.468937875751504
  ave_tree_nodes :   11.525050100200401
  ave_used_codons :      9.765531062124248
  best_ever :    Individual: pdiv(psqrt(plog(x[3])),psqrt(x[3])); 0.0365482543342
  best_fitness :     0.0365482543342
  gen :      50
  invalids :     745
  max_genome_length :    82
  max_tree_depth :   17
  max_tree_nodes :   32
  max_used_codons :      26
  min_genome_length :    21
  min_tree_depth :   2
  min_tree_nodes :   2
  min_used_codons :      1
  regens :   0
  time_taken :   0:00:00.001858
  total_inds :   25500
  unique_inds :      0
unused_search :      100.0

From d067e10ce5d554966570712cf12467a3f629d3d2 Mon Sep 17 00:00:00 2001
From: Erik Hemberg <[email protected]>
Date: Thu, 28 Jul 2016 09:05:44 -0400
Subject: [PATCH] Removing generator and looping instead. Reducing function
 calls by using local variables.

---
 src/algorithm/mapper.py | 51 ++++++++++++++++++++++++++++++++-----------------
 1 file changed, 34 insertions(+), 17 deletions(-)

diff --git a/src/algorithm/mapper.py b/src/algorithm/mapper.py
index f652f29..d04cc5c 100644
--- a/src/algorithm/mapper.py
+++ b/src/algorithm/mapper.py
@@ -10,16 +10,18 @@ def genome_map(_input, max_wraps=0):

     from utilities.helper_methods import python_filter
     # Depth, max_depth, and nodes start from 1 to account for starting root
+    MAX_TREE_DEPTH = params['MAX_TREE_DEPTH']
+    NT_SYMBOL = params['BNF_GRAMMAR'].NT
+    BNF_GRAMMAR = params['BNF_GRAMMAR']
+    n_input = len(_input)
     used_input, current_depth, current_max_depth, nodes = 0, 1, 1, 1
-    wraps, output, production_choices = -1, deque(), []
-    unexpanded_symbols = deque([(params['BNF_GRAMMAR'].start_rule,
-                                            1)])
-
+    wraps, output = -1, deque()
+    unexpanded_symbols = deque([(BNF_GRAMMAR.start_rule, 1)])
     while (wraps < max_wraps) and \
-            (len(unexpanded_symbols) > 0) and \
-            (current_max_depth <= params['MAX_TREE_DEPTH']):
+            (unexpanded_symbols) and \
+            (current_max_depth <= MAX_TREE_DEPTH):
         # Wrap
-        if used_input % len(_input) == 0 and \
+        if used_input % n_input == 0 and \
                         used_input > 0 and \
                 any([i[0][1] == "NT" for i in unexpanded_symbols]):
             wraps += 1
@@ -29,26 +31,40 @@ def genome_map(_input, max_wraps=0):
         current_symbol, current_depth = current_item[0], current_item[1]
         if current_max_depth < current_depth:
             current_max_depth = current_depth
+
         # Set output if it is a terminal
-        if current_symbol[1] != params['BNF_GRAMMAR'].NT:
+        if current_symbol[1] != NT_SYMBOL:
             output.append(current_symbol[0])
         else:
-            production_choices = params['BNF_GRAMMAR'].rules[current_symbol[0]]
+            production_choices = BNF_GRAMMAR.rules[current_symbol[0]]
             # Select a production
-            current_production = _input[used_input % len(_input)] % \
+            # TODO store the length of production choices to avoid len call?
+            current_production = _input[used_input % n_input] % \
                                  len(production_choices)
             # Use an input
             used_input += 1
             # Derviation order is left to right(depth-first)
+            # TODO is a list comprehension faster? (Only if the loop for
+            # counting NT for each production can be avoided, by using a
+            # lookup instead
             children = deque()
-            (children.append([prod, current_depth + 1]) for prod in production_choices[current_production])
-
-            NT_kids = [child for child in children if child[0][1] == "NT"]
-            if any(NT_kids):
-                nodes += len(NT_kids)
+            NT_count = 0
+            for prod in production_choices[current_production]:
+                child = [prod, current_depth + 1]
+                # Extendleft reverses the order, thus reverse adding
+                # WARNING loss of readability and coupling of lines?
+                children.appendleft(child)
+                # TODO store number of NT to avoid counting and simply do
+                # lookup instead?
+                if child[0][1] == "NT":
+                    NT_count += 1
+
+            unexpanded_symbols.extendleft(children)
+
+            if NT_count > 0:
+                nodes += NT_count
             else:
                 nodes += 1
-            unexpanded_symbols = children + unexpanded_symbols

     output = "".join(output)

@@ -57,8 +73,9 @@ def genome_map(_input, max_wraps=0):
         return None, _input, None, nodes, True, current_max_depth, \
                used_input

-    if params['BNF_GRAMMAR'].python_mode:
+    if BNF_GRAMMAR.python_mode:
         output = python_filter(output)
+
     return output, _input, None, nodes, False, current_max_depth, \
            used_input

-- 
2.6.2