Test performance between recursion and ahead calculation with looping trough collections

mine_exploder_performance_test.py

import numpy as np
import timeit
from collections import deque

NUMBER_OF_MINES = 10 ** 5
# Keep this low to prevent RuntimeError: maximum recursion depth exceeded
# (we can increase recursion depth, but it's ok also to avoid it just for the test)
MAX_BLAST_RADIUS = 200
MAX_COORDINATE_XY = 700000

def generateMines():
  # Generate array of coordinates (x, y)
  coordinates = np.random.randint(MAX_COORDINATE_XY, size=(NUMBER_OF_MINES,2))
  # Generate array of random blasts
  radiuses = np.random.randint(MAX_BLAST_RADIUS, size=NUMBER_OF_MINES)
  # Now insert blast to each coordinate array and convert numpy list to simple one and return
  return np.insert(coordinates, 2, radiuses, 1).tolist()

mines = generateMines()

def within_blast_radius(x1, y1, blast_radius, x2, y2):
  return ((x1 - x2) ** 2 + (y1 - y2) ** 2) <= (blast_radius ** 2)


#### NORMAL CODE ####
def explode_mine(mines, mine, exploded):
  destroyed = 0
  for rest in mines:
    if rest != mine and not rest in exploded:
      if within_blast_radius(mine[0], mine[1], mine[2], rest[0], rest[1]):
        exploded.append(rest)
        destroyed += 1
        destroyed += explode_mine(mines, rest, exploded)
  return destroyed

def calculateChainReaction(mines):
  result = []
  for mine in mines:
    result.append(explode_mine(mines, mine, [mine]) + 1)
  maxExploded = max(result)
  indexesOfMax = [i for i, j in enumerate(result) if j == maxExploded]
  print ('Max exploded mines: %s \nMines with maximum explosion: %s' %
    (maxExploded, ','.join(map(str, [x+1 for x in indexesOfMax]))))


#### OPTIMIZED CODE ####
def collect(token, tree):
    "returns a list of every mine in radius"
    visited = set()
    child_list = []
    to_crawl = deque([token])
    while to_crawl:
        current = to_crawl.popleft()
        if current in visited:
            continue
        visited.add(current)
        child_list.append(current)
        node_children = tree[current]
        to_crawl.extend(node_children)
    return child_list

def calculateOptimized(mines):
  # First we detect mines in radius of each mine and store them as dict of indexes
  explosionMap = {}
  for idx, mine in enumerate(mines):
    explosionMap[idx] = []
    for cidx, compareMine in enumerate(mines):
      if compareMine != mine:
        # First we do the simple test without expencive calculation (is the point in a square)
        if mine[0] + mine[2] > compareMine[0] and mine[1] + mine[2] > compareMine[1]:
          # Now we test it more precisely
          if within_blast_radius(mine[0], mine[1], mine[2], compareMine[0], compareMine[1]):
            explosionMap[idx].append(cidx)

  result = []
  # Now that we have all calculations done, we can collect recursive explosions by iterating trough the indexes
  for idx in explosionMap:
    bombs = collect(idx, explosionMap)
    result.append(len(bombs))
  maxExploded = max(result)
  indexesOfMax = [i for i, j in enumerate(result) if j == maxExploded]
  print ('Max exploded mines: %s \nMines with maximum explosion: %s' %
    (maxExploded, ','.join(map(str, [x+1 for x in indexesOfMax]))))

#### RUNNERS ####
def runOptimized():
  # Cloning the list in order to have exact starting point for both algorithms
  cloned = np.copy(mines).tolist()
  cloned = sorted(cloned, key=lambda x: x[2])
  calculateOptimized(cloned)

def run():
  cloned = np.copy(mines).tolist()
  cloned = sorted(cloned, key=lambda x: x[2])
  calculateChainReaction(cloned)

if __name__ == '__main__':
  res = timeit.timeit(run, number=1)
  print "Time taken:", res
  res = timeit.timeit(runOptimized, number=1)
  print "Time taken:", res