Charles Krug <[EMAIL PROTECTED]> wrote:
> On 2006-02-11, Alex Martelli <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
