Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
[Tim] 1. Merge 2 at a time instead of just 1. That is, first sort the next 2 elements to be merged (1 compare and a possible swap). Then binary search to find where the smaller belongs, and a shorter binary search to find where the larger belongs. Then shift both into place. [Armin] Good idea, but when I tried that it seemed to increase the total number of comparisons (on random inputs with only up to 136 items). The increase is on the order of 5%. I'm not sure reduced data movement can compensate for that in Python. Which is another way of saying bad idea - that must be why I didn't pursue it to begin with ;-) Thanks for trying! I plugged a similar routine into the code I showed before to count the # of comparisons in Nha Pham's idea, and this merge 2 at a time thing has a higher average # of compares (over all permutations) than Nha's (which in turn has a higher average than the status quo). That makes some sense, thinking about what they do. Nha's algorithm has some supernaturally good cases (input array already ascending or already descending), but merge 2 at a time doesn't appear to have any. In any case, the information-theoretic minimum average number of comparisons for merging N sorted elements with 2 sorted elements is (where do the 2 belong in the final list of N+2 elements? = comb(N+2, 2)): log2((N+2)*(N+1)/2) = log2(N+2) + log2(N+1) - 1 Add a comparison to get the 2 elements in order to begin with, and we're up to log2(N+2) + log2(N+1) Two independent binary inserts (first to a list of size N, and then to a list of size N+1) comes out to the same. So even being supernaturally clever can't reduce the average number of compares this way. And since, in context, we're only looking at short arrays, a marginal saving in data movement costs (which are still O(N**2) worst case) are unlikely to be significant. Still, if anyone wants to go nuts ... ;-) ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
Hi Tim, On 10 March 2015 at 18:22, Tim Peters tim.pet...@gmail.com wrote: 1. Merge 2 at a time instead of just 1. That is, first sort the next 2 elements to be merged (1 compare and a possible swap). Then binary search to find where the smaller belongs, and a shorter binary search to find where the larger belongs. Then shift both into place. Good idea, but when I tried that it seemed to increase the total number of comparisons (on random inputs with only up to 136 items). The increase is on the order of 5%. I'm not sure reduced data movement can compensate for that in Python. Test and code available here: https://bitbucket.org/arigo/arigo/src/default/hack/pypy-hack/list_sort/ The change to insert two items at a time is here: https://bitbucket.org/arigo/arigo/commits/68e04d143dc242cfd9e3934451321f685a68a8e2 (This is taken straight from PyPy's code.) A bientôt, Armin. ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
I suspect that you will find the Python community extremely conservative about any changes to its sorting algorithm, given that it took thirteen years and some really impressive automated verification software to find this bug: http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ On Sun, Mar 8, 2015 at 5:17 PM, nha pham phq...@gmail.com wrote: We can optimize the TimSort algorithm by optimizing its binary insertion sort. The current version of binary insertion sort use this idea: Use binary search to find a final position in sorted list for a new element X. Then insert X to that location. I suggest another idea: Use binary search to find a final postion in sorted list for a new element X. Before insert X to that location, compare X with its next element. For the next element, we already know if it is lower or bigger than X, so we can reduce the search area to the left side or on the right side of X in the sorted list. I have applied my idea on java.util. ComparableTimSort.sort() and testing. The execute time is reduced by 2%-6% with array of random integer. Here is detail about algorithm and testing: https://github.com/nhapq/Optimize_binary_insertion_sort Sincerely. phqnha ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/rmsr%40lab.net ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
On Mon, Mar 9, 2015 at 10:53 AM, Steven D'Aprano st...@pearwood.info wrote: On Sun, Mar 08, 2015 at 10:57:30PM -0700, Ryan Smith-Roberts wrote: I suspect that you will find the Python community extremely conservative about any changes to its sorting algorithm, given that it took thirteen years and some really impressive automated verification software to find this bug: On the other hand, the only person who really needs to be convinced is Tim Peters. It's really not up to the Python community. Also, there's no sense discouraging people who have ideas to contribute. So what if nha pham's contribution isn't accepted? You never know when the next Tim Peters, Georg Brandl, Mark Dickinson, or Brett Cannon will turn up. (That list is practically endless. Don't feel slighted if I failed to mention you.) With seven billion people out there, a few of them are bound to be pretty smart. Skip ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
On Sun, Mar 08, 2015 at 10:57:30PM -0700, Ryan Smith-Roberts wrote: I suspect that you will find the Python community extremely conservative about any changes to its sorting algorithm, given that it took thirteen years and some really impressive automated verification software to find this bug: On the other hand, the only person who really needs to be convinced is Tim Peters. It's really not up to the Python community. The bug tracker is the right place for discussing this. -- Steve ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
On 15-03-08, nha pham wrote: We can optimize the TimSort algorithm by optimizing its binary insertion sort. The current version of binary insertion sort use this idea: Use binary search to find a final position in sorted list for a new element X. Then insert X to that location. I suggest another idea: Use binary search to find a final postion in sorted list for a new element X. Before insert X to that location, compare X with its next element. For the next element, we already know if it is lower or bigger than X, so we can reduce the search area to the left side or on the right side of X in the sorted list. I don't understand how this is an improvement, since with binary search the idea is that each comparison cuts the remaining list to search in half; i.e., each comparison yields one bit of information. Here, you're spending a comparison to cut the list to search at the element you just inserted, which is probably not right in the middle. If you miss the middle, you're getting on average less than a full bit of information from your comparison, so you're not reducing the remaining search space by as much as you would be if you just compared to the element in the middle of the list. I have applied my idea on java.util. ComparableTimSort.sort() and testing. The execute time is reduced by 2%-6% with array of random integer. For all that, though, experiment trumps theory... Here is detail about algorithm and testing: https://github.com/nhapq/Optimize_binary_insertion_sort Sincerely. phqnha ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
I do not know exactly, one thing I can imagine is: it turns the worst case of binary insertion sort to best case. With sorted array in range of 32 or 64 items, built from zero element. The new element you put into the sorted list has a high chance of being the smallest or the the highest of the sorted list (or nearly highest or nearly smallest) If that case happen, the old binary insertion sort will have the investigate all the list, while with my idea, it just have to compare more 1-2 times. I will try to run more test an more thinking to make sure though. On Mon, Mar 9, 2015 at 11:48 AM, nha pham phq...@gmail.com wrote: I do not know exactly, one thing I can imagine is: it turns the worst case of binary insertion sort to best case. With sorted array in range of 32 or 64 items, built from zero element. The new element you put into the sorted list has a high chance of being the smallest or the the highest of the sorted list (or nearly highest or nearly smallest) If that case happen, the old binary insertion sort will have the investigate all the list, while with my idea, it just have to compare more 1-2 times. I will try to run more test an more thinking to make sure though. On Mon, Mar 9, 2015 at 10:39 AM, Isaac Schwabacher ischwabac...@wisc.edu wrote: On 15-03-08, nha pham wrote: We can optimize the TimSort algorithm by optimizing its binary insertion sort. The current version of binary insertion sort use this idea: Use binary search to find a final position in sorted list for a new element X. Then insert X to that location. I suggest another idea: Use binary search to find a final postion in sorted list for a new element X. Before insert X to that location, compare X with its next element. For the next element, we already know if it is lower or bigger than X, so we can reduce the search area to the left side or on the right side of X in the sorted list. I don't understand how this is an improvement, since with binary search the idea is that each comparison cuts the remaining list to search in half; i.e., each comparison yields one bit of information. Here, you're spending a comparison to cut the list to search at the element you just inserted, which is probably not right in the middle. If you miss the middle, you're getting on average less than a full bit of information from your comparison, so you're not reducing the remaining search space by as much as you would be if you just compared to the element in the middle of the list. I have applied my idea on java.util. ComparableTimSort.sort() and testing. The execute time is reduced by 2%-6% with array of random integer. For all that, though, experiment trumps theory... Here is detail about algorithm and testing: https://github.com/nhapq/Optimize_binary_insertion_sort Sincerely. phqnha ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
It may be that the comparison that you do is between two elements that are almost always in the same cache line whereas the binary search might often incur a cache miss. On Mon, Mar 9, 2015 at 2:49 PM, nha pham phq...@gmail.com wrote: I do not know exactly, one thing I can imagine is: it turns the worst case of binary insertion sort to best case. With sorted array in range of 32 or 64 items, built from zero element. The new element you put into the sorted list has a high chance of being the smallest or the the highest of the sorted list (or nearly highest or nearly smallest) If that case happen, the old binary insertion sort will have the investigate all the list, while with my idea, it just have to compare more 1-2 times. I will try to run more test an more thinking to make sure though. On Mon, Mar 9, 2015 at 11:48 AM, nha pham phq...@gmail.com wrote: I do not know exactly, one thing I can imagine is: it turns the worst case of binary insertion sort to best case. With sorted array in range of 32 or 64 items, built from zero element. The new element you put into the sorted list has a high chance of being the smallest or the the highest of the sorted list (or nearly highest or nearly smallest) If that case happen, the old binary insertion sort will have the investigate all the list, while with my idea, it just have to compare more 1-2 times. I will try to run more test an more thinking to make sure though. On Mon, Mar 9, 2015 at 10:39 AM, Isaac Schwabacher ischwabac...@wisc.edu wrote: On 15-03-08, nha pham wrote: We can optimize the TimSort algorithm by optimizing its binary insertion sort. The current version of binary insertion sort use this idea: Use binary search to find a final position in sorted list for a new element X. Then insert X to that location. I suggest another idea: Use binary search to find a final postion in sorted list for a new element X. Before insert X to that location, compare X with its next element. For the next element, we already know if it is lower or bigger than X, so we can reduce the search area to the left side or on the right side of X in the sorted list. I don't understand how this is an improvement, since with binary search the idea is that each comparison cuts the remaining list to search in half; i.e., each comparison yields one bit of information. Here, you're spending a comparison to cut the list to search at the element you just inserted, which is probably not right in the middle. If you miss the middle, you're getting on average less than a full bit of information from your comparison, so you're not reducing the remaining search space by as much as you would be if you just compared to the element in the middle of the list. I have applied my idea on java.util. ComparableTimSort.sort() and testing. The execute time is reduced by 2%-6% with array of random integer. For all that, though, experiment trumps theory... Here is detail about algorithm and testing: https://github.com/nhapq/Optimize_binary_insertion_sort Sincerely. phqnha ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/mistersheik%40gmail.com ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
[nha pham phq...@gmail.com] Statement_1: With an array of size N or less than N, we need at most log2(N) comparisons to find a value (or a position, incase the search miss), using the binary search algorithm. proof: This statement is trivia, and I believe, someone outthere already proved it. Sorry for the quick message here. It's just a simple point where it will pay not to get off on a wrong foot ;-) Correct: for an array of size N, binary search can require as many as ceiling(log2(N+1)) comparisons. That's because there are N+1 possible results for an array of size N. For example, for an array of size 3, [A, B, C], the answer may be before A, between A and B, between B and C, or after C. 3 elements, 3+1 = 4 possible results. log2(3) comparisons are not enough to distinguish among 4 results. Make it trivial, an array of length 1. Then 1 comparison is obviously necessary and sufficient in all cases. And, indeed, ceiling(log2(1+1)) = 1. log2(1) equals 0, too small. For the rest, I haven't been able to understand your description or your pseudo-code. I'll try harder. Some things clearly aren't doing what you _intend_ them to do. For example, in your Python code, each time through the outer loop you're apparently trying to sort the next CHUNK elements, but you end up appending CHUNK+1 values to data2 (or data3). Or in this part: for i in range(low,high): x = data[i] if x = data[i-1]: the first time that loop is executed low == 0, and so i == 0 on the first iteration, and so the conditional is if x = data[0-1] That's referencing data[-1], which is the very last element in data - which has nothing to do with the CHUNK you're trying to sort at the time. So there are a number of errors here, which makes it that much harder to sort out (pun intended wink) what you're trying to do. It would help you to add some asserts to verify your code is doing what you _hope_ it's doing. For example, add assert data2[low: high] == sorted(data[low: high]) assert len(data2) == high to the end of your `sample` loop, and similarly for data3 in your `new` loop. Until those asserts all pass, you're not testing code that's actually sorting correctly. Repair the errors and you almost certainly won't find `new` running over 10 times faster than `sample` anymore. I don't know what you _will_ discover, though. If the code doesn't have to sort correctly, there are much simpler ways to make it run _very_ much faster ;-) ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
Thank you very much. I am very happy that I got a reply from Tim Peter. You are correct, my mistake. The python code should be: for i in range(low+1,high): //because we already add data[low] x = data[i] if x = data[i-1]: After I fix it, here is the result: random array 10^6: Old binsort: 1.3322 New binsort: 1.0015 ratio: 0.33 You are right, it is not ten times faster anymore. I will update other results soon. I do check the result of two sorting methods many times to make sure they are the same. It is just because I do not know how to put assert into the timeit.Timer class. I am pretty sure about this. I will try to write the proof more clearly, sorry for inconvenience. Thank you very much. Nha Pham. On Mon, Mar 9, 2015 at 9:27 PM, Tim Peters tim.pet...@gmail.com wrote: [nha pham phq...@gmail.com] Statement_1: With an array of size N or less than N, we need at most log2(N) comparisons to find a value (or a position, incase the search miss), using the binary search algorithm. proof: This statement is trivia, and I believe, someone outthere already proved it. Sorry for the quick message here. It's just a simple point where it will pay not to get off on a wrong foot ;-) Correct: for an array of size N, binary search can require as many as ceiling(log2(N+1)) comparisons. That's because there are N+1 possible results for an array of size N. For example, for an array of size 3, [A, B, C], the answer may be before A, between A and B, between B and C, or after C. 3 elements, 3+1 = 4 possible results. log2(3) comparisons are not enough to distinguish among 4 results. Make it trivial, an array of length 1. Then 1 comparison is obviously necessary and sufficient in all cases. And, indeed, ceiling(log2(1+1)) = 1. log2(1) equals 0, too small. For the rest, I haven't been able to understand your description or your pseudo-code. I'll try harder. Some things clearly aren't doing what you _intend_ them to do. For example, in your Python code, each time through the outer loop you're apparently trying to sort the next CHUNK elements, but you end up appending CHUNK+1 values to data2 (or data3). Or in this part: for i in range(low,high): x = data[i] if x = data[i-1]: the first time that loop is executed low == 0, and so i == 0 on the first iteration, and so the conditional is if x = data[0-1] That's referencing data[-1], which is the very last element in data - which has nothing to do with the CHUNK you're trying to sort at the time. So there are a number of errors here, which makes it that much harder to sort out (pun intended wink) what you're trying to do. It would help you to add some asserts to verify your code is doing what you _hope_ it's doing. For example, add assert data2[low: high] == sorted(data[low: high]) assert len(data2) == high to the end of your `sample` loop, and similarly for data3 in your `new` loop. Until those asserts all pass, you're not testing code that's actually sorting correctly. Repair the errors and you almost certainly won't find `new` running over 10 times faster than `sample` anymore. I don't know what you _will_ discover, though. If the code doesn't have to sort correctly, there are much simpler ways to make it run _very_ much faster ;-) ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
Thank you for your comment. I admit that I did not thinking about the proof before. Here is my naive proof. I hope you can give me some comments: = # This proof is an empirical thinking and is not completed, it just gives us a closer look. I hope someone can make it more mathematically. In the proof, we assume we are dealing with unique values array (none of them are equal together). Because if they are equal, the lucky search can happen and it is obviously not fair. Statement_1: With an array of size N or less than N, we need at most log2(N) comparisons to find a value (or a position, incase the search miss), using the binary search algorithm. proof: This statement is trivia, and I believe, someone outthere already proved it. We can check again by counting manually. let assume we have array of 32 items: 32 = 16 = 8 = 4 = 2 = 1 (5 comparison) how about 24 items (24 32): 24 = 12 = 6 = 3 = 2 = 1 (5 comparison) ok, good enough. Let's just believe on it to move on. Statement_2: If we divide an array into two parts, the more unbalanced arrays we divide, the more benefit we get from the binary search algorithm. proof: Let's assume we have an array of 256 items. case1: If we divide in middle: 128 - 128 Now, if we search on the left, it costs log2(128) = 7 If we search on the right, it cost los2(128) = 7 case2: If we divide unbalanced: 32 - 224 Now, if we search on the left, it costs log2(32) = 5 If we search on the right, it cost at max 8 comparisons (based on the statement_1). You may not believe me, so let's count it by hand: 224 = 112 = 56 = 28 = 14 = 7 = 4 = 2 = 1 So, if we search on the left, we win 2 comparisons compare to case1. We search on the right, we lose 1 comparison compare to case1 I call this is a benefit. case3: What if we divide more unbalanced: 8 - 248 Search on the left: log2(8) = 3 comparisons. Search on the right, it costs at max 8 comparisons. So if we search on the left, we win 4 comparisons. We search on the right, we lose 1 comparisons. It is more benefit, isnt it? Statement3: Because we are using random array. There is a 50-50 chance that next_X will be bigger or smaller than X. Statement4: We call N is the size of the sorted list, index is the position of X in the sorted list. Because the array is random, index has an equal chance to exist in any position in the sorted list. Statement5: Now we build a model based on previous statements: My idea costs 1 comparison (between X and next_X) to devide the array into two unbalanced parts. The old idea costs 1 comparison to divide the array into two balanced parts. Now let's see which one can find position for next_X faster: If index belongs to [N/4 to 3N/4]: we may lose 1 comparison, or we may not lose. If index belongs to [N/8 to N/4] or [3N/4 to 7N/8]: We may lose 1 comparison, or we win 1 comparison. If index belongs to [N/16 to N/8] or [7N/8 to 15N/16]: We may lose 1 comparison, or we win 2 comparison. If index belongs to [N/32 to N/16] or [15N/16 to 31N/32]: We may lose 1 comparison, or we win 3 comparison. If index belongs to [N/64 to N/32] or [31N/32 to 64N/64]: We may lose 1 comparison, or we win 4 comparison. ... and so on. Statement6: Now we apply the model to a real example. Assume that we already has a sorted list with 16 items. And we already know about index of X. We can think of it as a gamble game with 16 slots. In every slot, we only can bid 1 dollar (statement4). From slot 5th to slot 12th, we may lose 1, or we may not lose, 50-50 chance. So after a huge play times, probability told us that we will lose (8 x 1)/2 = 4 dollars. For slot 3, slot 4, slot 13, slot 14, We may lose 1, or we win 1. So after a huge play times, We wont lose or win anything. For slot 2, slot 15. We may lose 1, or we win 2. So after a huge play times, we can win (2-1)x2 = 2 dollars. For slot 1, slot 16. We may lose 1, or we win 3. So after a huge play times, we can win 4 dollars. In total, after a huge play times, we win 4 + 2 + 0 -4 = 2 dollars ! You can test with sorted list 32 or 64 items or any number you want, I believe the benefit is even more. Conclusion: The unbalanced model give us more benefit than the balanced model. That means with an array big enough, My idea give more benefit than the old idea. I think the lucky ticket companies is already know about this. It is a shame that I do not know mathematic principle about this problem. If I have something more, I will update my proof at: https://github.com/nhapq/Optimize_binary_insertion_sort/blob/master/proof.txt == Thank you. Nha Pham. On Mon, Mar 9, 2015 at 10:39 AM, Isaac Schwabacher ischwabac...@wisc.edu wrote: On 15-03-08, nha pham wrote: We can optimize the TimSort algorithm by optimizing its binary insertion sort. The
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
[nha pham phq...@gmail.com] Thank you very much. I am very happy that I got a reply from Tim Peter. My pleasure to speak with you too :-) You are correct, my mistake. The python code should be: for i in range(low+1,high): //because we already add data[low] x = data[i] if x = data[i-1]: After I fix it, here is the result: random array 10^6: Old binsort: 1.3322 New binsort: 1.0015 ratio: 0.33 You are right, it is not ten times faster anymore. I will update other results soon. I do check the result of two sorting methods many times to make sure they are the same. It is just because I do not know how to put assert into the timeit.Timer class. `assert` is just another Python statement. You simply add it to the code - there's nothing tricky about this. You could, e.g., simply copy and paste the `assert`s I suggested last time. Before you do, trying adding `print index` to your inner loops, and make SIZE much smaller (say, 1000) so you're not overwhelmed with output. You'll be surprised by what you see on the second (and following) CHUNKs. For example, in both `sample` and `new` it will print 900 ninety nine times in a row when doing the last CHUNK. The code still isn't doing what you intend. Until it does, timing it makes little sense :-) I am pretty sure about this. Note that I'm talking about the Python code here, the code you run through timeit. You cannot have checked the results of running _that_ specific code, because it doesn't work at all. You may have checked _other_ code many times. We may get to that later, but since I speak Python, I'm not going to understand what you're doing until we have Python code that works ;-) ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Tunning binary insertion sort algorithm in Timsort.
On 3/8/2015 8:17 PM, nha pham wrote: We can optimize the TimSort algorithm by optimizing its binary insertion sort. The current version of binary insertion sort use this idea: Use binary search to find a final position in sorted list for a new element X. Then insert X to that location. I suggest another idea: Use binary search to find a final postion in sorted list for a new element X. Before insert X to that location, compare X with its next element. For the next element, we already know if it is lower or bigger than X, so we can reduce the search area to the left side or on the right side of X in the sorted list. I have applied my idea on java.util. ComparableTimSort.sort() and testing. The execute time is reduced by 2%-6% with array of random integer. Here is detail about algorithm and testing: https://github.com/nhapq/Optimize_binary_insertion_sort Apply the idea to timsort in python, and try the different cases discussed in Tim's documentation. If it still looks good, open an issue with the patch and put tim.peters as nosy. -- Terry Jan Reedy ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
[Python-Dev] Tunning binary insertion sort algorithm in Timsort.
We can optimize the TimSort algorithm by optimizing its binary insertion sort. The current version of binary insertion sort use this idea: Use binary search to find a final position in sorted list for a new element X. Then insert X to that location. I suggest another idea: Use binary search to find a final postion in sorted list for a new element X. Before insert X to that location, compare X with its next element. For the next element, we already know if it is lower or bigger than X, so we can reduce the search area to the left side or on the right side of X in the sorted list. I have applied my idea on java.util. ComparableTimSort.sort() and testing. The execute time is reduced by 2%-6% with array of random integer. Here is detail about algorithm and testing: https://github.com/nhapq/Optimize_binary_insertion_sort Sincerely. phqnha ___ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
