Cách học cấu trúc dữ liệu và giải thuật giúp bạn trở thành một lập trình viên tốt hơn

“Tôi là một người ủng hộ mạnh mẽ việc thiết kế mã nguồn xoay quanh dữ liệu, hơn là cách ngược lại, và tôi nghĩ đó cũng là một trong những lý do Git đã khá thành công. Thực tế, tôi có thể tuyên bố rằng sự khác nhau giữa một lập trình viên tồi và một lập trình viên giỏi là ở việc liệu anh ta sẽ xem mã nguồn hay cấu trúc dữ liệu quan trọng hơn.” – Linus Torvalds (Một nhà khoa học máy tính, Người phát triển chính của lõi Linux)

“Cấu trúc dữ liệu thông minh và “dumb code” hoạt động tốt hơn rất nhiều so với điều ngược lại.” – Eric S. Raymond, The Cathedral and The Bazaar

Tìm hiểu về cấu trúc dữ liệu và thuật toán làm cho bạn trở thành một lập trình viên “cừ khôi”

Cấu trúc dữ liệu và giải thuật là những khuôn mẫu để giải quyết vấn đề. Càng có nhiều kiến thức về hai lĩnh vực này thì bạn càng có thể giải quyết được nhiều vấn đề khác nhau. Bạn cũng sẽ có thể đưa ra nhiều giải pháp tối ưu cho những vấn đề mới.

Bạn sẽ hiểu sâu sắc hơn về cách máy tính hoàn thành công việc. Điều này ảnh hưởng lên bất kỳ quyết định mang tính kỹ thuật nào bạn đưa ra, bất kể bạn có đang trực tiếp sử dụng thuật toán cụ thể nào hay không. Mọi thứ từ cấp phát bộ nhớ bên trong hệ điều hành, cho đến hoạt động bên trong RDMBS (Relational Database Management System) và các ngăn xếp mạng của bạn quản lý việc gửi dữ liệu từ nơi này đi nơi khác.Tất cả máy tính đều dựa trên những cấu trúc dữ liệu và giải thuật cơ bản, vì vậy hiểu chúng tốt hơn sẽ giúp bạn hiểu máy tính tốt hơn.

Trau dồi kiến thức sâu rộng về giải thuật và bạn sẽ có kho giải pháp cho tập hợp lớn nhiều vấn đề. Các lỗ hổng vấn đề trước kia mà bạn gặp khó khăn khi lập mô hình thường được sắp xếp gọn gàng vào các cấu trúc dữ liệu quen thuộc và xử lý  các Use-case đã biết một cách tinh tế. Đi sâu hơn vào việc triển khai dù là các cấu trúc dữ liệu cơ bản nhất và bạn sẽ bắt đầu thấy các ứng dụng của chúng trong các công việc lập trình hàng ngày của bạn.

Bạn cũng có thể đưa ra các giải pháp mới lạ cho các vấn đề bạn đang gặp phải hiệu quả hơn. Cấu trúc dữ liệu và giải thuật có thói quen tự chứng minh chúng hữu ích trong các tình huống mà chúng không có ý định ban đầu và cách duy nhất để bạn tự khám phá ra chúng là bằng việc có kiến thức sâu sắc và trực quan về ít nhất là những điều cơ bản.

Lý thuyết như vậy có lẽ là đủ rồi nhỉ. Hãy tham khảo một số ví dụ sau.

Tìm cách nhanh nhất để tới địa điểm nào đó.

Cho rằng chúng ta đang xây dựng phần mềm để tìm đường đi ngắn nhất từ một sân bay quốc tế tới một nơi khác. Giả sử chúng ta bị ràng buộc với các tuyến đường như sau:

Dựa vào sơ đồ về các điểm đến và khoảng cách giữa chúng, hãy tìm đường đi ngắn nhất từ Helsinki tới London. Thuật toán Dijkstra là thuật toán sẽ chắc chắn đưa cho chúng ta câu trả lời trong thời gian ngắn nhất.

Rất có thể, nếu bạn đã từng gặp phải vấn đề này và biết rằng thuật toán Dijkstra là giải pháp, bạn có lẽ sẽ không bao giờ phải triển khai  nó từ con số 0. Chỉ cần biết về nó sẽ chỉ  bạn tới một thư viện thực thi và giải quyết vấn đề cho bạn.

