Java: Структура данных Память

Question

Есть ли у кого-нибудь список грубых оценок большого размера для различных структур данных? например

• Массивы
• Списки
• HashMaps
• LinkedLists

Я помню некоторые из этих оценок брошенные вокруг в разных местах, но я не могу найти один прямо сейчас.

Я знаю, что это на самом деле невероятно сложный, особенно для таких вещей, как HashMaps, но я искал что-то действительно грубый, как:

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

конечно это будет рознятся в зависимости от этого и это, но даже приблизительная оценка внутри-фактора-2 была бы чрезвычайно полезной.

Answer 1

Проверьте это.

Answer 2

Это довольно грубо, но эти оценки должны быть правильными. Это для структур данных без костей без включения переменных длины или любых других дополнений, которые, как правило, включаются в Java.

где DATATYPE является тип данных, хранящихся

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) 

Answer 3

Эта таблица является довольно исчерпывающей и имеет дело с вариантами реализации JDK, измеренными в байтах на элемент ввода/элемент. Если вы хотите сделать это на своей собственной машине - если вы работаете на другой машине, возможно - этот сайт Google Code позволит вам загрузить его источник. http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures

Answer 4

Вот это простая программа, которая только потребляет 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 

Это примитивный итератор и должно быть заменено чем-то более сложным - например, если вам нужно 37 МБ для вызова RamInit с элементами Collection a и 1M, вы должны начать с 2M элементов с более чем.

И вы должны выбрать шаги в двоичном поиске, например, если 20M слишком мало, отметьте 128, затем (20 + 128)/2, а затем avg этого, в зависимости от успеха или неудачи с нижним пределом или верхний предел.

Поскольку HashMap хранит 2 входа на элемент, он может начинаться с примерно двойного размера 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 объясняет себя из первых экспериментов. Как мы видим, размер увеличивается почти линейно.

Модификация кода для проверки влияния он используется Longs, до вас - я думаю, вы закончите с коэффициентом 2.

Answer 5

На Infoq, there is a presentation InfoQ-11-Nov-jvmperformance.mp3 от рабочий в твиттере: Pdf-слайды, аудио: mp3 и видео.

В нем много говорится о коллекциях и других деталях размера объектов в JVM.