多维数组与字典性能

Question

我需要使用x,y,z坐标(仅限整数)对大型bool集进行查找.我试图确定一个块是否可以在x,y,z位置遍历.

目前我正在使用数组bool[,,].然而,这不是非常灵活,并且对于尺寸合适的地图,尺寸很快变得很大.

我认为只有真正价值观的字典会更灵活,内存更少.我创建了一个结构Vector3Int来保存x,y,z值并用作字典键.字典看起来像Dictionary<Vector3Int, bool>.

但是,使用此键进行字典查找似乎比使用x,y,z整数的数组查找慢20-100倍.

有没有更快/更好的方法来做到这一点？我使用查找进行路径查找,因此查找需要非常快,因为单个路径可能有数百/数千个查找.

Vector3Int代码:

public struct Vector3Int
{
public int x,y,z;

public Vector3Int(int x, int y, int z)
{
    this.x =x;
    this.y=y;
    this.z=z;
}

//checks for equality
public static bool operator ==(Vector3Int a, Vector3Int b)
{
    return a.x==b.x && a.y ==b.y && a.z ==b.z;
}

public override bool Equals(object obj)
{
    return obj is Vector3Int && this == (Vector3Int)obj;
}

public override int GetHashCode ()
{
    return x.GetHashCode() ^ y.GetHashCode() ^ z.GetHashCode();
}

//checks the two vectors for non-equality
public static bool operator !=(Vector3Int a, Vector3Int b)
{
    return !(a==b);
}
}

数组查找:

bool[,,] worldWalkable= new bool[1000,1000,1000];

public bool CheckWalkable(int x, int y, int z)
{
    return worldWalkable[x,y,z];
}

与字典查找:

Dictionary<Vector3Int, bool> worldTraversable = new Dictionary<Vector3Int, bool>();

public bool CheckTraversable(Vector3Int block)
{
    bool tempBool;
    worldTraversable.TryGetValue(block, tempBool);
    return tempBool;
} 

测试代码:

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class SpeedTest : MonoBehaviour {

Dictionary<Vector3Int, bool> testDict;
bool[,,] testArray;

// Use this for initialization
void Start () 
{
    InitializeContainers();
    RunTest();

}

void InitializeContainers()
{
    testDict= new Dictionary<Vector3Int, bool>(1000);
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            for(int k=0; k<10; k++)
            {
                testDict[new Vector3Int(i,j,k)]=true;
            }
        }
    }

    testArray=new bool[10,10,10];
}

void RunTest()
{
    bool tempBool;
    float timer1, timer2;

    timer1=Time.realtimeSinceStartup;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            for(int k=0; k<10; k++)
            {
                tempBool= testDict[new Vector3Int(i,j,k)];
            }
        }
    }
    timer2=Time.realtimeSinceStartup;
    Debug.Log("Dictionary completion time: "+(timer2-timer1)*1000+"ms");

    timer1=Time.realtimeSinceStartup;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            for(int k=0; k<10; k++)
            {
                tempBool=testArray[i,j,k];
            }
        }
    }
    timer2=Time.realtimeSinceStartup;

    Debug.Log("Array completion time: "+(timer2-timer1)*1000+"ms");
}
}

编辑:修复了修复问题的结构:

using UnityEngine;
using System.Collections;
using System;
using System.Collections.Generic;

//makes a Vector3 of integers
public struct Vector3Int : IEquatable<Vector3Int>
{
public int x,y,z;

public Vector3Int(int x, int y, int z)
{
    this.x =x;
    this.y=y;
    this.z=z;
}

public bool Equals(Vector3Int other)
{
    return other.x==this.x && other.y==this.y && other.z==this.z;
}

public static bool operator ==(Vector3Int a, Vector3Int b)
{
    return a.Equals(b);
}

public override bool Equals(object obj)
{
    if(obj==null || !(obj is Vector3Int))
        return false;

    return Equals((Vector3Int)obj);
}

public override int GetHashCode ()
{
    return x ^ (y<<10) ^ (z<<10);
}

public override string ToString ()
{
    return string.Format ("("+x+", "+y+", "+z+")");
}

public static bool operator !=(Vector3Int a, Vector3Int b)
{
    return !(a==b);
}
}

问题是像阿列克谢建议的拳击/拆箱.使用此链接中的说明来解决问题.

Answer 1

关于右对阵阵的20-100个差异声音Dictionary.这取决于数据集的大小以及它是否适合CPU缓存.Dictionary除了执行单个加载指令和一些地址计算之外,还有很多其他功能.它也是O(1),但具有更高的常数因子.

Dictionary通过实现自己的哈希表并删除不需要的东西,你可以比内置更快几次(比如3倍).特别%是它使用的操作非常慢.当您使用位掩码替换它时,这会立即显示在配置文件上作为改进.

另请注意,您的哈希函数可能会产生大量冲突.例如,相同坐标的所有排列都散列到相同的槽.我试试rotate(x, 23) ^ rotate(y, 11) ^ z.

Answer 2

通常，您可以通过使用适当的通用方法来显着加快对结构的操作，从而消除装箱/拆箱的需要。

如果Dictionary实施IEquatable<T>是一个好的起点：

public struct Vector3Int : IEquatable<Vector3Int>
{
    public int x,y,z;

    public bool Equals(Vector3Int other)
    {
       return  x == other.x && y == other.y && z == other.z;
    }

    public override int GetHashCode ()
    {
        return x^ (y <<5)^ (z << 5);
    }
    ....

请注意，您仍然需要保持体面GetHashCode以避免碰撞。如果您的范围有限（即 0-1024），您可能会使用非常基本的方法<<10来获得完美的哈希函数。否则，请查看提供的其他链接，例如覆盖 System.Object.GetHashCode 的最佳算法是什么？