3 ms·

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. M

by 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 agbell 5y ago

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