Hướng dẫn data structure implementation in python - triển khai cấu trúc dữ liệu trong python

Cộng đồng

Hướng dẫn chuyên sâu về cấu trúc dữ liệu trong Python

Khám phá sáu cấu trúc dữ liệu cơ bản và việc triển khai của chúng trong Python.

Pythonistas rất thành thạo về sự phức tạp của các loại dữ liệu Python, được trang bị các phương pháp tích hợp ngoài hộp để lưu trữ, thao tác và định hình lại dữ liệu theo nhịp điệu của các nét bàn phím.

Nhưng không có nhiều nhà khoa học dữ liệu và kỹ sư dữ liệu mở khóa hoàn toàn tiềm năng của các cấu trúc dữ liệu trong Python - tiềm năng viết mã dễ dàng hơn để duy trì, hiệu quả hơn theo các đơn đặt hàng và giải quyết các vấn đề một cách thanh lịch hơn.

Trong bài viết này, chúng tôi có một cái nhìn sâu sắc về các cấu trúc dữ liệu trong Python thông qua nhiều chủ đề.

Ngừng làm việc trên cơ sở hạ tầng dữ liệu của bạn và bắt đầu sử dụng nó thay thế. Tạo một tài khoản miễn phí mãi mãi và thanh toán khi bạn phát triển!

1. Cấu trúc dữ liệu (trong Python) là gì?

Cấu trúc dữ liệu nằm ở giao điểm giữa khoa học máy tính và khoa học dữ liệu. Họ chiếm một thế giới ở giữa mã máy hiệu suất cao một mặt và mặt khác dễ hiểu.

Các cấu trúc dữ liệu mô tả cách tổ chức dữ liệu để nó giải quyết một vấn đề tính toán trong khi tạo ra độ phức tạp lưu trữ (không gian) và độ phức tạp thời gian của nó càng được tối ưu hóa càng tốt.

Chúng tôi đã chạm vào một số cấu trúc dữ liệu trước đây - bạn có thể nhớ từ điển trong Python, điều này có hiệu suất cao (O (1) độ phức tạp thời gian trong việc truy xuất các giá trị được lưu trữ trong từ điển khi được cung cấp khóa). & NBSP;

Tuy nhiên, hiện tại, chúng tôi sẽ đi sâu hơn vào các cấu trúc dữ liệu cơ bản và cổ điển:

1. Cây rơm
2. Xếp hàng
3. Bản đồ
4. Mảng
5. Đồ thị
6. Bộ
   

Đối với mỗi kiểu dữ liệu, chúng tôi sẽ làm ba điều:

1. Giải thích cách nó hoạt động.
2. Hiển thị tầm quan trọng và ứng dụng của nó.
3. Cung cấp các ví dụ mã để thực hiện nó trong ngôn ngữ lập trình Python.
   

Trước khi chúng tôi làm điều đó, trước tiên chúng tôi cần phải làm rõ một ranh giới âm u. Làm thế nào, nếu có, các cấu trúc dữ liệu có khác với các loại dữ liệu trong Python không?

1.1 Cấu trúc dữ liệu Python khác với các loại dữ liệu như thế nào?

Trong các ngôn ngữ lập trình được yêu thích theo truyền thống như Java và C ++, các ngôn ngữ tạo ra sự khác biệt mạnh mẽ giữa các loại dữ liệu trừu tượng (ADT) và cấu trúc dữ liệu. & NBSP;

Trong những ngôn ngữ được loại mạnh mẽ đó, ADT là một sự trừu tượng, giúp chúng ta tự mình viết mã máy tính. ADT cung cấp các nhóm hoạt động mà bạn có thể thực hiện qua kiểu dữ liệu. Tương đương Python sẽ là các phương thức lớp so với các loại dữ liệu, chẳng hạn như vòng (float) hoặc str.upper () hoặc dict.keys ().

