检索结果-内蒙古大学图书馆

BLOCK sorting OF A LARGE FILE IN EXTERNAL STORAGE BY A 2-COMPONENT KEY

COMPUTER JOURNAL 1982年第3期25卷 327-330页

作者： TAN, KP HSU, LS Department of Computer Science National University of Singapore Kent Ridge Singapore 0511

This paper introduces a sorting method (a block sort embedded with another sorting algorithm) to sort a large volume of records in external storage by means of a 2-component numeric key consisting of key 1 and key 2. Based on the value of key 1, the data file is split into many subfiles. Each subfile contains records of common key 1, but with different key 2s. After sorting, all records are linked together by pointers to form a sort file. An index array keeps the list heads to these separate subfiles. The list structure in the file organization facilities updating of the file. This sorting method can be applied to a key of any number of digits. A subroutine of the methodology is illustrated in the Appendix.

关键词： Data Files sorting algorithm grade Appendix Records as Topic AUXILIARY STORAGE large volume list structure file organisation sorting programs

来源：评论

学校读者我要写书评

暂无评论

sorting strings and constructing digital search trees in parallel

引用

THEORETICAL COMPUTER SCIENCE 1996年第2期154卷 225-245页

作者： Jaja, JF Ryu, KW Vishkin, U UNIV MARYLAND DEPT ELECT ENGN COLLEGE PK MD 20742 USA KYUNGPOOK NATL UNIV DEPT COMP ENGN TAEGU SOUTH KOREA TEL AVIV UNIV DEPT COMP SCI RAMAT AVIV ISRAEL

We describe two simple optimal-work parallel algorithms for sorting a list L = (X(1),X(2),...,X(m)) of m strings over an arbitrary alphabet Sigma, where Sigma(i=1)(m) \X(i)\ = n and two elements of Sigma can be compared in unit time using a single processor. The first algorithm is a deterministic algorithm that runs in O(log(2) m/log log m) time and the second is a randomized algorithm that runs in O(log m) time. Both algorithms use O(mlog m + n) operations. Compared to the best-known parallel algorithms for sorting strings, our algorithms offer the following improvements. 1. The total number of operations used by our algorithms is optimal while all previous parallel algorithms use a nonoptimal number of operations. 2. We make no assumption about the alphabet while the previous algorithms assume that the alphabet is restricted to {1,2,...,n(0)(1)}. 3. The computation model assumed by our algorithms is the Common CRCW PRAM unlike the known algorithms that assume the Arbitrary CRCW PRAM. 4. Our algorithms use O(mlogm + n) space, while the previous parallel algorithms use O(n(1+epsilon)) space, where epsilon is a positive constant. We also present optimal-work parallel algorithms to construct a digital search tree for a given set of strings and to search for a string in a sorted list of strings. We use our parallel sorting algorithms to solve the problem of determining a minimal starting point of a circular string with respect to lexicographic ordering, Our solution improves upon the previous best-known result to solve this problem.

关键词： List ranking Computation Computational modeling Tree searching parallel random access machine model Parallel algorithms sorting algorithm deterministic algorithms concurrency theory randomized algorithms algorithms Alphabets Cosmic strings

来源：评论

学校读者我要写书评

暂无评论

A lossless image compression for medical images based on hierarchical sorting technique

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2002年第1期E85D卷 108-114页

作者： Myojoyama, A Yamamoto, T Hokkaido Univ Grad Sch Engn Sapporo Hokkaido 0608628 Japan

We propose new lossless medical image compression method based on hierarchical sorting technique. Hierarchical sorting is a technique to achieve high compression ratio by detecting the regions where image pattern varies abruptly and sorting pixel order by its value to increase predictability. In this method, we can control sorting accuracy along with size and complexity. As the result, we can reduce the sizes of the permutation-tables and rouse the tables to other image regions. Comparison using experimental implementation of this method shows better performance for medical image set measured by X-ray CT and MRI instruments where similar sub-block patterns appear frequently. This technique applies quad-tree division method to divide an image to blocks in order to support progressive decoding and fast preview of large images.

