cách efficent nhất của việc tìm kiếm các phao tối thiểu trong một danh sách python

Question

Nhanh câu hỏi, đó là hiệu quả hơn cho việc tìm kiếm số nhỏ nhất (float) trong một danh sách dài (Trên 10000 phần tử)

là nó

min(mylist) 

hoặc

mylist.sort() 

và sau đó trở

mylist[0] 

hoặc cái gì khác ...

cảm ơn!

Answer 1

Nếu danh sách đã được điền, min() là cách hiệu quả nhất.

Có một số thủ thuật bạn có thể sử dụng trong các tình huống đặc biệt:

• Nếu bạn xây dựng danh sách từ đầu, bạn chỉ cần giữ cho mục nhỏ nhất được nêu ra trong một biến bên ngoài, do đó câu trả lời sẽ được đưa ra trong O(1).
• Nếu chỉ có phao trong danh sách, hãy sử dụng Array mang lại hiệu suất tốt hơn.
• Bạn có thể giữ danh sách được sắp xếp bằng cách sử dụng bisect.
• Sử dụng Python Heap, thậm chí có hiệu quả thực hiện min(). Hãy chắc chắn rằng bạn hiểu các hiệu ứng, chủ yếu là một chèn chậm hơn. (credit: interjay)

Answer 2

Vâng, bạn chắc chắn phải lặp qua toàn bộ danh sách, vì vậy thời gian chạy của bạn phải là O (n).

Như sắp xếp đã mất thời gian O (n log n), điều này rõ ràng không phải là cách tốt nhất để làm điều này. Tôi không biết việc thực hiện min(), nhưng nó phải là cách đúng để làm điều này.

Answer 3

Frst, nếu bạn quan tâm về hiệu suất trong Python (mà không phải lúc nào cũng là một điều hợp lý để quan tâm, nhưng đó là chuyện khác), bạn nên sử dụng các timeit module. Ngay cả trong C thật khó để dự đoán một số chức năng sẽ hoạt động như thế nào sau khi biên dịch, và khó hơn trong Python. Mọi người thường tự tin thể hiện ý kiến ​​về những chức năng nào nhanh hơn phụ thuộc vào dữ liệu. Sau đó - bằng cách sử dụng timeit, ý tôi là - bạn có thể tự mình phát hiện ra.

Thứ hai, nếu bạn thực sự quan tâm đến hiệu suất trên danh sách phao, bạn không nên sử dụng danh sách nào cả, nhưng mảng có nhiều mảng. Sử dụng IPython tại đây, theo Python 2.7.2, giúp việc định thời dễ dàng:

In [41]: import random, numpy 
In [42]: a = [0.1*i for i in range(10**5)] 
In [43]: timeit min(a) 
100 loops, best of 3: 4.55 ms per loop 
In [44]: timeit sorted(a)[0] 
100 loops, best of 3: 4.57 ms per loop 
In [45]: random.shuffle(a) 
In [46]: timeit min(a) 
100 loops, best of 3: 6.06 ms per loop 
In [47]: timeit min(a) # to make sure it wasn't a fluke 
100 loops, best of 3: 6.07 ms per loop 
In [48]: timeit sorted(a)[0] 
10 loops, best of 3: 65.9 ms per loop 
In [49]: b = numpy.array(a) 
In [50]: timeit b.min() 
10000 loops, best of 3: 97.5 us per loop 

Và chúng tôi lưu ý một vài điều. (1) Sắp xếp của Python (timsort) hoạt động rất tốt trên dữ liệu đã sắp xếp chạy, do đó việc sắp xếp danh sách đã sắp xếp gần như không bị phạt. (2) Việc sắp xếp một danh sách ngẫu nhiên, mặt khác, chậm hơn rất nhiều, và điều này sẽ chỉ trở nên tệ hơn khi dữ liệu lớn hơn. (3) Numpy.min() trên một mảng float hoạt động nhanh hơn sáu mươi lần so với min trong danh sách Python, vì nó không phải là chung.