Tôi có một tập hợp các phạm vi như {(2-8), (13-22), (380-7931), (40032-63278)}. Để đơn giản, chúng tôi có thể giả định rằng chúng không trùng lặp (các phạm vi chồng chéo đã được hợp nhất).Thuật toán để bao gồm phạm vi bộ nhớ?
Mục tiêu của tôi là "che" các dải ô này bằng cách sử dụng các kết hợp của một tập hợp "độ dài" nhất định chẳng hạn như {4, 64, 1024, 16384}. Tôi bị hạn chế sử dụng tối đa N độ dài, chẳng hạn như N = 32. Tôi không quan tâm bao nhiêu "độ dài" tôi sử dụng miễn là tôi dưới mức tối đa của tôi, nhưng tôi muốn giảm thiểu tổng số "thêm" khu vực - số "được bảo hiểm" theo độ dài không nằm trong tập hợp dải ô ban đầu.
Ví dụ {(2-8)} được bao phủ bởi (2-66) (một chiều dài 64 được sử dụng) có 58 số "phụ". {(2-8)} được bao phủ bởi {(2-6), (6-10)} (hai độ dài 4) chỉ có 2 số "phụ" và thích hợp hơn. Ứng dụng thế giới thực của tôi liên quan đến việc lập trình trước một TLB MMU cố định để đảm bảo rằng chỉ có một số địa chỉ bộ nhớ nhất định có thể truy cập được (TLB bị thiếu do đó đại diện cho quyền truy cập bị cấm & có thể được xử lý theo đó). Tôi muốn bao gồm các phạm vi càng chặt càng tốt để các vi phạm được phát hiện sớm hơn là sau này, nhưng tôi chỉ có 32 vị trí để làm việc với 4 kích thước trang cố định. Tôi có thể điều chỉnh mã của mình bằng tay đến một mức hiệu suất đầy đủ, nhưng tôi tò mò nếu có một giải pháp mục đích trang nhã/tổng quát hơn cho vấn đề này. Nó có vẻ liên quan đến vấn đề chiếc ba lô nhưng đủ khác nhau, rất khó để tìm kiếm.