Làm thế nào để lát một deque?

Question

Tôi đã thay đổi một số mã sử dụng danh sách để sử dụng deque. Tôi không còn có thể cắt vào nó nữa, vì tôi gặp lỗi:

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

Đây là một REPL hiển thị sự cố.

>>> 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' 

Vì vậy, có cách giải quyết khác để hỗ trợ cắt thành bản đồ trong Python?

Answer 1

Hãy thử itertools.islice().

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

Indexing thành một deque đòi hỏi sau đây một danh sách liên kết từ đầu mỗi lần, vì vậy phương pháp islice(), bỏ qua mục để có được sự khởi đầu của những lát, sẽ cung cấp hiệu suất tốt nhất có thể (tốt hơn so với mã hóa nó như là một hoạt động chỉ mục cho mỗi phần tử).

Bạn có thể dễ dàng viết một lớp con deque thực hiện điều này một cách tự động cho bạn.

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) 

Lưu ý rằng bạn không thể sử dụng chỉ số âm hoặc giá trị bước với islice. Có thể viết mã xung quanh điều này, và có thể là đáng giá nếu bạn làm theo cách tiếp cận phân lớp. Để bắt đầu tiêu cực hoặc dừng bạn chỉ có thể thêm chiều dài của deque; đối với bước tiêu cực, bạn cần phải ném một số reversed() vào nơi nào đó. Tôi sẽ để nó như một bài tập. :-)

Hiệu suất của việc truy xuất các mục riêng lẻ từ deque sẽ được giảm nhẹ theo thử nghiệm if cho lát cắt. Nếu đây là một vấn đề, bạn có thể sử dụng một mô hình EAFP để cải thiện điều này phần nào - với chi phí làm con đường lát hơi ít performant do nhu cầu để xử lý ngoại lệ:

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)) 

Tất nhiên có một thêm chức năng gọi trong đó vẫn còn, so với một thường xuyên deque, vì vậy nếu bạn thực sự quan tâm về hiệu suất, bạn thực sự muốn thêm một phương pháp riêng biệt slice() hoặc tương tự.

Answer 2

Nếu hiệu suất là mối quan ngại, hãy xem xét phương pháp truy cập/đọc trực tiếp như được đề xuất trong this answer. Đó là nhanh hơn nhiều so islice vào bộ sưu tập lớn:

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 

Theo @RaymondHettinger bình luận dưới đây, phương pháp hiểu là chỉ tốt hơn khi lát là ngắn. Trên lát dài hơn, islice giành chiến thắng thuyết phục. Ví dụ: dưới đây là thời gian để cắt 10.000 mục được tách ra khỏi bù trừ 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 

Lần đọc đầu tiên ít lát rất nhanh, nhưng hiệu suất giảm đáng kể khi độ dài tăng. islice là chậm hơn trên lát nhỏ hơn, nhưng tốc độ trung bình của nó là tốt hơn nhiều.

Đây là cách tôi thử nghiệm:

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)