Tất cả các cuốn sách tôi đã đọc trên cấu trúc dữ liệu cho đến nay dường như sử dụng C/C++, và sử dụng nhiều kiểm soát con trỏ "thủ công" mà chúng cung cấp. Vì Python ẩn kiểu quản lý bộ nhớ và thu gom rác từ người dùng này nên thậm chí có thể thực hiện các cấu trúc dữ liệu hiệu quả trong ngôn ngữ này, và có lý do nào để thực hiện thay vì sử dụng các trình dựng sẵn không?Cấu trúc dữ liệu trong Python
Python cung cấp cho bạn một số cấu trúc dữ liệu được tối ưu hóa mạnh mẽ , cả hai đều được tích hợp sẵn và như một phần của một vài mô-đun trong thư viện chuẩn (list s và dict s, tất nhiên, nhưng cũng là tuple s, set s, array s trong mô-đun array và một số vùng chứa khác trong mô-đun collections).
Kết hợp các cấu trúc dữ liệu này (và có thể một số chức năng từ mô-đun trợ giúp như heapq và bisect) thường đủ để thực hiện hầu hết các cấu trúc phong phú hơn có thể cần trong lập trình thực tế; tuy nhiên, đó không phải lúc nào cũng vậy.
Khi bạn cần thứ gì đó hơn thư viện phong phú cung cấp, hãy xem xét thực tế rằng thuộc tính của đối tượng (và các mục trong bộ sưu tập) về cơ bản là "con trỏ" tới các đối tượng khác (không có số học con trỏ), nghĩa là "tham chiếu có thể lặp lại" Python giống như trong Java.Trong Python, bạn thường sử dụng giá trị None trong một thuộc tính hoặc mục để đại diện cho những gì NULL có nghĩa là trong C++ hoặc null có nghĩa là trong Java.
Vì vậy, ví dụ, bạn có thể thực hiện cây nhị phân qua, ví dụ:
class Node(object):
__slots__ = 'payload', 'left', 'right'
def __init__(self, payload=None, left=None, right=None):
self.payload = payload
self.left = left
self.right = right
cộng phương pháp hoặc các chức năng cho traversal và các hoạt động tương tự (thuộc tính __slots__ lớp là không bắt buộc - chủ yếu là một tối ưu hóa bộ nhớ, để tránh mỗi trường hợp Node có __dict__ riêng, số lượng này sẽ lớn hơn đáng kể so với ba thuộc tính/tham chiếu cần thiết).
ví dụ khác về cấu trúc dữ liệu phù hợp nhất có thể được đại diện bởi các lớp học Python dành riêng, chứ không phải bởi thành phần trực tiếp của các cấu trúc Python khác hiện có, bao gồm tries (xem ví dụ here) và graphs (xem ví dụ here).
Đối với một số cấu trúc dữ liệu đơn giản (ví dụ: ngăn xếp), bạn chỉ có thể sử dụng danh sách dựng sẵn để hoàn thành công việc của mình. Với các cấu trúc phức tạp hơn (ví dụ: một bộ lọc nở hoa), bạn sẽ phải tự thực hiện chúng bằng cách sử dụng các nguyên thủy mà ngôn ngữ hỗ trợ.
Bạn nên sử dụng nội trang nếu chúng phục vụ mục đích của bạn thực sự vì chúng được gỡ lỗi và tối ưu hóa bởi một đám người trong một thời gian dài. Làm nó từ đầu bằng chính mình có lẽ sẽ tạo ra một cấu trúc dữ liệu kém hơn.
Nếu tuy nhiên, bạn cần thứ gì đó không có sẵn như nguyên thủy hoặc nếu nguyên thủy không hoạt động đủ tốt, bạn sẽ phải triển khai loại của riêng mình.
Các chi tiết như quản lý con trỏ, v.v ... chỉ là nói chuyện thực hiện và không thực sự giới hạn khả năng của chính ngôn ngữ đó.
Sách cấu trúc dữ liệu C/C++ chỉ cố gắng dạy cho bạn các nguyên tắc cơ bản đằng sau các cấu trúc khác nhau - chúng thường không khuyên bạn thực sự đi ra ngoài và phát minh lại bánh xe bằng cách xây dựng thư viện ngăn xếp và danh sách của riêng bạn.
Cho dù bạn đang sử dụng Python, C++, C#, Java, bất cứ điều gì, bạn nên luôn luôn tìm đến cấu trúc dữ liệu được tích hợp trước. Họ thường sẽ được thực hiện bằng cách sử dụng cùng một hệ thống nguyên thủy bạn sẽ phải sử dụng làm nó cho mình, nhưng với lợi thế của việc đã được thử và thử nghiệm.
Chỉ khi cấu trúc dữ liệu được cung cấp không cho phép bạn thực hiện những gì bạn cần và không có thư viện thay thế và đáng tin cậy cho bạn, bạn nên xem xét xây dựng thứ gì đó từ đầu (hoặc mở rộng những gì được cung cấp).
Cách Python xử lý các đối tượng ở mức thấp không quá kỳ lạ. This document nên phân biệt nó một chút; về cơ bản là tất cả logic con trỏ mà bạn đã quen thuộc.
Không thể triển khai một cái gì đó giống như một vector C++ trong Python, vì bạn không có mảng nguyên thủy theo cách C/C++ làm. Tuy nhiên, bất cứ điều gì phức tạp hơn có thể được thực hiện (hiệu quả) trên đầu trang của nó, bao gồm, nhưng không giới hạn: danh sách liên kết, bảng băm, multisets, bộ lọc hoa, v.v.
Tôi không quen với việc thực hiện vector C++ nhưng kiểu danh sách Python * được * thực hiện như một mảng (http://bytes.com/topic/python/answers/101848-list-implementation) chứ không phải là một liên kết danh sách. Đó không phải là một vector cơ bản là gì sao? –
Có, một Python được thực hiện như một mảng (giống như một vector C++). Những gì tôi nói là bạn không thể thực hiện danh sách của riêng bạn * trong * Python, ngoại trừ trên đầu trang của một hiện tại. –
Vâng, kiểu danh sách python thực sự giống ArrayList của Java hơn (ví dụ: một mảng con trỏ tới đối tượng). –
Với Python, bạn có quyền truy cập vào một loạt các mô-đun thư viện được viết và sửa lỗi bởi những người khác. Tỷ lệ cược là rất tốt mà một nơi nào đó ra khỏi đó, có một mô-đun mà ít nhất một phần của những gì bạn muốn, và tỷ lệ cược thậm chí tốt mà nó có thể được thực hiện trong C cho hiệu suất.
Ví dụ, nếu bạn cần phải làm ma trận toán học, bạn có thể sử dụng NumPy, được viết bằng C và Fortran.
Python là đủ chậm rằng bạn sẽ không được hạnh phúc nếu bạn cố gắng viết một số loại mã thực sự tính toán chuyên sâu (Ví dụ, một Fast Fourier Transform) bằng Python bản xứ. Mặt khác, bạn có thể nhận được một Fourier Transform C mã hóa như là một phần của SciPy, và chỉ sử dụng nó.
Tôi chưa bao giờ có một tình huống mà tôi muốn giải quyết vấn đề bằng Python và nói "darn, tôi chỉ không thể diễn tả cấu trúc dữ liệu tôi cần."
Nếu bạn là người tiên phong, và bạn đang làm điều gì đó bằng Python mà không có bất kỳ mô-đun thư viện nào ở đó, bạn có thể thử viết bằng Python thuần túy. Nếu nó đủ nhanh, bạn đã xong. Nếu nó quá chậm, bạn có thể cấu hình nó, tìm ra nơi các phần chậm và viết lại chúng trong C bằng cách sử dụng Python C API. Tôi chưa bao giờ cần phải làm điều này.
Hầu hết các cấu trúc C/C++ "nặng [ily] sử dụng con trỏ thủ công" vì chúng phải, thay vì vì nó hiệu quả hơn để làm như vậy. – notnoop