Lập Trình

Ứng dụng thuật toán và cấu trúc dữ liệu lúc đi làm

18288

Bài viết được sự cho phép của tác giả Trần Thiện Khiêm

Nhiều bạn thắc mắc sau này ra trường có ứng dụng thuật toán và cấu trúc dữ liệu không? Tại sao có nhiều công ty tuyển dụng lại hỏi cái này?

Vì sao phải hiểu rõ thuật toán và cấu trúc dữ liệu

Nhiều bạn cho rằng, đi làm sau này các bạn sẽ không cần dùng tới thuật toán hay cấu trúc dữ liệu gì đặc biệt cả. Nhưng nếu bạn không học sâu về thuật toán và cấu trúc dữ liệu, thì các bạn sẽ không biết những điều căn bản sau đây, ví dụ:

Std::map trong C++ là 1 cái map được cài đặt bằng 1 cây nhị phân tìm kiếm tự cân bằng, trong khi đó HashMap (implement lớp Map) trong Java, lại sử dụng 1 bảng băm ở bên dưới, trong khi lớp tương ứng lại phải là TreeMap (implement SortedMap). Và std::unordered_map trong C++ mới là lớp sử dụng bảng hash như Hash Map.

Điều này có nghĩa là gì? Std::map sẽ có các key được sắp xếp, trong khi các lớp implement lớp Map trong java, không có yêu cầu này. Về độ phức tạp của hàm lấy ra 1 phần tử của std::map sẽ là O (logN) trong khi nếu sử dụng HashMap, thì sẽ là O (1).

Những người học kỹ cấu trúc dữ liệu và thuật toán sẽ hoàn toàn nắm vững điều này, khi sử dụng bất cứ API nào, họ sẽ tìm hiểu cài đặt bên dưới, độ phức tạp thuật toán là nhiêu, có phù hợp với việc họ đang làm hay không?

Mấy thông tin này hoàn toàn có thể đọc từ tài liệu của C++, hoặc Java.

Ví dụ, tài liệu lớp std::map của C++ ở đây, hàm at, https://www.cplusplus.com/reference/map/map/at/ sẽ có phần Complexity giải thích là “Logarithmic in size.” (tức là O (logN)).

Tương tự, tài liệu của TreeMap bên java trong phần overview sẽ ghi là “This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations”. Xem ở đây: https://docs.oracle.com/…/docs/api/java/util/TreeMap.html

Cho dù là ngôn ngữ, framework nào đi nữa, thì những thứ căn bản sẽ rất giống nhau. Mình đưa ra 1 ví dụ đơn giản để các bạn thấy rõ thuật toán nó nằm ở ngay bên dưới cái hàm các bạn đang xài, nên hãy tập cho mình thói quen tìm hiểu cái sâu, cái bản chất, thay vì cái hời hợt bên trên.

Vì sao phải quan trọng những điều này?

Thứ nhất, khi nhận yêu cầu, mình hoàn toàn phán đoán được có khả năng giải quyết được vấn đề trong yêu cầu hay không.

Thứ hai, trước khi mình viết code, mình sẽ luôn cố gắng tìm ra giải pháp tối ưu.

Thứ ba, trong khi viết code, mình có thể đánh giá được năng suất của đoạn code của mình ở trên production.

Thứ tư, khi có vấn đề về hiệu năng xảy ra, mình sẽ phán đoán được vấn đề nằm ở đâu để xử lí.

VÌ SAO LẠI PHẢI QUAN TRỌNG NHƯ VẬY?

Mình lấy ví dụ công ty cũ của mình đi:

Ở Amazon, khi bạn đưa 1 chức năng lên trên trang www. amazon. com, bạn phải đảm bảo chức năng của bạn không được tăng thời gian thực thi của 1 request lên 3 mili-giây. Sẽ có công cụ để quét và bắt bạn phải gỡ chức năng của mình xuống nếu vi phạm quy định này, và thậm chí bạn còn phải viết “kiểm điểm”

Ở VISA, mình từng optimize hệ thống xử lý email của công ty từ việc xử lý 5 triệu email trong vòng 24 tiếng còn 5 phút.

Công ty bạn không cần tối ưu?

Việc optimize hệ thống nó có ý nghĩa rất lớn: tiết kiệm chi phí, tăng trải nghiệm người dùng, ngoài ra còn giúp bạn tiến xa trong công việc. Công ty bạn có thể không cần thuật toán tối ưu, nhưng bạn chắc chắn cần, nếu bạn muốn tiến xa hơn.

Bài viết gốc được đăng tải tại fanpage Khiem Tran – Programmer

Xem thêm:

Hàng loạt việc làm IT lương cao trên TopDev đang chờ bạn, ứng tuyển ngay!