<posted & mailed> 

Alex Martelli wrote:

>  JB wrote:
>          ...
>  
> > <list2> remains sorted, that is, the entries from <list1>
> > should be inserted to the right positions in <list2>.
> > When <n> is defined by
> > n := max(len(list1),len(list2)),
> > then <move> should work in O(n) time.
> > 
> > Any hints of how to do this (as fast as possible)?
>  
>  Hmmm, I hadn't seen the O(N) constraint.  The approach
>  previously posted by Emile and commented on by me does
>  not guarantee meeting that constraint: it CAN happen to
>  become O(N log N) when most of list2 ends up appended
>  to list1.  For an O(N) guarantee, I think you must use
>  a merge-like linear scan on the lists -- also requiring
>  O(N) temporary auxiliary storage, of course.
>  
>  
>  Here's a fancifully-expressed solution...:
>  
>  au = [None] * 2
>  it = iter(list1)
>  au[0] = [ it.next(), 0, it, [] ]
>  it = iter(list2)
>  au[1] = [ it.next(), 1, it, [] ]
>  
>  while True:
>      m = min(au)
>      i = m[1]
>      if i and f(m[0]): i = 0
>      au[i][3].append(m[0])
>      try: m[0] = m[2].next()
>      except StopIteration: break
>  
>  # now, either list is exhausted
>  # if any tail is left in the first list, copy it
>  au[0][3].extend(au[0][2])
>  # if any tail is left in the second list, distribute it
>  for x in au[1][2]:
>      au[not f(x)][3].append(x)
>  
>  # finally, copy the results back
>  list1[:] = au[0][3]
>  list2[:] = au[1][3]
>  
>  
>  OK, OK, NOT the most lucid code I ever posted, I agree.
>  
>  But I get it by reasoning back from the GENERAL case of
>  mergesort (for any number of streams) and specializing
>  for 2 streams AND adding the subtle asymmetry beteween
>  the first list (whose items must all go to the first
>  auxiliary list) and the second one (whose item must go
>  to the first auxiliary list iff they satisfy predicate
>  f, otherwise to the second auxiliary list).  I bet you
>  can do better by exploiting the specifics of this case!-)
>  
>  Still -- this IS O(N) in time and space!

Thx. I shell try to understand this to-morrow.
I am working on a list view item. Deoending on a string 
(that even may be a regular expression), some of the 
entries of the list view are shown and some of them are 
not. I thought, I should use two lists for that: A list of 
the visible entries and a list of the invisble entries. The 
original QListView (I use PyQt, that is wonderful by the 
way) is not very suitable for this as it is too slow. If I 
do everything myself, I can be much faster as I only 
implement zje functionality I need. Later I can do 
everything in C++ and assembly language, if I have the time 
for this.

-- 
Janos Blazi


-----------== Posted via Newsfeed.Com - Uncensored Usenet News ==----------
   http://www.newsfeed.com       The #1 Newsgroup Service in the World!
-----= Over 100,000 Newsgroups - Unlimited Fast Downloads - 19 Servers =-----
-- 
http://mail.python.org/mailman/listinfo/python-list