is there a better way?

[markscala]

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

hope this is clear.
thanks

[Jeremy Sanders]

ma*******@gmail.com wrote:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

What not

for x in list:
if x == O:
break
storage.append(x)

??

--
Jeremy Sanders
http://www.jeremysanders.net/

[snoe]

ma*******@gmail.com wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

hope this is clear.
thanks

There's a few ways to do this, really depends on :

mylist = [1,2,3,4,5,6,0,0,0]

list comprehension (will get ALL non zeros, and strip out all zeros,
but is different from your function):
[x for x in mylist if x != 0]

list slice(same as your function):
mylist[:mylist.index(0)]

Depends what you want to happen if your list is something like:
[1,2,3,0,4,5,6,0,0]
[0,1,2,3,4,5,6]
[0,1,2,3,4,5,6,0]
[1,2,3,4,5,6]

[Paul McGuire]

<ma*******@gmail.com> wrote in message
news:11********************@g47g2000cwa.googlegrou ps.com...

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

hope this is clear.
thanks

Use itertools.

import itertools
lst = "X,X,X,O,O,O,O,O,X,X,X,X,O,X".split(",")
[z for z in itertools.takewhile(lambda x:x=="X",lst)]

['X', 'X', 'X']
-- Paul

[Tim Chase]

> You have a list of unknown length, such as this: list =

