Thứ tự Python về độ lớn của số

Mọi lập trình viên mới bắt đầu đều yêu thích vòng lặp for vì tiện ích của chúng và mức độ dễ hiểu của chúng. Tương tự như vậy, mọi người đều thích mảng. Tuy nhiên, thường xuyên hơn không, chúng tôi bắt đầu sử dụng mảng cho mọi thứ mà không cần suy nghĩ kỹ. Chúng tôi tham gia các lớp học về cấu trúc dữ liệu nhưng khi thực hành những gì đã học, chúng tôi không đạt được. Mãi đến gần đây tôi mới thấy mình rơi vào cái bẫy này. Tôi đang làm việc với một nhiệm vụ lập trình để thử thách bản thân viết mã hiệu quả và nhanh chóng

Chúng ta có thể làm tốt hơn

Trong bài đăng này, chúng ta sẽ xem xét ngắn gọn về từ điển và bộ trong Python.
Chúng tôi sẽ (tái) khám phá sức mạnh của những cấu trúc dữ liệu này trong việc thực hiện các thao tác dữ liệu siêu nhanh trong mã của chúng tôi. Chúng ta sẽ tìm hiểu cách các bảng băm có thể dẫn đến những cải tiến lớn về hiệu suất thuật toán.

Nhưng trước tiên chúng ta cần ôn lại một số khái niệm.
Đã đến lúc quay lại vấn đề cơ bản.

Cấu trúc dữ liệu trong ngôn ngữ lập trình là sự triển khai của cấu trúc dữ liệu trừu tượng trong Khoa học máy tính. Từ điển và bộ Python về cơ bản là một bảng băm. Bảng băm là một triển khai của cấu trúc dữ liệu trừu tượng được gọi là mảng kết hợp, từ điển hoặc bản đồ. Nói một cách đơn giản, bảng băm là ánh xạ từ khóa sang giá trị. Đưa ra một khóa, cấu trúc dữ liệu có thể được truy vấn để lấy giá trị tương ứng

Một cách đơn giản để thực hiện điều này sẽ là một bảng địa chỉ trực tiếp hoặc một mảng.
Vì vậy, đối với khóa 1, chúng tôi sẽ lưu trữ giá trị ở vị trí chỉ mục 1 của mảng.

Có một vấn đề với cách tiếp cận này mặc dù. Nếu có nhiều khóa, kích thước của mảng sẽ rất lớn. Điều này sẽ khiến việc lưu trữ theo bộ nhớ trở nên bất khả thi

Một giải pháp cho vấn đề này là sử dụng hàm băm. Hàm băm chịu trách nhiệm ánh xạ khóa tới giá trị được lưu trữ trong bảng băm. Bạn truyền cho nó một khóa và nó tạo ra một giá trị gọi là giá trị băm. Giá trị băm xác định vị trí trong bảng băm để lưu trữ giá trị tương ứng với khóa. Nói cách khác nó là một chỉ số

Bây giờ, kích thước của bảng băm sẽ nhỏ hơn kích thước của bảng địa chỉ trực tiếp. Điều này có nghĩa là một bảng băm khả thi để triển khai theo bộ nhớ. Tuy nhiên, điều này cũng có nghĩa là hai khóa có thể ánh xạ tới cùng một giá trị.
Đây được gọi là xung đột hàm băm và xảy ra khi hàm băm đưa ra cùng một giá trị với hai khóa riêng biệt.

Để giải quyết vấn đề này, chúng ta có thể lưu trữ các giá trị trong danh sách được liên kết nếu hai khóa có cùng giá trị (xem hình trên). Bất kỳ xung đột nào sau đó sẽ chỉ khiến giá trị được thêm vào danh sách được liên kết. Điều này được gọi là giải quyết va chạm bằng cách xâu chuỗi

Bây giờ bạn có thể tưởng tượng nếu tất cả các khóa được băm thành cùng một giá trị thì tất cả chúng sẽ được thêm vào danh sách được liên kết, nghĩa là hiệu suất sẽ không tốt hơn so với sử dụng danh sách

Các bảng băm được thay đổi kích thước nếu chúng quá đầy. Ngưỡng được gọi là hệ số tải và xác định tỷ lệ của các vị trí được sử dụng so với các vị trí có sẵn. Thông thường khi giá trị vượt quá 3/4, bảng băm sẽ được thay đổi kích thước. Điều này đảm bảo rằng các danh sách được liên kết không bao giờ quá đầy và đảm bảo hiệu suất trường hợp trung bình đã hứa. Cuối cùng, các hàm băm thường được chọn theo cách mà chúng phân phối các khóa đồng đều trên các vị trí. Điều này có nghĩa là khả năng xảy ra va chạm là rất nhỏ ngay từ đầu

Tuyệt quá. Bây giờ hãy xem một số ký hiệu O lớn

Việc tìm kiếm các phần tử trong một mảng có độ phức tạp về thời gian trường hợp trung bình là O(n) vì chúng ta cần duyệt qua danh sách một cách tuyến tính để tìm phần tử.
Kích thước danh sách càng lớn thì thời gian tìm kiếm phần tử càng lâu. Bạn có thể hình dung đây là một hàng người đang đứng và bạn bắt đầu từ người ngoài cùng bên trái và hỏi xem anh ta có phải là người bạn đang tìm không.
Nếu không thì bạn hỏi người bên cạnh, v.v. Bạn có thể tưởng tượng sẽ mất nhiều thời gian hơn để tìm người đó nếu có 1000 người so với 10 người.

Tuy nhiên, đối với bảng băm, độ phức tạp thời gian trường hợp trung bình cho một tìm kiếm là O(1) - nó không đổi. Bất kể kích thước của số lượng phần tử bạn lưu trữ là một triệu hay 10, sẽ luôn mất một đơn vị thời gian không đổi để tìm một phần tử. Nói cách khác, nó sẽ nhanh cho mọi kích cỡ đầu vào.
Bạn có thể tưởng tượng một nhóm người đang đứng và thêm một người trợ giúp cho bạn. Để tìm người bạn chỉ cần hỏi người trợ giúp thay vì tìm kiếm trong nhóm. Người trợ giúp cho bạn biết ngay lập tức người bạn quan tâm đang ở đâu.

Chèn và xóa các phần tử cũng là O(1)

Bấm vào đây để xem bảng cheat thực sự hay về cấu trúc dữ liệu và chữ O lớn

Được rồi, đã đến lúc viết mã và xem các bảng băm hoạt động

Chúng ta sẽ mô phỏng nhiệm vụ sau

• Một danh sách L chứa các phần tử từ 0 đến 100.000 theo thứ tự đã sắp xếp. Chỉ mục cuối cùng thứ ba có giá trị âm được tạo ngẫu nhiên trong phạm vi từ 0 đến 100.000
• Một danh sách R chứa các phần tử từ 0 đến 100.000 theo thứ tự được sắp xếp

Nhiệm vụ rất đơn giản. Chúng ta cần tìm giá trị trong L không xuất hiện trong R

Tôi biết có nhiều cách đơn giản hơn để giải quyết vấn đề này nhưng vì mục đích học tập, chúng tôi sẽ thử một cách tiếp cận phức tạp hơn

Hàm solution là một triển khai đơn giản của một giải pháp. Chúng tôi lặp lại trên L và đối với từng phần tử, hãy kiểm tra xem nó có tồn tại trong danh sách R không. Toán tử O(n)1 kiểm tra tư cách thành viên và giống như thực hiện thao tác tìm kiếm.
Nếu nó tồn tại, chúng ta chỉ cần trả về số nguyên âm.

Thời gian trôi qua cho giải pháp này là khoảng 60 giây

Nếu chúng ta phân tích mã cho hàm solution, chúng ta sẽ thấy rằng độ phức tạp về thời gian là O(n^2).
Điều này là do đối với mỗi phần tử trong L, chúng tôi đang duyệt qua R và kiểm tra tư cách thành viên. Vòng lặp for mất O(n) khi nó chạy trong n bước. Đối với mỗi bước, chúng tôi thực hiện các thao tác O(n) vì chúng tôi cần kiểm tra mọi phần tử trong danh sách R và xem liệu đó có phải là phần tử chúng tôi đang tìm kiếm không.
Điều này mang lại O(n)*O(n)=O(n^2)

Các hoạt động chạy trong thời gian bậc hai. Thời gian cần thiết sẽ tương đương với bình phương kích thước đầu vào. Bạn có thể tưởng tượng cách lấy bình phương của các số lớn hơn và lớn hơn sẽ mang lại các giá trị lớn hơn không ngừng

Chúng ta có thể làm gì để cải thiện điều này?

Thay vì duyệt R để kiểm tra tư cách thành viên, chúng ta có thể triển khai R dưới dạng bảng băm thay vì mảng. Do đó, độ phức tạp về thời gian để kiểm tra tư cách thành viên sẽ là O(1).
Kết quả là thao tác sẽ mất O(n)*O(1)=O(n).

Đây là tuyến tính trong kích thước của đầu vào. Vì vậy, thời gian cần thiết sẽ tỷ lệ thuận với kích thước đầu vào (trái ngược với bậc hai)

Đợi cho đến khi bạn thấy những cải tiến về hiệu suất

Thời gian O(n)3 cho thời gian trôi qua là 0. 011s. Đây là một cải tiến hơn 5000 lần

Tóm lại, bạn đã học được động lực đằng sau việc sử dụng hàm băm và bảng băm. Chúng tôi đã xem xét ngắn gọn ký hiệu O lớn cho bảng băm và so sánh nó với ký hiệu của mảng. Trên hết, chúng tôi đã xem xét một triển khai sử dụng bảng băm để giải quyết vấn đề thuật toán trong thời gian kỷ lục

Là kỹ sư phần mềm, chúng ta phải biết sử dụng đúng công cụ cho đúng tình huống và không cố gắng áp dụng các kỹ thuật vũ phu trong mọi tình huống mà chúng ta gặp phải

Với ý nghĩ đó, có một vài điểm cần nhớ

Giống như tất cả mọi thứ, bảng băm không phải là viên đạn bạc. Chúng sẽ không phù hợp với mọi trường hợp sử dụng. Chẳng hạn, các phần tử trùng lặp không thể được lưu trữ trong bảng băm. Vì vậy, nếu trường hợp sử dụng của bạn yêu cầu điều đó, tốt hơn hết bạn nên sử dụng một mảng. Tương tự, bảng băm không được sắp xếp. Nếu trường hợp sử dụng của bạn yêu cầu cấu trúc dữ liệu được sắp xếp, bảng băm không phải là câu trả lời. Cuối cùng, không có chức năng tích hợp để tìm các phần tử tối đa hoặc tối thiểu trong bảng băm. Cuối cùng, độ phức tạp thời gian được đề cập ở trên là trường hợp trung bình. Có thể có những tình huống xảy ra trường hợp xấu nhất có nghĩa là bảng băm sẽ hoạt động giống như mảng