Kiểm tra xem hai mục có nằm trong danh sách không, theo một thứ tự cụ thể?

Question

Giả sử tôi có một danh sách v = [1, 2, 3, 4, 3, 1, 2]. Tôi muốn viết một hàm, find_pair sẽ kiểm tra xem hai số có nằm trong danh sách và liền kề với nhau không. Vì vậy, find_pair(v, 2, 3) phải trả lại True, nhưng find_pair(v, 1, 4) phải trả lại False.

Có thể triển khai find_pair mà không có vòng lặp không?

Answer 1

v = [1,2,3,4,3,1,2] 
any([2,3] == v[i:i+2] for i in xrange(len(v) - 1)) 

Trong khi phiên bản @ PaoloCapriotti của hiện các trick, chương trình này là nhanh hơn, bởi vì nó dừng lại phân tích các v càng sớm càng hợp được tìm thấy.

Answer 2

[2, 3] in [v[i:i+2] for i in range(len(v) - 1)] 

Answer 3

Nói chung không thể lặp lại tất cả các giá trị. Sau cùng, danh sách một nghìn phần tử có thể kết thúc bằng [.., 2, 3].

Trong trường hợp đặc biệt, có các phím tắt. Các giá trị luôn được đặt hàng và bạn có luôn tìm kiếm một giá trị cụ thể không? Nếu có, bạn có thể, ví dụ: sử dụng tìm kiếm nhị phân để tìm giá trị và sau đó so sánh nó với giá trị tiếp theo. Nếu các giá trị không có thứ tự, không có phím tắt. Nếu bạn đang tìm kiếm bất kỳ hai giá trị tiếp theo nào, thì không có lối tắt nào. Đối với trường hợp ở giữa, có thể có một phím tắt.

Answer 4

Đây có lẽ là một chút của một vòng về cách để làm điều đó, nhưng bạn có thể sử dụng (với v biến của bạn ở trên):

' 2, 3' in str(v) 

Answer 5

Bạn sẽ cần một vòng lặp.

Không giống như chuỗi Python hỗ trợ kiểm tra sau đó bằng cách sử dụng toán tử trong, danh sách Python không có kiểm tra sau được tạo sẵn.

Answer 6

Nếu viết danh sách xảy ra ít thường xuyên hơn đọc từ nó, có lẽ bạn có thể xây dựng một cây tiền tố khi viết. [1] sẽ có một nút con [2], [2] sẽ có [3] và [3] a [4]. Với một bộ dữ liệu phức tạp hơn, cây sẽ hữu ích hơn. Nó sẽ có độ sâu 2 trong trường hợp của bạn và sẽ được lập chỉ mục trên phần tử ban đầu trong chuỗi tìm kiếm của bạn.

Bạn vẫn muốn truy cập từng nút, nhưng chỉ một lần cho vòng đời của chuỗi tìm kiếm, nếu chỉ nối thêm. Khi bạn chắp thêm một phần tử, bạn sẽ cập nhật cây để bao gồm phần tử con nếu không có. Sau đó, số lần đọc được giảm xuống tối đa O (2 * k) trong đó k là số phần tử duy nhất. Trong trường hợp các chữ số, đó là 20 lần đọc tối đa để kiểm tra xem một chuỗi có nằm trong danh sách hay không.

Lợi thế tốc độ xuất phát từ việc precomputing độ dài-2 sau đó danh sách chứa và xóa các bản sao. Nó cũng có vảy tốt với độ dài dài hơn. O (độ sâu * k) trường hợp xấu nhất. Thậm chí tốt hơn nếu hashtables được sử dụng.

Answer 7

v = [1,2,3,4,3,1,2] 

def find(x,y,v): 
     return (x,y) in zip(v,v[1:]) 

print find(2,3,v) 
print find(1,4,v) 

Answer 8

Tôi biết bạn đã hài lòng với một trong những câu trả lời trong bài viết này, nhưng bạn có thể thử với những sản phẩm sau

>>> v = [1,2,3,4,3,1,2] 
def InList(v,(i,j)): 
    start=1 
    try: 
     while True: 
      if v[v.index(i,start)+1]==j and v[v.index(j,start)-1]==i: 
       return True 
      start=v.index(i)+1 
    except IndexError: 
     return False 
    except ValueError: 
     return False 


>>> InList(v,(2,3)) 
True 
>>> InList(v,(4,5)) 
False 
>>> InList(v,(1,2)) 
True 
>>> InList(v,(12,2)) 
False 
>>> InList(v,(3,1)) 
True 

Ok Curiosity trở nên tốt hơn của tôi và vì vậy muốn kiểm tra cách thực hiện điều này thực hiện thực hiện với việc thực hiện đăng tải nhanh nhất

>>> stmt1=""" 
v = [1,2,3,4,3,1,2] 
def InList(v,(i,j)): 
    start=1 
    try: 
     while True: 
      if v[v.index(i,start)+1]==j and v[v.index(j,start)-1]==i: 
       return True 
      start=v.index(i)+1 
    except IndexError: 
     return False 
    except ValueError: 
     return False 
InList(v,(2,3)) 
InList(v,(4,5)) 
InList(v,(1,2)) 
InList(v,(12,2)) 
""" 
>>> stmt2=""" 
v = [1,2,3,4,3,1,2] 
def InList(v,(x,y)): 
    any([x,y] == v[i:i+2] for i in xrange(len(v) - 1)) 
InList(v,(2,3)) 
InList(v,(4,5)) 
InList(v,(1,2)) 
InList(v,(12,2)) 
""" 
>>> t1=timeit.Timer(stmt=stmt1) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=100000)/100000) 
13.67 usec/pass 
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=100000)/100000) 
20.67 usec/pass 
>>> 

Gosh đây là cách nhanh

Lưu ý ** Cảm ơn Michael đã chỉ ra. Tôi đã sửa chữa nó và đây là giải pháp cập nhật của tôi.

Answer 9

Câu trả lời của eumiro giành được sự thanh lịch, nhưng nếu bạn cần một cái gì đó nhanh hơn, bạn có thể tận dụng phương pháp được xây dựng trong list.index() giúp tiết kiệm thời gian trong việc lặp lại toàn bộ danh sách.

v = [1,2,3,4,3,1,2] 

def f1(items): 
    return any([2,3] == v[i:i+2] for i in xrange(len(v) - 1)) 

def f2(items): 
    i = 0 
    index = items.index 
    try: 
     while 1: 
      i = index(2, i) + 1 
      if items[i] == 3: 
       return True 
    except IndexError: 
     return False 

from timeit import repeat  
print "f1", min(repeat("f1(v)", "from __main__ import f1, v", number=1000)) 
print "f2", min(repeat("f2(v)", "from __main__ import f2, v", number=1000)) 

Khi tôi chạy này, tôi nhận được:

f1 0.00300002098083 
f2 0.0 

này cần được nhanh hơn khi trận đấu không phải là quá gần đầu danh sách.

Answer 10

Bạn có thể sử dụng Boyer-Moore algorithm để tăng tốc hoàn toàn không cần thiết. Các trường hợp chung là một chút khó khăn, nhưng nó đơn giản nếu bạn chỉ tìm kiếm một cặp.

def find_pair(seq, a, b): 
    i = 1 
    while i < len(seq): 
     if seq[i] == b and seq[i - 1] == a: return i - 1 
     i += 2 - (seq[i] == a) 

print find_pair([1, 5, 3, 4, 3, 1, 2, 3, 3], 2, 3) 

Answer 11

Có lẽ thậm chí đơn giản hơn:

a = range(100) 
exists = (55,56) in zip(a, a[1:])