[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

While it doesn't modify your list, you can try something like

storage = [q for q in myList if q != O]

If you've already got stuff in storage that you want to keep, you
can use

storage.extend([q for q in myList if q != O])

I suppose, if you wanted to remove all the O's, you could then
just do

myList = [q for q in myList if q == O]

(trickiness using Oh's vs. using zeros...)

-tkc

[Paul McGuire]

"Paul McGuire" <pt***@austin.rr._bogus_.com> wrote in message
news:PO*****************@tornado.texas.rr.com...

<ma*******@gmail.com> wrote in message
news:11********************@g47g2000cwa.googlegrou ps.com...

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

hope this is clear.
thanks

Use itertools.

import itertools
lst = "X,X,X,O,O,O,O,O,X,X,X,X,O,X".split(",")
[z for z in itertools.takewhile(lambda x:x=="X",lst)] ['X', 'X', 'X']
-- Paul

duh, last line should be:

list(itertools.takewhile(lambda x:x=="X",lst))

['X', 'X', 'X']

(Also, don't name variables "list")

-- Paul

[Scott David Daniels]

ma*******@gmail.com wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

Your names could be better as someone mentioned.
ex, oh = 7, 13 # for example
data = [ex, ex, ex, oh, oh, oh, oh]
If you need a list distinct from the original:
try:
result = data[: data.index(oh)]
except ValueError:
result = list(data)

Or you could simply:
try:
data = data[: data.index(oh)]
except ValueError:
pass
and data will be either the sublist you want or the original list.

--
-Scott David Daniels
sc***********@acm.org

[Schüle Daniel]

[...]

What not

for x in list:
if x == O:
break
storage.append(x)

i think this may take too long
better aproach would be to test for zero from the end

Regards, Daniel

[Schüle Daniel]

[...]

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

lst = [1,2,3,4,5,0,0,0,0]
del lst[lst.index(0):]
lst [1, 2, 3, 4, 5]

Regards, Daniel

[Lonnie Princehouse]

everybody is making this way more complicated than it needs to be.

storage = list[:list.index(O)]

incidentally, "list" is the name of a type, so you might want to avoid
using it as a variable name.

[Jeremy Dillworth]

You could eliminate a few lines like this:

-----------------------------
while list and list[0] != O:
storage.append(list.pop(0))
-----------------------------

Adding the "list and " to the front of the logic test will catch when
there are 0 elements, so the "if..break" lines are not needed. Also
pop() returns the element popped, so there's no need for a separate
"list[0]" and "list.pop(0)"

You could also do the whole thing as a list comprehension (assuming
storage is a list, otherwise += may or may not work):
-----------------------------
storage += [i for i in list if i == X]
-----------------------------

But this is less efficient, since it will loop through all the O's too.
The other solution stops at the first O. This will also break if
there are any X's mixed with O's, though you've said that's not
currently the case, things can always change.

Lastly, you could do this:
-----------------------------
list.append(O)
storage += list[:list.index(O)]
-----------------------------

The first line makes sure there is always an O in list, otherwise
index(O) will throw an exception. That's slightly ugly, but I still
like this solution, myself.

hope this helps,

Jeremy

[Schüle Daniel]

Lonnie Princehouse wrote:

everybody is making this way more complicated than it needs to be.

storage = list[:list.index(O)]

the question is whether the old list is needed in the future or not
if not then it would be easer/mor efficient to use

del lst[lst.index(0):]

Regards, Daniel

[Schüle Daniel]

I don't want to hijack the thread I was thinking
whether something like lst.remove(item = 0, all = True)
would be worth adding to Python?

it could have this signature

def remove(item, nItems = 1, all = False)
...
return how_many_deleted

lst.remove(item = 0, nItems = 1)
lst.remove(item = 0, nItems = 2)

lst.remove(item = 0, all = True)
in last case nItems is ignored

Regards, Daniel

[Scott David Daniels]

Scott David Daniels wrote:

ma*******@gmail.com wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

Your names could be better as someone mentioned.
ex, oh = 7, 13 # for example
data = [ex, ex, ex, oh, oh, oh, oh]
If you need a list distinct from the original:
try:
result = data[: data.index(oh)]
except ValueError:
result = list(data)

Or you could simply:
try:
data = data[: data.index(oh)]
except ValueError:
pass
and data will be either the sublist you want or the original list.

I forgot the obvious:

result = data.count(ex) * [ex]

--
-Scott David Daniels
sc***********@acm.org

[Dave Hansen]

On Sat, 11 Feb 2006 01:37:59 +0100 in comp.lang.python, Schüle Daniel
<uv**@rz.uni-karlsruhe.de> wrote:

Lonnie Princehouse wrote:

everybody is making this way more complicated than it needs to be.

storage = list[:list.index(O)]

the question is whether the old list is needed in the future or not
if not then it would be easer/mor efficient to use

del lst[lst.index(0):]

And you're both forgetting the list can end with X. the index method
raises a ValueError exception if the desired value is not found in the
list. Assuming you want to keep the original list and create a new
list called storage, you could try

if lst[-1] == X:
storage = lst[:]
else:
storage = lst[:lst.index(O)]

or even

try:
storage = lst[:lst.index(O)]
except ValueError:
storage = lst[:]

(WARNING: untested!)

Regards,

-=Dave

--
Change is inevitable, progress is not.

[Alex Martelli]

ma*******@gmail.com <ma*******@gmail.com> wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

If the list is incredibly long, you should use a bisection approach.
Standard module bisect in the Python library could help, but mostly as
an _example_, since it unfortunately relies on normal alphabetic order,
and alphabetically speaking X should come _after_ O, not _before_.

But the algorithm is still sound:

1. look at the midpoint.
2. if it's an X, so are all previous items -- recurse to second half
3. if it's an O, so are all following items -- recurse to first half

Getting all conditions exactly right is tricky (which is why bisect is a
good model!), but this way you get O(log N) performance for a list of
length N.

If N is not too huge, O(N) might be OK, and is, of course, way simpler
to code!-)
Alex

[Paul Rubin]

"ma*******@gmail.com" <ma*******@gmail.com> writes:

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

Note that "list" is the name of a built-in type; I used "mylist".
Alex Martelli described how to do it in log n time using the bisect
module. Here's a dumb linear time method that might be faster for
small n (of course you should time the different methods for your
particular Python implementation, if the speed matters):

del mylist[len(mylist) - mylist.count(0):]

The above an example of where the natural

del mylist[-mylist.count(0):]

does totally the wrong thing if there are no 0's in the list. There
was a huge thread a while back about ways to fix that.

Another way, might be faster, esp. there's more than a few 0's:

try:
del mylist[mylist.index(0)]
except ValueError:
pass # no 0's in the list

[Charles Krug]

On 2006-02-11, Alex Martelli <al*****@yahoo.com> wrote:

ma*******@gmail.com <ma*******@gmail.com> wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

If the list is incredibly long, you should use a bisection approach.
Standard module bisect in the Python library could help, but mostly as
an _example_, since it unfortunately relies on normal alphabetic order,
and alphabetically speaking X should come _after_ O, not _before_.

Isn't every call to list.index() an O(n) operation? We certainly want
to avoid multiple calls there if we can.

What happens if your split occurs in the middle of your block of Xs?
Then the split before/after fails --the stated algorithm says, "If the
split is an X, choose the front half," so perhaps the statement was
inprecise?

The only way you'll know if you have an X in a particular block is using
a linear search method, either in Python or with list.index()

If (as the OP seemed to state) we KNOW that there's only one block of
X's in the list:

1. Find the index of the first X
2. Find the index of the last X.
3. Delete the block we've found.

That relies on the underlying language, which means we're working in
"Linear Time in C", more or less.

If we make no such guarantee, then I can do the operation in linear
"Python Time" by scanning the list once, finding each instance and
calling list.del() as I find each block, keeping track of my current
position so I don't have to start over again.

Judging from way the OP worded the question, I'd advise making something
that works and that you understand how it works.

After that, s/he can worry about whether or not its performance is
suboptimal.

How large must the list be before "logarithmic Python algorithm" is
faster than "linear C algorithm"? I've never measured, but it may be a
question worth exploring if one has a huge pile of data to chew on--like
US Census or UN budget-sized.

[Steve Holden]

ma*******@gmail.com wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

hope this is clear.

X = "X"
O = "O"
def fl(l): ... for i, v in enumerate(l):
... if v == O:
... return l[:i]
... return l
... fl([X,X,X,X,O,O,O]) ['X', 'X', 'X', 'X'] fl([]) [] fl([O]) [] fl([X]) ['X']

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Carl Friedrich Bolz]

Alex Martelli wrote:

ma*******@gmail.com <ma*******@gmail.com> wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

If the list is incredibly long, you should use a bisection approach.
Standard module bisect in the Python library could help, but mostly as
an _example_, since it unfortunately relies on normal alphabetic order,
and alphabetically speaking X should come _after_ O, not _before_.

But the algorithm is still sound:

1. look at the midpoint.
2. if it's an X, so are all previous items -- recurse to second half
3. if it's an O, so are all following items -- recurse to first half

Getting all conditions exactly right is tricky (which is why bisect is a
good model!), but this way you get O(log N) performance for a list of
length N.

If N is not too huge, O(N) might be OK, and is, of course, way simpler
to code!-)

