用其他数据结构替换二维数组
我有一个复杂的问题，我不知道我是否能恰当地描述它。
我有一个类的对象的二维数组。目前，我的算法只在这个二维数组上运行，但只占用了该数组的一些位置。(接近40%)
它对于小数据集工作得很好，但是如果我有大数据集( 2d数组中的大量元素，例如10000)，那么程序就会耗尽内存。因为我有10000 * 10000 = 100000000次迭代的嵌套循环。
我可以用Hashtable或其他数据结构替换2D数组吗？我的主要目标是通过改变数据结构来减少迭代次数。
请原谅我没有很好地解释。我正在使用C#进行开发
回答 4
Stack Overflow用户
发布于 2011-09-03 02:53:59
听起来您拥有的数据结构是一个稀疏矩阵，我将向您介绍Are there any storage optimized Sparse Matrix implementations in C#?
Stack Overflow用户
发布于 2011-09-03 03:09:22
您可以从数组坐标创建字典的键。类似于：
int key = x * 46000 + y;(这自然适用于类似于46000x46000的数组的坐标，这大约是您在int中可以容纳的大小。如果需要表示更大的数组，可以使用long值作为键。)
有了这个键，您就可以在Dictionary<int, YourClass>中存储和检索对象。从字典中存储和检索值非常快，并不比使用数组慢多少。
您可以迭代字典中的项，但您不会以可预测的顺序获得它们，即不同于循环数组的x和y坐标。
Stack Overflow用户
发布于 2011-09-03 03:26:05
如果您需要高性能，您可以降低自己的数据结构。如果对象只能包含在一个容器中，并且不能移动到其他容器中，则可以使用类似于数据结构的自定义哈希集。
将X、Y和Next字段添加到类中。您可以为存储在数组中的对象创建一个单链表，该数组就是您的哈希表。这可以非常非常快。
我从头开始写的，可能有bug。Clear和rehash都没有实现，这只是一个演示。所有运算的平均复杂度为O(1)。
为了便于在跳过空节点的所有节点上枚举，有一个双向链表。从双向链表中插入和删除的复杂度为O(1)，并且您将能够枚举跳过未使用节点的所有节点，因此枚举所有节点的复杂度为O(n)，其中n是节点的数量，而不是这个稀疏矩阵的“虚拟”大小。
使用双向链接表，您可以按照插入项的相同顺序枚举项。该顺序与X和Y坐标无关。
public class Node
{
internal NodeTable pContainer;
internal Node pTableNext;
internal int pX;
internal int pY;
internal Node pLinkedListPrev;
internal Node pLinkedListNext;
}
public class NodeTable :
IEnumerable<Node>
{
private Node[] pTable;
private Node pLinkedListFirst;
private Node pLinkedListLast;
// Capacity must be a prime number great enough as much items you want to store.
// You can make this dynamic too but need some more work (rehashing and prime number computation).
public NodeTable(int capacity)
{
this.pTable = new Node[capacity];
}
public int GetHashCode(int x, int y)
{
return (x + y * 104729); // Must be a prime number
}
public Node Get(int x, int y)
{
int bucket = (GetHashCode(x, y) & 0x7FFFFFFF) % this.pTable.Length;
for (Node current = this.pTable[bucket]; current != null; current = current.pTableNext)
{
if (current.pX == x && current.pY == y)
return current;
}
return null;
}
public IEnumerator<Node> GetEnumerator()
{
// Replace yield with a custom struct Enumerator to optimize performances.
for (Node node = this.pLinkedListFirst, next; node != null; node = next)
{
next = node.pLinkedListNext;
yield return node;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public bool Set(int x, int y, Node node)
{
if (node == null || node.pContainer != null)
{
int bucket = (GetHashCode(x, y) & 0x7FFFFFFF) % this.pTable.Length;
for (Node current = this.pTable[bucket], prev = null; current != null; current = current.pTableNext)
{
if (current.pX == x && current.pY == y)
{
this.fRemoveFromLinkedList(current);
if (node == null)
{
// Remove from table linked list
if (prev != null)
prev.pTableNext = current.pTableNext;
else
this.pTable[bucket] = current.pTableNext;
current.pTableNext = null;
}
else
{
// Replace old node from table linked list
node.pTableNext = current.pTableNext;
current.pTableNext = null;
if (prev != null)
prev.pTableNext = node;
else
this.pTable[bucket] = node;
node.pContainer = this;
node.pX = x;
node.pY = y;
this.fAddToLinkedList(node);
}
return true;
}
prev = current;
}
// New node.
node.pContainer = this;
node.pX = x;
node.pY = y;
// Add to table linked list
node.pTableNext = this.pTable[bucket];
this.pTable[bucket] = node;
// Add to global linked list
this.fAddToLinkedList(node);
return true;
}
return false;
}
private void fRemoveFromLinkedList(Node node)
{
Node prev = node.pLinkedListPrev;
Node next = node.pLinkedListNext;
if (prev != null)
prev.pLinkedListNext = next;
else
this.pLinkedListFirst = next;
if (next != null)
next.pLinkedListPrev = prev;
else
this.pLinkedListLast = prev;
node.pLinkedListPrev = null;
node.pLinkedListNext = null;
}
private void fAddToLinkedList(Node node)
{
node.pLinkedListPrev = this.pLinkedListLast;
this.pLinkedListLast = node;
if (this.pLinkedListFirst == null)
this.pLinkedListFirst = node;
}
}https://stackoverflow.com/questions/7287971
复制相似问题
腾讯云开发者
