Học cấu trúc dữ liệu trong python hay c++ có tốt không?

Các ngôn ngữ cấp cao như Python và Ruby thường được đề xuất vì chúng ở cấp độ cao và cú pháp khá dễ đọc. Tuy nhiên, tất cả các ngôn ngữ này đều có sự trừu tượng hóa cho các cấu trúc dữ liệu chung. Không có gì ngăn cản bạn triển khai các phiên bản của riêng mình như một bài tập học tập nhưng bạn có thể thấy rằng mình đang xây dựng cấu trúc dữ liệu cấp cao trên các cấu trúc dữ liệu cấp cao khác, điều này không nhất thiết phải hữu ích

Ngoài ra, Ruby và Python là các ngôn ngữ được gõ động. Điều này có thể tốt nhưng nó cũng có thể gây nhầm lẫn cho người mới bắt đầu và có thể khó bắt lỗi hơn (ban đầu) vì chúng thường không rõ ràng cho đến khi chạy

C ở một cực khác. Thật tốt nếu bạn muốn tìm hiểu các chi tiết thực sự ở cấp độ thấp như cách quản lý bộ nhớ nhưng việc quản lý bộ nhớ đột nhiên là một vấn đề quan trọng cần cân nhắc, chẳng hạn như cách sử dụng chính xác malloc()/free(). Điều đó có thể gây mất tập trung. Ngoài ra, C không hướng đối tượng. Đó không phải là một điều xấu mà chỉ đơn giản là đáng chú ý

C++

C++ đã được đề cập. Như tôi đã nói trong phần nhận xét, tôi nghĩ đây là một lựa chọn tồi tệ. C ++ cực kỳ phức tạp ngay cả trong cách sử dụng đơn giản và có một lượng "gotchas" vô lý. Ngoài ra, C++ không có lớp cơ sở chung. Điều này rất quan trọng vì các cấu trúc dữ liệu như bảng băm phụ thuộc vào việc có một lớp cơ sở chung. Bạn có thể triển khai phiên bản cho lớp cơ sở danh nghĩa nhưng nó kém hữu ích hơn một chút

Java

Java cũng đã được đề cập. Nhiều người thích ghét Java và sự thật là ngôn ngữ này cực kỳ dài dòng và thiếu một số tính năng ngôn ngữ hiện đại hơn (ví dụ: bao đóng) nhưng không có điều nào thực sự quan trọng. Java được gõ tĩnh và có bộ sưu tập rác. Điều này có nghĩa là trình biên dịch Java sẽ phát hiện nhiều lỗi mà các ngôn ngữ được nhập động sẽ không phát hiện được (cho đến khi chạy) và không xử lý các lỗi phân đoạn (điều đó không có nghĩa là bạn không thể rò rỉ bộ nhớ trong Java; rõ ràng là bạn có thể). Tôi nghĩ Java là một lựa chọn tốt

C#

C# ngôn ngữ giống như một phiên bản hiện đại hơn của Java. Giống như Java, nó là ngôn ngữ biên dịch trung gian được quản lý (thu gom rác) chạy trên máy ảo. Mọi ngôn ngữ khác được liệt kê ở đây ngoài C/C++ cũng chạy trên máy ảo nhưng Python, Ruby, v.v. được diễn giải trực tiếp thay vì được biên dịch thành mã byte

Về cơ bản, C# có những ưu và nhược điểm giống như Java

Haskell (vv)

Cuối cùng, bạn có ngôn ngữ chức năng. Haskell, OCaml, Scheme/Lisp, Clojure, F#, v.v. Những điều này nghĩ về tất cả các vấn đề theo một cách rất khác và đáng để học ở một số điểm nhưng một lần nữa, nó phụ thuộc vào những gì bạn muốn học. lập trình chức năng hoặc cấu trúc dữ liệu? . Nếu bạn học một ngôn ngữ chức năng tại một thời điểm nào đó (mà tôi muốn giới thiệu), Haskell là một lựa chọn an toàn và tốt

