Zobrazeno 1 - 10
of 121
pro vyhledávání: '"Nebel, Markus E."'
Publikováno v:
ALENEX 2023
We present a stable mergesort variant, Multiway Powersort, that exploits existing runs and finds nearly-optimal merging orders for k-way merges with negligible overhead. This builds on Powersort (Munro & Wild, ESA2018), which has recently replaced Ti
Externí odkaz:
http://arxiv.org/abs/2209.06909
We extend randomized jumplists introduced by Br\"onnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomized algorithms with expected $O(\log n)$ time complexity that maintai
Externí odkaz:
http://arxiv.org/abs/1609.08513
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In
Externí odkaz:
http://arxiv.org/abs/1412.0193
The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to quantify an algorithm's efficiency. In some cases, however, features of m
Externí odkaz:
http://arxiv.org/abs/1411.2059
Autor:
Nebel, Markus E., Wild, Sebastian
The new dual-pivot Quicksort by Vladimir Yaroslavskiy - used in Oracle's Java runtime library since version 7 - features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than c
Externí odkaz:
http://arxiv.org/abs/1403.6602
Autor:
Wild, Sebastian, Nebel, Markus E.
Publikováno v:
In L. Epstein & P. Ferragina (Eds.), ESA 2012 (LNCS 7501, pp. 825-836). Springer Berlin/Heidelberg
Recently, a new Quicksort variant due to Yaroslavskiy was chosen as standard sorting method for Oracle's Java 7 runtime library. The decision for the change was based on empirical studies showing that on average, the new algorithm is faster than the
Externí odkaz:
http://arxiv.org/abs/1310.7409
Autor:
Jin, Emma Yu, Nebel, Markus E.
In this paper we prove a $q$-analogue of Koshy's formula in terms of the Narayana polynomial due to Lassalle and a $q$-analogue of Koshy's formula in terms of $q$-hypergeometric series due to Andrews by applying the inclusion-exclusion principle on D
Externí odkaz:
http://arxiv.org/abs/1309.0949
There is excitement within the algorithms community about a new partitioning method introduced by Yaroslavskiy. This algorithm renders Quicksort slightly faster than the case when it runs under classic partitioning methods. We show that this improved
Externí odkaz:
http://arxiv.org/abs/1306.3819
In this paper we present a sampling framework for RNA structures of fixed topological genus. We introduce a novel, linear time, uniform sampling algorithm for RNA structures of fixed topological genus $g$, for arbitrary $g>0$. Furthermore we develop
Externí odkaz:
http://arxiv.org/abs/1304.7397
Publikováno v:
ACM Transactions on Algorithms 11, 3, Article 22 (Jan 2015)
In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation i
Externí odkaz:
http://arxiv.org/abs/1304.0988