Nếu bạn đã đi sâu vào triển khai, bạn sẽ làm việc với một trong những thuật toán đồ thị quan trọng nhất mà chúng ta biết. Bạn sẽ biết rằng trong thực tế, nó hơi tốn tài nguyên nên một phần mở rộng được gọi là A* thường được sử dụng ở vị trí của nó. Nó được sử dụng ở mọi nơi từ robot hướng dẫn đến định tuyến gói tin TCP đến tìm đường định vị GPS.

Tìm thứ tự để làm việc

Hãy nói rằng bạn đang cố gắng để dựng mô hình các khóa học trên nền tảng MOOC ( Massive Open Online Courses). Một vài khóa học phụ thuộc lẫn nhau. Ví dụ, một người dùng phải hoàn thành khóa Calculus trước khi cô ấy đủ điều kiện cho khóa Newtonian Mechanics. Các khóa học có thể có nhiều ràng buộc. Đây là một vài ví dụ về những gì trông có thể giống như được viết trong YAML:

Với những ràng buộc đã cho, đặt vị trí của một người dùng, tôi muốn mình có thể đặt bất kỳ một khóa học nào và có hệ thống cho tôi biết thứ tự danh sách các khóa học mà tôi phải hoàn thành để đủ điều kiện. Do đó, nếu tôi đặt khóa “calculus”, Tôi sẽ muốn hệ thống gửi cho tôi danh sách sau:

Hai hạn chế quan trọng về điều này có thể không rõ ràng:

Ở mọi giai đoạn trong danh sách khóa học, tính phụ thuộc của khóa học tiếp theo phải được đáp ứng

Chúng ta không muốn bất kỳ khóa học nào bị trùng lặp trong danh sách.

Đây là một ví dụ về việc giải quyết tính phụ thuộc và thuật toán mà chúng ta đang tìm kiếm  được gọi là sắp xếp tôpô (tsort). Tsort hoạt động trên biểu đồ phụ thuộc như chúng tôi đã phác thảo trong YAML ở trên. Dưới đây là những gì sẽ trông giống như trên một biểu đồ (trong đó mỗi mũi tên có nghĩa là yêu cầu):

Những gì sắp xếp tôpô thực hiện là lấy một biểu đồ như trên và tìm một thứ tự trong đó tất cả các phụ thuộc được đáp ứng ở mỗi giai đoạn. Vì vậy, nếu chúng ta lấy một biểu đồ con chỉ chứa radioactivity và những phụ thuộc của nó, sau đó chạy tsort trên nó, chúng ta có thể nhận được thứ tự sau:

arithmetic algebra trigonometry calculus mechanics atomic_physics radioactivity

Điều này đáp ứng các yêu cầu đặt ra trong trường hợp sử dụng mà chúng ta đã mô tả ở trên. Một người dùng chỉ cần chọn radioactivity và họ sẽ nhận được một danh sách theo thứ tự tất cả các khóa học họ phải thực hiện trước khi họ được phép. Chúng ta thậm chí không cần phải đi sâu vào chi tiết về cách thức phân loại tôpô hoạt động trước khi chúng ta sử dụng nó.. Rất có thể, Ngôn ngữ lập trình bạn đang sử dụng cũng đã tích hợp Tsort trong thư viện tiêu chuẩn. Trong trường hợp xấu nhất, Hệ điều hành Unix của bạn có lẽ đã tích hợp Tsort mặc định, gõ lệnh “man tsort” và trải nghiệm nó.

Một số trường hợp khác sử dụng tsort

Những công cụ như make cho phép bạn khai báo công việc mang tính phụ thuộc. Tsort được dùng để tìm ra thứ tự các công việc nên được thực thi.

Bất kỳ ngôn ngữ lập trình nào có lệnh require, chỉ ra rằng tệp hiện tại yêu cầu mã trong các tệp khác được chạy trước. Ở đây, tsort có thể được sử dụng để tìm kiếm ra thứ tự các tệp nên được tải kèm, từ đó mỗi khi một tệp được tải, tất cả yêu cầu về tính phụ thuộc đều được đáp ứng. và tất cả các phụ thuộc của nó khi tải một tệp chưa các lệnh require.