关键词： lossless compression medical images sorting algorithm hierarchical coding

来源：评论

学校读者我要写书评

暂无评论

What is a sorting function?

引用

JOURNAL OF LOGIC AND ALGEBRAIC PROGRAMMING 2009年第7期78卷 552-572页

作者： Henglein, Fritz Univ Copenhagen DIKU Dept Comp Sci DK-2100 Copenhagen Denmark

What is a sorting function-not a sorting function for a given ordering relation, but a sorting function with nothing given? Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: a function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function. We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction. Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms;inequality tests forfeit this possibility. (C) 2008 Elsevier Inc. All rights reserved.

关键词： sorting Sort function sorting function sorting algorithm Stable Permutation Comparator Inequality test Isomorphism Parametric Parametricity

来源：评论

学校读者我要写书评

暂无评论

The sorting order on a Coxeter group

引用

JOURNAL OF COMBINATORIAL THEORY SERIES A 2009年第8期116卷 1285-1305页

作者： Armstrong, Drew Univ Minnesota Sch Math Minneapolis MN 55455 USA

Let (W, S) be an arbitrary Coxeter system. For each word omega in the generators we define a partial order-called the omega-sorting order-on the set of group elements W-omega subset of W that occur as subwords of omega. We show that the omega-sorting order is a supersolvable join-distributive lattice and that it is strictly between the weak and Bruhat orders on the group. Moreover, the omega-sorting order is a "maximal lattice" in the sense that the addition of any collection of Bruhat covers results in a nonlattice. Along the way we define a class of structures called supersolvable antimatroids and we show that these are equivalent to the class of supersolvable join-distributive lattices. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Coxeter group Partial order Lattice Antimatroid Abstract convex geometry Supersolvable lattice Join-distributive lattice Catalan number sorting algorithm

来源：评论

学校读者我要写书评

暂无评论

Benefits of Physical Interaction with Array Elements and Code Consolidation on Student Comprehension of sorting algorithms 19

Benefits of Physical Interaction with Array Elements and Cod...

引用

Proceedings of the 50th ACM Technical Symposium on Computer Science Education

作者： Anisha Kaul Julia Ann Pinedo Anya Wallace Scripps College Claremont CA USA Harvey Mudd College Claremont CA USA

ISBN: (纸本)9781450358903

This study was a qualitative analysis of introductory-level computer science students' comprehension of sorting algorithms. We asked six students to read and summarize the code of a sorting algorithm. Next, we asked them to trace through the code, first using a provided array with pencil and paper, then again using sticky-notes to represent the array. Focused analysis of one interview found that a student who struggled to comprehend the algorithm during the pencil-and-paper trace quickly gained understanding when physically tracing the sticky-note array. We hypothesize that physical interaction with a sticky-note representation of an array facilitated student comprehension of sorting algorithms by consolidating multiple lines of code (LOC) into a single repeatable action. This research is relevant to computer science educators who may teach sorting algorithms to introductory-level students.

关键词： insertion sort introductory sorting algorithm undergraduate instruction bubble sort consolidation graphics/visualization

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON ADAPTIVE PARALLEL sorting

引用

INFORMATION PROCESSING LETTERS 1989年第4期33卷 187-191页

作者： LEVCOPOULOS, C PETERSSON, O Dep. Comp. Sci. Lund Univ. S-221 00 Lund Sweden

We present a cost optimal parallel algorithm for sorting presorted sequences. The measure of presortedness we consider is Rem, i.e., the smallest number of elements whose removal leaves a sorted sequence. The algorithm sorts a sequence X of length n, with Rem(X) = r, in O(log n) time, provided O(n + r log r)/log n) processors are available, in the EREW PRAM model. This is the first PRAM sorting algorithm which is cost optimal with respect to Rem.

关键词： sorting algorithm PRAM presortedness

来源：评论

学校读者我要写书评

暂无评论

sorting Using Complete Subintervals and the Maximum Number of Runs in a Randomly Evolving Sequence

引用

