`bisect` --- Thuật toán chia đôi mảng¶

Source code: Lib/bisect.py

Mô-đun này cung cấp hỗ trợ để duy trì danh sách theo thứ tự được sắp xếp mà không cần phải sắp xếp danh sách sau mỗi lần chèn. Đối với danh sách dài các mục có thao tác so sánh tốn kém, đây có thể là một cải tiến so với tìm kiếm tuyến tính hoặc sử dụng thường xuyên.

Mô-đun này được gọi là bisect vì nó sử dụng thuật toán chia đôi cơ bản để thực hiện công việc của mình. Không giống như các công cụ chia đôi khác tìm kiếm một giá trị cụ thể, các hàm trong mô-đun này được thiết kế để xác định vị trí điểm chèn. Theo đó, các hàm không bao giờ gọi phương thức __eq__() để xác định xem một giá trị có được tìm thấy hay không. Thay vào đó, các hàm chỉ gọi phương thức __lt__() và sẽ trả về điểm chèn giữa các giá trị trong một mảng.

Ghi chú

Các chức năng trong mô-đun này không an toàn theo luồng. Nếu nhiều luồng đồng thời sử dụng các hàm bisect trên cùng một chuỗi, điều này có thể dẫn đến hành vi không xác định. Tương tự, nếu chuỗi được cung cấp bị thay đổi bởi một luồng khác trong khi hàm bisect đang hoạt động trên chuỗi đó thì kết quả sẽ không được xác định. Ví dụ: sử dụng insort_left() trên cùng một danh sách từ nhiều luồng có thể khiến danh sách không được sắp xếp.

Các chức năng sau đây được cung cấp:

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)¶

Xác định vị trí điểm chèn cho x trong a để duy trì thứ tự được sắp xếp. Các tham số lo và hi có thể được sử dụng để chỉ định một tập hợp con của danh sách cần được xem xét; theo mặc định toàn bộ danh sách được sử dụng. Nếu x đã có trong a, điểm chèn sẽ ở trước (ở bên trái) bất kỳ mục nhập hiện có nào. Giá trị trả về phù hợp để sử dụng làm tham số đầu tiên cho list.insert() giả sử rằng a đã được sắp xếp.

Điểm chèn ip được trả về sẽ phân chia mảng a thành hai lát sao cho all(elem < x for elem in a[lo : ip]) đúng với lát cắt bên trái và all(elem >= x for elem in a[ip : hi]) đúng với lát cắt bên phải.

key chỉ định key function của một đối số được sử dụng để trích xuất khóa so sánh từ mỗi phần tử trong mảng. Để hỗ trợ tìm kiếm các bản ghi phức tạp, hàm key không được áp dụng cho giá trị x.

Nếu key là None, các phần tử sẽ được so sánh trực tiếp và không có hàm chính nào được gọi.

Thay đổi trong phiên bản 3.10: Đã thêm tham số key.

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)¶

bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)¶

Tương tự như bisect_left(), nhưng trả về một điểm chèn nằm sau (ở bên phải) bất kỳ mục nhập hiện có nào của x trong a.

Điểm chèn ip được trả về sẽ phân chia mảng a thành hai lát sao cho all(elem <= x for elem in a[lo : ip]) đúng với lát cắt bên trái và all(elem > x for elem in a[ip : hi]) đúng với lát cắt bên phải.

Thay đổi trong phiên bản 3.10: Đã thêm tham số key.

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)¶

Chèn x vào a theo thứ tự được sắp xếp.

Hàm này trước tiên chạy bisect_left() để xác định vị trí điểm chèn. Tiếp theo, nó chạy phương thức insert() trên a để chèn x vào vị trí thích hợp nhằm duy trì thứ tự sắp xếp.

Để hỗ trợ chèn bản ghi vào bảng, hàm key (nếu có) được áp dụng cho x cho bước tìm kiếm nhưng không áp dụng cho bước chèn.

