Đang tìm kiếm các bit đầu tiên thiết lập trong một bitmap

Question

Phỏng vấn câu hỏi lớn:

Trong một khe cắm bãi đậu xe có sức chứa triệu xe, bạn cần phải tìm một khe cắm bãi đậu xe miễn phí . Không có điều kiện về nơi vị trí có thể là, nghĩa là, bãi đỗ xe có thể có nhiều lối vào và tìm một khe gần lối vào, v.v., không quan trọng. Câu hỏi là loại cấu trúc dữ liệu nào nên được sử dụng và điều gì sẽ phức tạp trong các hoạt động khác nhau.

Tôi đã đề xuất sử dụng một mảng bit triệu bit, với 0/1 cho vị trí đã chụp/miễn phí, vì vậy để tìm điểm miễn phí câu hỏi được dịch để tìm bit thiết lập đầu tiên. Đừng giả sử bất cứ điều gì về có bao nhiêu chiếc xe, v.v., tức là mảng bit có thể thưa thớt hoặc dày đặc.

Cách nhanh nhất để tìm bit được đặt trong bitmap lớn là gì? Tôi đã đề nghị tìm kiếm nhị phân + ffs hiệu quả() trên mỗi từ làm lược đồ.

Answer 1

Bạn có thể đi theo cách này:

Store chỉ số của khe miễn phí cuối cùng trong một biến và sau đó tìm kiếm kế tiếp không quét bitmap từ đầu, nhưng từ giá trị này.

Nếu bạn cần giải phóng một số vị trí, hãy chỉ định vị trí đó cho chỉ mục cuối cùng.

std::vector<bool> có thể là mảng bit của bạn, vì vậy bạn sẽ không cần phải tự xử lý các bit (bool's được đóng gói thành ints nội bộ).

Bạn có thể giới thiệu một cấu trúc mip-mapped:

``std::vector<bool>`` Bitmap; 
``std::vector<bool>`` Bitmap2; // half-sized 
``std::vector<bool>`` Bitmap4; // 1/4 
``std::vector<bool>`` Bitmap8; // 1/8 
// etc 

Các free giá trị trong mảng trên cấp tương ứng với các tình huống mà các mảng cấp dưới có bất kỳ khe miễn phí. Bạn có thể sử dụng tìm kiếm nhị phân để duyệt qua cấu trúc này.

Answer 2

Một triệu số nguyên 32 bit yêu cầu khoảng 4MB bộ nhớ. Vì vậy, tôi muốn nói rằng bạn giữ một danh sách các khe miễn phí. Bất cứ khi nào một chiếc xe vào, bạn lấy một món hàng ra khỏi danh sách và chỉ định nó. Bất cứ khi nào một chiếc xe rời khỏi, bạn đặt số khe tự do vào danh sách.

Vì bạn chỉ có thể thao tác vào cuối danh sách (vì vậy đây thực tế là cấu trúc stack hoặc LIFO), điều này mang đến cho bạn hiệu suất O (1) tối ưu cho cả việc tìm kiếm vị trí miễn phí và trả lại một khe để trạng thái tự do. Nếu bạn làm điều này ở mức thấp với một đoạn dữ liệu thô, bạn sẽ cần một con trỏ cho biết kết thúc hiện tại của danh sách. Tìm một khe giảm dần con trỏ và trả về giá trị của nó. Trả lại một vị trí gán cho con trỏ và tăng nó sau đó.

Nếu bạn quyết định thêm các yêu cầu bổ sung sau này, bạn có thể thực hiện một số thao tác dữ liệu của mình, ví dụ: biến nó thành heap. Với một bản đồ lớn là 0/1 bit, các phần mở rộng như vậy sẽ không thể thực hiện được.