Optimize dùng Hashmap
TIL
633
@100daysTIL
72
White

Huy Trần viết ngày 07/02/2018

#Day004

Hôm nay nói về một ứng dụng của Hashmap trong việc optimize một số thuật toán thường gặp trên Frontend.

Giả sử có một mảng languages lưu danh sách các ngôn ngữ lập trình:

const languages = ["c++", "java", "javascript", "ruby", "rust", "golang"];

Và một hàm getLanguages nhận vào một mảng input, trả ra mảng gồm các phần tử vừa có trong input vừa có trong languages (nói theo kiểu tập hợp thì là phép giao hai tập $\texttt{input} \cap \texttt{languages}$):

const normalize = text => text.trim().toLowerCase();

const getLanguages = (input) => {
    return languages.filter(searchLang => {
        return input.findIndex(inputLang => 
               normalize(inputLang) === normalize(searchLang));
    });
};

Về mục đích của hàm trên, thì hãy tưởng tượng bạn đang làm một trang web về tuyển dụng, cho phép user (là ứng viên) nhập vào các ngôn ngữ mình sử dụng, có người sẽ nhập Ruby, có người nhập ruBy, ruby,... hàm trên sẽ filter các input sai lệch đó và trả về input đúng với database nhất.

Ví dụ:

getLanguages(["c++  ", "JavaScript", "GoLang"]);
// Output:
// [ "c++", "javascript", "golang" ]

Hàm getLanguages sẽ có độ phức tạp trong trường hợp xấu nhất là $O(n*k)$, hoặc nếu tập input có kích thước bằng tập languages luôn thì độ phức tạp sẽ là $O(n^2)$.

Sở dĩ tốn kém như vậy là vì chúng ta dùng array, và với array, để tìm ra tập giao nhau, hay nói cách khác, để tìm một phần tử languages[i] bất kì có cùng giá trị tương ứng với một phần tử input[j], ta không có cách nào khác là phải duyệt qua toàn bộ cả 2 mảng.

Vậy đây có thể là mấu chốt để chúng ta optimize thuật toán trên. Liệu có cách nào để từ giá trị của một phần tử input[j], ta có thể truy xuất ngay đến phần tử tương ứng nếu có của languages không? (truy xuất với độ phức tạp $O(1)$).

Một kiểu dữ liệu phù hợp với tính chất truy xuất trên đó là Hashmap, vậy nếu dùng hashmap để thực hiện bước lookup, ta có thể tiết kiệm được một vòng lặp bên trong.

Nhưng dữ liệu cho sẵn (ở đây là mảng languages) là một mảng, ta cần phải chuyển nó thành hashmap trước:

const languagesLookup = Object.create(null);
languages.forEach(lang => { languagesLookup[normalize(lang)] = 1; });

Như vậy ta có thể dễ dàng implement lại thuật toán của getLanguages thành:

const getLanguages = (input) => {
    return input.reduce((array, lang) => {
        let key = normalize(lang);
        if (languagesLookup[key]) {
            array.push(key);
        }
        return array;
    }, []);
};

Bằng cách lợi dụng tính chất truy xuất nhanh và ít tốn kém của Hashmap, ta đã có thể loại bỏ việc phải chạy 2 vòng lặp lồng nhau, và optimize thuật toán ban đầu từ $O(n^2)$ về $O(n)$.

huytd 07-02-2018

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Huy Trần

115 bài viết.
1763 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
167 46
Tại sao phải viết blog kĩ thuật? Có rất nhiều bài viết trên mạng nói về vấn đề tại sao một lập trình viên nên thường xuyên viết các bài blog kĩ thu...
Huy Trần viết hơn 3 năm trước
167 46
White
151 39
(Ảnh) Tiếp tục sêri (Link) lần này, chúng ta sẽ cùng tìm hiểu và mô phỏng lại một chức năng mà mọi người đang bắt đầu sử dụng hằng ngày, đó là chứ...
Huy Trần viết hơn 2 năm trước
151 39
White
108 17
Phần 1: Tự truyện Tui và Toán đã từng là hai kẻ thù không đội trời chung trong suốt hơn mười lăm năm ròng rã. Ngay từ ánh nhìn đầu tiên đã ghét nh...
Huy Trần viết hơn 2 năm trước
108 17
Bài viết liên quan
White
3 1
Javascript inititalValue trong reduce() có quan trọng không? Day 41: Đọc code mẫu về hàm reduce() trong (Link), thấy hàm reduce() khá "đơn giản"....
Minh-Trung Nguyễn viết 7 tháng trước
3 1
White
0 2
fCC: Technical Documentation Page note So I have finished the HTML part of this exercise and I want to come here to lament about the lengthy HTML ...
HungHayHo viết 5 tháng trước
0 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
115 bài viết.
1763 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!