Re: Classical FP problem in python : Hamming problem
Le vendredi 28 Janvier 2005 08:27, Paul Rubin a écrit :[color=blue]
> Francis Girard <francis.girard @free.fr> writes:[color=green]
> > Thank you Nick and Steven for the idea of a more generic imerge.[/color]
>
> 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.[/color]
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
Le vendredi 28 Janvier 2005 08:27, Paul Rubin a écrit :[color=blue]
> Francis Girard <francis.girard @free.fr> writes:[color=green]
> > Thank you Nick and Steven for the idea of a more generic imerge.[/color]
>
> 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.[/color]
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
Comment