Tìm kiếm nào là tốt nhất trong Python?

Tải xuống IMDb

Để lấy dữ liệu theo cách thủ công, hãy điều hướng trình duyệt web của bạn đến https. // bộ dữ liệu. imdbws. com/ và lấy tệp có tên

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Nó có một tiêu đề với các tên cột trong dòng đầu tiên, theo sau là các bản ghi dữ liệu trong mỗi dòng tiếp theo. Mỗi bản ghi chứa một mã định danh duy nhất, tên đầy đủ, năm sinh và một số thuộc tính khác. Tất cả đều được phân cách bằng ký tự tab

Có hàng triệu bản ghi, vì vậy đừng cố mở tệp bằng trình soạn thảo văn bản thông thường để tránh làm hỏng máy tính của bạn. Ngay cả phần mềm chuyên dụng như bảng tính cũng có thể gặp sự cố khi mở nó. Thay vào đó, bạn có thể tận dụng trình xem lưới dữ liệu hiệu suất cao có trong JupyterLab chẳng hạn

Đọc các giá trị được phân tách bằng tab

Có một số cách để phân tích tệp TSV. Ví dụ: bạn có thể đọc nó bằng Pandas, sử dụng ứng dụng chuyên dụng hoặc tận dụng một số công cụ dòng lệnh. Tuy nhiên, bạn nên sử dụng tập lệnh Python đơn giản có trong mã mẫu

Ghi chú. Theo nguyên tắc thông thường, bạn nên tránh phân tích cú pháp tệp theo cách thủ công vì bạn có thể bỏ qua các trường hợp cạnh. Ví dụ: ở một trong các trường, ký tự tab phân tách có thể được sử dụng theo nghĩa đen bên trong dấu ngoặc kép, điều này sẽ phá vỡ số lượng cột. Bất cứ khi nào có thể, hãy cố gắng tìm một mô-đun có liên quan trong thư viện tiêu chuẩn hoặc bên thứ ba đáng tin cậy

Cuối cùng, bạn muốn kết thúc với hai tệp văn bản theo ý của bạn

1. >>> fruits = ['orange', 'plum', 'banana', 'apple']
   >>> fruits.index('banana')
   2
   >>> fruits.index('blueberry')
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   ValueError: 'blueberry' is not in list
   

   0

2. >>> fruits = ['orange', 'plum', 'banana', 'apple']
   >>> fruits.index('banana')
   2
   >>> fruits.index('blueberry')
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   ValueError: 'blueberry' is not in list
   

   1

Một sẽ chứa danh sách các tên có được bằng cách cắt bỏ cột thứ hai khỏi tệp TSV gốc

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Cái thứ hai sẽ là phiên bản được sắp xếp của cái này

Khi cả hai tệp đã sẵn sàng, bạn có thể tải chúng vào Python bằng chức năng này

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Mã này trả về một danh sách các tên được lấy từ tệp đã cho. Lưu ý rằng việc gọi

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Đo thời gian thực hiện

Để đánh giá hiệu suất của một thuật toán cụ thể, bạn có thể đo thời gian thực hiện của thuật toán đó dựa trên bộ dữ liệu IMDb. Điều này thường được thực hiện với sự trợ giúp của các mô-đun

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Bạn cũng có thể xác định một trình trang trí tùy chỉnh để tính thời gian cho một chức năng nếu bạn muốn. Mã mẫu được cung cấp sử dụng, được giới thiệu trong Python 3. 7, vì nó mang lại độ chính xác cao tính bằng nano giây

Tìm kiếm ngẫu nhiên

Làm thế nào bạn có thể tìm kiếm một cái gì đó trong ba lô của bạn? . Nếu bạn không may mắn, thì bạn đặt món đồ trở lại, rửa sạch và lặp lại. Ví dụ này là một cách hay để hiểu tìm kiếm ngẫu nhiên, đây là một trong những thuật toán tìm kiếm kém hiệu quả nhất. Sự kém hiệu quả của cách tiếp cận này xuất phát từ thực tế là bạn có nguy cơ chọn sai cùng một thứ nhiều lần.

Ghi chú. Thật thú vị, về mặt lý thuyết, chiến lược này có thể là chiến lược hiệu quả nhất nếu bạn rất may mắn hoặc có một số lượng nhỏ các yếu tố trong bộ sưu tập

Nguyên tắc cơ bản của thuật toán này có thể được diễn đạt bằng đoạn mã Python sau

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Hàm lặp lại cho đến khi một số phần tử được chọn ngẫu nhiên khớp với giá trị đã cho làm đầu vào. Tuy nhiên, điều này không hữu ích lắm vì hàm trả về

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Nhận mã mẫu. Nhấp vào đây để lấy mã mẫu mà bạn sẽ sử dụng để tìm hiểu về tìm kiếm nhị phân trong Python trong hướng dẫn này

Đối với các bộ dữ liệu vi mô, thuật toán tìm kiếm ngẫu nhiên dường như đang thực hiện công việc của nó khá nhanh

>>>

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Tuy nhiên, hãy tưởng tượng bạn phải tìm kiếm như vậy qua hàng triệu phần tử. Dưới đây là tóm tắt nhanh về thử nghiệm hiệu suất đã được thực hiện đối với bộ dữ liệu IMDb

Search TermElement IndexBest TimeAverage TimeWorst TimeFred Astaire

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

Các yếu tố duy nhất tại các vị trí bộ nhớ khác nhau được chọn cụ thể để tránh sai lệch. Mỗi thuật ngữ được tìm kiếm mười lần để tính đến tính ngẫu nhiên của thuật toán và các yếu tố khác, chẳng hạn như các quy trình hệ thống đang chạy trong nền

Ghi chú. Nếu bạn muốn tự mình tiến hành thử nghiệm này, hãy tham khảo lại hướng dẫn trong phần giới thiệu của hướng dẫn này. Để đo lường hiệu suất mã của bạn, bạn có thể sử dụng các mô-đun

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Thuật toán có hiệu suất không xác định. Mặc dù thời gian trung bình để tìm một phần tử không phụ thuộc vào vị trí của nó, nhưng thời điểm tốt nhất và tồi tệ nhất cách nhau từ hai đến ba bậc độ lớn. Nó cũng bị hành vi không nhất quán. Cân nhắc việc có một bộ sưu tập các phần tử chứa một số bản sao. Vì thuật toán chọn các phần tử một cách ngẫu nhiên nên chắc chắn nó sẽ trả về các bản sao khác nhau trong các lần chạy tiếp theo

