using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication15 {
public static class ArrayExtensions {
public static int GetVectorLength(this double[] array) {
return array.Length;
}
}
class Program {
static void Main(string[] args) {
double[] array = new double[10];
int length = array.GetVectorLength();
}
}
}
Быстрый вектор на C#
Передо мной состоит следующая задача:
Реализация класса вектора на С#
Время запросов элемента вектора является критичным, поэтому решение типа:
Таковым не является.
Как решение я создал структуру
Это повысило скорость работы с вектором, но возникла проблема иного рода:
vector a = /..../;
vector b = a;
И казалось бы по правилам С# должны получиться две независимые структуры, но эти структуры имеют внутри себя ссылку на один и тот же массив.
Приходиться делать:
vector b = a.clone();
Поэтому хотелось бы унаследовать класс вектора непосрелдственно от double[]. Но это вроде как невозможно(даж от Array не унаследуешь).
Что можете посоветовать....?
Реализация класса вектора на С#
Время запросов элемента вектора является критичным, поэтому решение типа:
Код:
public class vector { protected double[]; }
Таковым не является.
Как решение я создал структуру
Код:
public struct vector { protected double[]; }
Это повысило скорость работы с вектором, но возникла проблема иного рода:
vector a = /..../;
vector b = a;
И казалось бы по правилам С# должны получиться две независимые структуры, но эти структуры имеют внутри себя ссылку на один и тот же массив.
Приходиться делать:
vector b = a.clone();
Поэтому хотелось бы унаследовать класс вектора непосрелдственно от double[]. Но это вроде как невозможно(даж от Array не унаследуешь).
Что можете посоветовать....?
Цитата: sigmov
Что можете посоветовать....?
Насколько серьезно расширяется функционал таких массивов? Если элементарно методы, то в C# 3.0 есть "методы-расширения" классов:
Код:
Другой вариант - использование буферов фиксированного размера:
Код:
public unsafe struct MyVector {
public const int BUFFER_SIZE = 10;
public fixed double Buffer[BUFFER_SIZE];
}
public const int BUFFER_SIZE = 10;
public fixed double Buffer[BUFFER_SIZE];
}
Цитата: hardcase
Насколько серьезно расширяется функционал таких массивов? Если элементарно методы, то в C# 3.0 есть "методы-расширения" классов:
Помимо расширить функционал, необходимо сокрыть базовый функционал System.Array, поэтому использовать методы-расширения это не выход.
Кроме того это будет неэтично.
Цитата: hardcase
Другой вариант - использование буферов фиксированного размера:
Вариант тоже не пойдойдет так как размер может варироваться от 2 до n.
Цитата: sigmov
Вариант тоже не пойдойдет так как размер может варироваться от 2 до n.
Если размер массива такой уж большой, то здесь вряд ли поможет использование векторов. Вообще, в гайдлайнах по дизайну типов CLR написано про структуры:
[quote=Microsoft guideline]
- It logically represents a single value, similar to primitive types (integer, double, and so on).
- It has an instance size smaller than 16 bytes.
- It is immutable.
- It will not have to be boxed frequently.
Источник.
Обратите внимание на пункт 3. Именно с ним связаны ваши проблемы. Вы строите тип таким образом, что массив, поверх которого построен struct, модифицируется. Вообще конструировать вектор лучше поверх массива, но не позволять модифицирование этого массива (вспомните класс System.String и его методы). Все операции над вектором (типа сложения, перемножения) нужно реализовать так, что результатом их становится новый вектор с новым массивом внутри, благо выделение памяти в дотнете это фактически бесплатная операция.
З.Ы. В качестве оптимизации можно попробовать совместить два решения: массив и фиксированный буфер. Если вектор мал (3-4 элемента), то использовать внутренний буфер, если велик - то использовать массив.
Цитата: hardcase
Обратите внимание на пункт 3. Именно с ним связаны ваши проблемы. Вы строите тип таким образом, что массив, поверх которого построен struct, модифицируется. Вообще конструировать вектор лучше поверх массива, но не позволять модифицирование этого массива (вспомните класс System.String и его методы). Все операции над вектором (типа сложения, перемножения) нужно реализовать так, что результатом их становится новый вектор с новым массивом внутри, благо выделение памяти в дотнете это фактически бесплатная операция.
Ну допустим - требуется изменить один(!) из элементов вектора из 500 элементов - получиться что я должен буду выделить память на новый массив и перенести туда 499 элементов, возвернуть новый вектор содержащий полученный массива.
А если потребуется в процессе алгоритма 1000000 раз изменять элементы? - скок КРИТИЧЕСКИ важного времени уйдет только на зачистку памяти от "устаревших" массивов! Не говоря уже о небесплатных операциях копирования массивов!
Цитата: hardcase
З.Ы. В качестве оптимизации можно попробовать совместить два решения: массив и фиксированный буфер. Если вектор мал (3-4 элемента), то использовать внутренний буфер, если велик - то использовать массив.
Тогда придется еще и хранить размерность массива и затраты времени на кодирование вырастут и думаю издежки такого метода превысят "+".
Цитата: sigmov
Ну допустим - требуется изменить один(!) из элементов вектора из 500 элементов
Ну, при таких "объемах производства" имеет смысл использовать оболочку в виде класса, и одним из ее свойств выставлять наружу ссылку на массив. Для тяжелых операций над вектором использовать именно эту ссылку.
Цитата: hardcase
Ну, при таких "объемах производства" имеет смысл использовать оболочку в виде класса, и одним из ее свойств выставлять наружу ссылку на массив. Для тяжелых операций над вектором использовать именно эту ссылку.
Если бы я делал для себя - то я бы поверьте так не заморачивался - вообще бы не делал "обертки" над массивами, а наделал бы расширений и использовал их!
Цитата: hardcase
Вы строите тип таким образом, что массив, поверх которого построен struct, модифицируется. Вообще конструировать вектор лучше поверх массива, но не позволять модифицирование этого массива (вспомните класс System.String и его методы). Все операции над вектором (типа сложения, перемножения) нужно реализовать так, что результатом их становится новый вектор с новым массивом внутри, благо выделение памяти в дотнете это фактически бесплатная операция.
Совершенно верно: это и есть value-object - паттерн проектирования, пришедший к нам из Java, где значащие типы нативно не поддерживаются. Я и от себя скажу, что модификатор readonly в структурах надо бы тыкать почаще - так проблем меньше. А по поводу случая, когда модифицируется всего одно значение, скажу следующее: абстрактные абстракции хороши в библиотеках, поскольку их предметная область не очерчена формально (то есть, автор библиотеки не может угадать все варианты её использования). Прикладным системам это ни к чему. Значения вектора изменяются ведь в результате какой-то вычислительной операции - вот и включите её в вектор, всего-то и делов.
Мне вот вопрос неудовлетворённости решением class Vector { double[] _data; } интересует вот в каком плане: у вас есть измеримые доводы, говорящие о том, что с производительностью вектора нужно что-то делать, или же это досужьи домыслы? Я, как обычно, взял да и проверил: описал три типа данных по прототипу
Код:
public interface IVector
{
double this[int index] { get; set; }
int Length { get; }
}
public class RefVector : IVector
{
public RefVector(int length)
{
_data = new double[length];
}
public double this[int index]
{
get { return _data[index]; }
set { _data[index] = value; }
}
public int Length
{
get { return _data.Length; }
}
readonly double[] _data;
}
{
double this[int index] { get; set; }
int Length { get; }
}
public class RefVector : IVector
{
public RefVector(int length)
{
_data = new double[length];
}
public double this[int index]
{
get { return _data[index]; }
set { _data[index] = value; }
}
public int Length
{
get { return _data.Length; }
}
readonly double[] _data;
}
Код:
static readonly Random _random = new Random();
static void Frobnicate(IVector vector)
{
var length = vector.Length;
vector[_random.Next() % length] = Math.Sin(vector[_random.Next() % length]);
vector[_random.Next() % length] = Math.Cos(vector[_random.Next() % length]);
}
static void Frobnicate(IVector vector)
{
var length = vector.Length;
vector[_random.Next() % length] = Math.Sin(vector[_random.Next() % length]);
vector[_random.Next() % length] = Math.Cos(vector[_random.Next() % length]);
}
Код:
public static void TestRef(int vector_length)
{
for (var i = 0; i < 1000000; i++)
{
var vector = new RefVector(vector_length);
for (var j = 0; j < vector_length * 2; j++)
Frobnicate(vector);
}
}
{
for (var i = 0; i < 1000000; i++)
{
var vector = new RefVector(vector_length);
for (var j = 0; j < vector_length * 2; j++)
Frobnicate(vector);
}
}
Цитата: Der Meister
Мне вот вопрос неудовлетворённости решением class Vector { double[] _data; } интересует вот в каком плане: у вас есть измеримые доводы, говорящие о том, что с производительностью вектора нужно что-то делать, или же это досужьи домыслы?
Всмотревшись в результаты уважаемого Der Meister, решил сам проверить:
Код:
struct SVec
{
double[] Arr;
public SVec(int size) { Arr = new double[size]; }
public double this[int j]
{
get { return Arr[j];}
set { Arr[j]=value; }
}
}
class CVec
{
double[] Arr;
public CVec(int size) { Arr = new double[size]; }
public double this[int j]
{
get { return Arr[j]; }
set { Arr[j] = value; }
}
}
static void Main(string[] args)
{
CVec cv = new CVec(100);
DateTime T = DateTime.Now;
for (int i = 0; i < 1000000; i++)
for (int j = 0; j < 100; j++)
cv[j] = j;
Console.WriteLine(DateTime.Now - T);
SVec sv = new SVec(100);
T = DateTime.Now;
for (int i = 0; i < 1000000; i++)
for (int j = 0; j < 100; j++)
sv[j] = j;
Console.WriteLine(DateTime.Now - T);
{
double[] Arr;
public SVec(int size) { Arr = new double[size]; }
public double this[int j]
{
get { return Arr[j];}
set { Arr[j]=value; }
}
}
class CVec
{
double[] Arr;
public CVec(int size) { Arr = new double[size]; }
public double this[int j]
{
get { return Arr[j]; }
set { Arr[j] = value; }
}
}
static void Main(string[] args)
{
CVec cv = new CVec(100);
DateTime T = DateTime.Now;
for (int i = 0; i < 1000000; i++)
for (int j = 0; j < 100; j++)
cv[j] = j;
Console.WriteLine(DateTime.Now - T);
SVec sv = new SVec(100);
T = DateTime.Now;
for (int i = 0; i < 1000000; i++)
for (int j = 0; j < 100; j++)
sv[j] = j;
Console.WriteLine(DateTime.Now - T);
Результаты действительно оказались ОДИНАКОВЫМИ
Видимо я изначально находился в заблуждении. Но дописав полностью Вектор - проверю его быстродействие и со struct и c class.