2 ms·

Interesting read. This post seems to be written by Adam Gordon Bell who is also the host of the excellect CoRecursive podcast. Recently featured at HN in The Un

by lyxell 5y ago

Interesting read. This post seems to be written by Adam Gordon Bell who is also the host of the excellect CoRecursive podcast. Recently featured at HN in The Untold Story of SQLite [0]. [0]: https://news.ycombinator.com/item?id=27718701 https://news.ycombinator.com/item?id=27718701

agbell 5y ago
That's me. Thanks for reading it and listening to the podcast. The SQLite episode is now nearly the most listened to, thanks to hacker news. On Merging lists: I was caught off guard by recommendation to use sort to merge sorted lists. Everyone I mentioned it to was surprised as well so I thought it was worthy of some investigation. This is my first C extension in Python and I got help so someone else might be able to do even better than this. It is interesting when our normal short hands for thinking about runtime complexity break down.
- CogitoCogito 5y ago
  > It is interesting when our normal short hands for thinking about runtime complexity break down. Actually I think more interesting would be to write a python version following the algorithm of your C extension (i.e. only allow two lists, don't allow generators, don't return generators, etc). You could probably do that quite quickly and generate the same graphs. I would expect that python version to lie somewhere between your C extension and the heapq.merge() version which is more general. edit: If you were to do this, I wouldn't recommend using the python version in your blog since it pops the lists from the front. This seems to be O(n) in general: https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity I did a 10 minute glance at the python source code and couldn't totally verify this (it needs more than 10 minutes...), but it makes sense for popping from anywhere but the back to cause a list copy to occur. Maybe this isn't technically necessary when popping from the front, but I couldn't verify it. Either way it's easy to avoid by just not mutating the input lists anyway so I don't see a good reason not to go that way.
  - agbell 5y ago
    So we could determine what gains I am getting are due to C and the specific compares and which are due just being 2 lists? That would be an interesting test. Maybe I'll do a follow-up. Thanks for reading the article. I suspect you know way more about C extensions in Python than I do. I saw you have a talk on this topic. I think you are totally right that pop is not the way to go, but using an offset to track the head, like the C example does. I actually put that in a footnote, because I was considering testing my python version but the SO answer mentioned pop being expensive. I think the simple version is still great as psuedo-code for communicating a solution though and hopefully it makes the c code a bit easier to follow once you've seen the python version.
    - CogitoCogito 5y ago
      Well the version I'm saying is essentially the same as the pop version you have so I don't think it's too complicated. You would just do something like this instead: def merge_sorted_lists(l1, l2): sorted_list = [] i = 0 j = 0 while i < len(l1) or j < len(l2): if i == len(l1): sorted_list.append(l2[j]) j += 1 continue if j == len(l2): sorted_list.append(l1[i]) i += 1 continue if l1[i] < l2[j]: sorted_list.append(l1[i]) i += 1 else: sorted_list.append(l2[j]) j += 1 return sorted_list I haven't tested that (you probably should before using it), but it looks mostly right and is essentially the same algorithm as yours.
      - RogerL 5y ago
        This simple change is about 3x as fast. I think it is relevant because the same should be done in the original c code. 2x comes from the list swap, the rest comes from the use of N in the while conditional. def merge2(l1, l2): if len(l1) == 0: return [x for x in l2] if len(l2) == 0: return [x for x in l1] # ensure l1 is exhausted first to minimize # comparisons if l1[-1] > l2[-1]: l1, l2 = l2, l1 sorted_list = [] i = 0 j = 0 N = len(l1) while i < N: if l1[i] <= l2[j]: sorted_list.append(l1[i]) i += 1 else: sorted_list.append(l2[j]) j += 1 sorted_list.extend(l2[j:]) return sorted_list

by lyxell 5y ago

agbell 5y ago

That's me. Thanks for reading it and listening to the podcast. The SQLite episode is now nearly the most listened to, thanks to hacker news. On Merging lists: I was caught off guard by recommendation to use sort to merge sorted lists. Everyone I mentioned it to was surprised as well so I thought it was worthy of some investigation. This is my first C extension in Python and I got help so someone else might be able to do even better than this. It is interesting when our normal short hands for thinking about runtime complexity break down.

CogitoCogito 5y ago
> It is interesting when our normal short hands for thinking about runtime complexity break down. Actually I think more interesting would be to write a python version following the algorithm of your C extension (i.e. only allow two lists, don't allow generators, don't return generators, etc). You could probably do that quite quickly and generate the same graphs. I would expect that python version to lie somewhere between your C extension and the heapq.merge() version which is more general. edit: If you were to do this, I wouldn't recommend using the python version in your blog since it pops the lists from the front. This seems to be O(n) in general: https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity I did a 10 minute glance at the python source code and couldn't totally verify this (it needs more than 10 minutes...), but it makes sense for popping from anywhere but the back to cause a list copy to occur. Maybe this isn't technically necessary when popping from the front, but I couldn't verify it. Either way it's easy to avoid by just not mutating the input lists anyway so I don't see a good reason not to go that way.
- agbell 5y ago
  So we could determine what gains I am getting are due to C and the specific compares and which are due just being 2 lists? That would be an interesting test. Maybe I'll do a follow-up. Thanks for reading the article. I suspect you know way more about C extensions in Python than I do. I saw you have a talk on this topic. I think you are totally right that pop is not the way to go, but using an offset to track the head, like the C example does. I actually put that in a footnote, because I was considering testing my python version but the SO answer mentioned pop being expensive. I think the simple version is still great as psuedo-code for communicating a solution though and hopefully it makes the c code a bit easier to follow once you've seen the python version.
  - CogitoCogito 5y ago
    Well the version I'm saying is essentially the same as the pop version you have so I don't think it's too complicated. You would just do something like this instead: def merge_sorted_lists(l1, l2): sorted_list = [] i = 0 j = 0 while i < len(l1) or j < len(l2): if i == len(l1): sorted_list.append(l2[j]) j += 1 continue if j == len(l2): sorted_list.append(l1[i]) i += 1 continue if l1[i] < l2[j]: sorted_list.append(l1[i]) i += 1 else: sorted_list.append(l2[j]) j += 1 return sorted_list I haven't tested that (you probably should before using it), but it looks mostly right and is essentially the same algorithm as yours.
    - RogerL 5y ago
      This simple change is about 3x as fast. I think it is relevant because the same should be done in the original c code. 2x comes from the list swap, the rest comes from the use of N in the while conditional. def merge2(l1, l2): if len(l1) == 0: return [x for x in l2] if len(l2) == 0: return [x for x in l1] # ensure l1 is exhausted first to minimize # comparisons if l1[-1] > l2[-1]: l1, l2 = l2, l1 sorted_list = [] i = 0 j = 0 N = len(l1) while i < N: if l1[i] <= l2[j]: sorted_list.append(l1[i]) i += 1 else: sorted_list.append(l2[j]) j += 1 sorted_list.extend(l2[j:]) return sorted_list