Làm thế nào bạn có thể cải thiện về điều này?

Tìm kiếm tuyến tính

Khi quyết định ăn gì cho bữa trưa, bạn có thể nhìn quanh thực đơn một cách hỗn loạn cho đến khi có thứ gì đó thu hút sự chú ý của bạn. Ngoài ra, bạn có thể thực hiện một cách tiếp cận có hệ thống hơn bằng cách quét menu từ trên xuống dưới và xem xét kỹ lưỡng từng mục theo trình tự. Tóm lại đó là tìm kiếm tuyến tính. Để triển khai nó trong Python, bạn có thể

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Hàm lặp qua một tập hợp các phần tử theo thứ tự được xác định trước và nhất quán. Nó dừng lại khi tìm thấy phần tử hoặc khi không còn phần tử nào để kiểm tra. Chiến lược này đảm bảo rằng không có phần tử nào được truy cập nhiều hơn một lần vì bạn đang duyệt qua chúng theo thứ tự trước

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

Hãy xem tìm kiếm tuyến tính đối phó tốt như thế nào với bộ dữ liệu IMDb bạn đã sử dụng trước đây

Search TermElement IndexBest TimeAverage TimeWorst TimeFred Astaire

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Hầu như không có bất kỳ sự khác biệt nào trong thời gian tra cứu của một phần tử riêng lẻ. Thời gian trung bình hầu như giống như thời gian tốt nhất và tồi tệ nhất. Vì các phần tử luôn được duyệt theo cùng một thứ tự nên số lần so sánh cần thiết để tìm cùng một phần tử không thay đổi

Tuy nhiên, thời gian tìm kiếm tăng lên với chỉ mục tăng dần của một phần tử trong bộ sưu tập. Phần tử càng xa đầu danh sách thì càng phải chạy nhiều phép so sánh hơn. Trong trường hợp xấu nhất, khi thiếu một phần tử, phải kiểm tra toàn bộ tập hợp để đưa ra câu trả lời chắc chắn

Khi bạn chiếu dữ liệu thử nghiệm lên một biểu đồ và kết nối các dấu chấm, thì bạn sẽ thấy ngay mối quan hệ giữa vị trí phần tử và thời gian cần thiết để tìm thấy nó

Tất cả các mẫu nằm trên một đường thẳng và có thể được mô tả bằng một hàm tuyến tính, đó là nguồn gốc của tên thuật toán. Bạn có thể giả định rằng, trung bình, thời gian cần thiết để tìm bất kỳ phần tử nào bằng cách sử dụng tìm kiếm tuyến tính sẽ tỷ lệ thuận với số lượng tất cả các phần tử trong tập hợp. Chúng không mở rộng tốt khi lượng dữ liệu để tìm kiếm tăng lên

Ví dụ: máy quét sinh trắc học có sẵn tại một số sân bay sẽ không nhận ra hành khách chỉ trong vài giây nếu chúng được triển khai bằng tìm kiếm tuyến tính. Mặt khác, thuật toán tìm kiếm tuyến tính có thể là một lựa chọn tốt cho các tập dữ liệu nhỏ hơn vì thuật toán này không yêu cầu tiền xử lý dữ liệu. Trong trường hợp như vậy, lợi ích của tiền xử lý sẽ không hoàn lại chi phí của nó

Python đã đi kèm với tìm kiếm tuyến tính, vì vậy không có ích gì khi bạn tự viết nó. Ví dụ, cấu trúc dữ liệu

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Điều này cũng có thể cho bạn biết nếu phần tử có trong bộ sưu tập, nhưng một cách Pythonic hơn sẽ liên quan đến việc sử dụng toán tử

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

Điều đáng chú ý là mặc dù sử dụng tìm kiếm tuyến tính ẩn, nhưng các hàm và toán tử tích hợp sẵn này sẽ thổi bay quá trình triển khai của bạn. Đó là bởi vì chúng được viết bằng C thuần túy, biên dịch thành mã máy gốc. Trình thông dịch Python tiêu chuẩn không phù hợp với nó, cho dù bạn có cố gắng thế nào

Một thử nghiệm nhanh với mô-đun

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

>>>

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

Tuy nhiên, đối với các bộ dữ liệu đủ lớn, ngay cả mã gốc cũng sẽ đạt đến giới hạn của nó và giải pháp duy nhất là suy nghĩ lại về thuật toán

Ghi chú. Toán tử

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Trong các tình huống thực tế, thường nên tránh sử dụng thuật toán tìm kiếm tuyến tính. Ví dụ, đã có lúc tôi không thể đăng ký con mèo của mình tại phòng khám thú y vì hệ thống của họ liên tục gặp sự cố. Bác sĩ nói với tôi rằng cuối cùng anh ấy phải nâng cấp máy tính của mình vì thêm nhiều bản ghi vào cơ sở dữ liệu khiến nó chạy ngày càng chậm hơn

Tôi nhớ mình đã nghĩ vào thời điểm đó rằng người viết phần mềm đó rõ ràng không biết về thuật toán tìm kiếm nhị phân

Tìm kiếm nhị phân

Từ nhị phân thường được liên kết với số 2. Trong ngữ cảnh này, nó đề cập đến việc chia một tập hợp các phần tử thành hai nửa và loại bỏ một trong số chúng ở mỗi bước của thuật toán. Điều này có thể làm giảm đáng kể số lần so sánh cần thiết để tìm một phần tử. Nhưng có một nhược điểm—các phần tử trong bộ sưu tập phải được sắp xếp trước

Ý tưởng đằng sau nó giống như các bước tìm trang trong một cuốn sách. Lúc đầu, bạn thường mở cuốn sách đến một trang hoàn toàn ngẫu nhiên hoặc ít nhất một trang gần với nơi bạn nghĩ có thể có trang bạn muốn.

Đôi khi, bạn sẽ đủ may mắn để tìm thấy trang đó trong lần thử đầu tiên. Tuy nhiên, nếu số trang quá thấp, thì bạn biết trang phải ở bên phải. Nếu bạn vượt quá trong lần thử tiếp theo và số trang hiện tại cao hơn trang bạn đang tìm kiếm, thì bạn biết chắc chắn rằng nó phải ở đâu đó ở giữa

Bạn lặp lại quy trình, nhưng thay vì chọn ngẫu nhiên một trang, bạn kiểm tra trang nằm ngay giữa phạm vi mới đó. Điều này giảm thiểu số lần thử. Một cách tiếp cận tương tự có thể được sử dụng trong trò chơi đoán số. Nếu bạn chưa nghe nói về trò chơi đó, thì bạn có thể tra cứu nó trên Internet để có rất nhiều ví dụ được triển khai trong Python

