Cho đến thời điểm này, chúng tôi chủ yếu quan tâm đến các công cụ để truy cập và thao tác trên dữ liệu mảng với NumPy. Phần này bao gồm các thuật toán liên quan đến việc sắp xếp các giá trị trong mảng NumPy. Các thuật toán này là một chủ đề yêu thích trong các khóa học khoa học máy tính cơ bản. nếu bạn đã từng thực hiện một lần, có lẽ bạn đã có những giấc mơ [hoặc, tùy thuộc vào tính khí của bạn, những cơn ác mộng] về các loại chèn, sắp xếp lựa chọn, sắp xếp hợp nhất, sắp xếp nhanh, sắp xếp bong bóng, v.v. Tất cả đều là phương tiện để hoàn thành một nhiệm vụ tương tự. sắp xếp các giá trị trong một danh sách hoặc mảng
Ví dụ: sắp xếp lựa chọn đơn giản liên tục tìm giá trị nhỏ nhất từ danh sách và thực hiện hoán đổi cho đến khi danh sách được sắp xếp. Chúng ta có thể viết mã này chỉ trong một vài dòng Python
Trong 1]
import numpy as np def selection_sort[x]: for i in range[len[x]]: swap = i + np.argmin[x[i:]] [x[i], x[swap]] = [x[swap], x[i]] return x
Trong 2]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]
Ra[2]
array[[1, 2, 3, 4, 5]]
Như bất kỳ sinh viên năm nhất chuyên ngành khoa học máy tính nào cũng sẽ cho bạn biết, sắp xếp lựa chọn rất hữu ích vì tính đơn giản của nó, nhưng quá chậm để hữu ích cho các mảng lớn hơn. Đối với một danh sách các giá trị $N$, nó yêu cầu các vòng lặp $N$, mỗi vòng lặp thực hiện phép so sánh $\sim N$ theo thứ tự để tìm giá trị hoán đổi. Xét về ký hiệu "big-O" thường được sử dụng để mô tả các thuật toán này [xem Ký hiệu Big-O], giá trị trung bình của sắp xếp lựa chọn $\mathcal{O}[N^2]$. nếu bạn tăng gấp đôi số mục trong danh sách, thời gian thực hiện sẽ tăng lên khoảng bốn lần
Tuy nhiên, ngay cả sắp xếp lựa chọn cũng tốt hơn nhiều so với các thuật toán sắp xếp yêu thích mọi thời đại của tôi, bogosort
Trong 3]
def bogosort[x]: while np.any[x[:-1] > x[1:]]: np.random.shuffle[x] return x
Trong [4]
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]
Ra[4]
array[[1, 2, 3, 4, 5]]
Phương pháp sắp xếp ngớ ngẩn này dựa trên cơ hội thuần túy. nó liên tục áp dụng một sự xáo trộn ngẫu nhiên của mảng cho đến khi kết quả được sắp xếp. Với tỷ lệ trung bình là $\mathcal{O}[N \times N. ]$, [tức là N nhân N giai thừa] cái này–rõ ràng–không bao giờ được sử dụng cho bất kỳ tính toán thực tế nào
May mắn thay, Python chứa các thuật toán sắp xếp tích hợp hiệu quả hơn nhiều so với một trong các thuật toán đơn giản vừa được trình bày. Chúng ta sẽ bắt đầu bằng cách xem xét các phần mềm tích hợp sẵn của Python, sau đó xem xét các quy trình có trong NumPy và được tối ưu hóa cho các mảng NumPy
Sắp xếp nhanh trong NumPy. def bogosort[x]:
while np.any[x[:-1] > x[1:]]:
np.random.shuffle[x]
return x
9 và x = np.array[[2, 1, 4, 3, 5]]
bogosort[x]
0¶
Mặc dù Python có các hàm
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]1 và
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]2 tích hợp để làm việc với các danh sách, nhưng chúng tôi sẽ không thảo luận về chúng ở đây vì hàm
def bogosort[x]: while np.any[x[:-1] > x[1:]]: np.random.shuffle[x] return x9 của NumPy hóa ra hiệu quả và hữu ích hơn nhiều cho các mục đích của chúng tôi. Theo mặc định,
def bogosort[x]: while np.any[x[:-1] > x[1:]]: np.random.shuffle[x] return x9 sử dụng thuật toán sắp xếp nhanh $\mathcal{O}[N\log N]$, mặc dù sáp nhập và sắp xếp theo khối cũng có sẵn. Đối với hầu hết các ứng dụng, quicksort mặc định là quá đủ
Để trả về một phiên bản đã sắp xếp của mảng mà không sửa đổi đầu vào, bạn có thể sử dụng
def bogosort[x]: while np.any[x[:-1] > x[1:]]: np.random.shuffle[x] return x9
Trong [5]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]3
Ra[5]
array[[1, 2, 3, 4, 5]]
Nếu bạn muốn sắp xếp mảng tại chỗ, thay vào đó, bạn có thể sử dụng phương pháp mảng
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]1
Trong [6]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]6
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]7
Một hàm liên quan là
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]7, thay vào đó trả về các chỉ số của các phần tử được sắp xếp
Trong [7]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]0
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]1
Phần tử đầu tiên của kết quả này đưa ra chỉ số của phần tử nhỏ nhất, giá trị thứ hai đưa ra chỉ số của phần tử nhỏ thứ hai, v.v. Các chỉ số này sau đó có thể được sử dụng [thông qua lập chỉ mục ưa thích] để xây dựng mảng được sắp xếp nếu muốn
Trong [8]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]2
Ra[8]
array[[1, 2, 3, 4, 5]]
Sắp xếp theo hàng hoặc cột¶
Một tính năng hữu ích của các thuật toán sắp xếp của NumPy là khả năng sắp xếp dọc theo các hàng hoặc cột cụ thể của một mảng nhiều chiều bằng cách sử dụng đối số
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]8. Ví dụ
Trong [9]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]4
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]5
Trong [10]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]6
Ra[10]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]7
Trong [11]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]8
Ra[11]
x = np.array[[2, 1, 4, 3, 5]] selection_sort[x]9
Hãy nhớ rằng điều này coi mỗi hàng hoặc cột là một mảng độc lập và mọi mối quan hệ giữa các giá trị của hàng hoặc cột sẽ bị mất
Sắp xếp một phần. Phân vùng¶
Đôi khi chúng ta không quan tâm đến việc sắp xếp cả mảng mà chỉ muốn tìm k giá trị nhỏ nhất trong mảng. NumPy cung cấp điều này trong hàm
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]9.
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]9 lấy một mảng và một số K;
Trong [12]
array[[1, 2, 3, 4, 5]]0
Ra[12]
array[[1, 2, 3, 4, 5]]1
Lưu ý rằng ba giá trị đầu tiên trong mảng kết quả là ba giá trị nhỏ nhất trong mảng và các vị trí mảng còn lại chứa các giá trị còn lại. Trong hai phân vùng, các phần tử có thứ tự tùy ý
Tương tự như sắp xếp, chúng ta có thể phân vùng dọc theo một trục tùy ý của một mảng nhiều chiều
Trong [13]
array[[1, 2, 3, 4, 5]]2
Ra[13]
array[[1, 2, 3, 4, 5]]3
Kết quả là một mảng trong đó hai vị trí đầu tiên trong mỗi hàng chứa các giá trị nhỏ nhất từ hàng đó, với các giá trị còn lại lấp đầy các vị trí còn lại
Cuối cùng, giống như có một
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]0 tính toán các chỉ số của loại, có một
array[[1, 2, 3, 4, 5]]2 tính toán các chỉ số của phân vùng. Chúng ta sẽ thấy điều này hoạt động trong phần sau
Thí dụ. k-Láng giềng gần nhất¶
Hãy nhanh chóng xem cách chúng ta có thể sử dụng hàm
x = np.array[[2, 1, 4, 3, 5]] bogosort[x]7 này dọc theo nhiều trục để tìm các hàng xóm gần nhất của mỗi điểm trong một tập hợp. Chúng ta sẽ bắt đầu bằng cách tạo một tập hợp ngẫu nhiên gồm 10 điểm trên mặt phẳng hai chiều. Sử dụng quy ước chuẩn, chúng ta sẽ sắp xếp chúng trong một mảng $10\times 2$