# 46: Nhận thức giới hạn của bản thân
Làm người phải biết giới hạn của bản thân - Dirty Harry
Mọi nguồn lực của bạn đều hữu hạn. Bạn chỉ có thật nhiều thời gian và tiền bạc để bạn thực hiện công việc của bạn, kể cả thời gian và tiền bạc giúp bạn giữ cho kiến thức, kỹ năng và dụng cụ lúc nào cũng nhạy bén. Bạn chỉ có thể làm việc chăm chỉ, thật nhanh, thật thông minh, và thật bền bỉ. Dụng cụ mà bạn có chính là những trợ thủ đắc lực nhất. Và chính mục tiêu của bạn cũng mạnh mẽ không kém. Chính vì vậy bạn phải tôn trọng giới hạn của những nguồn tài nguyên mà bạn có.
Vậy chúng ta thực hiện nó bằng cách nào? Đó là hiểu bản thân, hiểu đồng nghiệp, hiểu ngân sách của bạn và cuối cùng chính là thấu hiểu dụng cụ của bạn. Điển hình như cách mà một kỹ sư phần mềm hiểu biết và sự độ phức tạp không gian và thời gian của thuật toán và cấu trúc dữ liệu, cũng như cấu trúc và hiệu năng riêng biệt của hệ thống. Công việc của bạn chính là tạo nên sự gắn bó chặt chẽ tối ưu giữa phần mềm và hệ thống.
Sự phức tạp về không gian và thời gian thực hiện của một thuật toán được xác định bởi hàm O(f(n)) (với n là kích thước đầu vào của chương trình) là sự dự đoán về thời gian hay không gian lưu trữ của thuật toán khi n tiến đến vô cực. Một số lớp quan trọng của hàm f(n) bao gồm:
ln(n), n, n ln(n), ne và cuối cùng là en. Khi tổng hợp kết quả từ việc thử nghiệm hàm này và biểu diễn bằng đồ thị chúng ta sẽ nhận thấy sự khác biết rõ ràng, khi n ngày càng lớn, O(ln(n)) sẽ cho kết quả vô cùng nhỏ khi so sánh với O(n) hay O(n ln(n)), và còn nhỏ hơn rất nhiều lần so với O(ne) và O(en). Khi Sean Parent thử với mọi n lớn nhất có thể đạt được thì tất cả các lớp trả về một kết quả gần như hằng số hay gần tuyến tính hay gần như vô cùng lớn.
Access time Capacity
Register <1ns 64b
Cache line 64B
L1 cache 1ns 64KB
L2 cache 4ns 8MB
RAM 20ns 32GB Disk 10ms 10TB
LAN 20ms >1PB
Internet 100ms >1ZB
Phân tích độ phức tạp chính là một trong những phần của máy tính trừu tượng, nhưng phần mềm lại chạy trên những cỗ máy thật. Những hệ thống máy tính hiện đại được chế tạo dựa trên lý thuyết vật lý cùng với những hệ thống trừu tượng, bao gồm cả thời gian xử lý ngôn ngữ, CPUs, bộ nhớ cache, RAM, ổ cứng, và mạng máy tính. Bảng trên cho thấy giới hạn của thời gian truy cập nhiên và khả năng lưu trữ của một server máy tính tiêu biểu.
Chúng ta nhận thấy tốc độ truy cập tỉ lệ thuận với khả năng lưu trữ, khi khả năng lưu trữ càng lớn thời gian truy cập của chúng ngày chậm. Bộ nhớ cache và toàn bộ phần trước nó đều được tận dụng một cách triệt để trong hệ thống của chúng ta và giảm thiểu tối đa các phương tiện còn lại tuy nhiên điều này chỉ có thể thực hiện được khi những lượt truy cập đấy có thể dự đoán được. Và khi thiếu cache hệ thống thường sẽ dừng lại. Lấy ví dụ đơn giản, nếu chúng ta kiểm tra ngẫu nhiên từng byte trên một ở cứng có thể mất đến 32 năm, kể cả kiểm tra ngẫu nhiên mọi byte trong RAM có thể tốn đến 11 phút. Lượng truy cập ngẫu nhiên là không thể đoán trước được. Chính vì thế chúng ta có một phương pháp thay thế khác đó chính là truy cập lại các phần tử đã được sử dụng và truy cập chúng một cách tuần tự.
Và thuật toán và cấu trúc dữ liệu cho thấy chúng hiệu quả như thế nào trong việc tận dụng cache. Lấy ví dụ:
- Tìm kiếm tuyến tính có công dụng tốt trong việc tìm kiếm một giá trị nào đó nhưng lại cần đến O(n) phép so sánh.
- Tìm kiếm nhị phân trong một mảng phần tử đã được sắp xếp chỉ cần O(log(n)) phép so sánh.
- Cây van Emde Boas tìm kiếm và thuật toán Cache-Oblivious chỉ cần O(log(log(n))).
Số phần tử Thời gian tìm kiếm (ns) tuyến tính nhị phân vEB
8 50 90 40
64 180 150 70
512 1200 230 100
4096 17000 320 160
Vậy chúng ta nên sử dụng thuật toán nào? Dựa trên số liệu thống kê và đo đạc được bảng trên thể hiện thời gian cần thiết tìm kiếm trong một mảng số nguyên 64 bit bằng ba phương pháp kể trên. Cá nhân tôi cho rằng:
- Tìm kiếm tuyến tính có thể áp dụng cho mảng nhỏ, nhưng nó dần trở nên rất lâu với những mảng lớn hơn.
- Còn cây van Emde Boas chiến thắng tất cả, nhờ vào sự dự đoán trước lượt truy cập.
Bạn phải trả giá cho lựa chọn của bản thân mình - Punch