Bất kỳ ai biết về việc triển khai java.util.Map được tối ưu hóa để sử dụng bộ nhớ thấp?

Question

Tôi đã xem các địa điểm thông thường (apache commons, google) và không thể tìm thấy một ...

Nó phải là nguồn mở.

Khá nhiều người đang tìm kiếm dựa trên danh sách được liên kết. Trường hợp sử dụng là bản đồ 10'000, không nhất thiết phải có nhiều giá trị. Nó không cần phải mở rộng, vì tôi có thể chuyển đổi nó khi nó quá lớn.

Một số số, kích thước sử dụng một số giá trị jvm được tính toán (8byte/java.lang.Object, 4bytes/ref) HashMap là khoảng 100 + 32n byte, lý thuyết tốt nhất là 12 + 20 * n. < - Tôi muốn điều đó, cho nhỏ n.

Answer 1

Ok, tự mình thực hiện cuối cùng. Tôi đã làm một so sánh tốc độ, và tìm thấy khi so sánh với một HashMap rằng nó vẫn còn nhanh hơn một chút với 4 mục, nhưng chậm hơn với 5 hoặc nhiều hơn. Tôi đã làm các bài kiểm tra với một danh sách dài các phím mà tôi đã cố gắng để cung cấp cho một trang điểm tương tự như một danh sách các từ tiếng Anh ngẫu nhiên.

import java.util.*; 

// PUBLIC DOMAIN 
public class SmallMap extends AbstractMap { 

    private Entry entry = null; 

    public void clear() { entry = null; } 
    public boolean isEmpty() { return entry==null; }  
    public int size() { 
     int r = 0; 
     for(Entry e = entry; e!=null; e = e.next) r++; 
     return r; 
    } 

    public boolean containsKey(Object key) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.key.equals(key)){ 
       return true; 
      } 
     } 
     return false; 
    } 

    public boolean containsValue(Object value) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.value==null){ 
       if(value==null) return true; 
      }else if(e.value.equals(value)){ 
       return true; 
      } 
     } 
     return false; 
    } 

    public Object get(Object key) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.key.equals(key)){ 
       return e.value; 
      } 
     } 
     return null; 
    } 

    public Object put(Object key, Object value) { 
     for(Entry e = entry; e!=null; e = e.next){ 
      if(e.key.equals(key)){ 
       Object r = e.value; 
       e.value = value; 
       return r; 
      } 
     } 
     entry = new Entry(key, value, entry); 
     return null; 
    } 

    public Object remove(Object key) { 
     if(entry!=null){ 
      if(entry.key.equals(key)){ 
       Object r = entry.value; 
       entry = entry.next; 
       return r; 
      } 
      for(Entry e = entry; e.next!=null; e = e.next){ 
       if(key.equals(e.next.key)){ 
        Object r = e.next.value; 
        e.next = e.next.next; 
        return r; 
       } 
      } 
     } 
     return null; 
    } 

    public Set entrySet() { return new EntrySet(); } 

    class EntrySet extends AbstractSet{ 
     public Iterator iterator() { 
      return new Iterator(){ 

       Entry last = null; 
       Entry e = entry; 
       public boolean hasNext() { return e!=null; } 

       public Object next() { 
        last = e; 
        e = e.next; 
        return last; 
       } 

       public void remove() { 
        if(last == null) throw new IllegalStateException(); 
        SmallMap.this.remove(last.key); 
       } 
      }; 
     } 

     public int size() { return SmallMap.this.size();} 
    } 

    static private class Entry implements java.util.Map.Entry { 
     final Object key; 
     Object value; 
     Entry next; 
     Entry(Object key, Object value, Entry next){ 
      if(key==null) throw new NullPointerException(); 
      this.key = key; 
      this.value = value; 
      this.next = next; 
     } 
     public Object getKey() { return key; } 
     public Object getValue() { return value; } 
     public Object setValue(Object value) { 
      Object r = this.value; 
      this.value = value; 
      return r; 
     } 
     public int hashCode() { 
      return (key == null ? 0 : key.hashCode())^
       (value == null ? 0 : value.hashCode()); 
     } 
    } 
} 

