Giới thiệu về các thuật toán và cấu trúc dữ liệu (Javascript Edition)

Giới thiệu

Hiểu các thuật toán và cấu trúc dữ liệu là yếu tố quan trọng để nâng cao hiệu suất của bạn gấp 10 lần so với các đồng nghiệp không làm như vậy. Điều này là do bạn phân tích vấn đề một cách nghiêm túc và đưa ra phương pháp tốt nhất để giải quyết chúng. Nó có thể có nghĩa là tăng tốc thời gian yêu cầu máy chủ hoặc tìm cách tốt nhất để lưu trữ các tập dữ liệu lớn với dung lượng ổ đĩa tối thiểu.

Bài viết này nhằm giúp bạn hiểu các khái niệm cơ bản về thuật toán và cấu trúc dữ liệu cũng như cách triển khai chúng bằng JavaScript.

Thuật toán là gì? Thuật toán là một tập hợp các hướng dẫn từng bước để hoàn thành một nhiệm vụ. Giả sử bạn gặp khó khăn khi thức dậy sớm và bạn liên tục bỏ lỡ thời hạn. Làm thế nào để bạn giải quyết điều này? Aha! Đặt báo thức. Đó là những gì một thuật toán trông giống như.

Mặt khác, cấu trúc dữ liệu là cách lưu trữ dữ liệu hiệu quả.

Cấu trúc dữ liệu và thuật toán (DSA) rất quan trọng nên chúng rất quan trọng đối với hiệu suất tổng thể của một máy tính. Thuật toán bạn chọn sẽ xác định thời gian chạy (Ký hiệu Big O) hoặc hiệu quả của nó. Một số DSA phổ biến là tìm kiếm nhị phân, đệ quy, sắp xếp, mảng, danh sách liên kết và bảng băm.

Tìm kiếm nhị phân là gì?

Giả sử bạn đang tìm kiếm tên trong danh bạ của một quốc gia; nó bắt đầu bằng chữ J. Bạn có thể bắt đầu từ đầu (từ các quốc gia "A") và tiếp tục lật các trang cho đến khi bạn đến danh sách các quốc gia "J" (các quốc gia này được sắp xếp theo thứ tự bảng chữ cái). Nếu quốc gia bắt đầu bằng chữ "Z", thì bạn tiếp tục lật đến cuối danh bạ. Đây được biết đến như một thuật toán tìm kiếm đơn giản. Nhưng hãy tưởng tượng nếu đây là một danh bạ điện thoại với hơn 100.000 số điện thoại thì điều này thật khó ngoài sức tưởng tượng. Làm thế nào để bạn tối ưu hóa điều này? Tìm kiếm nhị phân để giải cứu.

Thuật toán tìm kiếm nhị phân lấy một danh sách các phần tử được sắp xếp làm đầu vào và nếu phần tử bạn đang tìm kiếm có trong danh sách, thì tìm kiếm nhị phân sẽ trả về vị trí mà nó nằm, nếu không, nó trả về giá trị rỗng. Thay vì đi từng bước một để đến Nhật Bản, tìm kiếm nhị phân chia mảng này thành nhiều phần và tìm kiếm từng phần tương ứng.

Bằng cách này, việc tìm kiếm diễn ra nhanh chóng.

Mảng

Chúng là một tập hợp các phần tử được lập chỉ mục bởi một khóa. Các phần tử của mảng được lưu trữ tuần tự, với khóa đóng vai trò là mã định danh trong tập hợp. Các chỉ mục của nó bắt đầu bằng 0.

Chúng siêu hữu ích vì việc truy xuất hoặc sắp xếp bất kỳ phần tử nào cần thời gian không đổi O (1). nó cũng có thể được sử dụng để triển khai nhiều cấu trúc dữ liệu khác đặt ra các hạn chế bổ sung về cách dữ liệu được thao tác. Ví dụ, một chuỗi có thể được triển khai dưới dạng một mảng các ký tự.

