Various methods for determining whether a list is sorted in Python and its performance analysis
WBOY
Release： 2016-07-21 14:53:15
Original
1795 people have browsed it
Statement
Based on the Python2.7 language, this article gives various methods to determine whether the list is sorted, and compares and analyzes its performance on the author's Windows XP host (Pentium G630 2.7GHz main frequency 2GB memory).
1. Question raising
Haskell training teacher asked a question: How to determine whether the list has been sorted?
Sorting or not is actually just some binary relationship between adjacent elements, that is, a->a->Bool. So the first step is to find the list of tuples; the second step is to apply this function to each tuple, and then use the and operation. The implementation code given by the teacher is as follows:
pair lst = zip lst ( tail lst )
sorted lst predict = and [ predict x y | (x,y) <- pair lst]
Copy after login
In Haskell, the equal sign is preceded by the name and parameters of the function, followed by the function definition. The pair function displaces the list lst (tail removes the first element of the list), and then combines it with the original list to form a tuple list of adjacent elements under the action of zip. The predict function accepts two numbers and returns True or False depending on the size. and sums all elements in a list of type [Bool], and its semantics are similar to Python's all() function.
Then, the teacher asked everyone to think about performance issues. The author proposed that if the accuracy requirements are not high, three sets of random numbers can be generated and sorted as subscripts, and the corresponding three sets of elements of the original list can be extracted to form three new sublists ("sampling"). If it is judged that the three sublists follow the same sorting rules, the original list is considered to be sorted. When the list is large and has been sorted in the previous section, selecting an appropriate number of random numbers can significantly reduce the scale of the operation while ensuring a certain accuracy.
In addition, data sources should also be considered in practical applications. For example, the os.listdir() method of the Python language returns list entries in alphabetical order on Windows systems, but returns out-of-order entries on Linux systems. Therefore, if the system platform (os.platform) is judged to be win32, the entries must have been sorted.
In order to compare and verify the feasibility of the random sampling method, the author first collected existing methods for judging list sorting on the Internet, mainly referring to the answers to the "Pythonic way to check if a list is sorted or not" question on the Stack Overflow website, and Relevant code examples are given in the second section of this article. Note that the "sorting" described in this article does not require strict sorting, that is, adjacent elements are allowed to be equal. For example, [1,2,2,3] is regarded as ascending order, and [3,3,2,2] is regarded as descending order.
2. Code implementation
The function name format for determining list sorting in this section is IsListSorted_XXX(). For the sake of brevity, except for code snippets and their output, they are always referred to as _XXX().
2.1 guess
def IsListSorted_guess(lst):
listLen = len(lst)
if listLen <= 1:
return True
#由首个元素和末尾元素猜测可能的排序规则
if lst[0] == lst[-1]: #列表元素相同
for elem in lst:
if elem != lst[0]: return False
elif lst[0] < lst[-1]: #列表元素升序
for i, elem in enumerate(lst[1:]):
if elem < lst[i]: return False
else: #列表元素降序
for i, elem in enumerate(lst[1:]):
if elem > lst[i]: return False
return True
Copy after login
_guess() is the most general implementation and is almost language independent. It is worth noting that the possible collation of the given list is guessed within this function, so there is no need for the external caller to specify the collation.
_sorted() uses the Python built-in function sorted(). Since sorted() sorts an unsorted list, the _sorted() function is mainly suitable for sorted lists.
If you want to determine if the list is unsorted and then sort it, it is better to call the sort() method of the list directly, because this method will internally determine whether the list is sorted. For a sorted list, the time complexity of this method is linear order O(n) - judging is O(n) and sorting is O(nlgn).
2.3 for-loop
def IsListSorted_forloop(lst, key=lambda x, y: x <= y):
for i, elem in enumerate(lst[1:]): #注意，enumerate默认迭代下标从0开始
if not key(lst[i], elem): #if elem > lst[i]更快，但通用性差
return False
return True
Copy after login
Regardless of whether the list is sorted or not, the time complexity of this function is linear order O(n). Note that the key parameter indicates that the default sorting rule is ascending order.
2.4 all
def IsListSorted_allenumk(lst, key=lambda x, y: x <= y):
return all(key(lst[i], elem) for i, elem in enumerate(lst[1:]))
import operator
def IsListSorted_allenumo(lst, oCmp=operator.le):
return all(oCmp(lst[i], elem) for i, elem in enumerate(lst[1:]))
def IsListSorted_allenumd(lst):
return all((lst[i] <= elem) for i, elem in enumerate(lst[1:]))
def IsListSorted_allxran(lst, key=lambda x,y: x <= y):
return all(key(lst[i],lst[i+1]) for i in xrange(len(lst)-1))
def IsListSorted_allzip(lst, key=lambda x,y: x <= y):
from itertools import izip #Python 3中zip返回生成器(generator)，而izip被废弃
return all(key(a, b) for (a, b) in izip(lst[:-1],lst[1:]))
Copy after login
Lambda expressions and operator operators are equally fast. The former is simple and flexible, while the latter is slightly more efficient (actual measurement is not necessarily true). But neither is as fast as direct comparison of list elements (there may be calling overhead). That is, _allenumd() is faster than _allenumo() and _allenumk().
If you use lambda expressions to indicate sorting rules, you only need to change the comparison operator between x and y when changing the rules; if you use the operator module to indicate sorting rules, you need to change the object comparison method when changing the rules. Specifically, lt(x, y) is equivalent to x < y, le(x, y) is equivalent to x <= y, eq(x, y) is equivalent to x == y, ne(x, y) is equivalent to x != y, gt(x, y) is equivalent to x > y, ge(x, y) is equivalent to x >= y. For example, if the _allenumo() function wants strict ascending order, set oCmp=operator.lt.
In addition, according to the help information of the all() function, _allenumk() is actually the equivalent form of _forloop().
NumPy is a basic Python package for scientific computing that can store and process large matrices. It contains a powerful N-dimensional array object that is much more efficient than Python's own nested list structure. The measured data in Section 3 shows that _numpy() performs very well when processing large lists.
def IsListSorted_itermap(iterable, key=lambda x, y: x <= y):
from itertools import imap, tee
a, b = tee(iterable) #为单个iterable创建两个独立的iterator
next(b, None)
return all(imap(key, a, b))
Copy after login
2.8 izip
def IsListSorted_iterzip(iterable, key=lambda x, y: x <= y):
from itertools import tee, izip
a, b = tee(iterable)
next(b, None)
return all(key(x, y) for x, y in izip(a, b))
def pairwise(iterable):
from itertools import tee, izip
a, b = tee(iterable)
next(b, None)
return izip(a, b) #"s -> (s0,s1), (s1,s2), (s2, s3), ..."
def IsListSorted_iterzipf(iterable, key=lambda x, y: x <= y):
return all(key(a, b) for a, b in pairwise(iterable))
def IsListSorted_fastd(lst):
it = iter(lst)
try:
prev = it.next()
except StopIteration:
return True
for cur in it:
if prev > cur:
return False
prev = cur
return True
def IsListSorted_fastk(lst, key=lambda x, y: x <= y):
it = iter(lst)
try:
prev = it.next()
except StopIteration:
return True
for cur in it:
if not key(prev, cur):
return False
prev = cur
return True
import random
def IsListSorted_rand(lst, randNum=3, randLen=100):
listLen = len(lst)
if listLen <= 1:
return True
#由首个元素和末尾元素猜测可能的排序规则
if lst[0] < lst[-1]: #列表元素升序
key = lambda dif: dif >= 0
else: #列表元素降序或相等
key = lambda dif: dif <= 0
threshold, sortedFlag = 10000, True
import numpy
if listLen <= threshold or listLen <= randLen*2 or not randNum:
return (key(numpy.diff(numpy.array(lst)))).all()
from random import sample
for i in range(randNum):
sortedRandList = sorted(sample(xrange(listLen), randLen))
flag = (key(numpy.diff(numpy.array([lst[x] for x in sortedRandList])))).all()
sortedFlag = sortedFlag and flag
return sortedFlag
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
