如何切片deque？

Question

我更改了一些使用列表來使用雙端隊列的代碼。我不能再進行切片了，因爲我收到了錯誤：

TypeError: sequence index must be integer, not 'slice'

這是顯示問題的REPL。

>>> import collections 
>>> d = collections.deque() 
>>> for i in range(3): 
...  d.append(i) 
... 
>>> d 
deque([0, 1, 2]) 
>>> d[2:] 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: sequence index must be integer, not 'slice' 

那麼，是否有一種解決方法來支持在Python中切入deques？

Answer 1

嘗試itertools.islice()。

deque_slice = collections.deque(itertools.islice(my_deque, 10, 20)) 

索引到一個deque需要以下每次從開始一個鏈表，所以islice()方法，跳繩項目才能到片的起點，將提供最好的性能（比編碼它更好每個元素的索引操作）。

你可以很容易地寫一個deque子類，它自動爲你做這個。

class sliceable_deque(collections.deque): 
    def __getitem__(self, index): 
     if isinstance(index, slice): 
      return type(self)(itertools.islice(self, index.start, 
               index.stop, index.step)) 
     return collections.deque.__getitem__(self, index) 

請注意，您不能對islice使用負指數或步數值。有可能對此進行編碼，如果採取子類方法，可能需要這樣做。對於負開始或停止，您可以添加deque的長度;對於負面的步驟，您需要在某處放置一個reversed()。我將把它作爲一個練習。 :-)

從deque中檢索單個項目的性能會略微降低if測試的分片。如果這是一個問題，你可以使用EAFP模式在一定程度上改善這一點 - 在製作切片路徑略少高性能的成本，因爲需要處理異常：

class sliceable_deque(collections.deque): 
    def __getitem__(self, index): 
     try: 
      return collections.deque.__getitem__(self, index) 
     except TypeError: 
      return type(self)(itertools.islice(self, index.start, 
               index.stop, index.step)) 

當然還有一個額外的函數調用仍然存在，與常規的deque相比，所以如果你真的關心性能，你真的想要添加一個單獨的slice()方法或類似的東西。

Answer 2

如果性能是一個問題，考慮如this answer中建議的直接訪問/理解方法。這是對大集合比islice快得多：下面

import timeit 

setup = """ 
import collections, itertools 
d = collections.deque(range(10000)) 
""" 

print timeit.timeit('list(itertools.islice(d, 9000, 9010))', setup, number=10000) 
## 0.631947040558 
print timeit.timeit('[d[i] for i in range(9000, 9010)]', setup, number=10000) 
## 0.0292208194733 

按@RaymondHettinger評論，修真法只有更好，當片很短。在較長的切片上，islice令人信服地獲勝。例如，這裏有一個切片萬件時限從6000偏移雙端隊列：

 
offset length  islice  compr 
6000  10  400.496  46.611 
6000  50  424.600  183.988 
6000  90  432.277  237.894 
6000  130  441.289  352.383 
6000  170  431.299  404.596 
6000  210  456.405  546.503 
6000  250  448.895  575.995 
6000  290  485.802  778.294 
6000  330  483.704  781.703 
6000  370  490.904  948.501 
6000  410  500.011  875.807 
6000  450  508.213 1045.299 
6000  490  518.894 1010.203 
6000  530  530.887 1192.784 
6000  570  534.415 1151.013 
6000  610  530.887 1504.779 
6000  650  539.279 1486.802 
6000  690  536.084 1650.810 
6000  730  549.698 1454.687 
6000  770  564.909 1576.114 
6000  810  545.001 1588.297 
6000  850  564.504 1711.607 
6000  890  584.197 1760.793 
6000  930  564.480 1963.091 
6000  970  586.390 1955.199 
6000 1010  590.706 2117.491 

的理解首先做幾片速度非常快，但性能下降大幅下降的長度增長。 islice在較小的切片上速度較慢，但​​其平均速度要好得多。

這是我的測試：

import timeit 

size = 10000 
repeats = 100 

setup = """ 
import collections, itertools 
d = collections.deque(range(%d)) 
""" % size 

print '%5s\t%5s\t%10s\t%10s' % ('offset', 'length', 'islice', 'compr') 

for offset in range(0, size - 2000, 2000): 
    for length in range(10, 2000, 40): 
     t1 = timeit.timeit('list(itertools.islice(d, %d, %d))' % (offset, offset + length), setup, number=repeats) 
     t2 = timeit.timeit('[d[i] for i in range(%d, %d)]' % (offset, offset + length), setup, number=repeats) 
     print '%5d\t%5d\t%10.3f\t%10.3f' % (offset, length, t1 * 100000, t2 * 100000)