Mảng có thể mở rộng


Trần Hải Vân
6 năm trước
Hữu ích 4 Chia sẻ Viết bình luận 0
Đã xem 3886

Trong GraphHopper, chúng ta có thể tạo các biểu đồ rất nhỏ để định tuyến trong nhà, nhưng chúng ta cũng có thể chia tỷ lệ thành các biểu đồ giữ mạng lưới đường từ hành tinh . Và chúng tôi có thể mở rộng đến kích thước này theo yêu cầu. Lý do là một mẹo rất đơn giản, mà chúng tôi đã không phát minh ra và có thể được tìm thấy trong các hệ thống khác như ElasticSearch .

Trong nội bộ chúng tôi đang sử dụng một mảng đơn giản. Nhưng điều này sẽ không mở rộng vì hai lý do:

  1. Một mảng, ví dụ byte [] được giới hạn chỉ 2GB vì nó được truy cập thông qua các giá trị nguyên.
  2. Để mở rộng kích thước của một mảng, bạn cần một mảng đích thứ hai lớn hơn

Điểm thứ hai là xấu về việc sử dụng bộ nhớ nếu bạn có một mảng lớn và bạn muốn tăng nó lên một chút, bạn cần nhiều hơn gấp đôi kích thước của mảng ban đầu.

Nhưng chúng ta có thể dễ dàng giải quyết cả hai vấn đề khi chúng ta sử dụng một danh sách các mảng thay thế. Giả sử lớp trình bao bọc sau đây có thể được tìm thấy trong cuộc sống thực:

public class RAMDataAccess {
  private int[][] segments = new int[0][];

  public void ensureCapacity( long bytes ) {
    ...
    // if you want to increase the size you just need to create new segments
    for (int i = segments.length; i < newSegs.length; i++)
      newSegs[i] = new int[1 << segmentSizeIntsPower];
    
    segments = newSegs;
    ...
  }

  public void setInt( long longIndex, int value ) {
    longIndex >>>= 2;
    int bufferIndex = (int) (longIndex >>> segmentSizeIntsPower);
    int index = (int) (longIndex & indexDivisor);
    segments[bufferIndex][index] = value;
  }

  public final int getInt( long longIndex ) {
    longIndex >>>= 2;
    int bufferIndex = (int) (longIndex >>> segmentSizeIntsPower);
    int index = (int) (longIndex & indexDivisor);
    return segments[bufferIndex][index];
  }
}

Nếu bạn nhìn vào các phương thức get và set chặt chẽ hơn, bạn sẽ thấy rằng quyền truy cập cũng được tối ưu hóa. Cách tiếp cận đơn giản nhất để tính toán các chỉ số truy cập sẽ là:

segments[longIndex / segments.length][longIndex % segments.length];

Nhưng nếu các phân đoạn của bạn có kích thước ala 2 ^ n, bạn có thể sử dụng các hoạt động bit nhanh hơn một chút như được chỉ ra, ví dụ ở đây .

Nhưng câu chuyện không kết thúc ở đây. Ví dụ: nếu chúng ta ẩn các phần bên trong đằng sau một giao diện (chúng ta gọi nó là DataAccess), chúng ta cũng có thể sử dụng mảng byte hoặc ByteBuffers thay vì mảng số nguyên. Một ByteBuffer có thể được truy xuất từ ​​tệp ánh xạ bộ nhớ, sau đó cho phép chúng tôi truy cập hàng trăm megabyte trên các thiết bị di động như Android, nơi bạn chỉ có 32 MB RAM.

Nếu bạn quan tâm đến các cấu trúc dữ liệu hiệu quả hơn về bộ nhớ, OpenStreetMap, JavaScript hiệu quả hoặc các thuật toán định tuyến trong Java rẽ nhánh repo của chúng tôi hoặc thậm chí tham gia nhóm GraphHopper của chúng tôi!

Hữu ích 4 Chia sẻ Viết bình luận 0
Đã xem 3886