snip
Another idea for this method would be that in some cases I noticed that
it was useful to know which source each element would come from as well,
as well as removing duplicates from the results.
For instance
s1 = [1, 3, 5, 7]
s2 = [2, 3, 4]
for k, s in merge_by_sort(s1, s2):
print
Lasse Vågsæther Karlsen wrote:
snip
Another idea for this method would be that in some cases I noticed that
it was useful to know which source each element would come from as well,
as well as removing duplicates from the results.
snip
The removing duplicates problem would probably be
Function name is perhaps not the best one. It occurs to me that this
is the GROUP BY in SQL so perhaps a different name is better, but
then again this might be moot if such a already exists somewhere :)
Amazing, you keep reinventing things, even with the exact same name :)
from itertools
George Sakkis wrote:
Function name is perhaps not the best one. It occurs to me that this
is the GROUP BY in SQL so perhaps a different name is better, but
then again this might be moot if such a already exists somewhere :)
Amazing, you keep reinventing things, even with the exact same name
George Sakkis [EMAIL PROTECTED] wrote:
...
manipulation of a heap to place an item in the right spot, but with 4-5
or a few more sources might not make an impact at all.
Unless you're talking about hundreds or thousands sources, it probably
won't. I would still go for the heap solution
Alex Martelli [EMAIL PROTECTED] wrote:
George Sakkis [EMAIL PROTECTED] wrote:
...
manipulation of a heap to place an item in the right spot, but with 4-5
or a few more sources might not make an impact at all.
Unless you're talking about hundreds or thousands sources, it probably
Alex Martelli wrote:
George Sakkis [EMAIL PROTECTED] wrote:
...
manipulation of a heap to place an item in the right spot, but with 4-5
or a few more sources might not make an impact at all.
Unless you're talking about hundreds or thousands sources, it probably
won't. I would still
George Sakkis [EMAIL PROTECTED] wrote:
...
i.e., a heap solution may be over 4 times faster than a sort-based one
(in the following implementations).
Interesting; I thought timsort on small almost ordered lists would be
practically as fast as the heap. Still, how is 0.10344 over 4 times
Mike C. Fletcher [EMAIL PROTECTED] wrote:
...
One thing to keep in mind (if you care about performance) is that you
one could use bisect, instead of sort, as the sorted list of streams is
already in order save for the one element you are processing. Btw, nice
trick with reverse to reduce
George Sakkis [EMAIL PROTECTED] wrote:
Lasse Vågsæther Karlsen [EMAIL PROTECTED] wrote:
Thanks, that looks like Mike's solution except that it uses the
built-in heapq module.
This make a big difference for the algorithmic complexity; replacing an
item in a heap is much more efficient
Alex Martelli wrote:
try it (and read the Timbot's article included in Python's sources, and the
sources themselves)...
Just a reading advise. The translated PyPy source
pypy/objectspace/listsort.py might be more accessible than the
corresponding C code.
Kay
--
Kay Schluehr wrote:
Alex Martelli wrote:
try it (and read the Timbot's article included in Python's sources, and the
sources themselves)...
Just a reading advise. The translated PyPy source
pypy/objectspace/listsort.py might be more accessible than the
corresponding C code.
indeed. it
[Alex Martelli]
try it (and read the Timbot's article included in Python's sources, and the
sources themselves)...
[Kay Schluehr]
Just a reading advise. The translated PyPy source
pypy/objectspace/listsort.py might be more accessible than the
corresponding C code.
[cfbolz]
indeed. it is at
Alex Martelli wrote:
George Sakkis [EMAIL PROTECTED] wrote:
snip
Yes, it's a little inconvenient that the builtin heap doesn't take a
comparison operation but you can easily roll your own heap by transforming
each item to a (key,item) tuple. Now that I'm thinking about it, it might
be a good
Lasse Vågsæther Karlsen [EMAIL PROTECTED] wrote:
Alex Martelli wrote:
George Sakkis [EMAIL PROTECTED] wrote:
snip
Yes, it's a little inconvenient that the builtin heap doesn't take a
comparison operation but you can easily roll your own heap by transforming
each item to a (key,item) tuple.
George Sakkis wrote:
snip
Just added a recipe at
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440673. You can try
both and see if there's any significant performance difference for your data.
snip
Thanks, will take a look at it later. The sort solution seems to work
nicely. Might
Lasse Vågsæther Karlsen [EMAIL PROTECTED] wrote:
George Sakkis wrote:
snip
Just added a recipe at
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/440673. You can
try
both and see if there's any significant performance difference for your
data.
snip
Thanks, will take a look
Ok, that one looks more sleak than what I came up with.
Couple of things I learn from your solution, please correct me if I
misunderstood something:
1. list containing other lists will sort itself based on first element
on lists inside ?
2. sort(), pop() is not costly operations
Other than that
Lasse Vågsæther Karlsen [EMAIL PROTECTED] wrote:
Ok, that one looks more sleak than what I came up with.
For the most efficient and elegant solution, check out Raymond Hettinger's
reply to:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/141934
George
--
Thanks, that looks like Mike's solution except that it uses the
built-in heapq module.
While this one contains less code than Mike's solution it seems to lack
the ability to control the comparison operation, which means it won't
work in my case. I need to both be able to sort on an arbitrary
Lasse Vågsæther Karlsen [EMAIL PROTECTED] wrote:
Thanks, that looks like Mike's solution except that it uses the
built-in heapq module.
This make a big difference for the algorithmic complexity; replacing an item in
a heap is much more
efficient than sorting the whole list.
While this one
Lasse Vågsæther Karlsen wrote:
Ok, that one looks more sleak than what I came up with.
Couple of things I learn from your solution, please correct me if I
misunderstood something:
1. list containing other lists will sort itself based on first element
on lists inside ?
Correct, comparison is
Lasse Vågsæther Karlsen wrote:
I need to merge several sources of values into one stream of values. All
of the sources are sorted already and I need to retrieve the values from
snip
Ok, after working through the various sources and solutions, here's what
I finally ended up with:
def
I need to merge several sources of values into one stream of values. All
of the sources are sorted already and I need to retrieve the values from
them all in sorted order.
In other words:
s1 = [10, 20, 30, 40, 50]
s2 = [15, 25]
s3 = [17, 27, 37]
for value in ???(s1, s2, s3):
print value
Lasse Vågsæther Karlsen wrote:
I need to merge several sources of values into one stream of values.
All of the sources are sorted already and I need to retrieve the
values from them all in sorted order.
In other words:
s1 = [10, 20, 30, 40, 50]
s2 = [15, 25]
s3 = [17, 27, 37]
for
Lasse Vågsæther Karlsen wrote:
I need to merge several sources of values into one stream of values. All
of the sources are sorted already and I need to retrieve the values from
them all in sorted order.
In other words:
s1 = [10, 20, 30, 40, 50]
s2 = [15, 25]
s3 = [17, 27, 37]
for value in
26 matches
Mail list logo