1. 首頁
  2. 問答
  3. Java：數據結構內存估計

Java：數據結構內存估計

2012-03-22 56 views
5

有沒有人有各種數據結構的粗略的經驗法則估計的列表？例如Java：數據結構內存估計

  • 陣列
  • 列表
  • 包含HashMap
  • LinkedLists

我記得看到一些這樣的估計在不同的地方攔腰抱住，但我似乎無法找到一個現在。

我知道它實際上是令人難以置信的複雜，尤其是對於像HashMaps這樣，但我正在尋找的東西真的很粗糙，比如：

Memory(HashMap) = fixedOverhead + variableOverhead * tableSize + A*numKeys + B*numValues + Memory(allKeys) + Memory(allValues)
當然

它會根據這個變化了很多，即使在2倍的因素估計中，也是非常有用的。

來源

2012-03-22 Li Haoyi

+0

我知道我已經回答了那些東西了好幾次，但是我甚至找不到我自己的帖子。下面是熱點的非常短的，不完整的版本：每個對象都有2個字開銷並且是8字節對齊的。數組的大小有額外的4字節。參考大小取決於JVM位數，但64位系統上的堆<32gb存在壓縮oops。 – Voo 2012-03-22 02:03:03

+0

我不知道visualvm是否可以爲你做...這是一個內存分析器，但我從來沒有使用它。 – 2012-03-22 02:17:51

+0

我還沒有設法找到你的答案，要麼= D如果你可以找到你的一箇舊的答案，涵蓋這將是可怕的。 – 2012-03-22 02:28:37

回答

0

這很粗糙，但這些估計應該是正確的。這些適用於不包含長度變量或任何其他傾向於包含在Java中的額外內容的基本數據結構。

其中數據類型的數據類型被存儲

Array: (length n) 
    n*sizeOf(dataType) 

LinkedList: 
    n*(sizeOf(dataType)+sizeOf(pointer))+sizeOf(pointer[head pointer]) 

List: 
    Array-backed=SpaceEfficiency(Array) 
    LinkedList-backed=SpaceEfficiency(LinkedList) 

HashMap: with v values, k keys 
    v*sizeOf(valueDataType) 

Tree: k-way tree with n nodes 
    n*(sizeOf(nodeDataType)+(k*sizeOf(pointer)))+sizeOf(pointer[head pointer]) 

Graph: e edges, v vertices 
    AdjacencyList: 
     at most: v*((v*sizeOf(vertexDataType))+(e*sizeOf(pointer))) fully connected graph 
     at least: v*sizeOf(vertexDataType) disconnected graph 
    AdjacencyMatrix: 
     v^2*sizeOf(int)

來源

2012-03-22 04:59:14 Drew

+0

這很有用，但我知道如何從理論上分析這些東西=）。這是我感興趣的常量：什麼（以字節爲單位）數組中的每項開銷？在一個鏈表中？在HashMap中？什麼是固定開銷？我想要比這更詳細一點的東西，這是沒有任何常數的有效漸近表示法。 – 2012-03-22 06:11:11

+0

我很困惑，除了理論上我們確定的是甚麼問題。所以我的意思是應該有一個數組中的* no *每項開銷權？鏈表中的每項開銷只是指向下一個節點的指針，HashMap中的開銷不存在（除了存儲代碼執行散列算法的內存空間外），因爲它只是數組。你在尋找比這更具體的東西嗎？任何更具體的東西都是Java實現選擇的結果。或者那是你在找什麼？我發現這很有趣：p – Drew 2012-03-22 06:56:24

+0

OP在詢問Java實現選項@Mako。 – 2012-03-22 09:54:42

0

下面是一個簡單的程序，剛剛消耗RAM：

import java.util.*; 
/** 
    RamInit (c) GPLv3 

    @author Stefan Wagner 
    @date Do 22. Mär 08:40:40 CET 2012 

*/ 
public class RamInit 
{ 
    private java.lang.Object consumer; 

    public RamInit (char type, int size) 
    { 
     switch (type) 
     { 
      case 'a': Integer [] ai = new Integer [size]; 
       for (int i = 0; i < size; ++i) 
        ai[i] = i; 
       consumer = ai; 
       break; 
      case 'l': List<Integer> li = new ArrayList<Integer>(); 
       for (int i = 0; i < size; ++i) 
        li.add (i); 
       consumer = li; 
       break; 
      case 'h': HashMap <Integer, Integer> hm = new HashMap <Integer, Integer>(); 
       for (int i = 0; i < size; ++i) 
        hm.put (i, size - i); 
       consumer = hm; 
       break; 
      case 'L': LinkedList <Integer> ll = new LinkedList <Integer>(); 
       for (int i = 0; i < size; ++i) 
        ll.add (i);  
       consumer = ll;   
       break; 
      default: System.err.println ("invalid: " + type); 
     } 
    } 

    public static void main (String args[]) 
    { 
     char type = 'a'; 
     int size = 1000000; // 1M 
     if (args.length == 2) 
     { 
      type = args[0].charAt (0); 
      size = Integer.parseInt (args[1]); 
     } 
     try { 
      new RamInit (type, size); 
     } 
     catch (OutOfMemoryError oome) 
     { 
      System.exit (1); 
     } 
    } 
}

這裏是一個非常簡單的腳本來測試它：

#!/bin/bash 

iterProg() { 
ram=$1 
maxram=$2 
typ=$3 
size=$4 
# echo java -Xmx${ram}M RamInit $typ $((size*1000*1000)) 
echo -n "." 
java -Xmx${ram}M RamInit $typ $((size*1000*1000)) && echo -en "\n"$typ $size ${ram}M || { 
    if (($ram==$maxram)) 
    then 
     # echo "fail" 
     return 
    else 
     iterProg $((ram+1)) $maxram $typ $size 
    fi 
    } 
} 

# try from 16 MB to 256 
for typ in {a,l,h,L}; do 
    for size in {1,2,4}; do 
    iterProg $((size*17+1)) 256 $typ $size 
    done 
done

這是一種原始的迭代器，並應及時更換通過更復雜的事情 - 例如，如果您需要37MB來爲RamInit調用Collection a和1M元素，那麼您應該開始使用2M元素以上的元素。

而且您應該選擇二進制搜索的步驟，例如，如果20M太少，請選擇128，然後選擇（20 + 128）/ 2，然後選擇平均值，具體取決於成功或失敗的下限或上限。

由於HashMap每個元素存儲2個Ints，因此它可以以大約兩倍的List/Array/Vector大小開始。但是 - 時間過得就像一個箭頭，一邊寫，結果完成：

bash iterRamFind.sh 
.. 
a 1 19M..... 
a 2 39M............... 
a 4 83M.. 
l 1 19M....... 
l 2 41M....................... 
l 4 91M.............................................. 
h 1 63M............................................................................................. 
h 2 127M........................................................................................................................................................................................... 
h 4 255M...................... 
L 1 39M................................................. 
L 2 83M............................................................................................... 
L 4 163

值17從第一個實驗解釋本身。我們可以看到，尺寸幾乎呈線性增長。

修改代碼來檢查的影響，就要使用多頭，是你 - 我想你會的2

來源

2012-03-22 09:58:57

0

因素結束對Infoq, there is a presentation相關的-年11月11 jvmperformance.mp3從工人在推特：Pdf幻燈片，音頻：MP3和視頻。

它處理了很多關於JVM中對象的集合和其他細節。

來源

2012-03-27 20:11:11

相關問題

 相關問題