The code would look something like this:

low = 0
high = len(L)
while low < high:
mid = (low + high) // 2
if L[mid] == 0:
high = mid
else:
low = mid + 1
list_of_X = L[:low]
Cheers,

Carl Friedrich Bolz

[Carl Friedrich Bolz]

Hi!

ma*******@gmail.com wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?
Depends on what you mean with "better". I (heavily inspired by the
bisect module) came up with:

low = 0
high = len(L)
while low < high:
mid = (low + high) // 2
if L[mid] == 0:
high = mid
else:
low = mid + 1
storage = L[:low]

This has the advantage to be more efficient compared to other
approaches, which of course only matters if your list is big. It still
features a "while" loop, though.
hope this is clear.

It is not entirely clear what the X is supposed to be. I assumed that it
can be anything except 0.

Cheers,

Carl Friedrich

[Alex Martelli]

Charles Krug <cd****@aol.com> wrote:

On 2006-02-11, Alex Martelli <al*****@yahoo.com> wrote:

ma*******@gmail.com <ma*******@gmail.com> wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.
If the list is incredibly long, you should use a bisection approach.
Standard module bisect in the Python library could help, but mostly as
an _example_, since it unfortunately relies on normal alphabetic order,
and alphabetically speaking X should come _after_ O, not _before_.

Isn't every call to list.index() an O(n) operation? We certainly want
to avoid multiple calls there if we can.

Why should we have ANY call to index whatsoever?
What happens if your split occurs in the middle of your block of Xs?
Then the split before/after fails --the stated algorithm says, "If the
split is an X, choose the front half," so perhaps the statement was
inprecise?
What statement? What are you TALKING about?! What I said, and you
don't quote, was:

