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]

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)

??

 

[snoe]

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]

 

[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]

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

 

[Paul McGuire]

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:
['X', 'X', 'X']

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

-- Paul

 

[Steve Holden]

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.

... 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

 

[Scott David Daniels]

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.

 

[Carl Friedrich Bolz]

Hi!

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

 

[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

 

[=?ISO-8859-1?Q?Sch=FCle_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

 

[=?ISO-8859-1?Q?Sch=FCle_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

 

[Scott David Daniels]

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]

 

[=?ISO-8859-1?Q?Sch=FCle_Daniel?=]

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

 

[=?ISO-8859-1?Q?Sch=FCle_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

 

[Dave Hansen]

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

 

[Alex Martelli]

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]

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]

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.