Refine the module hill_climb_best_neighbor.
BUG=None
TEST=unit testings for the pipeline stage, pipeline workers, generation,
steering, task, flag and hill climbing.
Change-Id: I95fd82072f1474b73735a643f2da589eb930b838
Reviewed-on: https://gerrit-int.chromium.org/42663
Reviewed-by: Luis Lozano <llozano@chromium.org>
Tested-by: Yuheng Long <yuhenglong@google.com>
Commit-Queue: Yuheng Long <yuhenglong@google.com>
diff --git a/bestflags/generation.py b/bestflags/generation.py
index 6fe851a..331c810 100644
--- a/bestflags/generation.py
+++ b/bestflags/generation.py
@@ -12,7 +12,7 @@
set of tasks that could potentially be used to generate the next generation,
e.g., in the genetic algorithm, a set of good species will be kept to evolve to
the successive generations. For the hill climbing algorithm example, the
-candidate_pool will contain a current task t being evaluated and the exe_pool
+candidate_pool will contain a current task t being evaluated and the exe_set
will contains all the task t's neighbor.
"""
@@ -28,27 +28,27 @@
"""A generation of a framework run.
The base class of generation. Concrete subclasses, e.g., GAGeneration should
- override the Next and Improved method to implement algorithm specific
+ override the Next and IsImproved method to implement algorithm specific
applications.
"""
- def __init__(self, exe_pool, candidate_pool):
+ def __init__(self, exe_set, candidate_pool):
"""Set up the tasks set of this generation.
Args:
- exe_pool: A set of tasks to be run.
+ exe_set: A set of tasks to be run.
candidate_pool: A set of tasks to be considered to be used to generate the
next generation.
"""
- self._exe_pool = exe_pool
+ self._exe_set = exe_set
self._candidate_pool = candidate_pool
# Keeping the record of how many tasks are pending. Pending tasks are the
# ones that have been sent out to the next stage for execution but have not
# finished. A generation is not ready for the reproduction of the new
# generations until all its pending tasks have been executed.
- self._pending = len(exe_pool)
+ self._pending = len(exe_set)
def CandidatePool(self):
"""Return the candidate tasks of this generation."""
@@ -58,7 +58,7 @@
def Pool(self):
"""Return the task set of this generation."""
- return self._exe_pool
+ return self._exe_set
def Done(self):
"""All the tasks in this generation are done.
@@ -96,13 +96,13 @@
"""
# If there is a match, the input task belongs to this generation.
- if task not in self._exe_pool:
+ if task not in self._exe_set:
return False
# Remove the place holder task in this generation and store the new input
# task and its result.
- self._exe_pool.remove(task)
- self._exe_pool.add(task)
+ self._exe_set.remove(task)
+ self._exe_set.add(task)
# The current generation will have one less task to wait on.
self._pending -= 1
@@ -111,7 +111,7 @@
return True
- def Improved(self):
+ def IsImproved(self):
"""True if this generation has improvement upon its parent generation.
Raises:
diff --git a/bestflags/genetic_algorithm.py b/bestflags/genetic_algorithm.py
index 0e7de07..be9e897 100644
--- a/bestflags/genetic_algorithm.py
+++ b/bestflags/genetic_algorithm.py
@@ -200,7 +200,7 @@
Generation.__init__(self, tasks, parents)
self._total_stucks = total_stucks
- def Improved(self):
+ def IsImproved(self):
"""True if this generation has improvement upon its parent generation."""
tasks = self.Pool()
@@ -216,7 +216,7 @@
best_current = sorted(tasks, key=lambda task: task.GetTestResult())[0]
# At least one task has improvement.
- if best_current.Improved(best_parent):
+ if best_current.IsImproved(best_parent):
self._total_stucks = 0
return True
diff --git a/bestflags/hill_climb_best_neighbor.py b/bestflags/hill_climb_best_neighbor.py
index aec420f..409b42c 100644
--- a/bestflags/hill_climb_best_neighbor.py
+++ b/bestflags/hill_climb_best_neighbor.py
@@ -23,35 +23,39 @@
class HillClimbingBestBranch(Generation):
"""A variation of the hill climbing algorithm.
- Given a task, it explores all its neighbors. Pick if best neighbor for the
+ Given a task, it explores all its neighbors. Pick the best neighbor for the
next iteration.
"""
- def __init__(self, exe_pool, parents, specs):
+ def __init__(self, exe_set, parents, specs):
"""Set up the tasks set of this generation.
Args:
- exe_pool: A set of tasks to be run.
+ exe_set: A set of tasks to be run.
parents: A set of tasks to be used to check whether their neighbors have
improved upon them.
specs: A list of specs to explore. The spec specifies the flags that can
be changed to find neighbors of a task.
"""
- Generation.__init__(self, exe_pool, parents)
+ Generation.__init__(self, exe_set, parents)
self._specs = specs
- def Improved(self):
+ def IsImproved(self):
"""True if this generation has improvement over its parent generation.
+ If this generation improves upon the previous generation, this method finds
+ out the best task in this generation and sets it to _next_task for the
+ method Next to use.
+
Returns:
True if the best neighbor improves upon the parent task.
"""
# Find the best neighbor.
best_task = None
- for task in self._exe_pool:
- if not best_task or task.Improved(best_task):
+ for task in self._exe_set:
+ if not best_task or task.IsImproved(best_task):
best_task = task
if not best_task:
@@ -63,7 +67,7 @@
assert len(parents) == 1
self._next_task = best_task
# If the best neighbor improves upon the parent task.
- return best_task.Improved(parents[0])
+ return best_task.IsImproved(parents[0])
self._next_task = best_task
return True
diff --git a/bestflags/steering.py b/bestflags/steering.py
index 5cdf8ae..a7a559e 100644
--- a/bestflags/steering.py
+++ b/bestflags/steering.py
@@ -99,7 +99,7 @@
# A generation may not generate the next generation, e.g., because a
# fixpoint has been reached, there has not been any improvement for a few
# generations or a local maxima is reached.
- if not generation.Improved():
+ if not generation.IsImproved():
continue
for new_generation in generation.Next(cache):
diff --git a/bestflags/steering_test.py b/bestflags/steering_test.py
index 5063079..2000dc4 100644
--- a/bestflags/steering_test.py
+++ b/bestflags/steering_test.py
@@ -53,7 +53,7 @@
def Next(self, _):
return self._next_generations
- def Improved(self):
+ def IsImproved(self):
if self._next_generations:
return True
return False
diff --git a/bestflags/task.py b/bestflags/task.py
index b20493f..f1ac417 100644
--- a/bestflags/task.py
+++ b/bestflags/task.py
@@ -391,7 +391,7 @@
# Write out the result in the comma-separated format (CSV).
out_file.write('%s,%s,%s\n' % test_result)
- def Improved(self, other):
+ def IsImproved(self, other):
"""Compare the current task with another task.
Args:
