Danh sách hoặc bộ nào nhanh hơn trong Python?

Danh sách Python là cấu trúc dữ liệu động đẹp mắt. Chúng là cấu trúc dữ liệu lựa chọn cho rất nhiều thứ, vì vậy điều quan trọng nhất là phải ý thức được tốc độ của từng thao tác. Điều này thường được gọi là Big O hoặc độ phức tạp thời gian của giải pháp

Có nhiều cách để tạo mảng trong python, hãy xem cách nào tốn ít thời gian nhất. Đây là thiết lập chúng tôi đã sử dụng

Danh sách hiểu là phương pháp đầu tiên để tạo mảng. Chúng đơn giản và dễ đọc khiến chúng dễ viết

listComp = [i for i in range[0, end]]

Nối là phương pháp tiếp theo. Tôi có xu hướng chuyển sang giải pháp này vì nó là một trong những giải pháp dễ sử dụng hơn. Nó tương tự như cách bạn thêm vào danh sách ở hầu hết các ngôn ngữ khác

append_list = []
for i in range[0,end]:
  append_list.append[i]

Phân bổ trước là phương pháp cuối cùng chúng tôi sẽ kiểm tra. Điều này chỉ hoạt động đối với các mảng có độ dài được xác định trước. Điều này liên quan đến việc tạo trước tất cả các đối tượng mảng và sau đó sửa đổi giá trị của chúng theo chỉ mục

preAllocate = [0] * end
for i in range[0, end]:
  preAllocate[i] = i

Kết quả. Mặc dù việc hiểu danh sách không phải lúc nào cũng có ý nghĩa nhất ở đây nhưng chúng là người chiến thắng rõ ràng. Tôi không khuyên bạn nên thử và đưa mọi vòng lặp for vào một sự hiểu biết. Điều hợp lý là khi bạn đang sử dụng các vòng lặp for đơn giản hoặc tạo các mảng đặc biệt lớn

Method:            Median Time:
listComprehension  0.5556 ms
preAllocate        1.1466 ms
append             1.3842 ms

Bài kiểm tra này tương tự như bài kiểm tra ở trên. Chúng tôi đã tạo hai danh sách với 50.000 số ngẫu nhiên trong khoảng từ 0 đến 50.000. Sau đó, chúng tôi so sánh hai danh sách để xem nếu

Nhân đôi cho vòng lặp. Cái này phải có độ phức tạp về thời gian là O[n²]. Đối với mỗi phần tử, chúng ta sẽ phải lặp lại một phần hoặc toàn bộ danh sách thứ hai

for i in list_a:
  for j in list_b:
    if i == j:
      break

Đang tìm. Độ phức tạp về thời gian của 'in' gây nhầm lẫn. Biết rằng vòng lặp for kép thực thi trong thời gian O[n²], sẽ hợp lý khi quyền truy cập 'vào' hoạt động theo cách tương tự. Điều này dường như không phải là trường hợp. Nó dường như hoạt động gần với thời gian O[n log n]. Nếu ai đó quen thuộc với việc triển khai 'in' trong CPython, hãy để lại nhận xét bên dưới và tôi sẽ đưa câu trả lời vào đây

for i in list_a:
  if i in list_b:
    continue

Đặt độ phức tạp của thời gian tìm kiếm hơi khác một chút. Việc triển khai set trong Python về cơ bản là của bảng băm để nó có quyền truy cập O[1]. Do đó, vì chúng tôi đang xem qua danh sách một lần và kiểm tra trong danh sách thứ hai là thao tác O[1] nên tìm kiếm theo tập hợp sẽ hoạt động trong thời gian O[n]

unique = set[list_b]
for i in list_a:
  if i in unique:
    continue

Kết quả. So sánh với các bộ là tuyệt vời. Đối với bất kỳ ai thắc mắc, vòng lặp for kép là vòng lặp mà tôi không bao giờ mong đợi sẽ hoạt động tốt. Điều làm tôi ngạc nhiên là thời gian sử dụng toán tử 'in' ít hơn bao nhiêu so với sử dụng toán tử double for

Method:       Median Time:   Big O: 
Set Syntax:   0.0046ms       O[n]
In Syntax:    3.4710ms       O[n log n]
Double For:   42.3418ms      O[n^2]

Đối với phần cuối cùng của chúng tôi, chúng tôi sẽ nói về sắp xếp danh sách trong python. Có nhiều thuật toán sắp xếp phổ biến chúng ta sẽ so sánh. Để xem danh sách đầy đủ hơn về các thuật toán sắp xếp, hãy xem StackAbuse để biết thêm

Khi nói về sắp xếp, chúng ta cần nhớ rằng có các thuật toán sắp xếp ổn định và không ổn định. Một thuật toán ổn định nếu nó bảo toàn thứ tự ban đầu của các phần tử bằng nhau. Đây là một ví dụ về lý do tại sao sự ổn định có thể quan trọng

Ví dụ ổn định

Giả sử chúng tôi có lỗi trong mã của mình và chúng tôi muốn xem điều gì đã xảy ra. Chúng tôi có thể truy cập tệp nhật ký và sắp xếp các yêu cầu của người dùng. Đây là tệp nhật ký mẫu của chúng tôi

Trong cách sắp xếp không ổn định, chúng tôi có thể kết thúc với thứ gì đó như thế này, trong đó các yêu cầu được sắp xếp bởi người dùng, nhưng vì nó không ổn định nên chúng tôi đã mất chuỗi sự kiện ban đầu. Chúng tôi có thể không bao giờ tìm thấy lỗi của mình vì chúng tôi sẽ không thể thấy rằng người dùng 10 đã gửi yêu cầu 2 đến máy chủ trước yêu cầu 1

# Unstable Sort Result
user10: { 'request_number': 1 }
user10: { 'request_number': 2 }
user11: { 'request_number': 1 }# Stable Sort Result
user10: { 'request_number': 2 }
user10: { 'request_number': 1 }
user11: { 'request_number': 1 }

Heapsort có độ phức tạp thời gian điển hình là O[n log n]. Tuy nhiên, đây không phải là thuật toán sắp xếp ổn định nên không đảm bảo rằng các mục sẽ theo thứ tự ban đầu. Thuật toán này hoạt động bằng cách đặt các mục trên cây nhị phân trong đó nút gốc là giá trị lớn nhất. Sau đó, nó sẽ giải cấu trúc cây đó để tạo thành mảng đã sắp xếp

Hợp nhất là một thuật toán chia để trị có độ phức tạp thời gian điển hình là O[n log n]. Thuật toán này tách danh sách thành hai nửa và các nửa đó thành hai nửa cho đến khi còn lại các phần tử riêng lẻ. Sau đó, các phần tử được ghép nối, sắp xếp và hợp nhất nhiều lần cho đến khi danh sách hoàn tất lần nữa. Thuật toán này ổn định nên thật tuyệt khi cần thiết

Quicksort là một thuật toán được sử dụng rất phổ biến vì nó dễ thực hiện và có độ phức tạp thời gian trung bình là O[n log n]. Vấn đề với điều này là mọi thứ đều dựa trên việc chọn một điểm xoay tốt đã ở đúng vị trí và sắp xếp xung quanh nó. Chọn một điểm trục kém có thể dẫn đến độ phức tạp thời gian O[n²]. Điều này gắn liền với thực tế là nó không ổn định nên tôi không khuyên dùng nó

Timsort là một loại mà bạn có thể chưa từng nghe nói đến. Kiểu sắp xếp này, được đặt tên theo người phát minh ra nó là Tim Peters, là sự kết hợp của tìm kiếm nhị phân, sắp xếp chèn và sắp xếp hợp nhất. Độ phức tạp thời gian trung bình của nó là O[n log n] tuy nhiên nó có thể đạt được điều này với tính nhất quán tốt hơn và có độ phức tạp trường hợp tốt nhất là O[n]. Ngoài ra, đây là một thuật toán ổn định giúp nó trở nên tuyệt vời khi sử dụng ở mọi nơi

Phần tốt nhất là sử dụng Timsort trong python chỉ mất một dòng. Đúng rồi. Đó là chức năng sắp xếp tích hợp

append_list = []
for i in range[0,end]:
  append_list.append[i]

Kết quả. Timsort vượt trội hơn tất cả những cái khác, đó là lý do tại sao nó là thuật toán sắp xếp cốt lõi cho python. Tiếp theo Mergesort và Quicksort là cổ và cổ. Cuối cùng, Heapsort đang kéo lên phía sau… tốt, ít nhất là phía sau của danh sách này. Có rất nhiều thuật toán sắp xếp tồi tệ hơn như sắp xếp ngẫu nhiên

append_list = []
for i in range[0,end]:
  append_list.append[i]

Đây là biểu đồ hiển thị Big O của tất cả các thuật toán sắp xếp này. Ngoài ra, chúng tôi có độ phức tạp không gian, đó là cần thêm bao nhiêu không gian để hoàn thành thuật toán

Đó là tất cả cho danh sách này. Bây giờ hãy tiếp tục và sử dụng những thứ này trong Python hàng ngày của bạn và làm theo để biết thêm các mẹo và thủ thuật

Được đặt nhanh hơn danh sách?

Danh sách hoặc bộ nào tốt hơn trong Python?

Bộ danh sách hoặc bộ dữ liệu nào nhanh hơn trong Python?

Việc lặp qua một tập hợp có nhanh hơn một danh sách không?