Ghi chú. Đôi khi, nếu các giá trị được phân phối đồng đều, bạn có thể tính chỉ số ở giữa bằng phép nội suy tuyến tính thay vì lấy giá trị trung bình. Biến thể này của thuật toán sẽ yêu cầu ít bước hơn

Số trang hạn chế phạm vi trang để tìm kiếm được gọi là giới hạn dưới và giới hạn trên. Trong tìm kiếm nhị phân, bạn thường bắt đầu với trang đầu tiên là giới hạn dưới và trang cuối cùng là giới hạn trên. Bạn phải cập nhật cả hai giới hạn khi bạn đi. Ví dụ: nếu trang bạn chuyển đến thấp hơn trang bạn đang tìm kiếm, thì đó là giới hạn dưới mới của bạn

Giả sử bạn đang tìm kiếm một quả dâu tây trong bộ sưu tập các loại trái cây được sắp xếp theo thứ tự tăng dần theo kích cỡ

Trong lần thử đầu tiên, phần tử ở giữa là một quả chanh. Vì nó to hơn quả dâu tây nên bạn có thể loại bỏ tất cả các yếu tố sang bên phải, bao gồm cả quả chanh. Bạn sẽ di chuyển cận trên đến vị trí mới và cập nhật chỉ mục ở giữa

Bây giờ, bạn chỉ còn lại một nửa số trái cây mà bạn đã bắt đầu. Yếu tố ở giữa hiện tại thực sự là quả dâu tây bạn đang tìm kiếm, kết thúc tìm kiếm. Nếu không, thì bạn chỉ cần cập nhật các giới hạn cho phù hợp và tiếp tục cho đến khi chúng vượt qua nhau. Ví dụ: tìm kiếm một quả mận bị thiếu, nằm giữa quả dâu tây và quả kiwi, sẽ có kết quả như sau

Lưu ý rằng không có nhiều so sánh phải được thực hiện để tìm phần tử mong muốn. Đó là sự kỳ diệu của tìm kiếm nhị phân. Ngay cả khi bạn đang xử lý hàng triệu yếu tố, bạn chỉ cần tối đa một số lần kiểm tra. Con số này sẽ không vượt quá logarit cơ số hai của tổng số phần tử do giảm một nửa. Nói cách khác, số phần tử còn lại giảm đi một nửa ở mỗi bước

Điều này là có thể bởi vì các yếu tố đã được sắp xếp theo kích thước. Tuy nhiên, nếu bạn muốn tìm trái cây theo một phím khác, chẳng hạn như màu sắc, thì bạn phải sắp xếp lại toàn bộ bộ sưu tập một lần nữa. Để tránh chi phí sắp xếp tốn kém, bạn có thể thử tính toán trước các chế độ xem khác nhau của cùng một bộ sưu tập. Điều này hơi giống với việc tạo chỉ mục cơ sở dữ liệu

Xem xét điều gì sẽ xảy ra nếu bạn thêm, xóa hoặc cập nhật một phần tử trong bộ sưu tập. Để tìm kiếm nhị phân tiếp tục hoạt động, bạn cần duy trì thứ tự sắp xếp phù hợp. Điều này có thể được thực hiện với mô-đun

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Bạn sẽ thấy cách triển khai thuật toán tìm kiếm nhị phân trong Python sau trong hướng dẫn này. Hiện tại, hãy đối đầu với bộ dữ liệu IMDb. Lưu ý rằng có những người khác nhau để tìm kiếm so với trước đây. Đó là bởi vì tập dữ liệu phải được sắp xếp để tìm kiếm nhị phân, giúp sắp xếp lại các phần tử. Các yếu tố mới được định vị gần giống với các chỉ số như trước đây, để giữ cho các phép đo có thể so sánh được

Search TermElement IndexAverage TimeComparisons(…) Berendse

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Các câu trả lời gần như ngay lập tức. Trong trường hợp trung bình, chỉ mất vài phần triệu giây để tìm kiếm nhị phân tìm thấy một phần tử trong số chín phần triệu. Ngoài ra, số lượng so sánh cho các phần tử được chọn gần như không đổi, trùng khớp với công thức sau

Tìm hầu hết các phần tử sẽ yêu cầu số lần so sánh cao nhất, có thể được lấy từ logarit của kích thước của bộ sưu tập. Ngược lại, chỉ có một yếu tố ở giữa có thể được tìm thấy trong lần thử đầu tiên với một phép so sánh

Tìm kiếm nhị phân là một ví dụ tuyệt vời về kỹ thuật phân chia và chinh phục, phân chia một vấn đề thành một loạt các vấn đề nhỏ hơn cùng loại. Các giải pháp riêng lẻ sau đó được kết hợp để tạo thành câu trả lời cuối cùng. Một ví dụ nổi tiếng khác của kỹ thuật này là thuật toán Quicksort

Ghi chú. Đừng nhầm lẫn giữa chia để trị với lập trình động, đây là một kỹ thuật hơi giống nhau

Không giống như các thuật toán tìm kiếm khác, tìm kiếm nhị phân có thể được sử dụng ngoài việc chỉ tìm kiếm. Ví dụ: nó cho phép kiểm tra tư cách thành viên đã đặt, tìm giá trị lớn nhất hoặc nhỏ nhất, tìm hàng xóm gần nhất của giá trị đích, thực hiện truy vấn phạm vi, v.v.

Nếu tốc độ là ưu tiên hàng đầu, thì tìm kiếm nhị phân không phải lúc nào cũng là lựa chọn tốt nhất. Thậm chí còn có các thuật toán nhanh hơn có thể tận dụng cấu trúc dữ liệu dựa trên hàm băm. Tuy nhiên, các thuật toán đó yêu cầu nhiều bộ nhớ bổ sung, trong khi tìm kiếm nhị phân mang lại sự cân bằng tốt giữa không gian và thời gian

Tìm kiếm dựa trên hàm băm

Để tìm kiếm nhanh hơn, bạn cần thu hẹp không gian vấn đề. Tìm kiếm nhị phân đạt được mục tiêu đó bằng cách giảm một nửa số lượng ứng viên ở mỗi bước. Điều đó có nghĩa là ngay cả khi bạn có một triệu phần tử, thì chỉ cần tối đa hai mươi lần so sánh để xác định xem phần tử đó có tồn tại hay không, với điều kiện là tất cả các phần tử đều được sắp xếp