Lời khuyên của tôi

Chọn Java hay C#. Cả hai đều có các IDE tuyệt vời, miễn phí (Eclipse, Netbeans và Phiên bản cộng đồng IntelliJ cho Java, Visual Studio Express cho C#, phiên bản cộng đồng Visual studio) giúp viết và chạy mã nhanh chóng. Nếu bạn không sử dụng cấu trúc dữ liệu riêng phức tạp hơn một mảng và bất kỳ đối tượng nào bạn tự viết, về cơ bản bạn sẽ học điều tương tự như trong C/C++ nhưng không cần phải thực sự quản lý bộ nhớ

Hãy để tôi giải thích. một bảng băm có thể mở rộng cần được thay đổi kích thước nếu đủ các phần tử được thêm vào. Trong bất kỳ triển khai nào, điều đó có nghĩa là thực hiện điều gì đó như tăng gấp đôi kích thước của cấu trúc dữ liệu sao lưu (thường là một mảng) và sao chép các phần tử hiện có. Việc triển khai về cơ bản giống nhau trong tất cả các ngôn ngữ bắt buộc nhưng trong C/C++, bạn phải xử lý các lỗi phân đoạn khi bạn không phân bổ hoặc phân bổ chính xác thứ gì đó

Python hoặc Ruby (cái nào thực sự không quan trọng) sẽ là lựa chọn tiếp theo của tôi (và rất gần với hai cái còn lại) chỉ vì lúc đầu, kiểu gõ động có thể gặp vấn đề

Tôi cảm thấy như tôi đã học được hàng tháng trong một tuần. Tôi thích cách Codecademy sử dụng cách học thông qua thực hành và đưa ra những thử thách lớn để giúp người học hiểu một khái niệm và chủ đề mới. Học viên Học viện mật mã Rodrigo @ Vương quốc Anh

Bài viết này dành cho những người mới bắt đầu học các thuật toán và tự hỏi nó sẽ ảnh hưởng như thế nào đến việc nâng cao kỹ năng nghề nghiệp/lập trình của họ. Nó cũng dành cho những người thắc mắc tại sao các công ty lớn như Google, Facebook và Amazon lại thuê những lập trình viên đặc biệt giỏi trong việc tối ưu hóa Thuật toán

---

Thuật toán là gì?

Một cách không chính thức, một thuật toán không là gì ngoài việc đề cập đến các bước để giải quyết vấn đề. Chúng thực chất là một giải pháp

Ví dụ, một thuật toán để giải quyết vấn đề về giai thừa có thể giống như thế này

Vấn đề. Tìm giai thừa của n

Initialize fact = 1
For every value v in range 1 to n:
    Multiply the fact by v
fact contains the factorial of n

Ở đây, thuật toán được viết bằng tiếng Anh. Nếu nó được viết bằng ngôn ngữ lập trình, chúng tôi sẽ gọi nó là mã thay thế. Đây là mã để tìm giai thừa của một số trong C++

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

---

Lập trình là tất cả về cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu được sử dụng để giữ dữ liệu trong khi thuật toán được sử dụng để giải quyết vấn đề bằng cách sử dụng dữ liệu đó

Cấu trúc dữ liệu và giải thuật (DSA) xem xét chi tiết các giải pháp cho các vấn đề tiêu chuẩn và cung cấp cho bạn cái nhìn sâu sắc về mức độ hiệu quả của việc sử dụng từng giải pháp trong số đó. Nó cũng dạy cho bạn khoa học về đánh giá hiệu quả của một thuật toán. Điều này cho phép bạn chọn tốt nhất trong số các lựa chọn khác nhau

---

Sử dụng cấu trúc dữ liệu và thuật toán để làm cho mã của bạn có thể mở rộng

Thời gian là quý giá

