I need a 2D array which is expandable in all directions and strictly tracks overall positioning of each element, but is most efficient at read.
我需要一个二维数组，它可以向各个方向展开，严格跟踪每个元素的整体定位，但在读取方面效率最高。
The use case I face is as follows: I am colliding and mashing 2D tectonic plates into one another. When they collide, they can shrink, grow, or neither. Every iteration, all elements are likely to be accessed, so read time is very important. They must be able to grow/shrink on all sides as well, and can contain holes and convex structures.
我所面临的用例如下:我正在碰撞并将二维的构造板块相互碰撞。当它们碰撞时，它们会收缩、生长，或者两者都不会。每次迭代，所有元素都可能被访问，所以读取时间非常重要。它们必须能够生长/收缩的所有方面，并可以包含孔和凸结构。
Memory is not a huge issue, but I'd like to save it where I can. My main concern is speed, as the old proof of concept this is loosely based on written in C++ takes 15 minutes to run, and I am adding substantially to the original concept.
记忆不是一个大问题，但我想把它保存在我能保存的地方。我主要关心的是速度，因为旧的概念证明是基于c++编写的，需要15分钟的时间来运行，而我正在大量增加最初的概念。
I initially thought of using a dictionary with coordinates, but this poses the issue of read times; dictionaries are slow when something they do not have a key for is requested, and this will happen often.
我最初想用一本有坐标的字典，但这就带来了阅读时间的问题;当一些字典没有键的东西被请求时，字典会变慢，这种情况经常发生。
I'm considering using a List<List<MyCLass>> structure now, using null class objects for empty locations.
我现在考虑使用List
>结构，空位置使用null类对象。
Another idea I had was to use an algebraic array (y * stride + x), but would rather avoid the complications thereof, and it would be both hard to build and maintain.
我的另一个想法是使用代数数组(y * stride + x)，但我宁愿避免它的复杂性，而且它也很难构建和维护。
So, essentially, what is the best way to have a very large 2D data set which is constantly accessed and frequently modified in C#?
那么，从本质上讲，拥有一个很大的2D数据集的最佳方式是什么?
EDIT: As requested; The arrays will likely be between 50x50 and 1000x1000 each, and there will be 10-30 at any given time. the overall 'world' will be 512x512 to 4096x4096 in size (set at start of simulation), with approximately 20% overlap max (excluding edge cases). However, up to 50% of each 2D plate will be empty space in a Cartesian system, so with a uniform size this would mean the actual size of arrays would be double that, so at most, approximately 20,132,659 non-null array elements, and a little less than that in null elements total in the simulation.
编辑:要求;数组可能在50x50和1000x1000之间，并且在任何给定的时间都有10-30个。整体的“世界”将是512x512到4096x4096的尺寸(在模拟开始时设置)，大约有20%的重叠最大值(不包括边界情况)。然而,多达50%的每个2 d板将在笛卡尔空间系统,用一个统一的大小这意味着数组的实际大小的两倍,所以最多,大约有20132659名非空数组元素,少一点总比空元素模拟。
I'm OK with this program taking up to several hours to complete a sim, but I worry that it will take days. That's why I am trying to come up with optimal ways to handle these data sets.
我可以接受这个程序需要几个小时来完成一个sim卡，但是我担心这需要几天的时间。这就是为什么我试图想出处理这些数据集的最佳方法。
2 个解决方案
#1
3
If you insist on having an expandable 2D array (matrix) then consider the following:
如果您坚持使用可扩展的2D数组(matrix)，请考虑以下内容:
public class Matrix<T> : Collection<T>
{
int row_count, col_count;
List<T> _list; //reference to inner list
T[] _items; //reference to inner array within inner list
public Matrix(int row_count, int col_count)
: this(row_count, col_count, new T[row_count*col_count])
{
if(row_count==0||col_count==0)
{
throw new NotSupportedException();
}
}
Matrix(int row_count, int col_count, T[] values)
: base(new List<T>(values))
{
// internal data arranged in 1D array, by rows.
this._list=base.Items as List<T>;
this.row_count=row_count;
this.col_count=col_count;
LinkInnerArray();
}
private void LinkInnerArray()
{
this._items=typeof(List<T>).GetField("_items",
System.Reflection.BindingFlags.NonPublic
|System.Reflection.BindingFlags.Instance).GetValue(base.Items) as T[];
}
public int RowCount { get { return row_count; } }
public int ColCount { get { return col_count; } }
public T[] Elements { get { return _list.ToArray(); } }
public T this[int row, int col]
{
get { return base[col_count*row+col]; }
set { base[col_count*row+col]=value; }
}
public T[] GetRow(int row)
{
if(row<0||row>=row_count) new IndexOutOfRangeException();
T[] result=new T[col_count];
lock(_items)
{
// fast array copy
Array.Copy(_items, col_count*row, result, 0, result.Length);
}
return result;
}
public T[] GetColumn(int column)
{
if(column<0||column>=col_count) new IndexOutOfRangeException();
T[] result=new T[row_count];
lock(_items)
{
// No shortcut exists, only if C# was more like FORTRAN
for(int i=0; i<row_count; i++)
{
result[i]=base[col_count*i+column];
}
}
return result;
}
public void SetRow(int row, params T[] values)
{
if(values==null||values.Length==0) return;
if(row<0||row>=row_count) new IndexOutOfRangeException();
// fast array copy
lock(_items)
{
Array.Copy(values, 0, _items, col_count*row, values.Length);
}
}
public void SetColumn(int column, params T[] values)
{
if(values==null||values.Length==0) return;
if(column<0||column>=col_count) new IndexOutOfRangeException();
lock(_items)
{
// No shortcut exists, only if C# was more like FORTRAN
for(int i=0; i<values.Length; i++)
{
base[col_count*i+column]=values[i];
}
}
}
public void AddRow(params T[] new_row)
{
lock(_list)
{
// add array to last row
T[] row=new T[col_count];
Array.Copy(new_row, 0, row, 0, new_row.Length);
_list.AddRange(row);
LinkInnerArray();
this.row_count++;
}
}
public void AddColumn(params T[] new_column)
{
lock(_list)
{
// go add an item on end of each row
for(int i=row_count-1; i>=0; i--)
{
T item=i<new_column.Length?new_column[i]:default(T);
_list.Insert(col_count*i+row_count-1, item);
}
LinkInnerArray();
this.col_count++;
}
}
public Matrix<R> Transform<R>(Func<T, R> operation)
{
R[] values=new R[row_count*col_count];
for(int i=0; i<values.Length; i++)
{
values[i]=operation(base[i]);
}
return new Matrix<R>(row_count, col_count, values);
}
public Matrix<R> Combine<R>(Matrix<T> other, Func<T, T, R> operation)
{
R[] values=new R[row_count*col_count];
for(int i=0; i<values.Length; i++)
{
values[i]=operation(base[i], other[i]);
}
return new Matrix<R>(row_count, col_count, values);
}
}
class Program
{
static void Main(string[] args)
{
int N=4;
var A=new Matrix<int>(N, N);
// initialize diagonal
for(int i=0; i<N; i++)
{
A[i, i]=1;
}
// A =
// | 1 0 0 0 |
// | 0 1 0 0 |
// | 0 0 1 0 |
// | 0 0 0 1 |
A.AddRow(5, 4, 3, 2);
A.AddColumn(1, 2, 3, 4, 5);
// A =
// | 1 0 0 0 1 |
// | 0 1 0 0 2 |
// | 0 0 1 0 3 |
// | 0 0 0 1 4 |
// | 5 4 3 2 5 |
var B=A.Transform(delegate(int x) { return 5-x; });
// B =
// | 4 5 5 5 4 |
// | 5 4 5 5 3 |
// | 5 5 4 5 2 |
// | 5 5 5 4 1 |
// | 0 1 2 3 0 |
var C=A.Combine(B, delegate(int x, int y) { return y-x; });
// C =
// | 3 5 5 5 3 |
// | 5 3 5 5 1 |
// | 5 5 3 5 -1 |
// | 5 5 5 3 -3 |
// |-5 -3 -1 1 -5 |
}
}
#2
1
It depends on how you are reading your Collections.
这取决于你如何阅读你的收藏。
For example, if you are looping through each element then a List will always be faster than a dictionary.
例如，如果对每个元素进行循环，那么列表总是比字典快。
List<List<Item>> collection = new List<List<Items>>();
//add items
for(List l : collection){
for(Item i : l){
//do something with item
}
}
If you're looking up indexes, based on a "key" value, then the dictionary will always be faster (constant vs linear).
如果您正在查找索引，基于“键”值，那么字典将总是更快(常量vs线性)。
Dictionary<String,List<Item>> collection = new Dictionary<String,List<Items>>();
//add items
List<String> keysWeNeedToWorkOn = new List<String>();
//add keys we care about
for(String key : keysWeNeedToWorkOn){
for(Item i : collection.get(key)){
// do something with this item
}
}
This Big O Cheat sheet might be helpful for you to decide exactly what you need.
这张大大的O小抄可能对你决定你到底需要什么很有帮助。
#1
3
If you insist on having an expandable 2D array (matrix) then consider the following:
如果您坚持使用可扩展的2D数组(matrix)，请考虑以下内容:
public class Matrix<T> : Collection<T>
{
int row_count, col_count;
List<T> _list; //reference to inner list
T[] _items; //reference to inner array within inner list
public Matrix(int row_count, int col_count)
: this(row_count, col_count, new T[row_count*col_count])
{
if(row_count==0||col_count==0)
{
throw new NotSupportedException();
}
}
Matrix(int row_count, int col_count, T[] values)
: base(new List<T>(values))
{
// internal data arranged in 1D array, by rows.
this._list=base.Items as List<T>;
this.row_count=row_count;
this.col_count=col_count;
LinkInnerArray();
}
private void LinkInnerArray()
{
this._items=typeof(List<T>).GetField("_items",
System.Reflection.BindingFlags.NonPublic
|System.Reflection.BindingFlags.Instance).GetValue(base.Items) as T[];
}
public int RowCount { get { return row_count; } }
public int ColCount { get { return col_count; } }
public T[] Elements { get { return _list.ToArray(); } }
public T this[int row, int col]
{
get { return base[col_count*row+col]; }
set { base[col_count*row+col]=value; }
}
public T[] GetRow(int row)
{
if(row<0||row>=row_count) new IndexOutOfRangeException();
T[] result=new T[col_count];
lock(_items)
{
// fast array copy
Array.Copy(_items, col_count*row, result, 0, result.Length);
}
return result;
}
public T[] GetColumn(int column)
{
if(column<0||column>=col_count) new IndexOutOfRangeException();
T[] result=new T[row_count];
lock(_items)
{
// No shortcut exists, only if C# was more like FORTRAN
for(int i=0; i<row_count; i++)
{
result[i]=base[col_count*i+column];
}
}
return result;
}
public void SetRow(int row, params T[] values)
{
if(values==null||values.Length==0) return;
if(row<0||row>=row_count) new IndexOutOfRangeException();
// fast array copy
lock(_items)
{
Array.Copy(values, 0, _items, col_count*row, values.Length);
}
}
public void SetColumn(int column, params T[] values)
{
if(values==null||values.Length==0) return;
if(column<0||column>=col_count) new IndexOutOfRangeException();
lock(_items)
{
// No shortcut exists, only if C# was more like FORTRAN
for(int i=0; i<values.Length; i++)
{
base[col_count*i+column]=values[i];
}
}
}
public void AddRow(params T[] new_row)
{
lock(_list)
{
// add array to last row
T[] row=new T[col_count];
Array.Copy(new_row, 0, row, 0, new_row.Length);
_list.AddRange(row);
LinkInnerArray();
this.row_count++;
}
}
public void AddColumn(params T[] new_column)
{
lock(_list)
{
// go add an item on end of each row
for(int i=row_count-1; i>=0; i--)
{
T item=i<new_column.Length?new_column[i]:default(T);
_list.Insert(col_count*i+row_count-1, item);
}
LinkInnerArray();
this.col_count++;
}
}
public Matrix<R> Transform<R>(Func<T, R> operation)
{
R[] values=new R[row_count*col_count];
for(int i=0; i<values.Length; i++)
{
values[i]=operation(base[i]);
}
return new Matrix<R>(row_count, col_count, values);
}
public Matrix<R> Combine<R>(Matrix<T> other, Func<T, T, R> operation)
{
R[] values=new R[row_count*col_count];
for(int i=0; i<values.Length; i++)
{
values[i]=operation(base[i], other[i]);
}
return new Matrix<R>(row_count, col_count, values);
}
}
class Program
{
static void Main(string[] args)
{
int N=4;
var A=new Matrix<int>(N, N);
// initialize diagonal
for(int i=0; i<N; i++)
{
A[i, i]=1;
}
// A =
// | 1 0 0 0 |
// | 0 1 0 0 |
// | 0 0 1 0 |
// | 0 0 0 1 |
A.AddRow(5, 4, 3, 2);
A.AddColumn(1, 2, 3, 4, 5);
// A =
// | 1 0 0 0 1 |
// | 0 1 0 0 2 |
// | 0 0 1 0 3 |
// | 0 0 0 1 4 |
// | 5 4 3 2 5 |
var B=A.Transform(delegate(int x) { return 5-x; });
// B =
// | 4 5 5 5 4 |
// | 5 4 5 5 3 |
// | 5 5 4 5 2 |
// | 5 5 5 4 1 |
// | 0 1 2 3 0 |
var C=A.Combine(B, delegate(int x, int y) { return y-x; });
// C =
// | 3 5 5 5 3 |
// | 5 3 5 5 1 |
// | 5 5 3 5 -1 |
// | 5 5 5 3 -3 |
// |-5 -3 -1 1 -5 |
}
}
#2
1
It depends on how you are reading your Collections.
这取决于你如何阅读你的收藏。
For example, if you are looping through each element then a List will always be faster than a dictionary.
例如，如果对每个元素进行循环，那么列表总是比字典快。
List<List<Item>> collection = new List<List<Items>>();
//add items
for(List l : collection){
for(Item i : l){
//do something with item
}
}
If you're looking up indexes, based on a "key" value, then the dictionary will always be faster (constant vs linear).
如果您正在查找索引，基于“键”值，那么字典将总是更快(常量vs线性)。
Dictionary<String,List<Item>> collection = new Dictionary<String,List<Items>>();
//add items
List<String> keysWeNeedToWorkOn = new List<String>();
//add keys we care about
for(String key : keysWeNeedToWorkOn){
for(Item i : collection.get(key)){
// do something with this item
}
}
This Big O Cheat sheet might be helpful for you to decide exactly what you need.
这张大大的O小抄可能对你决定你到底需要什么很有帮助。