Cách nhanh nhất để tìm kiếm là biết nơi để tìm những gì bạn đang tìm kiếm. Nếu bạn biết chính xác vị trí bộ nhớ của một phần tử, thì bạn sẽ truy cập trực tiếp vào phần tử đó mà không cần phải tìm kiếm ngay từ đầu. Ánh xạ một phần tử hoặc (phổ biến hơn) một trong các khóa của nó tới vị trí phần tử trong bộ nhớ được gọi là băm

Bạn có thể nghĩ về việc băm không phải là tìm kiếm phần tử cụ thể, mà thay vào đó tính toán chỉ mục dựa trên chính phần tử đó. Đó là công việc của một , cái cần giữ một số tính chất toán học nhất định. Một hàm băm tốt nên

• Lấy đầu vào tùy ý và biến nó thành đầu ra có kích thước cố định
• Có phân phối giá trị thống nhất để giảm thiểu va chạm băm
• Tạo ra kết quả xác định
• Là hàm một chiều
• Khuếch đại các thay đổi đầu vào để đạt được hiệu ứng tuyết lở

Đồng thời, nó không nên quá tốn kém về mặt tính toán, nếu không thì chi phí của nó sẽ lớn hơn lợi ích thu được. Hàm băm cũng được sử dụng để xác minh tính toàn vẹn của dữ liệu cũng như trong mật mã

Cấu trúc dữ liệu sử dụng khái niệm này để ánh xạ khóa thành giá trị được gọi là bản đồ, bảng băm, từ điển hoặc mảng kết hợp

Ghi chú. Python có hai cấu trúc dữ liệu tích hợp là

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Một cách khác để hình dung quá trình băm là tưởng tượng cái gọi là nhóm các phần tử tương tự được nhóm theo các khóa tương ứng của chúng. Ví dụ: bạn có thể thu hoạch trái cây vào các thùng khác nhau dựa trên màu sắc

Quả dừa và quả kiwi được cho vào thùng có nhãn màu nâu, trong khi quả táo được cho vào thùng có nhãn màu đỏ, v.v. Điều này cho phép bạn lướt qua một phần của các phần tử một cách nhanh chóng. Lý tưởng nhất là bạn chỉ muốn có một quả trong mỗi thùng. Nếu không, bạn sẽ nhận được cái gọi là xung đột, dẫn đến phải làm thêm

Ghi chú. Các thùng, cũng như nội dung của chúng, thường không theo thứ tự cụ thể

Hãy đặt các tên từ bộ dữ liệu IMDb vào một từ điển để mỗi tên trở thành một khóa và giá trị tương ứng trở thành chỉ mục của nó

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Sau khi tải các tên văn bản vào một danh sách cố định, bạn có thể

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Nhờ hàm băm được sử dụng ở hậu trường, bạn hoàn toàn không phải thực hiện bất kỳ tìm kiếm nào

Đây là cách thuật toán tìm kiếm dựa trên hàm băm hoạt động đối với bộ dữ liệu IMDb

Search TermElement IndexBest TimeAverage TimeWorst TimeFred Astaire

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Không chỉ thời gian trung bình nhanh hơn một bậc so với triển khai Python tìm kiếm nhị phân vốn đã nhanh, mà tốc độ còn được duy trì trên tất cả các phần tử bất kể chúng ở đâu

Giá cho mức tăng đó là khoảng 0. Quá trình Python tiêu thụ thêm 5 GB bộ nhớ, thời gian tải chậm hơn và nhu cầu giữ dữ liệu bổ sung đó phù hợp với nội dung từ điển. Đổi lại, tra cứu rất nhanh, trong khi cập nhật và chèn chậm hơn một chút khi so sánh với danh sách

Một hạn chế khác mà từ điển áp đặt cho các khóa của họ là chúng phải có thể băm được và giá trị băm của chúng không thể thay đổi theo thời gian. Bạn có thể kiểm tra xem một loại dữ liệu cụ thể có thể băm được trong Python hay không bằng cách gọi số

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Các bộ sưu tập có thể thay đổi—chẳng hạn như

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Hàm băm có nhiều công dụng khác. Ví dụ: nó được sử dụng trong mật mã để tránh lưu trữ mật khẩu ở dạng văn bản thuần túy, cũng như để xác minh tính toàn vẹn của dữ liệu

Tìm một phần tử

Để tìm chỉ mục của một phần tử hiện có trong danh sách được sắp xếp, bạn muốn

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Đầu ra cho bạn biết rằng chuối là loại trái cây thứ hai trong danh sách vì nó được tìm thấy ở chỉ mục

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Mặc dù những loại trái cây này chưa có trong danh sách nhưng bạn có thể biết được nên đặt chúng ở đâu. Ví dụ, quả mơ nên nằm giữa quả táo và quả chuối, trong khi quả dưa hấu nên là thành phần cuối cùng. Bạn sẽ biết liệu một phần tử có được tìm thấy hay không bằng cách đánh giá hai điều kiện

1. Là chỉ mục trong kích thước của danh sách?

2. Giá trị của phần tử có phải là giá trị mong muốn không?

Điều này có thể được dịch thành một chức năng phổ quát để tìm các phần tử theo giá trị

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Khi khớp hàm sẽ trả về chỉ số phần tử tương ứng. Nếu không, nó sẽ trả về

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Để tìm kiếm theo khóa, bạn phải duy trì một danh sách khóa riêng. Vì điều này phát sinh thêm chi phí nên bạn nên tính toán trước các phím và tái sử dụng chúng càng nhiều càng tốt. Bạn có thể định nghĩa một lớp trình trợ giúp để có thể tìm kiếm bằng các khóa khác nhau mà không cần sao chép nhiều mã

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Khóa là một hàm được truyền dưới dạng tham số đầu tiên cho

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Sau đó, có phương pháp thực tế để tìm các phần tử theo khóa

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Mã này chia đôi danh sách các khóa đã sắp xếp để lấy chỉ mục của một phần tử theo khóa. Nếu một khóa như vậy tồn tại, thì chỉ mục của nó có thể được sử dụng để lấy cặp tương ứng từ danh sách các cặp khóa-giá trị được tính toán trước đó. Phần tử thứ hai của cặp đó là giá trị mong muốn

Ghi chú. Đây chỉ là một ví dụ minh họa. Bạn sẽ tốt hơn nếu sử dụng công thức được đề xuất, được đề cập trong tài liệu chính thức