Giả sử, Alice và Bob đang cố giải một bài toán đơn giản tìm tổng của 1011 số tự nhiên đầu tiên. Trong khi Bob đang viết thuật toán, Alice đã triển khai nó, chứng minh rằng nó đơn giản như việc chỉ trích Donald Trump

Thuật toán (bởi Bob)

Initialize sum = 0
for every natural number n in range 1 to 1011(inclusive):
    add n to sum
sum is your answer

Mã (bởi Alice)

int findSum() {
    int sum = 0;
    for (int v = 1; v <= 100000000000; v++) {
        sum += v;
    }
    return sum;
}

Alice và Bob đang cảm thấy phấn khích về bản thân rằng họ có thể xây dựng thứ gì đó của riêng mình trong thời gian ngắn. Hãy lẻn vào không gian làm việc của họ và lắng nghe cuộc trò chuyện của họ

Alice: Let's run this code and find out the sum.
Bob: I ran this code a few minutes back but it's still not showing the output. What's wrong with it?

Rất tiếc, đã xảy ra sự cố. Một máy tính là máy quyết định nhất. Quay lại và cố gắng chạy lại sẽ không giúp được gì. Vì vậy, hãy phân tích những gì sai với mã đơn giản này

Hai trong số những tài nguyên quý giá nhất cho một chương trình máy tính là thời gian và bộ nhớ

Thời gian máy tính chạy mã là

Time to run code = number of instructions * time to execute each instruction

Số lượng lệnh tùy thuộc vào mã bạn đã sử dụng và thời gian để thực thi từng mã tùy thuộc vào máy và trình biên dịch của bạn

Trong trường hợp này, tổng số lệnh được thực thi (giả sử x) là

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

1, tức là

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

2

Chúng ta hãy giả sử rằng một máy tính có thể thực hiện các lệnh

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

3 trong một giây (nó có thể thay đổi tùy theo cấu hình máy). Thời gian để chạy đoạn mã trên là

Time to run y instructions = 1 second
Time to run 1 instruction = 1 / y seconds
Time to run x instructions = x * (1/y) seconds = x / y seconds

Hence,
Time to run the code = x / y 
                     = (2 * 1011 + 3) / 108 (greater than 33 minutes)

Có thể tối ưu hóa thuật toán để Alice và Bob không phải đợi 33 phút mỗi khi họ chạy mã này không?

Tôi chắc chắn rằng bạn đã đoán đúng phương pháp. Tổng của N số tự nhiên đầu tiên được cho bởi công thức

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

0

Chuyển đổi nó thành mã sẽ giống như thế này

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

1

Mã này thực thi chỉ trong một lệnh và hoàn thành tác vụ bất kể giá trị là bao nhiêu. Hãy để nó lớn hơn tổng số nguyên tử trong vũ trụ. Nó sẽ tìm thấy kết quả trong thời gian không

Thời gian cần thiết để giải quyết vấn đề, trong trường hợp này, là

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

4 (tức là 10 nano giây). Nhân tiện, phản ứng nhiệt hạch của bom khinh khí mất 40-50 ns, có nghĩa là chương trình của bạn sẽ hoàn thành thành công ngay cả khi ai đó ném bom khinh khí vào máy tính của bạn cùng lúc bạn chạy mã của mình. . )

Ghi chú. Máy tính thực hiện một số lệnh (không phải 1) để tính phép nhân và phép chia. Tôi đã nói 1 chỉ vì mục đích đơn giản

---

Thêm về khả năng mở rộng

Khả năng mở rộng là quy mô cộng với khả năng, nghĩa là chất lượng của thuật toán/hệ thống để xử lý bài toán có kích thước lớn hơn

Xem xét vấn đề thiết lập một lớp học gồm 50 sinh viên. Một trong những giải pháp đơn giản nhất là đặt phòng, lấy một cái bảng đen, vài viên phấn, và vấn đề được giải quyết

Nhưng nếu quy mô của vấn đề tăng lên thì sao?

