| Horizon68 <horizon@horizon.com>: Apr 01 10:55AM -0700 Hello, Read this: My new and more efficient Parallel Sort Library is here.. Here is what have changed: My algorithm of finding the median of Parallel merge of my Parallel Sort Library that you will find here in my website: https://sites.google.com/site/scalable68/parallel-sort-library Is O(log(min(|A|,|B|))), where |A| is the size of A, since the binary search is performed within the smaller array and is O(lgN). But this new algorithm of finding the median of parallel merge of my Parallel Sort Library is O(log(|A|+|B|)), which is slightly worse. With further optimizations the order was reduced to O(log(2*min(|A|,|B|))), which is better, but is 2X more work, since both arrays may have to be searched. All algorithms are logarithmic. Two binary searches were necessary to find an even split that produced two equal or nearly equal halves. Luckily, this part of the merge algorithm is not performance critical. So, more effort can be spent looking for a better split. This new algorithm in the parallel merge balances the recursive binary tree of the divide-and-conquer and improve the worst-case performance of parallel merge sort. You can download it from: https://sites.google.com/site/scalable68/parallel-sort-library-that-is-more-efficient Thank you, Amine Moulay Ramdane. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com. |
No comments:
Post a Comment