本節(jié)判斷列表排序的函數(shù)名格式為IsListSorted_XXX()。為簡(jiǎn)潔起見，除代碼片段及其輸出外，一律以_XXX()指代。
成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括建陽網(wǎng)站建設(shè)、建陽網(wǎng)站制作、建陽網(wǎng)頁制作以及建陽網(wǎng)絡(luò)營(yíng)銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，建陽網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到建陽省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！
2.1 guess
def IsListSorted_guess(lst):
listLen = len(lst) if listLen = 1: return True
#由首個(gè)元素和末尾元素猜測(cè)可能的排序規(guī)則
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
_guess()是最通用的實(shí)現(xiàn)，幾乎與語言無關(guān)。值得注意的是，該函數(shù)內(nèi)會(huì)猜測(cè)給定列表可能的排序規(guī)則，因此無需外部調(diào)用者指明排序規(guī)則。
2.2 sorted
def IsListSorted_sorted(lst):
return sorted(lst) == lst or sorted(lst, reverse=True) == lst
_sorted()使用Python內(nèi)置函數(shù)sorted()。由于sorted()會(huì)對(duì)未排序的列表排序，_sorted()函數(shù)主要適用于已排序列表。
若想判斷列表未排序后再對(duì)其排序，不如直接調(diào)用列表的sort()方法，因?yàn)樵摲椒▋?nèi)部會(huì)判斷列表是否排序。對(duì)于已排序列表，該方法的時(shí)間復(fù)雜度為線性階O(n)——判斷為O(n)而排序?yàn)镺(nlgn)。
2.3 for-loop
def IsListSorted_forloop(lst, key=lambda x, y: x = y):
for i, elem in enumerate(lst[1:]): #注意，enumerate默認(rèn)迭代下標(biāo)從0開始
if not key(lst[i], elem): #if elem lst[i]更快，但通用性差
return False
return True
無論列表是否已排序，本函數(shù)的時(shí)間復(fù)雜度均為線性階O(n)。注意，參數(shù)key表明缺省的排序規(guī)則為升序。
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 operatordef 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:]))
lambda表達(dá)式與operator運(yùn)算符速度相當(dāng)，前者簡(jiǎn)單靈活，后者略為高效(實(shí)測(cè)并不一定)。但兩者速度均不如列表元素直接比較(可能存在調(diào)用開銷)。亦即，_allenumd()快于_allenumo()快于_allenumk()。
若使用lambda表達(dá)式指示排序規(guī)則，更改規(guī)則時(shí)只需要改變x和y之間的比較運(yùn)算符；若使用operator模塊指示排序規(guī)則，更改規(guī)則時(shí)需要改變對(duì)象比較方法。具體地，lt(x, y)等效于x y，le(x, y)等效于x = y，eq(x, y)等效于x == y，ne(x, y)等效于x != y，gt(x, y)等效于x y，ge(x, y)等效于x = y。例如，_allenumo()函數(shù)若要嚴(yán)格升序可設(shè)置oCmp=operator.lt。
此外，由all()函數(shù)的幫助信息可知，_allenumk()其實(shí)是_forloop()的等效形式。
2.5 numpy
def IsListSorted_numpy(arr, key=lambda dif: dif = 0):
import numpy try: if arr.dtype.kind == 'u': #無符號(hào)整數(shù)數(shù)組執(zhí)行np.diff時(shí)存在underflow風(fēng)險(xiǎn)
arr = numpy.int64(lst) except AttributeError: pass #無dtype屬性，非數(shù)組
return (key(numpy.diff(arr))).all() #numpy.diff(x)返回相鄰數(shù)組元素的差值構(gòu)成的數(shù)組
NumPy是用于科學(xué)計(jì)算的Python基礎(chǔ)包，可存儲(chǔ)和處理大型矩陣。它包含一個(gè)強(qiáng)大的N維數(shù)組對(duì)象，比Python自身的嵌套列表結(jié)構(gòu)(nested list structure)高效得多。第三節(jié)的實(shí)測(cè)數(shù)據(jù)表明，_numpy()處理大型列表時(shí)性能非常出色。
在Windows系統(tǒng)中可通過pip install numpy命令安裝NumPy包，不建議登錄官網(wǎng)下載文件自行安裝。
2.6 reduce
def IsListSorted_reduce(iterable, key=lambda x, y: x = y):
cmpFunc = lambda x, y: y if key(x, y) else float('inf') return reduce(cmpFunc, iterable, .0) float('inf')
reduce實(shí)現(xiàn)是all實(shí)現(xiàn)的變體。累加器(accumulator)中僅存儲(chǔ)最后一個(gè)檢查的列表元素，或者Infinity(若任一元素小于前個(gè)元素值)。
前面2.1~2.5小節(jié)涉及下標(biāo)操作的函數(shù)適用于列表等可迭代對(duì)象(Iterable)。對(duì)于通用迭代器(Iterator)對(duì)象，即可以作用于next()函數(shù)或方法的對(duì)象，可使用_reduce()及后面除_rand()外各小節(jié)的函數(shù)。迭代器的計(jì)算是惰性的，只有在需要返回下一個(gè)數(shù)據(jù)時(shí)才會(huì)計(jì)算，以避免不必要的計(jì)算。而且，迭代器方式無需像列表那樣切片為兩個(gè)迭代對(duì)象。
2.7 imap
def IsListSorted_itermap(iterable, key=lambda x, y: x = y):
from itertools import imap, tee
a, b = tee(iterable) #為單個(gè)iterable創(chuàng)建兩個(gè)獨(dú)立的iterator
next(b, None) return all(imap(key, a, b))
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))
第三節(jié)的實(shí)測(cè)數(shù)據(jù)表明，雖然存在外部函數(shù)調(diào)用，_iterzipf()卻比_iterzip()略為高效。
2.9 fast
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 Truedef 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
_fastd()和_fastk()是Stack Overflow網(wǎng)站回答里據(jù)稱執(zhí)行最快的。實(shí)測(cè)數(shù)據(jù)表明，在列表未排序時(shí)，它們的性能表現(xiàn)確實(shí)優(yōu)異。
2.10 random
import randomdef IsListSorted_rand(lst, randNum=3, randLen=100):
listLen = len(lst) if listLen = 1: return True
#由首個(gè)元素和末尾元素猜測(cè)可能的排序規(guī)則
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
_rand()借助隨機(jī)采樣降低運(yùn)算規(guī)模，并融入其他判斷函數(shù)的優(yōu)點(diǎn)。例如，猜測(cè)列表可能的排序規(guī)則，并在隨機(jī)采樣不適合時(shí)使用相對(duì)快速的判斷方式，如NumPy。
通過line_profiler分析可知，第20行和第21行與randLen有關(guān)，但兩者耗時(shí)接近。因此randLen應(yīng)小于listLen的一半，以抵消sorted開銷。除內(nèi)部限制外，用戶可以調(diào)節(jié)隨機(jī)序列個(gè)數(shù)和長(zhǎng)度，如定制單個(gè)但較長(zhǎng)的序列。
注意，_rand()不適用于存在微量異常數(shù)據(jù)的長(zhǎng)列表。因?yàn)檫@些數(shù)據(jù)很可能被隨機(jī)采樣遺漏，從而影響判斷結(jié)果的準(zhǔn)確性。
1、首先創(chuàng)建一個(gè)手機(jī)的列表，用print函數(shù)將列表打印到屏幕上。
2、用列表自帶的sort函數(shù)對(duì)手機(jī)價(jià)格排序。
3、再次用print函數(shù)，把排序后的手機(jī)列表打印到屏幕上，獲取完整代碼，實(shí)現(xiàn)手機(jī)排名程序。
8個(gè)超好用內(nèi)置函數(shù)set（），eval（），sorted（），reversed（），map（），reduce（），filter（），enumerate（）
python中有許多內(nèi)置函數(shù)，不像print那么廣為人知，但它們卻異常的強(qiáng)大，用好了可以大大提高代碼效率。
這次來梳理下8個(gè)好用的python內(nèi)置函數(shù)
1、set()
當(dāng)需要對(duì)一個(gè)列表進(jìn)行去重操作的時(shí)候，set()函數(shù)就派上用場(chǎng)了。
用于創(chuàng)建一個(gè)集合，集合里的元素是無序且不重復(fù)的。集合對(duì)象創(chuàng)建后，還能使用并集、交集、差集功能。
2、eval()之前有人問如何用python寫一個(gè)四則運(yùn)算器，輸入字符串公式，直接產(chǎn)生結(jié)果。用eval()來做就很簡(jiǎn)單：eval(str_expression)作用是將字符串轉(zhuǎn)換成表達(dá)式，并且執(zhí)行。
3、sorted()在處理數(shù)據(jù)過程中，我們經(jīng)常會(huì)用到排序操作，比如將列表、字典、元組里面的元素正/倒排序。這時(shí)候就需要用到sorted() ，它可以對(duì)任何可迭代對(duì)象進(jìn)行排序，并返回列表。對(duì)列表升序操作：
對(duì)元組倒序操作：
使用參數(shù)：key，根據(jù)自定義規(guī)則，按字符串長(zhǎng)度來排序：
根據(jù)自定義規(guī)則，對(duì)元組構(gòu)成的列表進(jìn)行排序：
4、reversed()如果需要對(duì)序列的元素進(jìn)行反轉(zhuǎn)操作，reversed()函數(shù)能幫到你。reversed()接受一個(gè)序列，將序列里的元素反轉(zhuǎn)，并最終返回迭代器。
5、map()做文本處理的時(shí)候，假如要對(duì)序列里的每個(gè)單詞進(jìn)行大寫轉(zhuǎn)化操作。這個(gè)時(shí)候就可以使用map()函數(shù)。
map()會(huì)根據(jù)提供的函數(shù)，對(duì)指定的序列做映射，最終返回迭代器。也就是說map()函數(shù)會(huì)把序列里的每一個(gè)元素用指定的方法加工一遍，最終返回給你加工好的序列。舉個(gè)例子，對(duì)列表里的每個(gè)數(shù)字作平方處理：
6、reduce()前面說到對(duì)列表里的每個(gè)數(shù)字作平方處理，用map()函數(shù)。那我想將列表里的每個(gè)元素相乘，該怎么做呢？這時(shí)候用到reduce()函數(shù)。
reduce()會(huì)對(duì)參數(shù)序列中元素進(jìn)行累積。第一、第二個(gè)元素先進(jìn)行函數(shù)操作，生成的結(jié)果再和第三個(gè)元素進(jìn)行函數(shù)操作，以此類推，最終生成所有元素累積運(yùn)算的結(jié)果。再舉個(gè)例子，將字母連接成字符串。
你可能已經(jīng)注意到，reduce()函數(shù)在python3里已經(jīng)不再是內(nèi)置函數(shù)，而是遷移到了functools模塊中。這里把reduce()函數(shù)拎出來講，是因?yàn)樗匾恕?/p>
7、filter()一些數(shù)字組成的列表，要把其中偶數(shù)去掉，該怎么做呢？
filter()函數(shù)輕松完成了任務(wù)，它用于過濾序列，過濾掉不符合條件的元素，返回一個(gè)迭代器對(duì)象。filter()函數(shù)和map()、reduce()函數(shù)類似，都是將序列里的每個(gè)元素映射到函數(shù)，最終返回結(jié)果。我們?cè)僭囋嚕绾螐脑S多單詞里挑出包含字母w的單詞。
8、enumerate()這樣一個(gè)場(chǎng)景，同時(shí)打印出序列里每一個(gè)元素和它對(duì)應(yīng)的順序號(hào)，我們用enumerate()函數(shù)做做看。
enumerate翻譯過來是枚舉、列舉的意思，所以說enumerate()函數(shù)用于對(duì)序列里的元素進(jìn)行順序標(biāo)注，返回(元素、索引)組成的迭代器。再舉個(gè)例子說明，對(duì)字符串進(jìn)行標(biāo)注，返回每個(gè)字母和其索引。
cmp(x,y) 就是compare(x,y)
numbers.sort(cmp)，意思是對(duì)numbers這個(gè)list進(jìn)行排序，其中排序使用的規(guī)則是cmp
重慶分公司
重慶分公司