Giải pháp vẫn giữ nhưng nó cần nhiều tài nguyên hơn. Trong trường hợp này, bạn có thể sẽ cần một căn phòng lớn hơn nhiều (có thể là rạp chiếu phim), màn hình máy chiếu và bút kỹ thuật số

Nếu số học sinh tăng lên 1000 thì sao?

Giải pháp không thành công hoặc sử dụng nhiều tài nguyên khi kích thước của vấn đề tăng lên. Điều này có nghĩa là giải pháp của bạn không thể mở rộng

Một giải pháp có thể mở rộng sau đó là gì?

Hãy xem xét một trang web như Khanacademy, hàng triệu sinh viên có thể xem video, đọc câu trả lời cùng một lúc và không cần thêm tài nguyên. Vì vậy, giải pháp có thể giải quyết các vấn đề về kích thước lớn hơn trong điều kiện khan hiếm tài nguyên

Nếu bạn thấy giải pháp đầu tiên của chúng tôi để tìm tổng của N số tự nhiên đầu tiên, thì giải pháp đó không thể mở rộng. Đó là bởi vì nó yêu cầu sự tăng trưởng tuyến tính theo thời gian với sự tăng trưởng tuyến tính về quy mô của vấn đề. Các thuật toán như vậy còn được gọi là thuật toán có thể mở rộng tuyến tính

Giải pháp thứ hai của chúng tôi rất có thể mở rộng và không yêu cầu sử dụng thêm thời gian để giải quyết vấn đề có kích thước lớn hơn. Chúng được gọi là thuật toán thời gian không đổi

---

Bộ nhớ đắt tiền

Trí nhớ không phải lúc nào cũng dồi dào. Trong khi xử lý mã/hệ thống yêu cầu bạn lưu trữ hoặc tạo ra nhiều dữ liệu, điều quan trọng đối với thuật toán của bạn là tiết kiệm mức sử dụng bộ nhớ bất cứ khi nào có thể. Ví dụ. Trong khi lưu trữ dữ liệu về mọi người, bạn có thể tiết kiệm bộ nhớ bằng cách chỉ lưu trữ ngày sinh của họ chứ không phải tuổi của họ. Bạn luôn có thể tính toán nó một cách nhanh chóng bằng cách sử dụng ngày sinh và ngày hiện tại của họ

---

Ví dụ về hiệu quả của thuật toán

Dưới đây là một số ví dụ về những thuật toán học tập và cấu trúc dữ liệu cho phép bạn làm

ví dụ 1. Vấn đề nhóm tuổi

Các vấn đề như tìm người ở một nhóm tuổi nhất định có thể dễ dàng được giải quyết bằng một phiên bản sửa đổi nhỏ của thuật toán tìm kiếm nhị phân (giả sử rằng dữ liệu đã được sắp xếp)

Thuật toán ngây thơ đi qua từng người một và kiểm tra xem nó có thuộc nhóm tuổi nhất định hay không có khả năng mở rộng tuyến tính. Trong khi đó, tìm kiếm nhị phân tự cho mình là một thuật toán có thể mở rộng logarit. Điều này có nghĩa là nếu quy mô của vấn đề được bình phương hóa, thời gian để giải quyết vấn đề đó chỉ tăng gấp đôi

Giả sử, phải mất 1 giây để tìm tất cả những người ở một độ tuổi nhất định cho một nhóm 1000 người. Sau đó, đối với một nhóm 1 triệu người,

• thuật toán tìm kiếm nhị phân sẽ chỉ mất 2 giây để giải quyết vấn đề
• thuật toán ngây thơ có thể mất 1 triệu giây, tức là khoảng 12 ngày

Thuật toán tìm kiếm nhị phân tương tự được sử dụng để tìm căn bậc hai của một số

---

ví dụ 2. Bài toán khối Rubik

Hãy tưởng tượng bạn đang viết một chương trình để tìm lời giải của khối Rubik

