LazySorted: A Lazily, Partially Sorted Python List

Naftali Harris

Journal of Statistical Software, 2015, vol. 065, issue c01

Abstract: LazySorted is a Python C extension implementing a partially and lazily sorted list data structure. It solves a common problem faced by programmers, in which they need just part of a sorted list, like its middle element (the median), but sort the entire list to get it. LazySorted presents them with the abstraction that they are working with a fully sorted list, while actually only sorting the list partially with quicksort partitions to return the requested sub-elements. This enables programmers to use naive "sort first" algorithms but nonetheless attain linear run-times when possible. LazySorted may serve as a drop-in replacement for the built-in sorted function in most cases, and can sometimes achieve run-times more than 7 times faster.

Date: 2015-06-01
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.jstatsoft.org/index.php/jss/article/view/v065c01/v65c01.pdf
https://www.jstatsoft.org/index.php/jss/article/do ... 65c01/LazySorted.zip

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jss:jstsof:v:065:c01

DOI: 10.18637/jss.v065.c01

Access Statistics for this article

Journal of Statistical Software is currently edited by Bettina Grün, Edzer Pebesma and Achim Zeileis

More articles in Journal of Statistical Software from Foundation for Open Access Statistics
Bibliographic data for series maintained by Christopher F. Baum ().