Hardware evolution has been one of the driving factors for the redesign of database systems. Recently, approximate storage emerges in the area of computer architecture. It trades off precision for better performance a...
详细信息
ISBN:
(纸本)9781450335317
Hardware evolution has been one of the driving factors for the redesign of database systems. Recently, approximate storage emerges in the area of computer architecture. It trades off precision for better performance and/or energy consumption. Previous studies have demonstrated the benefits of approximate storage for applications that are tolerant to imprecision such as image processing. However, it is still an open question whether and how approximate storage can be used for applications that do not expose such intrinsic tolerance. In this paper, we study one of the most basic operations in database-sorting on a hybrid storage system with both precise storage and approximate storage. Particularly, we start with a study of three common sorting algorithms on approximate storage. Experimental results show that a 95% sorted sequence can be obtained with up to 40% reduction in total write latencies. Thus, we propose an approx-refine execution mechanism to improve the performance of sorting algorithms on the hybrid storage system to produce precise results. Our optimization gains the performance benefits by offloading the sorting operation to approximate storage, followed by an efficient refinement to resolve the unsortedness on the output of the approximate storage. Our experiments show that our approx-refine can reduce the total memory access time by up to 11%. These studies shed light on the potential of approximate hardware for improving the performance of applications that require precise results.
In today's scenario, this world is moving rapidly toward the global warming. Various experiments are performed, to concentrate more on the energy efficiency. One way to achieve this is by implementing the sorting ...
详细信息
ISBN:
(纸本)9789811088483;9789811088476
In today's scenario, this world is moving rapidly toward the global warming. Various experiments are performed, to concentrate more on the energy efficiency. One way to achieve this is by implementing the sorting algorithms in such a programming language which consumes least amount of energy which is our current area of research in this paper. In this study, our main goal is to find such a programming language which consumes least amount of energy and contributes to green computing. In our experiment, we implemented different sorting algorithms in different programming languages in order to find the most power-efficient language.
Using multisets, we develop novel techniques for mechanizing the proofs of the synthesis conjectures for list-sorting algorithms, and we demonstrate them in the Theorema system. We use the classical principle of extra...
详细信息
Using multisets, we develop novel techniques for mechanizing the proofs of the synthesis conjectures for list-sorting algorithms, and we demonstrate them in the Theorema system. We use the classical principle of extracting the algorithm as a set of rewrite rules based on the witnesses found in the proof of the synthesis conjecture produced from the specification of the desired function (input and output conditions). The proofs are in natural style, using standard rules, but most importantly domain specific inference rules and strategies. In particular the use of multisets allows us to develop powerful strategies for the synthesis of arbitrarily structured recursive algorithms by general Noetherian induction, as well as for the automatic generation of the specifications of all necessary auxiliary functions (insert, merge, split), whose synthesis is performed using the same method. The proof techniques are implemented in the Theorema system and generate 8 sorting algorithms and 19 auxiliary functions. (C) 2020 Elsevier Inc. All rights reserved.
The problem of analyzing and synthesizing sorting algorithms is studied. That is, given a sorting algorithm we want to investigate how it works in a step-by-step manner and consequently to assert that it indeed arrang...
详细信息
The problem of analyzing and synthesizing sorting algorithms is studied. That is, given a sorting algorithm we want to investigate how it works in a step-by-step manner and consequently to assert that it indeed arranges the objects according to a certain ordering relationship, and conversely, given an ordering relationship according to which a set of objects are to be arranged, we want to determine an algorithm that will yield the desired result.
With the advent of mobile application development a new software quality concern - energy consumption - was introduced. For mobile software developers knowledge about software and algorithm design choices and their im...
详细信息
ISBN:
(纸本)9781450372831
With the advent of mobile application development a new software quality concern - energy consumption - was introduced. For mobile software developers knowledge about software and algorithm design choices and their implications on energy consumption is crucial. However, software developers either lack this knowledge or tools to support them in estimating the energy consumption of their applications and therefore are unable to reflect on their design choices. In this empirical study we examine the energy consumption of 12 sorting algorithms and the resulting energy impact when used with different data types. We propose a methodology to obtain energy readings and relate them to application execution traces. Our results show that the choice of data type together with algorithm design can have significant impact on the energy profile of an application.
Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Theta(N log N), and it is in fact faster than most other sorting algorithms o...
详细信息
Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Theta(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 Theta(N-2). 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 Theta(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 Theta(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. (C) 1997 by John Wiley & Sons, Ltd.
In this article, we present a semester-long study on using smartphone devices in computing engineering education. We developed Sortko, an Android-based smartphone application for learning sorting algorithms, an import...
详细信息
In this article, we present a semester-long study on using smartphone devices in computing engineering education. We developed Sortko, an Android-based smartphone application for learning sorting algorithms, an important undergraduate computer science topic. The application consists of four main componentsthe module for interactive sorting, the scaffolding module, the motivational module, and the graphical user interface module, each with a distinct role of helping students in learning sorting algorithms. Our research methodology included data collection with administered two surveys, collected exam results and recorded application usage data. Analysis of the collected data shows our approach is an effective way of learning sorting algorithms. (c) 2012 Wiley Periodicals, Inc. Comput Appl Eng Educ 21:E41-E50, 2013
In this paper we present our experience in the development and use of interactive simulation-based Learning Objects (LOs) in an introductory course of programming. The focus of our research is on the teaching of one o...
详细信息
In this paper we present our experience in the development and use of interactive simulation-based Learning Objects (LOs) in an introductory course of programming. The focus of our research is on the teaching of one of the important topics in introductory courses of programming - sorting algorithms and their programming implementation. The characteristics of the LOs developed and the scenarios used for their deployment are described. The results from the pilot study, discussed in the paper, demonstrate an increase of student interest and a level of understanding of the learning content.
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...
详细信息
This research work introduces a clustering-based in-place sorting algorithm, cluster sort. It is designed in such a way that it improves sorting efficiency by using data locality. It works in two phases: first, data e...
详细信息
This research work introduces a clustering-based in-place sorting algorithm, cluster sort. It is designed in such a way that it improves sorting efficiency by using data locality. It works in two phases: first, data elements are clustered based on the similarity in the values and then each of these clusters is sorted independently using comb or shell sort. This is a hybrid approach, and it helps minimize multiple comparisons within the clusters, which in turn improves performance, especially in large datasets with specific distributions. The traditional algorithms were selected due to their well-known efficiency and widespread use in sorting large datasets. This experiment of ours includes ordered, reverse-ordered, Gaussian, repeated values, same values, and uniform distributions. The results acquired from this experiment show that Cluster Sort (comb) outperforms Cluster Sort (shell) by 88% in ordered datasets and is 92.32% faster than Merge Sort. For reverse-ordered datasets, Cluster Sort (Comb) is 70.79% faster than Bucket Sort and 90.69% faster than Cluster Sort (Shell). In Gaussian distributions, Cluster Sort (Shell) improves by 25.88% over Bucket Sort and 74.41% over Merge Sort. In repeated-value datasets, although Quick Sort is faster, Cluster Sort (Shell) surpasses Bucket Sort by 13.64%. For uniform distributions, Cluster Sort (Shell) is 30.28% faster than Bucket Sort and 75% faster than Merge Sort. The reduction in unwanted comparisons through clustering is essentially what made Cluster Sort significantly outperform traditional algorithms in these datasets with inherent patterns, making Cluster Sort a coherent choice for practical applications.
暂无评论