Moving list entries from one list to another

[François Pinard]

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

Being O(n) and being as fast as possible may be contradictory goals.

If you use `list1.remove()' and `list2.insert()', you may get up to O(n**2).
But if you evaluate first how many moves will be required, which can be
decided in O(n), and find out that this number is "small", you may beat with
`list1.remove()' and `list2.insert()' an algorithm designed to be O(n).

Now, being O(n) is all of a requirement.  It means in particular that you
cannot use neither `list2.insert()' that might climb up to O(n**2), nor
`list2.sort()' which is O(n*log(n)).  The only choice left seems to build
a `prelist2' holding only the elements to move, and then merge `prelist2'
with `list2' in a O(n) pass.  You also have no choice but separately copy
`list1' without the moved elements, and this can be done O(n) too.

Of course, I presume that `f' is efficient itself, probably based on a
dictionary of some sort say.  dictionary lookup is slightly more than O(1),
but I hope it is O(1) enough for your purpose.  Else, you have to implement
another way.  If `f' is more than O(1), your problem cannot be solved.

If `prelist2.append()' is not O(1) enough for you either, you have to
pre-allocate it at once to full length, and using `f', the length may be
predicted in O(n) time, and then fill its slots using indexing.

All in all, I think that you will pay a high multiplicator price for being
strictly O(n), and you could achieve something much faster _in practice_
by relaxing this constraint.

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard