Comments (12)
Great idea, +1 for using deque, thanks!
But this didn't format right in Github Markdown. I tried editing but it's still not right. Can you paste the patch again or put it in email?
from ponyge2.
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
from ponyge2.
I wonder if there are similar speedups we could realise with the tree mapper? If you turn on --mutation subtree or --crossover subtree (or both) it takes much longer
from ponyge2.
I believe so. The code is so mature now that it makes sense to use the profiler as a guide to the bottlenecks (The fitness evaluations are nice and fast, so I was slightly surprised to see that the mapping takes so much time)
- From brief view of the code for
genome_tree_derivation
(The possible speed-ups are- Use queues when you know that you will only pop or push (Lists have poor complexity compared to queue for some operations e.g. for remove it is (O(1) vs O(n), I do not remember exactly all...)
- Use generators and list comprehension, it could speed up
- Rewriting it non-recursively might help...
Attached is the profiling graph for python ponyge.py --mutation subtree
from ponyge2.
I think a large part of the issue comes from the sheer number of calls to the mapper. We re-initialise selected parents before crossover to avoid issues with parents who have the same tree instances. We do this to avoid the use of deepcopy, which slows things down immensely. Surely there has to be a better way of doing things than this.
from ponyge2.
Erik would you like to push this patch?
from ponyge2.
Pushed
from ponyge2.
There seems to be an issue with your changes Erik. I get different results with the new changes, everything runs substantially worse for me. Seeing 98% unused search (396 unique phenotypes out of 25500) with the following params:
--crossover onepoint --mutation int_flip --random_seed 0
Reverting to the previous version sees performance as expected (~66% unused search with the same args).
from ponyge2.
Sorry about that. It seems like it was the generator. I have a new patch suggestion (at the end of the message, based on my push).
- I removed that and added some changes by reducing function calls and dictionary lookups. (The method is called so many times that it seems to make a difference)
- There are some TODOs which could shave off some time.
- I tested it with
python ponyge.py --random_seed 0
and got the same performance as0c1ed159a40e215a61231908a324ce56beba8c31
but ~1s faster
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
Below is suggested patch:
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
from ponyge2.
Can you push that?
from ponyge2.
Pushed
from ponyge2.
Excellent, results are the same.
from ponyge2.
Related Issues (20)
- Default example doesn't run HOT 5
- Examples not working HOT 2
- `regex_improvement.txt` example - confusing message? HOT 1
- `seed_run_target.txt` example doesn't work
- Please help with solution min/max boundaries ❓ HOT 6
- Tree initialisation breaks when min = max depth
- Tree initialisation operators sometimes don't achieve stated depth
- Progsys with "Compare String Lengths" not giving valuable results
- Rethink if-else-classifier?
- progsys Digits problem
- progsys 'is' and 'is not' HOT 3
- missing contents of String Differences-Embed.txt HOT 1
- Statistics parser prog in Wiki incorrectly named
- save_state not working with multicore
- load_state not working with functions in custom module
- Post-processing python phenotypes is slow
- correct genome not returned when one of the codons is zero in the tree
- progsys count odds data
- Multi-objective optimisation is slow HOT 1
- Specifed moudle not found: fitness.xxx HOT 12
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from ponyge2.