Nếu bạn có nhiều chuối, thì

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Có thể dự đoán, để lấy được quả chuối ngoài cùng bên phải, bạn cần gọi tới số

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Khi bạn kết hợp mã, bạn có thể xem bạn có bao nhiêu chuối

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Nếu một phần tử bị thiếu, thì cả

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Chèn một phần tử mới

Một ứng dụng thực tế khác của mô-đun

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Bạn sẽ không thấy bất kỳ sự khác biệt nào cho đến khi có các bản sao trong danh sách của bạn. Nhưng ngay cả khi đó, nó sẽ không trở nên rõ ràng miễn là những bản sao đó là những giá trị đơn giản. Thêm một quả chuối khác vào bên trái sẽ có tác dụng tương tự như thêm nó vào bên phải

Để nhận thấy sự khác biệt, bạn cần một kiểu dữ liệu mà các đối tượng có thể có các đặc điểm nhận dạng duy nhất mặc dù có các giá trị bằng nhau. Hãy định nghĩa một loại

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Một người có một

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Mặt khác, hai biến đó đề cập đến các thực thể hoàn toàn riêng biệt, cho phép bạn phân biệt giữa chúng

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Các biến

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Lưu ý rằng các phiên bản của một lớp dữ liệu không thể so sánh được theo mặc định, điều này ngăn cản bạn sử dụng thuật toán chia đôi trên chúng

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Python không biết đặt hàng

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Đổi lại, điều này cho phép bạn so sánh hai người và quyết định ai đến trước

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Cuối cùng, bạn có thể tận dụng các thuộc tính

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Các số trong ngoặc đơn sau tên cho biết thứ tự chèn. Ban đầu, chỉ có một

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

lặp đi lặp lại

Phiên bản lặp của thuật toán bao gồm một vòng lặp, vòng lặp này sẽ lặp lại một số bước cho đến khi đáp ứng điều kiện dừng. Hãy bắt đầu bằng cách triển khai một hàm sẽ tìm kiếm các phần tử theo giá trị và trả về chỉ mục của chúng

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Bạn sẽ sử dụng lại chức năng này sau

Giả sử rằng tất cả các phần tử đã được sắp xếp, bạn có thể đặt ranh giới dưới và trên ở hai đầu đối diện của chuỗi

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Bây giờ, bạn muốn xác định phần tử ở giữa để xem nó có giá trị mong muốn không. Tính toán chỉ số giữa có thể được thực hiện bằng cách lấy trung bình của cả hai ranh giới

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Lưu ý cách một phép chia số nguyên giúp xử lý cả số lượng phần tử chẵn và lẻ trong phạm vi giới hạn bằng cách làm sàn kết quả. Tùy thuộc vào cách bạn cập nhật ranh giới và xác định điều kiện dừng, bạn cũng có thể sử dụng chức năng trần

Tiếp theo, bạn hoàn thành hoặc chia chuỗi thành hai và tiếp tục tìm kiếm ở một trong các nửa kết quả

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Nếu phần tử ở giữa trùng khớp, thì bạn trả về chỉ mục của nó. Ngược lại, nếu nó quá nhỏ, thì bạn cần di chuyển đường viền dưới lên trên. Nếu nó quá lớn, thì bạn cần di chuyển ranh giới trên xuống

Để tiếp tục, bạn phải đặt hầu hết các bước trong một vòng lặp, vòng lặp này sẽ dừng lại khi ranh giới phía dưới vượt qua ranh giới phía trên

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Nói cách khác, bạn muốn lặp lại miễn là ranh giới dưới thấp hơn hoặc bằng ranh giới trên. Mặt khác, không có kết quả khớp và hàm trả về

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

Tìm kiếm theo khóa rút gọn lại để xem xét các thuộc tính của đối tượng thay vì giá trị theo nghĩa đen của nó. Ví dụ, khóa có thể là số ký tự trong tên của một loại trái cây. Bạn có thể điều chỉnh

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Tuy nhiên, bạn cũng phải nhớ sắp xếp danh sách bằng cách sử dụng cùng một

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>>

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Trong ví dụ trên,

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Điều đó thật tuyệt, nhưng đồng thời, bạn vừa mất khả năng tìm kiếm theo giá trị. Để khắc phục điều này, bạn có thể gán cho

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Ngoài ra, bạn có thể xác định nội tuyến hàm nhận dạng bằng biểu thức lambda ẩn danh

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Với ba chức năng này, bạn có thể nói hầu hết mọi thứ về một phần tử. Tuy nhiên, bạn vẫn chưa giải quyết các trùng lặp trong quá trình triển khai của mình. Điều gì sẽ xảy ra nếu bạn có một nhóm người và một số người trong số họ có chung tên hoặc họ?

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

Để mô hình hóa loại

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Lưu ý việc sử dụng thuộc tính

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Cả hai định nghĩa đều tốt và có thể hoán đổi cho nhau. Mỗi người có một thuộc tính

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

>>>

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Lưu ý cách mọi người hiện được sắp xếp theo họ theo thứ tự tăng dần. Có

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

>>>

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Để bắt chước các tính năng của mô-đun

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Nếu một số chỉ mục đã được tìm thấy, thì bạn có thể nhìn sang bên trái và tiếp tục di chuyển cho đến khi bạn gặp một phần tử có khóa khác hoặc không còn phần tử nào nữa

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Khi bạn đi qua phần tử ngoài cùng bên trái, bạn cần di chuyển chỉ mục về bên phải một vị trí

Tìm trường hợp ngoài cùng bên phải cũng khá giống nhau, nhưng bạn cần lật điều kiện

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Thay vì đi sang trái, bây giờ bạn sẽ sang phải cho đến hết danh sách. Sử dụng cả hai chức năng cho phép bạn tìm tất cả các lần xuất hiện của các mục trùng lặp

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Hàm này luôn trả về một tập hợp. Nếu phần tử không được tìm thấy thì tập hợp sẽ trống. Nếu phần tử là duy nhất, thì tập hợp sẽ chỉ được tạo thành từ một chỉ mục duy nhất. Nếu không, sẽ có nhiều chỉ số trong tập hợp

Để kết thúc, bạn có thể xác định các hàm trừu tượng hơn nữa để hoàn thành thư viện Python tìm kiếm nhị phân của mình

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Điều này không chỉ cho phép bạn xác định chính xác vị trí của các phần tử trong danh sách mà còn truy xuất các phần tử đó. Bạn có thể đặt câu hỏi rất cụ thể