Mặt khác, các cấu trúc dữ liệu là việc triển khai các ADT đó. Để giữ cho mọi thứ hoạt động, các ngôn ngữ được đánh giá mạnh mẽ được xây dựng dựa trên các cấu trúc dữ liệu đã thử và cung cấp các phương pháp tốt nhất có thể để giải quyết các vấn đề tính toán. Một ví dụ về điều đó sẽ là lớp Dict () trong Python, cực kỳ hiệu quả trong các hoạt động đọc cho các cặp giá trị khóa được đặt tên.

Nhưng Python khác với các ngôn ngữ đó vì nó không phân biệt nghiêm ngặt giữa ADT và cấu trúc dữ liệu. Trên thực tế, mọi thứ là một đối tượng trong Python và do đó được thừa hưởng từ lớp mà nó rơi xuống. Đây là lý do tại sao số 1 được coi là đúng trong logic boolean - giá trị boolean là hậu duệ lớp của lớp số nguyên.

Vì vậy, tại sao phân biệt giữa các loại dữ liệu và cấu trúc dữ liệu trong Python?

Lý do chính là hiệu suất - Hiểu cách thực hiện cấu trúc dữ liệu có thể cải thiện hiệu suất đáng kể. Nhưng có những lợi ích khác để giải quyết các vấn đề với cấu trúc dữ liệu trong Python ...

2. Những lợi ích của việc sử dụng cấu trúc dữ liệu trong Python là gì?

Có nhiều lợi thế khi sử dụng cấu trúc dữ liệu:

1. Màn biểu diễn. Việc chọn cấu trúc dữ liệu phù hợp làm cho mã của bạn chạy hiệu quả hơn (AKA mất ít thời gian hơn hoặc ít không gian hơn hoặc cả hai).. Choosing the right data structure makes your code run more efficiently (aka takes less time, or less space, or both).
2. Đơn giản và khả năng bảo trì. Cấu trúc dữ liệu cung cấp logic xương sống hoặc chính cho một giải pháp thuật toán, giúp mã dễ dàng hơn để duy trì và sửa đổi.. Data structures provide the backbone or main logic for an algorithmic solution, which makes the code easier to maintain and modify.
3. Cơ quan. Đặt logic của bạn ở cấp độ của cấu trúc dữ liệu có nghĩa là cơ sở mã của bạn được tổ chức nhiều hơn thay vì có các tệp chức năng trợ giúp dài và logic phân tán.. Putting your logic on the level of a data structure means that your codebase is more organized instead of having lengthy helper function files and dispersed logic.
4. Sự hợp tác. Sử dụng cả ngôn ngữ phù hợp và việc triển khai chính xác giúp cộng tác dễ dàng hơn trong các dự án trải rộng trên nhiều giai đoạn của đường ống ETL, đặc biệt là khi làm việc với các đồng nghiệp được đào tạo bài bản về khoa học máy tính nhiều hơn.. Using both the right language and the correct implementation makes it easier to collaborate on projects which span multiple stages of the ETL pipeline, especially when working with coworkers who are more classically trained in computer science.
   

Hãy để kiểm tra cách các lợi ích này xuất phát từ việc triển khai cấu trúc dữ liệu thực tế.

3. Mảng

3.1 Mảng là gì?

Một mảng là một cấu trúc dữ liệu nhỏ gọn lưu trữ tuần tự các loại dữ liệu cơ bản (số nguyên, phao, v.v.) thông tin bằng cách phân bổ các vị trí bộ nhớ tuần tự. Đó là cách đơn giản nhất để lưu trữ thông tin trên máy tính. & NBSP;

Về mặt kỹ thuật, một mảng chỉ định rằng tất cả các phần tử mảng phải thuộc cùng một loại dữ liệu.

Các mục trong một mảng có thể được truy cập ngay lập tức (o (1) thời gian). & Nbsp;

3.2 Mảng được sử dụng như thế nào?

