Наверху массива.NET?
Создайте стек, содержащий узлы, которые могли быть частью дерева
- операнды Нажатия на стеке (A, 2, B, и т.д. операнды), поскольку вершины, не связанные с любым деревом в любом направлении
- операторы For, выталкивают необходимые операнды от стека, создают узел с оператором наверху, и операнды, зависающие ниже его, продвигают новый узел на стек
Для Ваших данных:
- Нажатие на стек
- Нажатие 2 на стек
- Pop 2 и A, создайте ^-node (с A и 2 ниже), продвиньте его на стеке
- Нажатие 2 на стеке
- Нажатие на стеке
- , Pop A и 2 и объединение для формирования *-node
- и т.д.
- и т.д.
Вот программа LINQPad , с которой можно провести эксперименты:
// Add the following two using-directives to LINQPad:
// System.Drawing
// System.Drawing.Imaging
static Bitmap _Dummy = new Bitmap(16, 16, PixelFormat.Format24bppRgb);
static Font _Font = new Font("Arial", 12);
void Main()
{
var elementsAsString = "A 2 ^ 2 A * B * - B 2 ^ + A B - / 2 ^";
var elements = elementsAsString.Split(' ');
var stack = new Stack();
foreach (var element in elements)
if (IsOperator(element))
{
Node rightOperand = stack.Pop();
Node leftOperand = stack.Pop();
stack.Push(new Node(element, leftOperand, rightOperand));
}
else
stack.Push(new Node(element));
Visualize(stack.Pop());
}
void Visualize(Node node)
{
node.ToBitmap().Dump();
}
class Node
{
public Node(string value)
: this(value, null, null)
{
}
public Node(string value, Node left, Node right)
{
Value = value;
Left = left;
Right = right;
}
public string Value;
public Node Left;
public Node Right;
public Bitmap ToBitmap()
{
Size valueSize;
using (Graphics g = Graphics.FromImage(_Dummy))
{
var tempSize = g.MeasureString(Value, _Font);
valueSize = new Size((int)tempSize.Width + 4, (int)tempSize.Height + 4);
}
Bitmap bitmap;
Color valueColor = Color.LightPink;
if (Left == null && Right == null)
{
bitmap = new Bitmap(valueSize.Width, valueSize.Height);
valueColor = Color.LightGreen;
}
else
{
using (var leftBitmap = Left.ToBitmap())
using (var rightBitmap = Right.ToBitmap())
{
int subNodeHeight = Math.Max(leftBitmap.Height, rightBitmap.Height);
bitmap = new Bitmap(
leftBitmap.Width + rightBitmap.Width + valueSize.Width,
valueSize.Height + 32 + subNodeHeight);
using (var g = Graphics.FromImage(bitmap))
{
int baseY = valueSize.Height + 32;
int leftTop = baseY; // + (subNodeHeight - leftBitmap.Height) / 2;
g.DrawImage(leftBitmap, 0, leftTop);
int rightTop = baseY; // + (subNodeHeight - rightBitmap.Height) / 2;
g.DrawImage(rightBitmap, bitmap.Width - rightBitmap.Width, rightTop);
g.DrawLine(Pens.Black, bitmap.Width / 2 - 4, valueSize.Height, leftBitmap.Width / 2, leftTop);
g.DrawLine(Pens.Black, bitmap.Width / 2 + 4, valueSize.Height, bitmap.Width - rightBitmap.Width / 2, rightTop);
}
}
}
using (var g = Graphics.FromImage(bitmap))
{
float x = (bitmap.Width - valueSize.Width) / 2;
using (var b = new SolidBrush(valueColor))
g.FillRectangle(b, x, 0, valueSize.Width - 1, valueSize.Height - 1);
g.DrawRectangle(Pens.Black, x, 0, valueSize.Width - 1, valueSize.Height - 1);
g.DrawString(Value, _Font, Brushes.Black, x + 1, 2);
}
return bitmap;
}
}
bool IsOperator(string s)
{
switch (s)
{
case "*":
case "/":
case "^":
case "+":
case "-":
return true;
default:
return false;
}
}
Вывод:
5 ответов
Вот немного более аккуратная (IMO) короткая, но полная программа, демонстрирующая то же самое:
using System;
class Test
{
const int Size = 100000;
static void Main()
{
object[] array = new object[Size];
long initialMemory = GC.GetTotalMemory(true);
for (int i = 0; i < Size; i++)
{
array[i] = new string[0];
}
long finalMemory = GC.GetTotalMemory(true);
GC.KeepAlive(array);
long total = finalMemory - initialMemory;
Console.WriteLine("Size of each element: {0:0.000} bytes",
((double)total) / Size);
}
}
Но я получаю те же результаты - накладные расходы для любого массива ссылочного типа составляют 16 байтов, тогда как накладные расходы для любого массива типов значений составляют 12 байт. Я все еще пытаюсь понять, почему это так, с помощью спецификации CLI. Не забывайте, что массивы ссылочного типа ковариантны, что может иметь значение ...
РЕДАКТИРОВАТЬ: С помощью cordbg я могу подтвердить ответ Брайана - указатель типа массива ссылочного типа один и тот же независимо от фактический тип элемента. Предположительно, в object.GetType () (который не виртуальный, помните) есть некоторая странность, чтобы учесть это.
Итак, с кодом:
object[] x = new object[1];
string[] y = new string[1];
int[] z = new int[1];
z[0] = 0x12345678;
lock(z) {}
мы получаем что-то вроде следующего :
Variables:
x=(0x1f228c8) <System.Object[]>
y=(0x1f228dc) <System.String[]>
z=(0x1f228f0) <System.Int32[]>
Memory:
0x1f228c4: 00000000 003284dc 00000001 00326d54 00000000 // Data for x
0x1f228d8: 00000000 003284dc 00000001 00329134 00000000 // Data for y
0x1f228ec: 00000000 00d443fc 00000001 12345678 // Data for z
Обратите внимание, что я ' Мы выгружаем память на 1 слово перед значением самой переменной.
Для x и y значения следующие:
- Блок синхронизации , используется для блокировки хэш-кода (или тонкой блокировки - см. комментарий Брайана)
- Указатель типа
- Размер массива
- Указатель типа элемента
- Ссылка на ноль (первый элемент)
Для z значения следующие:
- Блок синхронизации
- Указатель типа
- Размер массива
- 0x12345678 (первый элемент)
Массивы различных типов значений (байт [] , int [] и т. д.) имеют указатели разных типов, тогда как все массивы ссылочных типов используют один и тот же указатель типа, но имеют другой указатель типа элемента. Указатель типа элемента - это то же значение, что и указатель типа для объекта этого типа. Итак, если мы посмотрим на строковый объект ' s память в приведенном выше прогоне, она будет иметь указатель типа 0x00329134.
Слово перед указателем типа определенно имеет что-то , связанное либо с монитором, либо с хэш-кодом: вызов GetHashCode () заполняет этот бит памяти, и я считаю, что объект по умолчанию . GetHashCode () получает блок синхронизации, чтобы гарантировать уникальность хэш-кода на протяжении всего времени существования объекта. Однако простое выполнение lock (x) {} ничего не дало, что меня удивило ...
Все это, кстати, справедливо только для "векторных" типов - в CLR , "векторный" тип - это одномерный массив с нижней границей, равной 0. Другие массивы будут иметь другую компоновку - с одной стороны, им потребуется сохранить нижнюю границу ...
Пока что это имеет были эксперименты, но здесь ' догадки - причина того, что система внедряется именно так. С этого момента я просто предполагаю.
- Все
массивы объектов []могут использовать один и тот же JIT-код. Они будут вести себя таким же образом с точки зрения выделения памяти, доступа к массиву, свойстваLengthи (что важно) размещения ссылок для GC. Сравните это с массивами типов значений, где разные типы значений могут иметь разные «следы» GC (например, у одного может быть байт, а затем ссылка, у других вообще не будет ссылок и т. Д.). Каждый раз, когда вы присваиваете значение внутри объекта
[]среда выполнения должна проверить его действительность. Ему необходимо проверить, что тип объекта, ссылка на который вы используете для нового значения элемента, совместим с типом элемента массива. Например: объект [] y = новая строка [1]; x [0] = новый объект (); // Действительно y [0] = новый объект (); // Недействительно - выдаст исключение
Это ковариация, о которой я упоминал ранее. Теперь, учитывая, что это будет происходить для каждого отдельного присваивания , имеет смысл уменьшить количество косвенных обращений. В частности, я подозреваю, что вы действительно не хотите взорвать кеш, обращаясь к объекту типа для каждого задания, чтобы получить тип элемента. Я подозреваю (а моя сборка x86 недостаточно хороша, чтобы проверить это), что тест выглядит примерно так:
- Является ли значение, которое нужно скопировать, пустой ссылкой? Если да, то ничего страшного. (Готово.)
- Получите указатель типа объекта, на который указывает ссылка.
- Этот указатель типа совпадает с указателем типа элемента (простая проверка двоичного равенства)? Если да, то ничего страшного. (Готово.)
- Совместимо ли присвоение указателя типа с указателем типа элемента? (Гораздо более сложная проверка, с наследованием и задействованными интерфейсами.) Если да, то все в порядке - в противном случае выбросить исключение.
Если мы сможем завершить поиск на первых трех шагах, будет не так много косвенного обращения - что хорошо для того, что должно произойти так же часто, как присваивания массивов. Ничего из этого не должно происходить для присвоения типов значений, потому что это можно проверить статически.
Вот почему я считаю, что массивы ссылочных типов немного больше, чем массивы типов значений.
Отличный вопрос - действительно интересно вникнуть :)
Поскольку управление кучей (поскольку вы имеете дело с GetTotalMemory) может выделять только довольно большие блоки, которые последние выделяются более мелкими кусками для целей программиста с помощью CLR.
I ' Извините за оффтоп, но сегодня утром я нашел интересную информацию о перегрузке памяти.
У нас есть проект, который оперирует огромными объемами данных (до 2 ГБ). В качестве основного хранилища мы используем Dictionary . Фактически созданы тысячи словарей. После изменения на List для ключей и List для значений (мы реализовали IDictionary сами) использование памяти уменьшилось примерно на 30-40%.
Почему?
Массив - это ссылочный тип. Все ссылочные типы несут два дополнительных поля слова. Ссылка на тип и поле индекса SyncBlock, которое, помимо прочего, используется для реализации блокировок в CLR. Таким образом, накладные расходы на ссылочные типы составляют 8 байтов на 32 бита. Вдобавок к этому сам массив также хранит длину, которая составляет еще 4 байта. Это доводит общие накладные расходы до 12 байтов.
И я только что узнал из ответа Джона Скита, что массивы ссылочных типов имеют дополнительные 4 байта накладных расходов. Это можно подтвердить с помощью WinDbg. Оказывается, дополнительное слово - это еще одна ссылка на тип, хранящийся в массиве. Все массивы ссылочных типов хранятся внутри как объект [] с дополнительной ссылкой на объект типа фактического типа. Таким образом, строка [] на самом деле просто объект [] с дополнительной ссылкой на тип string . Подробнее см. Ниже.
Значения, хранящиеся в массивах: Массивы ссылочных типов содержат ссылки на объекты, поэтому каждая запись в массиве имеет размер ссылки (т.е. 4 байта на 32 бита). Массивы типов значений хранят значения встроенными, поэтому каждый элемент будет занимать размер рассматриваемого типа.
Этот вопрос также может представлять интерес: C # List
Gory Details
Рассмотрим следующий код
var strings = new string[1];
var ints = new int[1];
strings[0] = "hello world";
ints[0] = 42;
При прикреплении WinDbg показано следующее:
Сначала давайте посмотрим на массив типов значений.
0:000> !dumparray -details 017e2acc
Name: System.Int32[]
MethodTable: 63b9aa40
EEClass: 6395b4d4
Size: 16(0x10) bytes
Array: Rank 1, Number of elements 1, Type Int32
Element Methodtable: 63b9aaf0
[0] 017e2ad4
Name: System.Int32
MethodTable 63b9aaf0
EEClass: 6395b548
Size: 12(0xc) bytes
(C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
Fields:
MT Field Offset Type VT Attr Value Name
63b9aaf0 40003f0 0 System.Int32 1 instance 42 m_value <=== Our value
0:000> !objsize 017e2acc
sizeof(017e2acc) = 16 ( 0x10) bytes (System.Int32[])
0:000> dd 017e2acc -0x4
017e2ac8 00000000 63b9aa40 00000001 0000002a <=== That's the value
Сначала мы выгружаем массив и один элемент со значением 42. Как можно видеть, размер составляет 16 байтов. Это 4 байта для самого значения int32 , 8 байтов для служебных данных обычного ссылочного типа и еще 4 байта для длины массива.
Необработанный дамп показывает SyncBlock, таблицу методов для int [] , длину и значение 42 (2a в шестнадцатеричном формате). Обратите внимание, что SyncBlock расположен прямо перед ссылкой на объект.
Затем давайте посмотрим на строку [] , чтобы выяснить, для чего используется дополнительное слово.
0:000> !dumparray -details 017e2ab8
Name: System.String[]
MethodTable: 63b74ed0
EEClass: 6395a8a0
Size: 20(0x14) bytes
Array: Rank 1, Number of elements 1, Type CLASS
Element Methodtable: 63b988a4
[0] 017e2a90
Name: System.String
MethodTable: 63b988a4
EEClass: 6395a498
Size: 40(0x28) bytes <=== Size of the string
(C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
String: hello world
Fields:
MT Field Offset Type VT Attr Value Name
63b9aaf0 4000096 4 System.Int32 1 instance 12 m_arrayLength
63b9aaf0 4000097 8 System.Int32 1 instance 11 m_stringLength
63b99584 4000098 c System.Char 1 instance 68 m_firstChar
63b988a4 4000099 10 System.String 0 shared static Empty
>> Domain:Value 00226438:017e1198 <<
63b994d4 400009a 14 System.Char[] 0 shared static WhitespaceChars
>> Domain:Value 00226438:017e1760 <<
0:000> !objsize 017e2ab8
sizeof(017e2ab8) = 60 ( 0x3c) bytes (System.Object[]) <=== Notice the underlying type of the string[]
0:000> dd 017e2ab8 -0x4
017e2ab4 00000000 63b74ed0 00000001 63b988a4 <=== Method table for string
017e2ac4 017e2a90 <=== Address of the string in memory
0:000> !dumpmt 63b988a4
EEClass: 6395a498
Module: 63931000
Name: System.String
mdToken: 02000024 (C:\Windows\assembly\GAC_32\mscorlib\2.0.0.0__b77a5c561934e089\mscorlib.dll)
BaseSize: 0x10
ComponentSize: 0x2
Number of IFaces in IFaceMap: 7
Slots in VTable: 196
Сначала мы выгружаем массив и строка. Затем мы выводим размер строки [] . Обратите внимание, что WinDbg указывает здесь тип как System.Object [] . Размер объекта в этом случае включает саму строку, поэтому общий размер равен 20 из массива плюс 40 для строки.
Сбрасывая необработанные байты экземпляра, мы можем увидеть следующее: Сначала у нас есть SyncBlock, затем следует таблица методов для объекта [] , а затем длина массива. После этого находим дополнительные 4 байта со ссылкой на таблицу методов для строки. Это можно проверить с помощью команды dumpmt, как показано выше. Наконец, мы находим единственную ссылку на фактический экземпляр строки.
В заключение
Накладные расходы для массивов можно разбить следующим образом (на 32 бита)
- 4 байта SyncBlock
- 4 байта для таблицы методов (ссылка на тип) для самого массива
- 4 байта для длины массива
- Массивы ссылочных типов добавляют еще 4 байта для хранения таблицы методов фактического типа элемента (массивы ссылочного типа - это
объект []под капотом)
Т. накладные расходы составляют 12 байтов для массивов типов значений и 16 байтов для массивов ссылочных типов .
Я думаю, вы делаете некоторые ошибочные предположения при измерении, поскольку выделение памяти (через GetTotalMemory) во время вашего цикла может отличаться от фактического требуемого объема памяти только для массивов - память может быть выделена в больших блоках в памяти могут быть другие объекты, которые восстанавливаются во время цикла и т. д.
Вот некоторая информация для вас о накладных расходах массива: