一种新的映射链接排序算法

本文通过对长记录数据特性的分析,提出了一种谓之映射链接的新排序方法（以下简称为“晌射链接排序”）,给出了该排序算法的描述、时间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明：映射连接排序方法与待排序数据分布情况无关,其时间复杂度仅为Ｏ（Ｎ）;对于大规模长记录数据的排序,其速度远远优于快速排序、快速分组排序、Ｐｒｏｐｏｒｔｉｏｎ Ｓｐｌｉｔ Ｓｏｒｔ等算法。     

一种1553B总线表排序优化算法的设计与实现

为了优化1553B总线传输性能,降低总线上消息传输的延迟时间,提高总线带宽利用率,给出了一种1553B总线表排序优化算法,该算法充分考虑了应用系统中周期消息、事件消息和管理消息相结合的特点,以消息块为输入,通过排序、优化,生成满足消息的功能特性和时间特性,且可被总线控制器直接执行的总线表;工程实践表明该算法有效、可行,能够保证总线上消息的实时调度,具有实践应用价值.     

排序算法的选择

影响排序效率的首要因素是算法，但算法时间复杂性的“O”表示法仅反映了渐近特性，不能作为依据来选择排序算法。本文指出了影响排序效率的一些其它因素，在实际中还需要根据这些因素选择不同的算法；文章还给出了几种排序程序的实验数据，这些数据表明当待排序数据较多时，分配排序的程序在执行时间上具有明显的优势。     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

基于图形硬件的双调排序算法优化

介绍一种新的并行排序算法,该算法以双调归并排序为基础,运用图形硬件的并行体系结构和二叉排序树数据结构的优点,用部分并行代替所有阶段的顺序执行,对双调排序算法进行优化.对该算法进行分析,在理论上n个序列在P个流处理器上的排序,最优的时间复杂度为O((nlogn)/p).实验测试结果表明,优化后的算法比其它基于图形硬件的双调归并排序算法所用时间短.     

直接优化性能指标的多排序模型融合方法

现有排序学习算法忽视了查询之间的差异,在建立排序模型的过程中等同对待训练样本集中的所有查询及其相关文档,影响了排序模型的性能.文中描述了查询之间的差异,并在训练过程中考虑查询之间的差异,提出了一种基于有监督学习的多排序模型融合方法.这种方法首先使用每一个查询及其相关文档训练出子排序模型,并将每一个子排序模型的输出转化为体现查询差异的特征数据,使用监督学习方法,实现了多排序模型的融合.更进一步,针对排序问题的特性,文中提出了一种直接优化排序性能的融合函数融合子排序模型,使用梯度上升方法优化其下界函数.文中证明了直接优化排序性能的融合函数融合子排序模型的性能优于子排序模型线性合并的性能.基于较大规模真实数据应用的实验结果表明,直接优化性能指标的多排序模型融合方法可以比传统排序学习模型具有更好的排序性能.     

分档混合排序算法

对传统典型的几种排序算法：直接比较排序、冒泡排序、快速排序、分档排序与基数排序的效率进行了全面的分析与比较，在此基础上提出了一种称之为分档混合排序算法的新的排序算法，并用算例说明了它的优越性。     

二次堆排序算法和提高排序效率的途径

本文讨论了一种堆排序的改进算法，该算法的平均时间复杂度达到ｎｌｏｇ２ｎ＋Ｏ（ｎ）。在此基础上，提出了二次堆排序的算法，使该排序过程中优化数据处理，排序速度提高１８０％。同时，本文给出了提高效率的措施、排序算法和实验结果。最后，给出了快速排序的优化数据处理的途径，从而较大地提高了排序效率。     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

一种新的分“档”快速排序算法

本文提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法-分“档”快速排序法,算法分析和实验结果都表明,在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到O（n),而附加存储空间开销却仅仅为[（n 1)/2],同时排序速度明显优于Quick Sort[2]、快速分组排序[5]、分“档”统计插入排序[1]和Proportion Split Sort[4]等算法。     

An automatically‐tuned sorting library

We present ATSL, an automatically‐tuned sorting library. ATSL generates a sorting routine optimized to the target machine for a specific data type. ATSL finds a high‐performance sorting routine by searching an algorithmic space that we have defined. The search space includes basic sorting algorithms and automatically‐generated compositions of sorting algorithms. Performance measurements are used both for ranking candidate algorithms and for characterizing the behavior of candidates in specific settings (e.g. ranges of input sizes). These characterizations allow ATSL to generate hybrid algorithms that intelligently exploit the strengths of particular algorithms, such as high speed at specific input‐size ranges. Many sorting algorithms can be tuned using numeric parameters and ATSL searches these parameter spaces to find values that yield high performance on the target machine. The building blocks from which ATSL synthesizes sorting algorithms include adaptations of many of the most effective hand‐tuned sorting routines, including several that are tuned for cache efficiency. An extensive experimental evaluation shows that ATSL generates high‐performance codes that are well tuned for the target machine and data type. The experiments were conducted on six different machines, of several architectures, and with three different compilers. The algorithms that are generated are fast; in particular, they beat the hand‐tuned building blocks and the compiler's C++ built‐in sorting routine. The algorithms that ATSL generates on different machines and using different compilers are different from each other. Copyright © 2007 John Wiley & Sons, Ltd.     

龙芯3A处理器上FFT的高效实现

FFT(Fast Fourier transform,快速傅立叶变换)是工程应用中的一个基本算法,优化其性能对于推广龙芯系列处理器的应用具有重要意义.本文充分挖掘龙芯3A处理器的硬件特性,对运算量和调整位序的过程作了优化并使用128位访存来减少访存指令的比例,从而实现了高效的FFT算法.实验结果表明,在825M龙芯3A处理器上经过优化后的一维FFT的速度是FF-TW库的2.5倍左右,而二维FFT的速度则是FFTW的3倍左右.     

