Moving list entries from one list to another

[Emile van Sebille]

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 at fenx.com

---------