Đây là cách triển khai mảng và tìm kiếm nhị phân trong JavaScript.

 function binary_search(list, item) { let guess = list.find(element => element == item); if (guess) { return guess + "\ncountry index no: " + list.findIndex(country => country === guess); } return null + ": element is not in the array" } console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109 console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array

Thuật toán sắp xếp

Tính năng sắp xếp hiếm khi được các lập trình viên sử dụng. Nó hầu hết đã được xử lý bởi ngôn ngữ hoặc thư viện mà họ viết mã. Ví dụ: ngôn ngữ JavaScript sắp xếp các mảng bằng cách sử dụng sắp xếp chèn, sắp xếp theo nhóm hoặc sắp xếp nhanh.

Heapsort tương tự như phương pháp lọc mảng Javascript. Nó chia đầu vào thành một vùng được sắp xếp và một vùng chưa được sắp xếp và di chuyển lặp đi lặp lại các phần tử đến vùng được sắp xếp. Đây là một ví dụ;

Danh sách liên kết

Danh sách liên kết là một cấu trúc dữ liệu trong đó mọi phần tử đều chứa cả dữ liệu và một con trỏ đến phần tử tiếp theo trong danh sách. Một đặc điểm khác biệt của danh sách liên kết là các mục của nó có thể nằm rải rác ở bất cứ đâu trong bộ nhớ. Điều này không đúng với mảng. Xem một số ví dụ dưới đây;

Bảng băm là gì?

Bảng băm là danh sách các phần tử tùy ý trong một mảng. Phần tử sẽ được lưu trữ hoặc khóa của nó được sử dụng làm chỉ mục trong mảng. Đây là một ví dụ:

Hàm băm chuyển đổi khóa của các phần tử được đặt thành một hàm băm, sau đó ánh xạ các phần tử được băm đến một vị trí xác định trong bảng. Mỗi phần tử này cũng có thể là một mảng con của các phần tử tùy ý trong bảng.

Đệ quy

Đệ quy là một kỹ thuật mã hóa được sử dụng trong nhiều thuật toán khác. Nó là một lối tắt cho đoạn mã dài và có thể không mang lại bất kỳ hiệu suất nào ngoại trừ cho lập trình viên.

Giả sử bạn tìm thấy một chiếc vali kho báu. Để mở khóa trường hợp này, bạn cần lấy chìa khóa từ một hộp có các hộp khác nhỏ hơn, có thể vẫn còn các hộp khác trong đó.

Một cách tiếp cận là tạo một danh sách các hộp để tìm kiếm, sau đó xem qua từng hộp này. Nếu bạn tìm thấy một chìa khóa, tuyệt vời! Nếu không, hãy thêm ô trống mới vào danh sách đống để tìm kiếm sau.

Đệ quy loại bỏ bước nơi bạn thêm hộp trống mới được tìm thấy vào danh sách tìm kiếm. Nó gọi phương thức tìm kiếm ngay lập tức trên hộp tìm thấy trống mới. Đây là một ví dụ trong Javascript;

 const suitCase = new Map(); suitCase.set('box-0', '') .set('box-1', '') .set('box-2', '') .set('box-3', '') .set('box-4', 'key') .set('box-5', '') .set('box-6', ''); function search (suit) { for (let [key, value] of suit) { if (value === 'key') { console.log(`Found ${value} at ${key}!`); } } } search(suitCase); // prints Found key at box-4!

Bạn đã tìm thấy chìa khóa, Tada!

Tóm lại, DSA là một cách tuyệt vời để tư duy hiệu quả với tư cách là một lập trình viên. Nó cung cấp cho bạn các công cụ để giải quyết các vấn đề khó khăn. Nhấp vào liên kết kho lưu trữ GitHub để tải xuống tất cả các đoạn mã được sử dụng trong bài viết này. Chúc mừng Hacking!

Kho lưu trữ mã GitHub