2. if it's an X, so are all previous items -- recurse to second half
how can you POSSIBLY read this as "choose the front half"?! I say to
recurse (iteration works, too, but it's even trickier to code) to the
SECOND half, to find the first-if-any non-'X'.
The only way you'll know if you have an X in a particular block is using
a linear search method, either in Python or with list.index()
Reread markscala's problem statement: all the Xs are up front followed
by 0 or more Os. So, the list is L = ['X']*N + ['O']*M for unknown N>=0
and M>=0. All we have to do is find N and M (if we know either, the
other is immediately computed, since N+M==len(L) and len() is O(1)).
If (as the OP seemed to state) we KNOW that there's only one block of
X's in the list:

1. Find the index of the first X
Why would we do that? He stated, very clearly, and you and I have both
been quoting:

You know
the X's are all up front

So why would we do any work to find out what we altrady know?
2. Find the index of the last X.
Yep, the only certain task, and it's O(log(N+M)).
3. Delete the block we've found.
And the deletion is definitely linear time (and trivial), of course. I
was focusing on the only interesting part, (2).
Judging from way the OP worded the question, I'd advise making something
that works and that you understand how it works.

After that, s/he can worry about whether or not its performance is
suboptimal.

And indeed, part of what I said (and again you're snipping it rather
than quoting it was:
If N is not too huge, O(N) might be OK, and is, of course, way simpler
to code!-)

However, even though the O(N) in the deletion subtask would appear to
justify this shortcut, I think the task is way too trivial to justify a
linear-time approach to point 2 -- the obvious N = L.count('X'), of
course. It seems likely that the whole purpose of the exercise
(probably homework) is to have the student identify and develop a
bisection (a notoriously tricky-to-code thing).
Alex

[Bruno Desthuilliers]

ma*******@gmail.com a écrit :

Problem:

You have a list of unknown length,
This doesn't exist in Python:
len(alist)
such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's.
braindead solution - relying on zeros being zeros or any other False value:
all_xxx = filter(None, [X,X,X,O,O,O,O])
You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

Then it *may* be possible to optimize - but code will break as soon as
this rule change. So is there a real need for optimisation ? (hint: dont
guess, profile)
FWIW, I've collected all suggestions here (and perhaps some others) and
hacked a Q&D benchmark. Usage is:

python test_lists.py [repeat[list_size [xcount]]

where:
* repeat is the number of iteration, default to 1000
* list_size is the size of the list, default to 100
* xcount is the number or non-zero values in the list, default is random

I've run it a few times, and it seems that in most cases,
* the bisect-like approach (Alex Martelli / Karl Friedrich Bolz) is
the winner
* the while/pop approach of the OP (slightly rewritten...) is really wrong

FWIW, one of the dummiest possible approach IMHO
(ie filter(None, alist)) behaves quite correctly wrt some other
'optimized' approachs - and is still safe if the rules about the
composition of the list changes... Could it be that no optimization is
sometime the best optimisation ?-)
# test_lists.py
from itertools import takewhile
from timeit import Timer
from random import randint

def get_list(size, xcount=None):
if xcount is None:
xcount = randint(1, size)
else:
assert xcount <= size
zcount = size - xcount
return [1] * xcount + [0] * zcount

def with_while(alist):
res = []
while alist and alist[0]:
res.append(alist.pop(0))
return res

def with_for(alist):
res = []
for x in alist:
if not x: break
res.append(x)
return res

def with_filter(alist):
return filter(None, alist)

def with_comprehension(alist):
return [x for x in alist if x]

def with_takewhile(alist):
return list(takewhile(lambda x: x!=0, alist))

def with_slice_try(alist):
try:
return alist[:alist.index(0)]
except ValueError:
return alist[:]

def with_slice_safe(alist):
alist.append(0)
return alist[:alist.index(0)]

def with_delslice_safe(alist):
alist.append(0)
del alist[alist.index(0):]
return alist

def with_sect(alist):
low = 0
high = len(alist)
while low < high:
mid = (low + high) // 2
if alist[mid] == 0:
high = mid
else:
low = mid + 1
return alist[:low]

_candidates = [n for n, o in locals().copy().items() \
if n.startswith('with_') and callable(o)]

def run_test(repeat=1000, list_size='100', xcount='None'):
global _candidate

print """
params :
* repeat : %s
* list_size : %s
* xcounts : %s
""" % (repeat, list_size, xcount)
results = {}
for n in _candidates:
stm, stp = ('%s(get_list(%s, %s))' % (n, list_size, xcount),
'from __main__ import %s, get_list' % n)
results[n] = Timer(stm, stp).timeit(repeat)

sorted_results = sorted([(time, (n, time)) \
for n, time in results.items()])
for _, result in sorted_results:
print "%s : %s" % result
def main(args):
try:
repeat = int(args.pop(0))
except:
repeat = 1000
try:
list_size = args.pop(0)
except:
list_size = '100'
try:
xcount = args.pop(0)
except:
xcount = 'None' # -> random

run_test(repeat, list_size, xcount)

if __name__ == '__main__':
import sys
main(sys.argv[1:])
HTH

[drrngrvy]

Bruno Desthuilliers wrote:

ma*******@gmail.com a écrit :

Problem:

You have a list of unknown length,

This doesn't exist in Python:
len(alist)

such as this: list > [X,X,X,O,O,O,O]. You want to extract all and onlythe X's.

braindead solution - relying on zeros being zeros or any other False value:
all_xxx

You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

Then it *may* be possible to optimize - but code will break as soon as
this rule change. So is there a real need for optimisation ? (hint: dont
guess, profile)
FWIW, I've collected all suggestions here (and perhaps some others) and
hacked a Q&D benchmark. Usage is:

python test_lists.py [repeat[list_size [xcount]]

where:
* repeat is the number of iteration, default to 1000
* list_size is the size of the list, default to 100
* xcount is the number or non-zero values in the list, default is random

I've run it a few times, and it seems that in most cases,
* the bisect-like approach (Alex Martelli / Karl Friedrich Bolz) is
the winner
* the while/pop approach of the OP (slightly rewritten...) is really wrong

FWIW, one of the dummiest possible approach IMHO
(ie filter(None, alist)) behaves quite correctly wrt some other
'optimized' approachs - and is still safe if the rules about the
composition of the list changes... Could it be that no optimization is
sometime the best optimisation ?-)
# test_lists.py
from itertools import takewhile
from timeit import Timer
from random import randint

def get_list(size, xcount=None):
if xcount is None:
xcount else:
assert xcount < zcount return [1] * xcount + [0] * zcount

def with_while(alist):
res while alist and alist[0]:
res.append(alist.pop(0))
return res

def with_for(alist):
res for x in alist:
if not x: break
res.append(x)
return res

def with_filter(alist):
return filter(None, alist)

def with_comprehension(alist):
return [x for x in alist if x]

def with_takewhile(alist):
return list(takewhile(lambda x: x!=0, alist))

def with_slice_try(alist):
try:
return alist[:alist.index(0)]
except ValueError:
return alist[:]

def with_slice_safe(alist):
alist.append(0)
return alist[:alist.index(0)]

def with_delslice_safe(alist):
alist.append(0)
del alist[alist.index(0):]
return alist

def with_sect(alist):
low high while low < high:
mid if alist[mid] = 0:
high else:
low return alist[:low]

_candidates if n.startswith('with_') and callable(o)]

