乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:25:44Z","timestamp":1673987144288},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,1,13]]},"abstract":"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 in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance\u2014on the contrary: previous theoretical studies of other dual-pivot Quicksort variants even discouraged the use of two pivots. In 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy's algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy's algorithm needs more swaps, which renders the analysis inconclusive.<\/jats:p>\n To force the issue, we herein extend our analysis to the fully detailed style of Knuth: we determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy's algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort\u2014contradicting observed running times. As in Oracle's library implementation, we incorporate the use of Insertionsort on small subproblems and show that it indeed speeds up Yaroslavskiy's Quicksort in terms of Bytecodes; but even with optimal Insertionsort thresholds, the new Quicksort variant needs slightly more Bytecode instructions on average.<\/jats:p>\n \n Finally, we show that the (suitably normalized) costs of Yaroslavskiy's algorithm converge to a random variable whose distribution is characterized by a fixed-point equation. From that, we compute variances of costs and show that for large\n n<\/jats:italic>\n , costs are concentrated around their mean.\n <\/jats:p>","DOI":"10.1145\/2629340","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T14:29:58Z","timestamp":1421418598000},"page":"1-42","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Average Case and Distributional Analysis of Dual-Pivot Quicksort"],"prefix":"10.1145","volume":"11","author":[{"given":"Sebastian","family":"Wild","sequence":"first","affiliation":[{"name":"University of Kaiserslautern, Kaiserslautern"}]},{"given":"Markus E.","family":"Nebel","sequence":"additional","affiliation":[{"name":"University of Kaiserslautern, Kaiserslautern"}]},{"given":"Ralph","family":"Neininger","sequence":"additional","affiliation":[{"name":"J. W. Goethe University, Frankfurt am Main"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2006.12"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679613"},{"key":"e_1_2_1_4_1","unstructured":"Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press. Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Herbert A. David and Haikady N. Nagaraja. 2003. Order Statistics (3rd ed.). Wiley-Interscience. Herbert A. David and Haikady N. Nagaraja. 2003. Order Statistics (3rd ed.). Wiley-Interscience.","DOI":"10.1002\/0471722162"},{"key":"e_1_2_1_6_1","unstructured":"Edsger W. Dijkstra. 1976. A Discipline of Programming. Prentice Hall. Edsger W. Dijkstra. 1976. A Discipline of Programming. Prentice Hall."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00351-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362736.362753"},{"key":"e_1_2_1_9_1","volume-title":"Mathematics and Computer Science","author":"Fill James Allen","year":"2000"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00216-X"},{"key":"e_1_2_1_11_1","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"Graham Ronald L.","year":"1994"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Pascal Hennequin. 1989. Combinatorial analysis of Quicksort algorithm. Informatique th\u00e9orique et applications 23 3 (1989) 317--333. Pascal Hennequin. 1989. Combinatorial analysis of Quicksort algorithm. Informatique th\u00e9orique et applications 23 3 (1989) 317--333.","DOI":"10.1051\/ita\/1989230303171"},{"key":"e_1_2_1_13_1","unstructured":"Pascal Hennequin. 1991. Analyse en moyenne d'algorithmes: tri rapide et arbres de recherche. PhD Thesis. Ecole Politechnique Palaiseau. Pascal Hennequin. 1991. Analyse en moyenne d'algorithmes: tri rapide et arbres de recherche. PhD Thesis. Ecole Politechnique Palaiseau."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366642"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970138390X"},{"key":"e_1_2_1_18_1","unstructured":"Maurice G. Kendall. 1945. The Advanced Theory of Statistics (2nd ed.). Charles Griffin. Maurice G. Kendall. 1945. The Advanced Theory of Statistics (2nd ed.). Charles Griffin."},{"key":"e_1_2_1_19_1","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming: Sorting and Searching (2nd ed.). Addison Wesley. Donald E. Knuth. 1998. The Art of Computer Programming: Sorting and Searching (2nd ed.). Addison Wesley."},{"key":"e_1_2_1_20_1","unstructured":"Donald E. Knuth. 2005. The Art of Computer Programming: Volume 1 Fascicle 1. MMIX A RISC Computer for the New Millennium. Addison-Wesley. Donald E. Knuth. 2005. The Art of Computer Programming: Volume 1 Fascicle 1. MMIX A RISC Computer for the New Millennium. Addison-Wesley."},{"key":"e_1_2_1_21_1","volume-title":"Meeting on Algorithm Engineering and Experiments","author":"Kushagra Shrinu","year":"2014"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.025"},{"key":"e_1_2_1_23_1","unstructured":"Tim Lindholm and Frank Yellin. 1999. Java Virtual Machine Specification (2nd ed.). Addison-Wesley Longman Publishing. Tim Lindholm and Frank Yellin. 1999. Java Virtual Machine Specification (2nd ed.). Addison-Wesley Longman Publishing."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032886"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382108"},{"key":"e_1_2_1_26_1","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"McDiarmid Colin"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0055"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/359619.359629"},{"key":"e_1_2_1_29_1","unstructured":"Markus E. Nebel and Sebastian Wild. 2014. Pivot sampling in dual-pivot Quicksort. Retrieved from http:\/\/arxiv.org\/abs\/1403.6602. Markus E. Nebel and Sebastian Wild. 2014. Pivot sampling in dual-pivot Quicksort. Retrieved from http:\/\/arxiv.org\/abs\/1403.6602."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10010"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Mireille Regnier. 1989. A limiting distribution for Quicksort. Informatique th\u00e9orique et applications 23 3 (1989) 335--343. Mireille Regnier. 1989. A limiting distribution for Quicksort. Informatique th\u00e9orique et applications 23 3 (1989) 335--343.","DOI":"10.1051\/ita\/1989230303351"},{"key":"e_1_2_1_32_1","volume-title":"Informatique th\u00e9orique et applications 25, 1","author":"R\u00f6sler Uwe","year":"1991"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02679621"},{"key":"e_1_2_1_34_1","unstructured":"Robert Sedgewick. 1975. Quicksort. PhD Thesis. Stanford University. Robert Sedgewick. 1975. Quicksort. PhD Thesis. Stanford University."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289467"},{"key":"e_1_2_1_36_1","unstructured":"Robert Sedgewick and Philippe Flajolet. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley-Longman. Robert Sedgewick and Philippe Flajolet. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley-Longman."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/362875.362901"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7152(94)00209-Q"},{"key":"e_1_2_1_39_1","unstructured":"Sebastian Wild. 2012. Java 7's Dual Pivot Quicksort. Master's Thesis. University of Kaiserslautern. Sebastian Wild. 2012. Java 7's Dual Pivot Quicksort. Master's Thesis. University of Kaiserslautern."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_71"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2790158.2790163"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T19:41:50Z","timestamp":1672429310000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2629340"],"URL":"https:\/\/doi.org\/10.1145\/2629340","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2013-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}