A note on natural selection

Replacement selection is the most popular algorithm used in the creation of initial runs for a sort/merge external sort. In 1972, Frazer and Wong suggested a variation, called natural selection, which uses an auxiliary memory reservoir to increase the performance of replacement selection. Natural selection produces longer runs than replacement selection if the auxiliary memory reservoir is sufficiently large, but it behaves very strangely when the size of the auxiliary memory is small: while using more memory resources than replacement selection, it creates shorter runs, thus being less efficient.As it turns out, this deficiency can be avoided at low cost. This note presents a variation of natural selection that is efficient when the auxiliary memory is small.     

Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array.     

归并方式的多线程快速排序算法

本文基于Java平台针对经典快速排序提出改进方案,使用归并的思想对快速排序作了多线程优化,并对单、多线程下的快速排序进行了对比测试和分析。结果表明,通过多线程优化,快速排序在双核主机上对5千万个随机整型数据进行排序的速度是单线程的1.6倍,说明了该优化方法的有效性。该方法思路直观、容易理解,宜作为多核技术教学案例。     

Alphasort: A cache-sensitive parallel external sort

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using commodity processors, memory, and arrays of SCSI disks, AlphaSort runs the industrystandard sort benchmark in seven seconds. This beats the best published record on a 32-CPU 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in one minute. AlphaSort is a cache-sensitive, memoryintensive sort algorithm. We argue that modern architectures require algorithm designers to re-examine their use of the memory hierarchy. AlphaSort uses clustered data structures to get good cache locality, file striping to get high disk bandwidth, QuickSort to generate runs, and replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores. Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) MinuteSort: how much can you sort in one minute, and (2) PennySort: how much can you sort for one penny.     

A new external sorting algorithm with no additional disk space

This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster.     

Comparison of external sorting and internal sorting in virtual memory

To compare the performance of external sorting and internal sorting in virtual memory, (external) mergesort and (internal) quicksort are performed in corresponding environments. Quicksort is run using a virtual memory with fetch on demand and working set replacement policy. Mergesort uses sublists presorted by replacement selection, double buffering for input and output, and two disks. The performance is measured by main memory space allocation, execution time, and main memory space-time integral.To perform well, quicksort is satisfied with a smaller space allocation than mergesort, and it behaves more consistently with respect to space allocation. Mergesort needs far less execution time than quicksort, mainly because of its efficient overlapping of file handling and processor time. With respect to the space-time integral, quicksort outperforms mergesort only when small files (less than 1000 records) are sorted. With large files, mergesort is better, and the relative difference increases with increasing file size. The optimal page size and window size for quicksort are smaller than those typical to existing virtual memory systems, and they tend to decrease with increasing file size.     

A new run-based algorithm for Euler number computing

The Euler number of a binary image is an important topological feature for many image processing, image analysis, pattern recognition, and computer vision applications. This paper proposes a new run-based Euler number computation algorithm. The conventional run-based algorithm processes rows of the given image one-by-one from top to bottom in a single phase. For each row, it finds the runs in the row and records the start and end locations of each run to compute neighbor runs. In contrast, our algorithm calculates the Euler number of an image in two phases. In the first phase, we process odd rows alternately to find runs and only record its end location. In the second phase, we process each of the remaining even rows to find runs and calculate neighboring runs between the current row and the rows immediately above and below using the recorded run data. Using this method, the number of accesses required to compute the Euler number decreases in almost all cases. Analysis of the time complexity and experimental results demonstrate that our algorithm outperforms conventional Euler number computation algorithms.     

Sorting on STAR

This paper gives timing comparisons for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's sorting algorithm, which makes especially good use of vector operations but has a complexity of N (log N)2 as compared to a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.     

Performance of distributive partitioned sort in a demand paging environment

The performances of Distributive Partitioned Sort (DPS) and Quicksort are compared empirically in a demand paging environment. It is found that DPS requires an amount of real memory equal to approximately 40 to 50% in its image size in order to run faster than Quicksort. The performance of DPS deteriorates rapidly in smaller partitions due to excessive page faulting, while that of Quicksort remains fairly constant.     

Performance assessment of multithreaded quicksort algorithm on simultaneous multithreaded architecture

Sorting huge amounts of datasets have become essential in many computer applications, such as search engines, database and web-based applications, in order to improve searching performance. Moreover, due to the witnessed prevalence of the commercial Simultaneous Multithreaded architecture (SMT), parallel programming using multithreading becomes a dire need for efficiently using all available hardware resources for one application. In this paper, one of the efficient and quick algorithms, the Quicksort, is applied as a parallel multithreaded algorithm on SMT architecture, where virtual parallelization has been achieved using the POSIX threads (Pthreads) library. The proposed algorithm is evaluated and compared with its sequential counterpart. The obtained analytical and experimental results reveal that multithreading is a viable technique for implementing the parallel Quicksort algorithm efficiently on SMT architecture, where it has been shown both analytically and experimentally that the parallel multithreaded Quicksort algorithm outperforms the sequential Quicksort algorithm in terms of various performance metrics including; time complexity and speedup.     

介绍一种改进的选择排序算法

排序在数据处理中起着极其重要的作用，而排序在成批数据处理中占了相当的计算机时间，介绍的一种改进的选择排序算法，与通常的简单选择排序算法相比，大大地减少了比较次数，平均节省了４０％的ＣＰＵ时间。且已用ＴＵＲＢＯＰＡＳＣＡＬ语言实现。     

Space and time optimal algorithms for a class of rectangle intersection problems