ANNALS OF COMBINATORICS 2009年第4期12卷 417-447页

作者： Janson, Svante Uppsala Univ Dept Math SE-75106 Uppsala Sweden

We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0's, and then evolves by changing each 0 to 1, with the n changes done in random order. What is the maximal number of runs of 1's? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order n (1/2), and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1;there is also a second order term of order n (1/3). We also treat some variations, including priority queues and sock-sorting. The proofs use methods originally developed for random graphs.

关键词： sorting algorithm runs priority queues sock-sorting evolution of random strings Brownian motion

来源：评论

学校读者我要写书评

暂无评论

OVERLAPPING COMPUTATIONS, COMMUNICATIONS AND I/O IN PARALLEL sorting

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1995年第2期28卷 162-172页

作者： CLEMENT, MJ QUINN, MJ OREGON STATE UNIV DEPT COMP SCICORVALLISOR 97331

In this paper, we present a new parallel sorting algorithm which maximizes the overlap between the disk, network, and CPU subsystems of a processing node. This algorithm is shown to be of similar complexity to known efficient sorting algorithms. The pipelining effect exploited by our algorithm should lead to higher levels of performance on distributed memory parallel processors. In order to achieve the best results using this strategy, the CPU, network, and disk operations must take comparable time. We suggest acceptable levels of system balance for sorting machines and analyze the performance of the sorting algorithm as system parameters vary. (C) 1995 Academic Press, Inc.

关键词： sorting algorithm Level of Performance Separators Communication Research system parameter central processing units IO sorting programs

来源：评论

学校读者我要写书评

暂无评论

Shift-Limited Sort: Optimizing sorting Performance on Skyrmion Memory-Based Systems

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2020年第11期39卷 4115-4128页

作者： Hsieh, Yun-Shan Huang, Po-Chun Chen, Ping-Xiang Chang, Yuan-Hao Kang, Wang Yang, Ming-Chang Shih, Wei-Kuan Taipei Tech Dept Elect Engn Taipei 106 Taiwan Natl Tsing Hua Univ Hsinchu 300 Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu 300 Taiwan Acad Sinica Inst Informat Sci Taipei 11574 Taiwan Beihang Univ Fert Beijing Inst BDBC Beijing Peoples R China Beihang Univ Sch Microelect Beijing 100191 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Peoples R China

Modern nonvolatile memories (NVMs) are widely recognized as energy-efficient replacements of classical memory/storage media, such as SRAM, DRAM, and mechanical hard disk. Among the popular NVMs, the skyrmion racetrack memory (SK-RM) is well known for its high storage density and unique supports of insert/delete operations. However, the existing algorithms designed for classical media might experience serious performance degradation when working on the SK-RM, due to the distinct characteristics of SK-RM. Thus, the existing algorithms should be redesigned to adapt to the brand-new memory model based on the SK-RM, so as to fully reveal the potentials of SK-RM. In particular, many existing algorithms tend to access the in-memory data in a random-hopping fashion, which generates many time-consuming shift operations of SK-RM. It is therefore crucial for the existing algorithms to eliminate unnecessary shift operations of SK-RM to boost the performance of the algorithms. In many modern applications, such as multimedia and data analysis, it is a common operation to process two or more arrays/vectors of data to perform certain computation tasks. In the arrays/vectors, an appropriate data placement strategy is critical for avoiding unnecessary shift operations of SK-RM. The observation thus motivates this work in proposing a recursive back-to-back data placement manner to effectively reduces the shift operations of SK-RM. To demonstrate the back-to-back data placement, we take sorting algorithms as a case study, and propose a novel shift-limited sorting algorithm for SK-RM. Analytical studies show that the shift-limited sort effectively enhances the time complexity of classical merge sort from O(dn lg n) to O(n lg n), where d is the bit distance between adjacent access ports on the nanotracks of the SK-RM. After that, the efficacy of the proposed shift-limited sort is then verified by experimental studies, where the results are encouraging.

关键词： Back-to-back data placement Skyrmion racetrack memory (SK-RM) sorting algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：