Is it there?Where is it?What is it?

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Có thể tìm thấy mã hoàn chỉnh của thư viện Python tìm kiếm nhị phân này tại liên kết bên dưới

Nhận mã mẫu. Nhấp vào đây để lấy mã mẫu mà bạn sẽ sử dụng để tìm hiểu về tìm kiếm nhị phân trong Python trong hướng dẫn này

đệ quy

Để đơn giản, bạn sẽ chỉ xem xét phiên bản đệ quy của

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Ghi chú. Định nghĩa đệ quy yêu thích của tôi đã được đưa ra trong một tập của loạt bài Fun Fun Function về lập trình hàm trong JavaScript

“Đệ quy là khi một hàm gọi chính nó cho đến khi nó không. ”

— Mattias Petter Johansson

Cách tiếp cận đơn giản nhất là sử dụng phiên bản lặp lại của tìm kiếm nhị phân và sử dụng toán tử cắt để cắt danh sách

import random

def find(elements, value):
    while True:
        random_element = random.choice(elements)
        if random_element == value:
            return random_element

Thay vì lặp, bạn kiểm tra điều kiện một lần và đôi khi gọi hàm tương tự trong danh sách nhỏ hơn. Điều gì có thể đi sai với điều đó?

Để tránh sao chép, bạn có thể sử dụng lại cùng một danh sách nhưng chuyển các ranh giới khác nhau vào hàm bất cứ khi nào cần thiết

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Nhược điểm là mỗi khi bạn muốn gọi hàm đó, bạn phải vượt qua các ranh giới ban đầu, đảm bảo rằng chúng chính xác

>>>

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Nếu bạn mắc lỗi, thì có khả năng sẽ không tìm thấy phần tử đó. Bạn có thể cải thiện điều này bằng cách sử dụng các đối số hàm mặc định hoặc bằng cách giới thiệu một hàm trợ giúp ủy quyền cho hàm đệ quy

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Going further, you might prefer to nest one function in another to hide the technical details and to take advantage of variable reuse from outer scope

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

The

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

1. Local scope
2. Enclosing scope
3. Global scope
4. Built-in symbols

This allows variables that are defined in outer scope to be accessed from within nested blocks of code

The choice between an iterative and a recursive implementation is often the net result of performance considerations, convenience, as well as personal taste. However, there are also certain risks involved with recursion, which is one of the subjects of the next section

Integer Overflow

This is the Java bug that was just mentioned. If you recall, the binary search Python algorithm inspects the middle element of a bounded range in a sorted collection. But how is that middle element chosen exactly? Usually, you take the average of the lower and upper boundary to find the middle index

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

This method of calculating the average works just fine in the overwhelming majority of cases. However, once the collection of elements becomes sufficiently large, the sum of both boundaries won’t fit the integer data type. It’ll be larger than the maximum value allowed for integers

Some programming languages might raise an error in such situations, which would immediately stop program execution. Unfortunately, that’s not always the case. Ví dụ, Java âm thầm bỏ qua vấn đề này, để giá trị đảo ngược và trở thành một số dường như ngẫu nhiên. You’ll only know about the problem as long as the resulting number happens to be negative, which throws an

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Here’s an example that demonstrates this behavior in jshell, which is kind of like an interactive interpreter for Java

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

A safer way to find the middle index could be calculating the offset first and then adding it to the lower boundary

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Even if both values are maxed out, the sum in the formula above will never be. There are a few more ways, but the good news is that you don’t need to worry about any of these, because Python is free from the integer overflow error. Không có giới hạn trên về số nguyên lớn có thể khác với bộ nhớ của bạn

>>>

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

However, there’s a catch. When you call functions from a library, that code might be subject to the C language constraints and still cause an overflow. There are plenty of libraries based on the C language in Python. You could even build your own C extension module or load a dynamically-linked library into Python using

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

tràn ngăn xếp

Về mặt lý thuyết, vấn đề tràn ngăn xếp có thể liên quan đến việc triển khai đệ quy tìm kiếm nhị phân. Hầu hết các ngôn ngữ lập trình đều áp đặt giới hạn về số lần gọi hàm lồng nhau. Mỗi cuộc gọi được liên kết với một địa chỉ trả lại được lưu trữ trên ngăn xếp. Trong Python, giới hạn mặc định là vài nghìn cấp độ của các cuộc gọi như vậy

>>>

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Điều này sẽ không đủ cho nhiều hàm đệ quy. Tuy nhiên, rất khó có khả năng tìm kiếm nhị phân trong Python sẽ cần nhiều hơn do tính chất logarit của nó. Bạn sẽ cần một bộ sưu tập từ hai đến ba nghìn phần tử. Đó là một số có hơn chín trăm chữ số

Tuy nhiên, vẫn có thể xảy ra lỗi đệ quy vô hạn nếu điều kiện dừng được nêu không chính xác do lỗi. Trong trường hợp như vậy, đệ quy vô hạn cuối cùng sẽ gây ra tràn ngăn xếp

Ghi chú. Lỗi tràn ngăn xếp rất phổ biến ở các ngôn ngữ có quản lý bộ nhớ thủ công. Mọi người thường google những lỗi đó để xem liệu có ai khác đã gặp sự cố tương tự hay không, điều này đã đặt tên cho một trang web Hỏi & Đáp phổ biến dành cho các lập trình viên

Bạn có thể tạm thời tăng hoặc giảm giới hạn đệ quy để mô phỏng lỗi tràn ngăn xếp. Lưu ý rằng giới hạn hiệu quả sẽ nhỏ hơn do các chức năng mà môi trường thời gian chạy Python phải gọi

>>>

>>> from search.random import *  # Sample code to download
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

Hàm đệ quy được gọi ba lần trước khi bão hòa ngăn xếp. Bốn cuộc gọi còn lại phải được thực hiện bởi trình thông dịch tương tác. Nếu bạn chạy cùng mã đó trong PyCharm hoặc trình bao Python thay thế, thì bạn có thể nhận được kết quả khác

Các yếu tố trùng lặp

Bạn nhận thức được khả năng có các yếu tố trùng lặp trong danh sách và bạn biết cách xử lý chúng. Điều này chỉ để nhấn mạnh rằng tìm kiếm nhị phân thông thường trong Python có thể không tạo ra kết quả xác định. Tùy thuộc vào cách danh sách được sắp xếp hoặc có bao nhiêu phần tử mà bạn sẽ nhận được câu trả lời khác nhau

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Có hai quả chuối trong danh sách. Lúc đầu, lệnh gọi tới