Các mảng thường được sử dụng trong các tác vụ tính toán số hoặc như một cấu trúc dữ liệu hỗ trợ để thực hiện các cấu trúc dữ liệu khác (ví dụ: ngăn xếp, danh sách và hàng đợi). Khi nói về các hoạt động số, các mảng là triển khai đại số tuyến tính cho phép các hoạt động vectơ và ma trận hoặc các khối xây dựng của nhiều thuật toán học máy.

3.3 Cách thực hiện cấu trúc dữ liệu mảng trong Python

Python có việc triển khai số các mảng trong mô -đun mảng. Nó cho phép người dùng chỉ định loại dữ liệu Python (hoặc C) mà mảng giữ khi bắt đầu. Nó có thể giữ các phần tử của các ký tự nổi, số nguyên hoặc các ký tự Unicode (16 hoặc 32 bit, tùy thuộc vào nền tảng).

Mảng Python cũng đi kèm với nhiều phương pháp được xây dựng. Chúng bao gồm phụ lục (mục) để thêm các mục vào cuối mảng, đếm (mục) để đếm số lần xuất hiện của một mục trong mảng, chèn (chỉ mục, mục) để chèn một mục tại chỉ mục vị trí, xóa (mục mục (mục ) để xóa mục, và nhiều hơn nữa.append(item) for adding items to the end of the array, count(item) for counting the number of occurrences of an item within the array, insert(index, item) to insert an item at position index, remove(item) for item deletion, and more.

Có nhiều triển khai chuyên dụng khác của các mảng trong Python, chẳng hạn như các đối tượng byte (trình tự bất động của các byte đơn), các đối tượng bytearray (mảng có thể thay đổi của các byte đơn), các đối tượng STR (mảng bất biến của các ký tự unicode được khai báo là trích dẫn đơn, hoặc trích dẫn gấp đôi hoặc trích dẫn gấp đôi hoặc trích dẫn gấp đôi hoặc trích dẫn hoặc Báo giá ba) và các đối tượng tuple (kiểm tra bài viết của chúng tôi về chuỗi bất biến này).

Khi nói đến các mảng, Python thực hiện cấu trúc dữ liệu này như là một phần của thư viện tiêu chuẩn của nó, nhưng bạn nên sử dụng thư viện Numpy thay thế. Nó được tối ưu hóa cho điện toán khoa học và vectơ.

4. Stack (Lifo)

4.1 Một ngăn xếp là gì?

Một ngăn xếp là một thùng chứa các đối tượng trong đó việc chèn vật phẩm và xóa vật phẩm được thực hiện theo nguyên tắc LIFO. LIFO là viết tắt của ‘Last in First Out, và nó biểu thị mức độ ưu tiên của các mục khi chèn và loại bỏ.

Bạn có thể nghĩ về một ngăn xếp như một đống tấm. Sẽ là không thực tế khi nhặt tấm dưới cùng, vì vậy thông thường, chúng tôi đã đi cho cái trên đầu (cái cuối cùng được thêm vào ngăn xếp). & NBSP;

Ngăn xếp cần thực hiện ít nhất hai hoạt động:

1. Đẩy (Mục): Thêm mục vào đầu ngăn xếp.
2. pop (): Xóa mục được thêm vào cuối cùng khỏi ngăn xếp.
   

Tất nhiên, cấu trúc dữ liệu ngăn xếp có thể bao gồm các yếu tố khác, chẳng hạn như hàm trả về số lượng phần tử trong ngăn xếp hoặc một hàm kiểm tra xem ngăn xếp có trống không.

4.2 Ngăn xếp được sử dụng như thế nào?

Ngăn xếp có nhiều cách sử dụng trong thế giới của máy tính:

1. Các thuật toán tìm kiếm đầu tiên (DFS) dựa trên cấu trúc dữ liệu ngăn xếp và các thuật toán đó được sử dụng trên nhiều thuật toán quản lý bộ nhớ phân tích cú pháp và thời gian chạy.
2. Ngăn xếp được sử dụng để lập lịch trình và thuật toán.
3. Ở cấp độ cao hơn, ngăn xếp có thể được sử dụng như một phần của các ứng dụng. Ví dụ: nút UNDO UNDO trong một trình soạn thảo văn bản kiểm tra lệnh chèn cuối cùng, hoàn nguyên nó và bật nó ra khỏi ngăn xếp.
   

4.3 Cách thực hiện cấu trúc dữ liệu ngăn xếp trong Python

Cách dễ nhất để thực hiện một ngăn xếp trong Python là sử dụng danh sách. Danh sách cho phép bạn thêm các mục mới vào ngăn xếp hiện có bằng phương thức append () và xóa phần tử cuối cùng được thêm bằng phương thức pop (). & Nbsp;

Nếu bạn cần bồi dưỡng về cách bắt đầu danh sách (SPOILER ALERT: Khung vuông đủ) và các phương pháp làm việc khác với danh sách, hãy đọc bài viết của chúng tôi về các loại dữ liệu tích hợp.

Chạy một doanh nghiệp dựa trên dữ liệu 100% mà không gặp rắc rối thêm. Trả tiền khi bạn đi, bắt đầu với tầng miễn phí của chúng tôi.

5. Hàng đợi (FIFO)

5.1 Hàng đợi là gì?

Hàng đợi cũng là bộ sưu tập các mặt hàng chứa các yếu tố, nhưng bạn có thể nói rằng chúng trái ngược với các ngăn xếp. Hàng đợi thu thập các yếu tố theo khái niệm FIFO - ‘Đầu tiên trong lần đầu tiên ra ngoài - vì vậy phần tử đầu tiên được thêm vào hàng đợi là phần đầu tiên bị xóa.

Hàng đợi cần thực hiện ít nhất hai hoạt động:

1. Enqueue (mục): Thêm mục vào mặt sau của hàng đợi.
2. Dequeue (): Tháo các mục ở phía trước hàng đợi.
   

Bạn có thể nghĩ về một hàng đợi như một dòng người chờ đợi trước một chiếc xe tải thực phẩm. Người đầu tiên trong hàng đợi là người đầu tiên được phục vụ.

5.2 Một hàng đợi được sử dụng như thế nào?

Hàng đợi có nhiều ứng dụng thực dụng:

1. Các thuật toán tìm kiếm đầu tiên (BFS) dựa trên cấu trúc dữ liệu hàng đợi. Đổi lại, điều này được sử dụng bởi các cấu trúc dữ liệu cây hoặc đồ thị khác.
2. Môi giới tin nhắn và điện toán phân tán. Phần mềm nâng cao như Kafka sử dụng hàng đợi để môi giới tin nhắn và điện toán phân tán.
3. Ứng dụng cấp cao hơn. Bất cứ khi nào khách hàng tạo ra nhiều tin nhắn hoặc sự kiện theo kiểu phân tán hoặc phi tuyến tính, hàng đợi được đặt tại chỗ để xử lý thông tin đó. Hãy tưởng tượng một tiệm bánh pizza nhận được nhiều đơn đặt hàng. Nếu các đơn đặt hàng không đi theo thứ tự giống như chúng được đặt (ví dụ: họ đã sử dụng LIFO hoặc Stacks), họ sẽ không có nhiều khách hàng hạnh phúc.
   

5.3 Cách thực hiện cấu trúc dữ liệu hàng đợi trong Python

Nhiều lập trình viên sử dụng danh sách để thực hiện hàng đợi, vì bạn có thể thực hiện nguyên tắc FIFO với việc cắt. Tuy nhiên, như được ghi nhận trong tài liệu Python:

Cấm [L] IST không hiệu quả cho mục đích này. Mặc dù các lần nối và bật từ cuối danh sách rất nhanh, nhưng việc chèn hoặc bật từ đầu danh sách là chậm (vì tất cả các yếu tố khác phải được thay đổi bởi một).

Thay vào đó, hãy sử dụng Bộ sưu tập.Deque, được thiết kế để có sự thay đổi nhanh chóng và bật từ cả hai đầu. Bộ sưu tập mô -đun.Deque cũng có thể được sử dụng cho các ngăn xếp nhưng trong trường hợp này, chúng ta có thể tập trung vào các phương thức deque nối () và popleft (). Cái trước thêm một mục mới ở bên phải (cuối) của hàng đợi, trong khi phần sau quay lại và loại bỏ vật phẩm sang bên trái (bắt đầu) của hàng đợi.

6. Bản đồ

6.1 Bản đồ là gì?

Cấu trúc dữ liệu bản đồ (còn được gọi là bảng băm, bảng tra cứu, băm hoặc mảng kết hợp) là một tập hợp các mục được đặt tên. Nó cực kỳ hiệu quả trong việc chèn vật phẩm, tra cứu và xóa vật phẩm.

Tuy nhiên, hiệu quả này có chi phí - nó đòi hỏi nhiều không gian hơn nhiều so với các cấu trúc dữ liệu khác.

Điều này là do bản đồ được triển khai như một bảng giá trị khóa, trong đó mỗi giá trị có một khóa duy nhất liên quan được sử dụng để truy xuất mục nhanh.

Bản đồ thực hiện các hoạt động sau:

1. Đặt (khóa, giá trị): Thêm ánh xạ giá trị khóa vào bản đồ.
2. Xóa (khóa): Xóa khóa và giá trị liên quan của nó.
3. Nhận (khóa): Lấy giá trị được liên kết với khóa đã cho.
   

6.2 Bản đồ được sử dụng như thế nào?

Các bản đồ cực kỳ có lợi cho bất kỳ ứng dụng nào phụ thuộc nhiều vào thời gian đọc dữ liệu nhanh và không bị ảnh hưởng bởi các ràng buộc không gian. Điều này liên quan đến phần lớn các ứng dụng web hiện đại, trả về thông tin một cách hiệu quả. Bản đồ cũng rất phổ biến đối với các nhà khoa học dữ liệu trong quá trình làm sạch dữ liệu, trong đó kiểm tra các giá trị đối với đường cơ sở giá trị khóa được sử dụng để xác định xem dữ liệu đã bị hỏng trong quá trình vận chuyển hay trong quá trình thu thập và chuyển đổi.

6.3 Cách thực hiện cấu trúc dữ liệu bản đồ trong Python

Bản đồ được triển khai như là loại dữ liệu tích hợp Dict! Việc triển khai Python yêu cầu bạn chọn một đối tượng bất biến cho một khóa (các đối tượng có thể thay đổi như danh sách không thể được chuyển thành băm đáng tin cậy vì chúng có thể thay đổi với băm) và sau đó nó xây dựng một bảng băm trong nền.

Nếu bạn cần bồi dưỡng về cách bắt đầu từ điển trong Python (Cảnh báo spoiler: Đặt các cặp giá trị khóa giữa niềng răng xoăn) và các phương pháp làm việc khác với từ điển, hãy xem bài viết của chúng tôi về các loại dữ liệu tích hợp. & NBSP;

7. Đồ thị

7.1 Biểu đồ là gì?

Đồ thị sắp xếp dữ liệu dưới dạng nhiều nút (hoặc đỉnh trong toán học) được kết nối với các mối quan hệ (hoặc các cạnh trong toán học).

Đồ thị là các cấu trúc được sử dụng để mô hình hóa mối quan hệ theo cặp giữa các đối tượng. Ví dụ, nút khách hàng John Smith, có thể có một mối quan hệ về việc mua lại với nút Tóc của Node.

7.2 Biểu đồ được sử dụng như thế nào?

Các biểu đồ được sử dụng rộng rãi để mô hình hóa các mạng khác xảy ra tự nhiên trong cuộc sống thực, chẳng hạn như kết nối phương tiện truyền thông xã hội, phân tích ngôn ngữ ngữ nghĩa, lưu lượng truy cập trang web và liên kết với nhau, cấu trúc liên kết của các nguyên tử, v.v. (và danh sách thực sự tiếp tục).

Đây là cấu trúc dữ liệu linh hoạt nhất của tất cả vì người ta có thể xây dựng mọi cấu trúc dữ liệu khác bằng các biểu đồ.

7.3 Cách thực hiện cấu trúc dữ liệu đồ thị trong Python

Một cách đơn giản để thực hiện biểu đồ là với từ điển Python, theo đó hướng của một mối quan hệ đi từ khóa (nút nguồn) đến giá trị (nút đích). Điều này có thể cồng kềnh, nhưng nó khá hiệu quả.

Một cách tiếp cận trực quan hơn (và một cách tiếp cận được sử dụng rộng rãi bởi các nhà khoa học dữ liệu và kỹ sư mạng) là sử dụng thư viện NetworkX. Thư viện này cho phép bạn dễ dàng thêm và loại bỏ cả hai nút và cạnh và đi kèm với nhiều phương thức vượt trội, chẳng hạn như các phương pháp tìm đường dẫn ngắn nhất giữa các nút hoặc các biện pháp kết hợp và tính trung tâm trong biểu đồ.

8. Đặt

8.1 Một bộ là gì?

Một bộ là một bộ sưu tập không có thứ tự của các mục độc đáo (không trùng lặp). Nó là một cấu trúc dữ liệu bắt chước các bộ toán học, vì vậy nó cũng đi kèm với các hoạt động toán học, chẳng hạn như kiểm tra thành viên (là một phần của bộ? (Công đoàn, Giao lộ, v.v.).

8.2 Một bộ được sử dụng như thế nào?

Các bộ được sử dụng cho các hoạt động đặt cực kỳ hiệu quả. Chúng thường được sử dụng để xác thực dữ liệu (ví dụ: là một phần của việc làm sạch dữ liệu hoặc thậm chí các ứng dụng hướng tới khách hàng, chẳng hạn như kiểm tra xem thông tin đăng nhập của máy khách có trong cơ sở dữ liệu), tìm sự khác biệt giữa hai bộ dữ liệu, kết hợp các giá trị duy nhất với nhau (ví dụ: khi xây dựng bộ dữ liệu mới ), và nhiều hơn nữa.

8.3 Cách thực hiện cấu trúc dữ liệu đã đặt trong Python

Các bộ có triển khai gốc trong Python với đối tượng đã đặt. Sử dụng các phương thức SET đối tượng cho phép các hoạt động thiết lập ngoài hộp hiệu quả và được tối ưu hóa với các cuộc gọi phương thức.

9. Kết luận: Cấu trúc dữ liệu Python

Trong hướng dẫn này, bạn đã học được:

1. 6 cấu trúc dữ liệu cơ bản.
2. Việc triển khai các cấu trúc dữ liệu trong Python (với các mô-đun tích hợp hoặc thư viện bên ngoài).
3. Những lợi thế thực tế của việc sử dụng một cấu trúc dữ liệu cụ thể.
   

Cái gì tiếp theo?

Bây giờ, thời gian để đưa kiến ​​thức mới tìm thấy của bạn vào thử nghiệm. Sử dụng các cấu trúc dữ liệu để cải thiện mã hiện có hoặc viết các tập lệnh hiệu suất cao mới.

Các cấu trúc dữ liệu được thực hiện như thế nào trong Python?

Có dễ dàng thực hiện các cấu trúc dữ liệu trong Python không?

Cấu trúc dữ liệu trong triển khai là gì?

Cấu trúc dữ liệu nào được sử dụng trong Python?