Công cụ quản lý dự án với biểu đồ Gantt. Biểu đồ Gantt là một biểu đồ phác thảo tất cả sự phụ thuộc của một nhiệm vụ nhất định và đưa ra ước tính khi nào nó sẽ hoàn thành dựa trên các phụ thuộc đó. Tôi không phải là fan hâm mộ của biểu đồ Gantt, nhưng rất có khả năng tsort sẽ được sử dụng để vẽ chúng.

Nén dữ liệu với mã hóa Huffman

Mã hóa Huffman là một thuật toán được sử dụng cho việc nén dữ liệu chất lượng cao. Nó làm việc dựa trên sự phân tích dữ liệu bạn cần nén và tạo một mã nhị phân cho mỗi ký tự. Những ký tự thường xuyên xuất hiện sẽ có mã nhỏ hơn, do đó e có thể được mã hóa như 111 trong khi x có thể là 10010. Những mã được tạo ra sao cho chúng có thể được nối lại với nhau không cần phân cách và vẫn được giải mã chính xác.

Mã hóa Huffman được sử dụng cùng với LZ77 trong thuật toán DEFLATE, được sử dụng bởi gzip trong việc nén dữ liệu. Gzip được sử dụng ở mọi nơi, đặc biệt là nén các tệp (thường là bất cứ thứ gì có phần mở rộng là .gz) và cho các request/responses của http trong việc truyền dữ liệu.

Một số lợi ích khi biết cách triển khai và sử dụng mã hóa Huffman:

Bạn sẽ biết rằng tại sao một bối cảnh nén lớn hơn lại cho kết quả nén tổng thể tốt hơn (ví dụ: Bạn nén càng nhiều, tỉ lệ nén càng tốt). Đây là một trong những lợi ích được đề xuất bởi SPDY: rằng bạn có được chất lượng nén tốt hơn trên nhiều request/response của HTTP. Bạn sẽ biết rằng nếu bạn đang trong quá trình nén javascript/css, thì việc chạy một công cụ khai thác trên chúng là hoàn toàn vô nghĩa. Điều này cũng tương tự cho tệp PNG vốn đã được sử dụng thuật toán DEFLATE cho việc nén.

Nếu bạn từng cố gắng giải mã thông tin được mã hóa, bạn có thể nhận ra rằng một khi dữ liệu lặp lạicó độ nén tốt hơn, tỷ lệ nén của một bit bản mã nhất định sẽ giúp bạn xác định chế độ hoạt động của mật mã.

Chọn những gì để học tiếp theo là khó

Trở thành một lập trình viên bao gồm việc học hỏi không ngừng. Để hoạt động như một nhà phát triển web, bạn cần biết các ngôn ngữ đánh dấu, các ngôn ngữ bậc cao như Ruby​​/ Python, biểu thức chính quy, SQL và JavaScript. Bạn cần biết các chi tiết của HTTP, cách sử dụng terminal của Unix và nghệ thuật tinh tế của lập trình hướng đối tượng. Thật khó để điều hướng những mảng quan trọng đó một cách hiệu quả và chọn những gì sẽ học tiếp theo.

Tôi không phải là người học nhanh nên tôi phải chọn những gì để dành thời gian một cách rất cẩn thận. Càng nhiều càng tốt, tôi muốn học các kỹ năng và kỹ thuật bền vững và lâu dài, nghĩa là sẽ không bị lỗi thời trong một vài năm. Điều đó có nghĩa là tôi ngần ngại tìm hiểu Javascript Framework hoặc các ngôn ngữ và môi trường lập trình chưa được kiểm tra.

Chừng nào mô hình tính toán vượt trội của chúng ta vẫn giữ nguyên, các cấu trúc dữ liệu và giải thuật mà chúng ta sử dụng ngày nay sẽ được sử dụng ở dạng này hay dạng khác trong tương lai. Bạn có thể an tâm dành thời gian để có được kiến ​​thức sâu rộng và kỹ lưỡng về chúng và biết rằng chúng sẽ trả cổ tức cho toàn bộ sự nghiệp của bạn với tư cách là một lập trình viên.

Leave a Reply

Your email address will not be published. Required fields are marked *