josephus2.py

# Josephus problem
# See: http://blog.dhananjaynene.com/2008/07/performance-comparison-c-java-python-ruby-jython-jruby-groovy/
#
# Quoting from the post linked to above :
#
# Flavius Josephus was a roman historian of Jewish origin. During the
# Jewish-Roman wars of the first century AD, he was in a cave with fellow
# soldiers, 40 men in all, surrounded by enemy Roman troops. They decided to
# commit suicide by standing in a ring and counting off each third man. Each man
# so designated was to commit suicide...Josephus, not wanting to die, managed to
# place himself in the position of the last survivor.
#
# In the general version of the problem, there are n soldiers numbered from 1 to
# n and each k-th soldier will be eliminated. The count starts from the first
# soldier. What is the number of the last survivor

KILL_NUMBER = 3
NUMBER_OF_SOLDIERS = 40

class Soldier(object):
	def __init__(self, count):
		self.count = count
		self.prev = None
		self.next = None
	def __str__(self):
		return "soldier %i" % self.count

class Ring(object):
	def __init__(self):
		self.ring = []

	def build_ring(self, number_of_soldiers):
		prev = cur = None
		append_ring = self.ring.append
		for i in range(1, number_of_soldiers+1):
			cur = Soldier(i)
			append_ring(cur)
			if prev != None:
				prev.next = cur
				cur.prev = prev
			prev = cur
		# attach end to beginning and beginning to end
		cur.next = self.ring[0]
		self.ring[0].prev = cur
	
	def kill_soldier(self, soldier):
		soldier.next.prev = soldier.prev
		soldier.prev.next = soldier.next
		# not really necessary to remove soldiers from list, 
		# just skip killed soldiers by connecting prev and next soldier
		# with each other.
		# The length of the ring thus stays the same, but at one
		# point one soldier is only connected to it self, because
		# everybody else is dead.
		# This eliminates the need to remove items from the list.
		
	def start_killing(self, kill_every_number):
		kill = 1
		r = self.ring[0]
		while r.count != r.next.count: # if next soldier == current soldier then only one soldier is left
			if kill % kill_every_number == 0:
				self.kill_soldier(r)
				kill = 1
			else:
				kill += 1
			r = r.next
		return r
		
import time
ITER = 100000
start = time.time()
for i in range(ITER):
	rng = Ring()
	rng.build_ring(NUMBER_OF_SOLDIERS)
	soldier_left = rng.start_killing(KILL_NUMBER)
end = time.time()
print 'Time per iteration = %s microseconds ' % ((end - start) * 1000000 / ITER)

# Results:
# berry$ python josephus2.py 
# Time per iteration = 239.021520615 microseconds 
# berry$ pypy-c josephus2.py 
# Time per iteration = 12.9562306404 microseconds 

# See: http://stackoverflow.com/questions/725782/python-list-concatenation-what-is-difference-in-append-and
# After pre-loading the append command the time is:
# berry$ python josephus2.py 
# Time per iteration = 233.306939602 microseconds 
# berry$ pypy-c josephus2.py 
# Time per iteration = 11.5038013458 microseconds