Câu đố trông dễ thương này có 43.252.003.274.489.856.000 vị trí một cách khó chịu và đây chỉ là những vị trí. Hãy tưởng tượng số lượng con đường mà một người có thể đi để đến các vị trí sai

May mắn thay, cách giải quyết vấn đề này có thể được biểu diễn bằng cấu trúc dữ liệu đồ thị. Có một thuật toán đồ thị được gọi là thuật toán Dijkstra cho phép bạn giải bài toán này trong thời gian tuyến tính. đúng, bạn nghe đúng đấy. Điều đó có nghĩa là nó cho phép bạn đạt đến vị trí đã giải trong một số trạng thái tối thiểu

---

ví dụ 3. vấn đề DNA

ADN là phân tử mang thông tin di truyền. Chúng được tạo thành từ các đơn vị nhỏ hơn được biểu thị bằng các ký tự La Mã A, C, T và G

Hãy tưởng tượng bạn đang làm việc trong lĩnh vực tin sinh học. Bạn được giao nhiệm vụ tìm ra sự xuất hiện của một mẫu cụ thể trong chuỗi DNA

Đó là một vấn đề nổi tiếng trong học viện khoa học máy tính. Và, thuật toán đơn giản nhất có thời gian tỷ lệ thuận với

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

3

Một chuỗi DNA điển hình có hàng triệu đơn vị như vậy. Hở. đừng lo lắng. Thuật toán KMP có thể hoàn thành việc này trong thời gian tỷ lệ thuận với

int factorial(int n) {
    int fact = 1;
    for (int v = 1; v <= n; v++) {
        fact = fact * v;
    }
    return fact;
}

0

Toán tử * được thay thế bằng + tạo ra nhiều thay đổi

Xem xét rằng mẫu có 100 ký tự, thuật toán của bạn hiện nhanh hơn 100 lần. Nếu mẫu của bạn có 1000 ký tự, thuật toán KMP sẽ nhanh hơn gần 1000 lần. Nghĩa là, nếu bạn có thể tìm thấy sự xuất hiện của mẫu trong 1 giây, thì bây giờ bạn chỉ mất 1 ms. Chúng ta cũng có thể diễn đạt điều này theo một cách khác. Thay vì ghép 1 sợi, bạn có thể ghép 1000 sợi có độ dài tương tự cùng lúc

Và có vô số những câu chuyện như vậy

---

Từ cuối cùng

Nói chung, phát triển phần mềm liên quan đến việc học các công nghệ mới hàng ngày. Bạn có thể tìm hiểu hầu hết các công nghệ này khi sử dụng chúng trong một trong các dự án của mình. Tuy nhiên, nó không phải là trường hợp với các thuật toán

Nếu bạn không hiểu rõ về các thuật toán, bạn sẽ không thể xác định được liệu bạn có thể tối ưu hóa mã bạn đang viết hay không. Bạn phải biết trước chúng và áp dụng chúng bất cứ khi nào có thể và quan trọng

Chúng tôi đã nói cụ thể về khả năng mở rộng của các thuật toán. Một hệ thống phần mềm bao gồm nhiều thuật toán như vậy. Tối ưu hóa bất kỳ một trong số chúng dẫn đến một hệ thống tốt hơn

Tuy nhiên, điều quan trọng cần lưu ý là đây không phải là cách duy nhất để làm cho hệ thống có thể mở rộng. Ví dụ: một kỹ thuật được gọi là tính toán phân tán cho phép các phần độc lập của chương trình chạy trên nhiều máy cùng nhau, làm cho nó có khả năng mở rộng hơn nữa

Tôi nên học cấu trúc dữ liệu bằng Python hay C?

Học cấu trúc dữ liệu với Python có tốt không?

Ngôn ngữ nào là tốt nhất để học cấu trúc dữ liệu?

DSA tốt hơn trong C++ hay Python?