nconst     primaryName      birthYear  deathYear  (...)
nm0000001  Fred Astaire     1899       1987       (...)
nm0000002  Lauren Bacall    1924       2014       (...)
nm0000003  Brigitte Bardot  1934       \N         (...)
nm0000004  John Belushi     1949       1982       (...)

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Nguyên tắc tương tự, được gọi là tính ổn định của thuật toán, áp dụng cho các thuật toán sắp xếp. Một số ổn định, nghĩa là chúng không thay đổi vị trí tương đối của các phần tử tương đương. Những người khác không đảm bảo như vậy. Nếu bạn cần sắp xếp các phần tử theo nhiều tiêu chí, thì bạn phải luôn bắt đầu từ khóa ít quan trọng nhất để duy trì sự ổn định

Làm tròn dấu phẩy động

Cho đến nay, bạn chỉ tìm kiếm trái cây hoặc người, nhưng còn các con số thì sao?

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Danh sách phải chứa các số một phần mười, hai phần mười và ba phần mười. Đáng ngạc nhiên, chỉ có thể tìm thấy hai trong số ba số đó

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Đây không phải là vấn đề liên quan chặt chẽ đến tìm kiếm nhị phân trong Python, vì tìm kiếm tuyến tính tích hợp phù hợp với nó

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Nó thậm chí không phải là một vấn đề liên quan đến Python mà là cách các số dấu phẩy động được biểu diễn trong bộ nhớ máy tính. Điều này được xác định bởi tiêu chuẩn IEEE 754 cho số học dấu phẩy động. Không đi sâu vào chi tiết, một số số thập phân không có biểu diễn hữu hạn ở dạng nhị phân. Do bộ nhớ hạn chế, những con số đó được làm tròn, gây ra lỗi làm tròn dấu phẩy động

Ghi chú. Nếu bạn yêu cầu độ chính xác tối đa, thì hãy tránh xa các số có dấu phẩy động. Chúng tuyệt vời cho các mục đích kỹ thuật. Tuy nhiên, đối với các hoạt động tiền tệ, bạn không muốn tích lũy lỗi làm tròn. Bạn nên giảm quy mô tất cả giá và số tiền xuống đơn vị nhỏ nhất, chẳng hạn như xu hoặc xu và coi chúng là số nguyên

Ngoài ra, nhiều ngôn ngữ lập trình có hỗ trợ cho số điểm cố định, chẳng hạn như kiểu thập phân trong Python. Điều này giúp bạn kiểm soát thời gian và cách thức làm tròn đang diễn ra

Nếu bạn cần làm việc với các số dấu phẩy động, thì bạn nên thay thế đối sánh chính xác bằng so sánh gần đúng. Hãy xem xét hai biến có giá trị hơi khác nhau

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

So sánh thông thường cho kết quả âm tính, mặc dù cả hai giá trị gần giống nhau. May mắn thay, Python đi kèm với một chức năng sẽ kiểm tra xem hai giá trị có gần nhau trong một số vùng lân cận nhỏ không

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Vùng lân cận đó, là khoảng cách tối đa giữa các giá trị, có thể được điều chỉnh nếu cần

>>>

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Bạn có thể sử dụng chức năng đó để thực hiện tìm kiếm nhị phân trong Python theo cách sau

def find_index(elements, value):
    for index, element in enumerate(elements):
        if element == value:
            return index

Mặt khác, việc triển khai tìm kiếm nhị phân trong Python này chỉ dành riêng cho các số dấu phẩy động. Bạn không thể sử dụng nó để tìm kiếm bất kỳ thứ gì khác mà không gặp lỗi

Độ phức tạp thời gian-không gian

Độ phức tạp tính toán là thước đo tương đối về số lượng tài nguyên mà thuật toán cần để thực hiện công việc của nó. Các tài nguyên bao gồm thời gian tính toán cũng như dung lượng bộ nhớ mà nó sử dụng. So sánh độ phức tạp của các thuật toán khác nhau cho phép bạn đưa ra quyết định sáng suốt về thuật toán nào tốt hơn trong một tình huống nhất định

Ghi chú. Các thuật toán không cần phân bổ nhiều bộ nhớ hơn dữ liệu đầu vào đã tiêu thụ của chúng được gọi là thuật toán tại chỗ hoặc tại chỗ. Điều này dẫn đến việc thay đổi dữ liệu gốc, đôi khi có thể có tác dụng phụ không mong muốn

Bạn đã xem xét một vài thuật toán tìm kiếm và hiệu suất trung bình của chúng đối với một tập dữ liệu lớn. Rõ ràng từ các phép đo đó rằng tìm kiếm nhị phân nhanh hơn tìm kiếm tuyến tính. Bạn thậm chí có thể nói theo yếu tố nào

Tuy nhiên, nếu bạn thực hiện các phép đo tương tự trong một môi trường khác, bạn có thể nhận được kết quả hơi khác hoặc có thể hoàn toàn khác. Có những yếu tố vô hình đang diễn ra có thể ảnh hưởng đến bài kiểm tra của bạn. Bên cạnh đó, các phép đo như vậy không phải lúc nào cũng khả thi. Vì vậy, làm thế nào bạn có thể so sánh sự phức tạp về thời gian một cách nhanh chóng và khách quan?

Bước đầu tiên là chia nhỏ thuật toán thành các phần nhỏ hơn và tìm ra phần hoạt động hiệu quả nhất. Nó có thể sẽ là một hoạt động cơ bản nào đó được gọi rất nhiều và luôn mất khoảng thời gian như nhau để chạy. Đối với các thuật toán tìm kiếm, một hoạt động như vậy có thể là so sánh hai yếu tố

Sau khi thiết lập điều đó, bây giờ bạn có thể phân tích thuật toán. Để tìm độ phức tạp về thời gian, bạn muốn mô tả mối quan hệ giữa số lượng thao tác cơ bản được thực hiện so với kích thước của đầu vào. Chính thức, một mối quan hệ như vậy là một chức năng toán học. Tuy nhiên, bạn không quan tâm đến việc tìm kiếm công thức đại số chính xác của nó mà là ước tính hình dạng tổng thể của nó

Có một vài lớp hàm nổi tiếng mà hầu hết các thuật toán đều phù hợp. Khi bạn phân loại một thuật toán theo một trong số chúng, bạn có thể đặt nó lên thang điểm

Các lớp này cho bạn biết số lượng thao tác cơ bản tăng lên như thế nào khi kích thước đầu vào ngày càng tăng. Họ là, từ trái sang phải