def run_test(repeat00, list_size='100', xcount='None'):
global _candidate

print """
params :
* repeat : %s
* list_size : %s
* xcounts : %s
""" % (repeat, list_size, xcount)
results for n in _candidates:
stm, stp 'from __main__ import %s, get_list' % n)
results[n]
sorted_results for n, time in results..items()])
for _, result in sorted_results:
print "%s : %s" % result
def main(args):
try:
repeat except:
repeat try:
list_size except:
list_size try:
xcount except:
xcount
run_test(repeat, list_size, xcount)

if __name__ = '__main__':
import sys
main(sys.argv[1:])


HTH

[Magnus Lycka]

ma*******@gmail.com wrote:

Problem:

You have a list of unknown length, such as this: list =
[X,X,X,O,O,O,O]. You want to extract all and only the X's. You know
the X's are all up front and you know that the item after the last X is
an O, or that the list ends with an X. There are never O's between
X's.

I have been using something like this:
_____________________

while list[0] != O:
storage.append(list[0])
list.pop(0)
if len(list) == 0:
break
_____________________

But this seems ugly to me, and using "while" give me the heebies. Is
there a better approach?

It seems few suggested solutions actually do the same thing as
your code shows. I think this does. (Untested)

try:
ix = aList.index(O)
storage, aList = aList[:ix], aList[ix:]
except ValueError:
# No O's
storage, aList = aList, []
The main advantage with my approach over yours is that
all iterations, all the looping, takes place in fast C
code, unless your list elements are Python classes that
implement __cmp__ etc. If testing 'aList[0] == O'
involves Python, things might slow down a bit...

..index() takes linear time, but it's fairly fast. As
Alex suggested, you might want to replace it with a
O(log n) solution for big lists. You might need rather
big lists for the Python based O(log n) to get faster
than the C based O(n) though. Measure.