Answer 2

Đơn giản, tôi khuyên bạn nên sử dụng một trong HashMap, Hashtable và ConcurrentHashMap của JDK tùy thuộc vào yêu cầu đồng bộ hóa hoặc đồng thời. Nếu bạn quyết định sử dụng chúng, thiết lập initialCapacity và loadFactor một cách thích hợp trong hàm tạo có thể giúp ích.

Bộ sưu tập của Google và bộ sưu tập commache commons cung cấp nhiều tính năng hơn: LRUMap, ReferenceMap, MultikeyMap, v.v. Nhưng tôi không nghĩ rằng không chỉ có kích thước nhỏ.

Answer 3

LinkedHashMap sử dụng danh sách được liên kết, tôi nghĩ, nhưng tôi nghi ngờ rằng nó được tối ưu hóa để sử dụng bộ nhớ thấp. Thông thường, toàn bộ điểm của bản đồ là tăng tốc độ tra cứu từ khóa lên giá trị, điều này giải thích tại sao bạn không tìm thấy những gì bạn cần ở những nơi thông thường. Nó có thể chỉ đơn giản là để viết thực hiện của riêng bạn của Map, và có thể bạn thậm chí có thể phát hành mã trong trường hợp bất cứ ai khác cần điều tương tự.

Answer 4

Viết mã theo cách che giấu việc sử dụng bản đồ (bạn nên làm điều đó dù sao, và có vẻ như bạn cũng vậy). Tại thời điểm nó quan trọng, bởi vì bạn đã lược tả mã và có thể thấy rằng bộ nhớ thực sự là một vấn đề, hãy tìm một :-)

Nếu bạn biết tại thời điểm này có vấn đề, thì xin lỗi Tôi không biết một. Tuy nhiên, quá thường xuyên mọi người đối phó với "ý tưởng" rằng mã sẽ chậm/rất nhiều bộ nhớ/etc ... và bắt đầu cố gắng tối ưu hóa nó lên phía trước thay vì làm cho mã đúng.

Điều đó nói rằng, nếu bạn đang viết một cái gì đó mà bạn biết nó quan trọng bạn nên đo khi bạn đi. Ví dụ tôi đang làm việc trên mã để phân tích các tệp lớp, tôi thực hiện một thay đổi nhỏ và sau đó xem nó ảnh hưởng như thế nào đến hiệu suất. Ví dụ tôi biết một thực tế là một sự thay đổi tôi đã thực hiện (3 dòng) làm cho chương trình của tôi đi chậm hơn 4 lần ... Tôi đã dành thời gian tại thời điểm đó không tìm ra cách nhanh hơn để làm điều đó.

Ngoài ra, bạn có chắc chắn rằng bản đồ là cần thiết nếu giá trị "n" nhỏ? Có lẽ một danh sách đủ nhanh? Ngoài ra, bạn đã thử điều chỉnh Bản đồ hiện tại để có nó sử dụng ít bộ nhớ hơn?

Answer 5

thể có một cái nhìn tại commons-bộ sưu tập Flat3Map, nó được tối ưu hóa để lưu trữ 3 giá trị trong 3 lĩnh vực và tràn vào bản đồ khác tại 4.

Tôi đã không nhìn vào thực hiện nhưng nó có thể là đáng suy nghĩ về . Chỉ có rắc rối là vì các bộ sưu tập commons là 1,3 tương thích nên không có chung.

Answer 6

Gói một ArrayList bằng giao diện Bản đồ. ArrayList chỉ sử dụng một vài byte. Mỗi nút cần hai con trỏ, một cho khóa và một cho giá trị. Sử dụng tìm kiếm tuần tự để tra cứu các giá trị. Miễn là chỉ có vài mục, hiệu suất sẽ được OK [*]. Điều này sẽ cung cấp cho bạn nhiều thời gian để sử dụng bản đồ thực sự cho một vài bình mà bạn có một số lượng lớn các giá trị.

