Published by the Foundation for Open Access Statistics Editors-in-chief: Bettina Grün, Torsten Hothorn, Edzer Pebesma, Achim Zeileis    ISSN 1548-7660; CODEN JSSOBK
Authors: Naftali Harris
Title: LazySorted: A Lazily, Partially Sorted Python List
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.

Page views:: 4516. Submitted: 2014-02-19. Published: 2015-06-01.
Paper: LazySorted: A Lazily, Partially Sorted Python List     Download PDF (Downloads: 4862)
Supplements: LazySorted: A Lazily, Partially Sorted Python List Download (Downloads: 141; 15KB)

DOI: 10.18637/jss.v065.c01

This work is licensed under the licenses
Paper: Creative Commons Attribution 3.0 Unported License
Code: GNU General Public License (at least one of version 2 or version 3) or a GPL-compatible license.