Hãy nhớ rằng tìm kiếm O(log n) bị chi phối bởi bước chèn O(n) chậm.

Thay đổi trong phiên bản 3.10: Đã thêm tham số key.

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)¶

bisect.insort(a, x, lo=0, hi=len(a), *, key=None)¶

Tương tự như insort_left(), nhưng chèn x vào a sau bất kỳ mục nhập hiện có nào của x.

Hàm này trước tiên chạy bisect_right() để xác định vị trí điểm chèn. Tiếp theo, nó chạy phương thức insert() trên a để chèn x vào vị trí thích hợp nhằm duy trì thứ tự sắp xếp.

Để hỗ trợ chèn bản ghi vào bảng, hàm key (nếu có) được áp dụng cho x cho bước tìm kiếm nhưng không áp dụng cho bước chèn.

Hãy nhớ rằng tìm kiếm O(log n) bị chi phối bởi bước chèn O(n) chậm.

Thay đổi trong phiên bản 3.10: Đã thêm tham số key.

Ghi chú hiệu suất¶

Khi viết mã nhạy cảm với thời gian bằng bisect() và insort(), hãy ghi nhớ những suy nghĩ sau:

Chia đôi có hiệu quả để tìm kiếm phạm vi giá trị. Để định vị các giá trị cụ thể, từ điển có hiệu suất cao hơn.
Các hàm insort() là O(n) vì bước tìm kiếm logarit bị chi phối bởi bước chèn thời gian tuyến tính.
Các hàm tìm kiếm không có trạng thái và loại bỏ các kết quả chính của hàm sau khi chúng được sử dụng. Do đó, nếu các hàm tìm kiếm được sử dụng trong một vòng lặp thì hàm khóa có thể được gọi đi gọi lại trên cùng các phần tử mảng. Nếu hàm phím không nhanh, hãy cân nhắc gói nó bằng functools.cache() để tránh tính toán trùng lặp. Ngoài ra, hãy xem xét việc tìm kiếm một mảng các khóa được tính toán trước để xác định vị trí điểm chèn (như được hiển thị trong phần ví dụ bên dưới).

Xem thêm

Sorted Collections là mô-đun hiệu suất cao sử dụng bisect để quản lý các bộ sưu tập dữ liệu được sắp xếp.
Zz000zz sử dụng bisect để xây dựng một lớp bộ sưu tập đầy đủ tính năng với các phương pháp tìm kiếm đơn giản và hỗ trợ chức năng chính. Các phím được tính toán trước để lưu các cuộc gọi không cần thiết đến chức năng phím trong quá trình tìm kiếm.

Tìm kiếm danh sách đã sắp xếp¶

bisect functions ở trên rất hữu ích cho việc tìm kiếm các điểm chèn nhưng có thể phức tạp hoặc khó sử dụng cho các tác vụ tìm kiếm thông thường. Năm hàm sau đây hiển thị cách chuyển đổi chúng thành tra cứu tiêu chuẩn cho danh sách được sắp xếp:

chỉ số def (a, x):
    'Tìm giá trị ngoài cùng bên trái chính xác bằng x'
    i = bisect_left(a, x)
    nếu i != len(a) và a[i] == x:
        trả lại tôi
    tăng giá trịError

chắc chắn find_lt(a, x):
    'Tìm giá trị ngoài cùng bên phải nhỏ hơn x'
    i = bisect_left(a, x)
    nếu tôi:
        trả về a[i-1]
    tăng giá trịError

def find_le(a, x):
    'Tìm giá trị ngoài cùng bên phải nhỏ hơn hoặc bằng x'
    i = bisect_right(a, x)
    nếu tôi:
        trả về a[i-1]
    tăng giá trịError

def find_gt(a, x):
    'Tìm giá trị ngoài cùng bên trái lớn hơn x'
    i = bisect_right(a, x)
    nếu tôi != len(a):
        trả lại một [i]
    tăng giá trịError