社交网络中一种快速精确的节点影响力排序算法

在大规模在线社交网络中,通过对用户影响力进行排序找出其中最具影响力的节点（集合）是一个很重要的研究方向,对于有效控制信息扩散、舆情分析和控制、精准营销等均有重要的作用。已有的节点影响力排序算法或者需要网络的全局拓扑信息来计算单个节点影响力（如基于介数中心性的算法）而时间开销过大,不适用于大规模网络;或者基于传统的网页排序算法（如PageRank）而不能很好地处理社交网络中存在着大量“末梢”节点的问题以及不同用户之间的联系强度不同的问题。在传统的PageRank算法的基础上做出了两点改进。首先,通过在PageRank算法的权值回收步骤中考虑对不同的连接赋予不同的权值,有效避免了末梢节点带来的影响。其次,在PageRank算法的投票过程中考虑邻居个体的差异性,提出了一种基于半邻域信息的节点权值分配方法,有效提高了节点排序的准确度。在一个包含大约15 000个用户的样本网络中,我们所提出的改进算法能够找出前1 000个最有影响力的节点中的40%以上的节点,而传统的PageRank算法仅能找出其中11%的节点。同时,相比于基于介数中心性的算法,所提出的改进算法以小得多的时间开销达到了相近甚至更好的排序准确度。     

一种新型单循环排序算法

排序是计算机程序设计中一项经常而又重要的操作,研究排序算法具有重要的理论意义和广泛的应用价值。通过对目前常用的几种排序算法的研究,指出它们均为双重循环或多重循环结构设计,借鉴了军队排队列的思想,提出一种只需要单重循环结构即可完成排序过程的新型算法,并进行了编程实现。通过对该算法的时间复杂度、空间复杂度以及稳定性等性能分析,证明该算法对于基本有序的数据排列排序性能优秀,对于数据排列大都是两两错位的排序过程接近最优算法。     

龙芯3A处理器封装的散热设计

随着处理器的性能越来越高,处理器的功耗和温度也随之攀升,这就对处理器的封装提出了更高的要求。本文针对龙芯3A高性能处理器对封装的散热问题,根据成熟的工艺水平选择了FC-BGA封装形式,并对散热和外加散热措施的方法进行了分析和研究。实验模拟结果表明,FC-BGA的封装形式完全能满足龙芯3A处理器对封装散热的要求。     

THSORT:单机并行排序算法

排序是计算机事务处理的重要操作之一.前人已经就内部排序、外部排序和并行排序提出各种方法.从一种全新的视角研究了排序算法,提出一种在单机上实现的并行排序算法THSORT(Tsinghua SORT).它用多个进程分别控制不同的硬件部件,使输入、排序和输出能够同时进行,从而大大提高了硬件部件的并行性和运行效率.在带有双磁盘阵列的硬件平台上进行的测试表明,THSORT的性能达到了NTSORT(new technology SORT)的1倍左右,并成为2002年PennySort(Daytona类)世界排序纪录的保持者.     

A study on design of object sorting algorithms in the industrial application using hyperspectral imaging

Many industrial object-sorting applications leverage benefits of hyperspectral imaging technology. Design of object sorting algorithms is a challenging pattern recognition problem due to its multi-level nature. Objects represented by sets of pixels/spectra in hyperspectral images are to be allocated into pre-specified sorting categories. Sorting categories are often defined in terms of lower-level concepts such as material or defect types. This paper illustrates the design of two-stage sorting algorithms, learning to discriminate individual pixels/spectra and fusing the per-pixel decisions into a single per-object outcome. The paper provides a case-study on algorithm design in a real-world industrial sorting problem. Four groups of algorithms are studied varying the level of prior knowledge about the sorting problem. Apart of the sorting accuracy, the algorithm execution speed is estimated assuming an ideal implementation. Relating these two performance criteria allows us to discuss the accuracy/speed trade-off of different algorithms.

多核龙芯3A上二级BLAS库的优化

针对龙芯3A体系结构以及二级BLAS库函数的特点,在指令级、存储级和线程级抽取并行方案,总结了一些合适的优化方法,并对其进行了定量的分析.实验表明,这些优化可以将二级BLAS函数单线程的性能提升20%以上,多线程下也可以得到2.5倍左右的加速比,这对今后多核龙芯上的系统软件优化工作有着一定的帮助.     

一种基于listwise的在线学习书目排序检索算法

高效检索是数字图书馆的核心业务之一,其中排序是高效信息检索的核心问题。给定一系列的书目列表,利用排序模型生成目标书目的排序列表。将学习排序算法应用于信息检索领域时,常用方法是通过最小化pairwise损失函数值来优化排序模型。然而,已有结论表明,pairwise损失值最小化不一定能得到listwise算法的最佳排序性能。并且将在线学习排序算法与listwise算法相结合也非常困难。提出了一种基于listwise的在线学习排序算法,旨在保证listwise算法性能优势的前提下,实现在线学习排序算法,从而降低检索复杂度。首先解决将在线学习排序算法与listwise算法相结合的问题;然后通过最小化基于预测列表和真实列表定义的损失函数来优化排序模型;最后提出基于online-listwise算法的自适应学习率。实验结果表明,所提出算法具有较好的检索性能和检索速度。     

Distinctive features of structural programming of synchronous sorting algorithms

Parallel (synchronous) algorithms of sorting arrays are considered. A modified synchronous sorting algorithm based on the pairwise exchange method is proposed and simulated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 122–133, September–October 2006.