Moving list entries from one list to another

[JB]

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