def find_ge(a, x):
    'Tìm mục ngoài cùng bên trái lớn hơn hoặc bằng x'
    i = bisect_left(a, x)
    nếu tôi != len(a):
        trả lại một [i]
    tăng giá trịError

Ví dụ¶

Hàm bisect() có thể hữu ích cho việc tra cứu bảng số. Ví dụ này sử dụng bisect() để tra cứu điểm chữ cái cho điểm bài kiểm tra (giả sử) dựa trên một tập hợp các điểm dừng số theo thứ tự: 90 trở lên là 'A', 80 đến 89 là 'B', v.v.:

>>> điểm def (điểm)
... i = chia đôi([60, 70, 80, 90], điểm)
... trả về "FDCBA"[i]
...
>>> [điểm(điểm) cho điểm trong [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

Các hàm bisect() và insort() cũng hoạt động với danh sách các bộ dữ liệu. Đối số key có thể dùng để trích xuất trường được sử dụng để sắp xếp các bản ghi trong bảng

>>> từ bộ sưu tập nhập têntuple
>>> từ trình điều khiển nhập khẩu của nhà điều hành
>>> từ nhập bisect bisect, insort
>>> từ pprint nhập pprint

>>> Phim = têntuple('Phim', ('tên', 'đã phát hành', 'đạo diễn'))

>>> phim = [
... Phim('Jaws', 1975, 'Spielberg'),
... Phim('Titanic', 1997, 'Cameron'),
... Phim('The Birds', 1963, 'Hitchcock'),
... Phim('Người ngoài hành tinh', 1986, 'Cameron')
...]

>>> # Find bộ phim đầu tiên ra mắt sau năm 1960
>>> by_year = attrgetter('đã phát hành')
>>> movies.sort(key=by_year)
>>> phim[bisect(phim, 1960, key=by_year)]
Phim(name='The Birds', phát hành=1963, đạo diễn='Hitchcock')

>>> # Insert một bộ phim trong khi vẫn duy trì thứ tự sắp xếp
>>> lãng mạn = Phim('Chuyện tình', 1970, 'Hiller')
>>> insort(phim, lãng mạn, key=by_year)
>>> pprint(phim)
[Phim(name='The Birds', phát hành=1963, đạo diễn='Hitchcock'),
 Phim(name='Love Story', phát hành=1970, đạo diễn='Hiller'),
 Phim(name='Jaws', phát hành=1975, đạo diễn='Spielberg'),
 Phim(name='Người ngoài hành tinh', phát hành=1986, đạo diễn='Cameron'),
 Phim(name='Titanic', phát hành=1997, đạo diễn='Cameron')]

Nếu chức năng khóa đắt tiền, có thể tránh các lệnh gọi hàm lặp lại bằng cách tìm kiếm danh sách các khóa được tính toán trước để tìm chỉ mục của bản ghi:

>>> data = [('đỏ', 5), ('xanh', 1), ('vàng', 8), ('đen', 0)]
>>> data.sort(key=lambda r: r[1]) # Or sử dụng operator.itemgetter(1).
>>> phím = [r[1] cho r trong dữ liệu] # Precompute danh sách các phím.
>>> dữ liệu[bisect_left(keys, 0)]
('đen', 0)
>>> dữ liệu[bisect_left(keys, 1)]
('màu xanh', 1)
>>> dữ liệu[bisect_left(phím, 5)]
('đỏ', 5)
>>> dữ liệu[bisect_left(phím, 8)]
('màu vàng', 8)

`bisect` --- Thuật toán chia đôi mảng¶

Ghi chú hiệu suất¶

Tìm kiếm danh sách đã sắp xếp¶

Ví dụ¶

Table of Contents

Chủ đề trước

Chủ đề tiếp

Trang này

bisect --- Thuật toán chia đôi mảng¶

Ghi chú hiệu suất¶

Tìm kiếm danh sách đã sắp xếp¶

Ví dụ¶

`bisect` --- Thuật toán chia đôi mảng¶