JB
>  I have two lists <list1> and <list2>. The entries of these
>  lists have the format (id,rest), where <id> is a natural
>  number. The list are sorted, the key is <id>.

Your use of the term 'key' here is throwing me.  Lists don't have keys,
dicts do.  Dicts aren't sorted.  ;-/

>  I should like to write a funtion move:
> 
>  def move(f):
> 
>  The argument <f> is a predicate:
>    f: {set of entries of list1} --> {true, false}
>  Now all elements of list1, for which <f> returns true,
>  should be moved to list2. It is very important, that
>  <list2> remains sorted, that is, the entries from <list1>
>  should be inserted to the right positions in <list2>. When

So, you end up with duplicates in list1 based on id?

>  <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)?

> >>
> >> l1 = [1,4,7,10,32,45]
> >> l2 = [4,32]
> >>
> >> def f(lst): return 1
...
> >> [ l1.append(x) for x in l2 if f(x) ]
[None, None]
> >> l1.sort()
> >> l1
[1, 4, 4, 7, 10, 32, 32, 45]
> >>

There, only took a minute.  Is that fast enough?  ;-)

If you need a lot more speed, look into kjbuckets, but that'll take a
lot longer.  ;-)

--

Emile van Sebille
emile@[...].com

---------

-- 
http://mail.python.org/mailman/listinfo/python-list