Elimination

This post originally appeared on the Software Carpentry website.

I'm working up another essay on software design, and would like to ask readers of this blog how they handle something that comes up when simulating interacting agents. If your program models the behavior of a flock of birds, it probably looks something like this:

# create birds
birds = []
for i in range(num_birds):
  new_bird = Bird(...parameters...)
  birds.append(new_bird)

# simulate movement
for t in range(num_timesteps):
  for b in birds:
    b.move(birds) # need access to other birds to calculate forces

There's a flaw in this—or at least, something questionable. By the time you are moving the last bird for time t, every other bird is effectively at time t+1. There are many solutions, the simplest of which is to calculate each bird's new position in one loop, then update the bird in another:

# simulate movement
for t in range(num_timesteps):
  new_pos = []
  for b in birds:
    p = b.next_position(birds) # doesn't move the bird
    new_pos.append(p)
  for (b, p) in zip(birds, temp):
    b.set_position(p)

(If you haven't run into it, the built-in function zip takes two or more lists, and produces tuples of corresponding elements. For example, zip('abc', [1, 2, 3]) produces ('a', 1), ('b', 2), and ('c', 3).)

So far so good—but what if the things we're simulating can produce offspring, die, or eat one another? Offspring are relatively simple to handle: we just put them in a temporary list (or set), then append them to the main list after everything else has been moved.

Removing creatures that have died is a bit trickier, because modifying a list as we're looping over it may cause us to skip elements (we delete the element at location i, then advance our loop counter to i+1, and voila: the item that was at location i+1 but has been bumped down to location i is never seen in the loop). We can handle that either by "stuttering" the loop index:

i = 0
new_pos = []
while i < len(birds):
  state, p = birds[i].move(birds)
  if state == ALIVE:
    i += 1
    new_pos.append(p)
  else:
    del birds[i]

or by moving creatures that haven't died into another list, and swapping at the end of the loop:

temp = []
for b in birds:
  state, p = b.move(birds)
  if state == ALIVE:
    temp.append((b, p))
birds = []
for (b, p) in temp:
  b.set_position(p)
  birds.append(b)

I think the second is less fragile—modifying structures as I'm looping over them always gives me the shivers—but either will do the job.

But now comes the hard case. What happens if birds can eat each other? If bird i eats bird j, for i<j, it's no different from bird j dying. But if bird j eats bird i, we have a problem, because bird i is already in the list of survivors. Do we search for it and delete it (in which case, the stuttering solution above is definitely not the one we want, because the indexing logic becomes even more fragile)? Or... or what? Set a "but actually dead" flag in the bird's record in the temporary list, and not move it back into the bird list after all in the second loop? What would you do, and why?