list.without()?

[Mike Fletcher]

Hmm, actually, it's only cheap for certain subsets of the problem (which I
took to be the common case).  In particular, it shines for small numbers of
instances in lists of fairly arbitrary size.  It falls down completely when
you are removing large numbers of instances (such as all of them).  I just
tested five algos, testing 1 instance in middle of list, and a list composed
of only elements to be removed, findings, module, and raw test results
below...

Conclusions:
	First is the posted algo (while,try,except,break) <without> -- gives very
good performance for the few-in-many case but very poor performance for the
many in many cases for large values of many
	Second is a for loop with == test and append <without2> -- gives decent
(but not spectacular) results whenever memory effects are not a big factor,
not really a contender.
	Third is the lambda solution (which does surprisingly well) <without3> --
gives acceptable but not great performance all over, seems strange that
function-call-overhead is so minor a factor.
	Fourth is a backwards-index-counting scheme with del <without4> -- gives
marginally better performance than third on few-in-many case, marginally
worse than third in many-in-many case.
	Fifth is Preston's remove function <remove> -- gives best results for
few-in-many case, again, very poor results in many-in-many case

Summary:
	Looks like the fourth algo is likely the "winner" in this set (assuming
few-in-many is the most common case, but that many-in-many is a potential
case).  Third might be preferred due to the simplicity of the implementation
and similar speed.  For maximum few-in-many speed, the fifth is the most
appropriate.

Module is below, along with results run on a PIII 500 under NT.  Enjoy,
Mike

8<_____ without.py ____________________
def without( source, element):
	temp = source[:]
	while temp:
		try:
			temp.remove( element )
		except:
			break
	return temp

def without2( source, element ):
	temp = []
	for el in source:
		if el != element:
			temp.append( el )
	return temp

def without3( source, element ):
	return filter(lambda x, element=element: x!=element, source)
def without4( source, element ):
	temp = source[:]
	for index in xrange( len(temp)-1, -1, -1 ):
		if temp[index] == element:
			del temp[index]
	return temp
def remove(list, element):
    while element in list:
        list.remove(element)
    return list

def test( function):
	import time
	print "Testing function:", function
	print "  single element at middle:"
	for dl in (10, 100, 1000, 10000, 100000, 1000000):
		t = time.time()
		res = function( range( dl),  dl/2)
		delta = time.time()-t
		print "    %s: %s"%(dl,delta)
		if delta > 10:
			print "###Note: Tests skipped due to time overrun"
			break
	print
	print "  all elements being removed:"
	for dl in (10, 100, 1000, 10000, 100000, 1000000):
		t = time.time()
		res = function( [1]*dl,  1)
		delta = time.time()-t
		print "    %s: %s"%(dl,delta)
		if delta > 10:
			print "###Note: Tests skipped due to time overrun"
			break
	print


if __name__ == "__main__":
	#test( without )
	#test( without2 )
	test( without3 )
	test( without4 )
	test( remove )

8<_____ run results  ___________________
p:\>without
Testing function: <function without at 7d7f00>
  single element at middle:
    10: 0.0
    100: 0.0
    1000: 0.0
    10000: 0.00999999046326
    100000: 0.0699999332428
    1000000: 1.11199998856

  all elements being removed:
    10: 0.120000004768
    100: 0.0
    1000: 0.0100001096725
    10000: 0.770999908447
    100000: 78.7929999828
###Note: Tests skipped due to time overrun

Testing function: <function without2 at 7d7f80>
  single element at middle:
    10: 0.0
    100: 0.0
    1000: 0.0100001096725
    10000: 0.039999961853
    100000: 0.460999965668
    1000000: 19.6879999638
###Note: Tests skipped due to time overrun

  all elements being removed:
    10: 0.120000004768
    100: 0.0
    1000: 0.0
    10000: 0.0100001096725
    100000: 0.110999941826
    1000000: 1.16100001335

Testing function: <function without3 at 7d8f40>
  single element at middle:
    10: 0.0
    100: 0.0
    1000: 0.0
    10000: 0.0299999713898
    100000: 0.341000080109
    1000000: 3.39499998093

  all elements being removed:
    10: 0.129999995232
    100: 0.0
    1000: 0.0
    10000: 0.0299999713898
    100000: 0.320000052452
    1000000: 3.17499995232

Testing function: <function without4 at 7d8f60>
  single element at middle:
    10: 0.0
    100: 0.0
    1000: 0.0
    10000: 0.0199999809265
    100000: 0.19000005722
    1000000: 1.9129999876

  all elements being removed:
    10: 0.120000004768
    100: 0.0
    1000: 0.0
    10000: 0.039999961853
    100000: 0.401000022888
    1000000: 4.00499999523

Testing function: <function remove at 7daac0>
  single element at middle:
    10: 0.0
    100: 0.0
    1000: 0.0
    10000: 0.00999999046326
    100000: 0.0509999990463
    1000000: 0.580000042915

  all elements being removed:
    10: 0.130999922752
    100: 0.0
    1000: 0.00999999046326
    10000: 0.771000027657
    100000: 79.1130000353
###Note: Tests skipped due to time overrun