Optimize dùng Hashmap
TIL
500
@100daysTIL
43
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

102 bài viết.
1442 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
146 43
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 2 năm trước
146 43
White
143 37
(Ả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 1 năm trước
143 37
White
97 16
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 gần 2 năm trước
97 16
Bài viết liên quan
White
18 1
Toán tử XOR có tính chất: + A XOR A = 0 + 0 XOR A = A Với tính chất này, có thể cài đặt bài toán sau với độ phức tạp O(N) về runtime, và với O(1)...
kiennt viết hơn 1 năm trước
18 1
White
1 1
Chào mọi người, hôm nay mình viết một bài TIL nhỏ về cách lấy độ phân giải của màn hình hiện tại đang sử dụng. xdpyinfo | grep dimensions Kết quả...
namtx viết 7 tháng trước
1 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


White
{{userFollowed ? 'Following' : 'Follow'}}
102 bài viết.
1442 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á!