The intersection problem for a subclass of rectangles called r-rectangles is investigated and reduced to the balanced batched r(estricted)-range searching problem as well as to the balanced batched inverse r-range searching problem. Simple algorithms for these problems are given which are space and time optimal. The algorithm given for the balanced batched r-range searching problem leads to a new algorithm for the all-points ECDF problem in 2-space which is simple and optimal. Again, the balanced batched r-range searching algorithm is combined with a known algorithm for batched range searching problems, leading to a new algorithm for the rectangle intersection problem which is space and time optimal in the worst case when the given set of rectangles contains a much higher proportion of r-rectangles.     

Window‐LRFU: a cache replacement policy subsumes the LRU and window‐LFU policies

Replacement algorithms have been widely used as key technologies for cache management in areas such as file systems or database management. A replacement algorithm determines which page to be evicted when the cache is full and a new page is referenced. Because replacement policies considering only recency or frequency such as LRU (Least Recently Used) and LFU (Least Frequently Used) do not perform well, replacement polices that take both recency and frequency into account have been intensively studied. As a classical replacement policy, LRFU (Least Recently/Frequently Used) policy subsumes the LRU and LFU policy. However, because LFU is not able to adapt to the change of page accessing pattern and it is hard to select a suitable λ for each certain trace, LRFU cannot always guarantee a good performance. In this paper, we propose a Window‐LRFU policy, to subsume the LRU and Window‐LFU policies. Experimental results show that the Window‐LRFU policy outperforms LRFU and has at least competitive performance than other classical algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

Introspective Sorting and Selection Algorithms

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ(N²). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ(N log N) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.     

高效的一遍扫描式连通区域标记算法

二值图像的连通区域标记算法是图像处理的一个基本问题。为了提高算法的效率,以Suzuki等人提出的多遍扫描算法为基础,提出了一种快速的一遍扫描连通域标记算法。算法通过对图像做一次正向扫描,先计算出每个当前像素所在邻域内的最小标号,再利用一个递推过程,查找该连通域中具有较小标号的结点,将被更新结点所在连通分支连接到该结点,以保证等价信息不损失。同时,用最小标号更新递推查找路径上结点的临时标号,以减小分支的深度。通过对连接表的更新使每个结点获得最终标号。算法不需要动态数据结构和递归过程的支持,需要的存储空间较小,算法比原算法速度提高了近2倍,也快于近期提出的一些基于游程的算法。     

SC16 student cluster competition challenge: Investigating the reproducibility of results for the ParConnect application

At SC16, the SCC teams participated in a new application area: the Reproducibility Challenge. In this paper we report on our efforts to reproduce results presented in a paper titled “A Parallel Connectivity Algorithm for de Bruijn Graphs in Metagenomic Applications,” which shows that the parallel graph-based algorithm developed scales to over a thousand cores, and runs faster than traditional Breadth First Search algorithms. In general, using the smaller competition test data sets on over 128 processors, we were able to reproduce some, but not all, of the reported results: we were unable to run the D1 data set on 128 cores and 2GB/core memory; our results did show similar timing trends for the different algorithm variations; we were able to observe the trend of communication dominating the computation time; and the AP and AP_LB versions of our runs on smaller datasets only show a small time improvement in our graphs, which is similar but not exactly what was described within the paper. We believe that cluster architecture, required memory, network tuning, and number of processors available impacted our ability to exactly reproduce the results of the paper.     

基于Spark的并行社区发现算法

针对大规模图数据顶点聚类进行研究,提出了一种基于Spark的并行社区发现算法,其在基于极值优化的串行社区发现算法的基础上设计而成。此外还针对该串行算法在簇调整时因选择顶点数量过少而影响算法运行效率的问题,提出了一种多个顶点选择方法。该方法会计算一个阈值并发现所有适应度值小于该阈值的顶点,作为被选择的顶点;由于阈值是基于所有顶点的适应度值计算出来的,为了避免非常大的适应度值对阈值造成的影响该方法会限制被选择顶点的数量,若被选择的顶点过多,算法只保留其中的一部分。同时,还提出了一种顶点过滤方法,其可以有效减少图数据的数据量。在实验当中,提出算法的运行时间明显短于比较的其他基于Spark的并行化社区发现算法,可以发现提出算法的运行速度相对较快。     

基于最大节点接近度的局部社团结构探测算法

针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O（kd）。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。     

Randomized Selection on the Hypercube

In this paper, we present randomized algorithms for selection on the hypercube. We identify two variants of the hypercube, namely, thesequential modeland theparallel model. In the sequential model, any node at any time can handle only communication along a single incident edge, whereas in the parallel model a node can communicate along all its incident edges at the same time. We specify three variations of the parallel model and present optimal randomized algorithms on all these three versions of parallel model. In particular, we show that selection on an input of sizencan be performed on ap-node hypercube in timeO((n/p) + logp) with high probability, on any of the three versions of the parallel model. This result is important in view of a lower bound that implies that selection needs Ω((n/p)log logp+ logp) time on ap-node sequential hypercube. We modify our selection algorithm to run on the sequential hypercube in which case it runs in an expected time nearly matching this lower bound. For the special case whenn=p, our selection algorithm runs in an optimalO(logn) time on the sequential hypercube. Our algorithms are very simple and are most likely to perform well in practice.     

A review on quantum search algorithms

The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It is evident from the early invented quantum algorithms such as Deutsch’s algorithm, Deutsch–Jozsa algorithm and its variation as Bernstein–Vazirani algorithm, Simon algorithm, Shor’s algorithms, etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science because it comes as a subroutine in many important algorithms. Quantum database search of Grover achieves the task of finding the target element in an unsorted database in a time quadratically faster than the classical computer. We review Grover’s quantum search algorithms for a singe and multiple target elements in a database. The partial search algorithm of Grover and Radhakrishnan and its optimization by Korepin called GRK algorithm are also discussed.