*: Giả sử kích thước bản đồ trung bình của bạn là 10. Máy tính có thể so sánh khoảng 100 triệu khóa mỗi giây, vì vậy, mỗi lần tra cứu sẽ mất ít hơn năm micro giây.

Nếu hiệu suất vẫn quá tệ đối với trường hợp sử dụng của bạn, bạn có thể cố sắp xếp mảng theo khóa và sử dụng tìm kiếm nhị phân.

Answer 7

Phụ thuộc rất nhiều vào cách bạn sử dụng các bản đồ đó, bạn có thể đưa chúng vào một lần chụp và sau đó chỉ cần tra cứu (bạn cần những tra cứu đó là nhanh)?

An thực hiện sử dụng một số tiền tối thiểu của bộ nhớ sẽ được đặt tất cả các yếu tố trong một mảng và để làm một quét để tìm các yếu tố (nhưng tôi đoán đây không phải là nhanh đủ cho nhu cầu của bạn) ...

Nếu bạn biết tất cả các phần tử lúc đầu, bạn có thể thử chọn phương thức băm tốt mà không có quá nhiều va chạm.

Hoặc có thể bạn có thể sử dụng TreeMap nếu bạn cho phép thời gian chèn chậm ...

Answer 8

Có thể câu trả lời này hơi muộn, nhưng hãy xem dự án Javolution. Nó chứa các triển khai của nhiều cấu trúc dữ liệu, dành cho môi trường nhúng và thời gian thực. Cụ thể, có một lớp học FastMap có thể chỉ làm những gì bạn muốn.

Answer 9

Nếu bạn lưu trữ String s mà thôi, hãy nhìn vào http://code.google.com/p/flatmap

chỉnh sửa Oh xin lỗi, tôi thấy bạn đang tìm kiếm bản đồ không lớn nhỏ, quên đi lời khuyên của tôi sau đó.

Answer 10

Tôi biết đó là câu hỏi cũ nhưng có lẽ ai đó có thể thêm ý tưởng khác.

NB: Sau đây sẽ chỉ thực sự có ý nghĩa cho một tập hợp con cụ thể của trường hợp sử dụng:

Nếu yêu cầu bao gồm cao chồng chéo bộ phím (trong trường hợp cực đoan cùng một bộ chìa khóa cho tất cả các bản đồ) sau đó, rất giải pháp hiệu quả có thể là "ngoại giao" các khóa liên quan đến bản đồ và có bản đồ chỉ chứa các giá trị, trong một mảng.

Việc triển khai không nên phụ thuộc "cấu trúc" vào yếu tố trùng lặp, nhưng tôi thực hiện tốt hơn khi các phím chồng lên nhau nhiều hơn. Như bạn đã mong đợi.

Tôi không thể cung cấp chi tiết chính xác về việc triển khai, nhưng điều quan trọng là phải có cơ chế dịch phím (lưu trữ bên ngoài đối tượng bản đồ) của bạn thành chỉ mục vào mảng giá trị, đồng thời cho phép mảng giá trị ở lại nhỏ gọn, tức là có chiều dài năm nếu bản đồ của bạn chứa năm ánh xạ.

Nói các phím cho tất cả các bản đồ như vậy nằm trong một bản đồ riêng biệt, được ánh xạ tới số. Sau đó, nó là một vấn đề của việc có một cách liên quan đến các con số và các chỉ số mảng.

Xin lỗi nếu điều này không đủ cụ thể nhưng tôi nghĩ ý tưởng thú vị và đơn giản cùng một lúc và có thể được sử dụng như một hướng thay thế trong việc phát triển một bản đồ hiệu quả về bộ nhớ.

Một lần nữa, nó vốn phù hợp với trường hợp sử dụng "chồng chéo khóa" cao, nhưng bản thân nó là chung chung. Cũng có thể gặp vấn đề về hiệu suất nếu chồng chéo quá thấp, tùy thuộc vào chi tiết triển khai.