Classical FP problem in python : Hamming problem

[Francis Girard]

Le vendredi 28 Janvier 2005 08:27, Paul Rubin a écrit :
> Francis Girard <francis.girard at free.fr> writes:
> > Thank you Nick and Steven for the idea of a more generic imerge.
>
> If you want to get fancy, the merge should use a priority queue (like
> in the heapsort algorithm) instead of a linear scan through the
> incoming iters, to find the next item to output.  That lowers the
> running time to O(n log k) instead of O(n*k), where k is the number of
> iterators and n is the length.

The goal was only to show some FP construct on small problems. Here the number 
of iterators are intended to be fairly small.

Otherwise, yes, you could exploit the fact that, at one loop execution, you 
already seen most of the elements at previous loop execution, storing them in 
some heap structure and therefore not having to recan the whole list of 
"already seen" iterator values at each loop execution.

Thank you

Francis Girard