• Hằng số
• logarit
• tuyến tính
• chuẩn tuyến tính
• bậc hai
• số mũ
• yếu tố

Điều này có thể cung cấp cho bạn ý tưởng về hiệu suất của thuật toán mà bạn đang xem xét. Độ phức tạp không đổi, bất kể kích thước đầu vào là gì, là mong muốn nhất. Độ phức tạp logarit vẫn còn khá tốt, cho thấy kỹ thuật chia để trị đang được sử dụng. Càng xa về bên phải trên thang đo này, thuật toán càng phức tạp vì nó có nhiều việc phải làm hơn

Khi bạn đang nói về độ phức tạp của thời gian, điều bạn thường muốn nói là độ phức tạp tiệm cận, mô tả hành vi trong các tập dữ liệu rất lớn. Điều này giúp đơn giản hóa công thức hàm bằng cách loại bỏ tất cả các số hạng và hệ số trừ số hạng và hệ số tăng nhanh nhất (ví dụ: n bình phương)

Tuy nhiên, một chức năng duy nhất không cung cấp đủ thông tin để so sánh chính xác hai thuật toán. Độ phức tạp về thời gian có thể khác nhau tùy thuộc vào khối lượng dữ liệu. Ví dụ: thuật toán tìm kiếm nhị phân giống như một động cơ tăng áp, tạo ra áp suất trước khi nó sẵn sàng cung cấp năng lượng. Mặt khác, thuật toán tìm kiếm tuyến tính nhanh ngay từ đầu nhưng nhanh chóng đạt đến công suất cực đại và cuối cùng thua cuộc

Về tốc độ, thuật toán tìm kiếm nhị phân bắt đầu vượt qua tìm kiếm tuyến tính khi có một số phần tử nhất định trong tập hợp. Đối với các bộ sưu tập nhỏ hơn, tìm kiếm tuyến tính có thể là lựa chọn tốt hơn

Ghi chú. Lưu ý rằng cùng một thuật toán có thể có độ phức tạp thời gian lạc quan, bi quan và trung bình khác nhau. Ví dụ: trong trường hợp tốt nhất, thuật toán tìm kiếm tuyến tính sẽ tìm phần tử ở chỉ mục đầu tiên, sau khi chỉ chạy một lần so sánh

Ở đầu kia của quang phổ, nó sẽ phải so sánh một giá trị tham chiếu với tất cả các phần tử trong bộ sưu tập. Trong thực tế, bạn muốn biết độ phức tạp bi quan của một thuật toán

Có một vài ký hiệu toán học về độ phức tạp tiệm cận, được sử dụng để so sánh các thuật toán. Cho đến nay, phổ biến nhất là ký hiệu Big O

Ký hiệu O lớn

Ký hiệu Big O đại diện cho trường hợp xấu nhất về độ phức tạp tiệm cận. Mặc dù điều này nghe có vẻ khá đáng sợ, nhưng bạn không cần phải biết định nghĩa chính thức. Theo trực giác, đó là thước đo rất sơ bộ về tốc độ tăng trưởng ở phần đuôi của hàm mô tả độ phức tạp. Bạn phát âm nó là “big oh” của một cái gì đó

“Cái gì đó” đó thường là một hàm của kích thước dữ liệu hoặc chỉ là chữ số “một” tượng trưng cho một hằng số. Ví dụ: thuật toán tìm kiếm tuyến tính có độ phức tạp thời gian là

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Ghi chú. Khi bạn nói rằng một thuật toán nào đó có độ phức tạp

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

Trong thực tế, ký hiệu Big O được sử dụng ít trang trọng hơn với cả giới hạn trên và giới hạn dưới. Điều này rất hữu ích cho việc phân loại và so sánh các thuật toán mà không phải lo lắng về các công thức hàm chính xác

Sự phức tạp của tìm kiếm nhị phân

Bạn sẽ ước tính độ phức tạp về thời gian tiệm cận của tìm kiếm nhị phân bằng cách xác định số phép so sánh trong trường hợp xấu nhất—khi một phần tử bị thiếu—như một hàm của kích thước đầu vào. Bạn có thể tiếp cận vấn đề này theo ba cách khác nhau

1. dạng bảng
2. đồ họa
3. Phân tích

Phương pháp dạng bảng là về việc thu thập dữ liệu thực nghiệm, đặt nó vào một bảng và cố gắng đoán công thức bằng cách đánh dấu các giá trị được lấy mẫu

Số phần tửSố phép so sánh001122324353637384

Số lượng phép so sánh tăng lên khi bạn tăng số lượng phần tử trong tập hợp, nhưng tốc độ tăng trưởng chậm hơn so với khi đó là một hàm tuyến tính. Đó là dấu hiệu của một thuật toán tốt có thể mở rộng quy mô với dữ liệu

Nếu điều đó không giúp ích cho bạn, bạn có thể thử phương pháp đồ họa, phương pháp này trực quan hóa dữ liệu được lấy mẫu bằng cách vẽ biểu đồ

Các điểm dữ liệu dường như phủ một đường cong, nhưng bạn không có đủ thông tin để đưa ra câu trả lời kết luận. Nó có thể là một đa thức, có đồ thị tăng giảm đối với các đầu vào lớn hơn

Sử dụng phương pháp phân tích, bạn có thể chọn một số mối quan hệ và tìm kiếm các mẫu. Ví dụ: bạn có thể nghiên cứu cách số lượng phần tử co lại trong mỗi bước của thuật toán

Số phần tử so sánh-n1stn/22ndn/43rdn/8⋮⋮k-thn/2 k

Ban đầu, bạn bắt đầu với toàn bộ tập hợp n phần tử. Sau lần so sánh đầu tiên, bạn chỉ còn lại một nửa trong số họ. Tiếp theo, bạn có một phần tư, v.v. Mô hình phát sinh từ quan sát này là sau khi so sánh thứ k, có n/2 k phần tử. Biến k là số phép toán cơ bản dự kiến

Sau khi so sánh hết k còn phần tử nào nữa. Tuy nhiên, khi bạn lùi lại một bước, tức là k - 1, sẽ còn lại đúng một phần tử. Điều này mang lại cho bạn một phương trình thuận tiện

Nhân cả hai vế của phương trình với mẫu số, sau đó lấy logarit cơ số hai của kết quả và di chuyển hằng số còn lại sang phải. Bạn vừa tìm thấy công thức cho độ phức tạp tìm kiếm nhị phân, theo thứ tự của

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...