Vitalik phát hành bài viết mới "Memory access is O(N^[1/3])": Thảo luận về độ phức tạp truy cập bộ nhớ và hiệu suất của hệ thống blockchain

Vào ngày 5 tháng 10, Vitalik đã đăng tải bài viết mới "Memory access is O(N^(1/3))" để thảo luận về độ phức tạp truy cập bộ nhớ, bàn về vấn đề độ phức tạp “truy cập bộ nhớ” trong các cấu trúc dữ liệu và thuật toán, đồng thời đưa ra quan điểm rằng trong một số kiến trúc hoặc mô hình nhất định, chi phí truy cập bộ nhớ có thể có giới hạn trên là O(N^(1/3)). Ông chỉ ra rằng độ phức tạp thời gian của các thuật toán sắp xếp kinh điển là O(N log N), nhưng khi xem xét nút thắt truy cập bộ nhớ, cần phải đánh giá lại hiệu quả xử lý các tập dữ liệu lớn. Chủ đề này mang ý nghĩa gợi mở đối với thiết kế hệ thống nền tảng blockchain, đặc biệt là khi xử lý trạng thái quy mô lớn, đồng bộ hóa node cũng như các cơ chế về khả năng sẵn có của dữ liệu (DA / sampling khả năng sẵn có dữ liệu...), cần phải cân nhắc kỹ lưỡng hơn về nút thắt hiệu suất “đọc/ghi bộ nhớ”.