Thuật toán LRU cache

1017

Thuật toán cache thì khá đơn giản, bạn chỉ cần một hash table để lưu giữ giá trị của từng key.

Khi đó, việc set cache, và get cache sẽ có độ phức tạp trung bình là O(1)

Tuy nhiên, do memory là giới hạn, nên khi cache đầy, ta cần loại bỏ một số phần tử ra khỏi cache.

Thuật toán LRU lựa chọn những phần tử nào mà “lâu chưa được dùng tới” nhất.

Một key được định nghĩa là “dùng”, khi có một thao tác get hoặc set vào key đó.

Để có thể cài đặt LRU cache, bạn sẽ cần phải có 2 cấu trúc dữ liệu: một cấu trúc để lưu cặp key, value – cấu trúc này dễ thấy sẽ là HashMap, một cấu trúc để lưu và thay đổi vị trị các key theo chiều tăng dần theo thời gian. Thuật toán của chúng ta sẽ phụ thuộc nhiều vào cấu trúc để lưu các key.

Một cách dễ hình dung là sử dụng PriorityQueue để cài đặt cấu trúc dữ liệu này. Nhưng PriorityQueue, thì độ phức tạp khi set, get và, incr các key là O(logN), nên nếu cài đặt bằng PriorityQueue thì độ phức tạp của getset cache sẽ là O(logN).

Có mấy quan sát cho chúng ta khi xem xét cấu trúc dữ liệu lưu các key đó là:

  • cấu trúc này cần có thao tác remove phần tử đầu tiên (phẩn tử có thời gian truy cập nhỏ nhất) (1)
  • cấu trúc này cần có thao tác chuyển vị trị 1 phẩn tử bất kỳ về cuối (hay là set timestamp lên (2) timestamp hiện tại)
  • cấu trúc này cần có thao tác để search 1 phần tử theo key

Để search thì tốc độ tốt nhất là O(logN), nên nếu muốn xây dựng thuật toán tốt hơn O(logN), chúng ta cần loại bọ thao tác cuối. May thay, chúng sẽ có HashMap, HashMap có thể lưu trữ luôn vị trí của key.

Giờ chỉ cần thao tác (1) và (2). Do đó, thay vì cần sử dụng PriorityQueue, ta sẽ dùng Double Linked List, và lưu thêm head, tail của List này là có thể thực hiện 2 thao tác kia bằng O(1)

Chi tiết cài đặt

Techtalk via Kipalog

CHIA SẺ