2014-10-25 35 views
5

Tôi có trường hợp đặc biệt của vấn đề, nhưng nó sẽ là tốt đẹp để biết liệu có thể cho bất kỳ chức năng nào không.Làm thế nào để tìm thấy sự phức tạp của hàm dựng sẵn trong python

Vì vậy, tôi muốn tìm vị trí của chuỗi con trong chuỗi. Ok, trong python có một find method làm chính xác những gì là cần thiết.

string.find (s, phụ [, bắt đầu [, kết thúc]])

Return chỉ số thấp nhất trong là nơi các chuỗi phụ được tìm thấy như vậy mà phụ được hoàn toàn chứa trong s [bắt đầu: kết thúc]. Trả về -1 khi thất bại. Mặc định cho bắt đầu và kết thúc và giải thích các giá trị âm cũng giống như đối với các lát cắt.

tuyệt vời, nhưng vấn đề là tìm một chuỗi con lớn trong một chuỗi lớn có thể chạy từ O(n*m) để O(n) (đó là một việc rất lớn) depending on the algorithm. Tài liệu không cung cấp thông tin về độ phức tạp thời gian, cũng như thông tin về thuật toán cơ bản.

tôi thấy vài phương pháp làm thế nào để giải quyết này:

  • benchmark
  • đi vào mã nguồn và cố gắng hiểu nó

Cả hai âm thanh không thực sự dễ dàng (Tôi hy vọng rằng có một cách dễ dàng hơn). Vậy làm thế nào tôi có thể tìm thấy một sự phức tạp của một chức năng tích hợp?

+0

Bạn có thể xem mô-đun [big_o] (https://github.com/pberkes/big_O). –

+0

@AlexThornton cảm ơn Alex, nhưng điều này về cơ bản rơi vào danh mục 'điểm chuẩn' của tôi. Không chỉ mất nhiều thời gian để ước tính nó, đôi khi rất khó để có được nó (đối với một số thuật toán xác suất hoặc nhận được các trường hợp cạnh). Nghe có vẻ kỳ lạ là thông tin này không có sẵn trong tài liệu. –

+0

Thật kỳ lạ. Có một phần 'TimeComplexity' trên wiki mà nó cho bạn biết một vài, nhưng không phải cho các phương thức như 'string.find()'. –

Trả lời

3

Bạn nói, "đi đến mã nguồn và cố gắng hiểu nó", nhưng nó có thể dễ dàng hơn bạn nghĩ. Một khi bạn nhận được để mã thực hiện thực tế, trong Objects/stringlib/fastsearch.h, bạn thấy:

/* fast search/count implementation, based on a mix between boyer- 
    moore and horspool, with a few more bells and whistles on the top. 
    for some more background, see: http://effbot.org/zone/stringlib.htm */ 

Các URL referenced there có một cuộc thảo luận tốt của thuật toán và tính phức tạp của nó.

+1

có vẻ đủ tốt. Tôi chỉ nghĩ, điểm không bao gồm thông tin này trong tài liệu là gì? –

+0

Đây sẽ là thông tin tốt để đưa vào tài liệu, bạn nói đúng. Bạn có thể thử gửi một lỗi về nó tại http://bugs.python.org/ Một vấn đề là stdlib có thể được thực hiện khác nhau bởi các triển khai Python khác nhau và chúng có thể không muốn đưa ra lời hứa về sự phức tạp cho một hàm như thế này . –

Các vấn đề liên quan