c# - 在列表/数组中查找元素的更快方法

Question

我正在开发一个有限元程序，其中我的输入是节点列表 (ListNodes double[node_index, x, y, z] where (x,y,z) 是笛卡尔系统中节点的坐标)，一个元素列表 (ListElements double[element_index, node1_index, node2_index, etc]) 和每个元素的一些数据 (double[ element_index]).

我必须不断地在有限元模型中的某个给定区域搜索数据，一个区域由一些绑定(bind) [xmin, xmax, ymin, ymax, zmin, zmax] 定义。为了检索该区域的数据，我首先查找它的节点(搜索 (x,y,z) 在边界内的节点)然后查找它的元素并最终检索数据这样的元素。

函数一:检查节点是否在区域内

private static bool IsBounded(double[] node, double xmin, double ymin, double zmin, double xmax, double ymax, double zmax)
{
    return ((node[1] >= xmin) && (node[1] <= xmax) && (node[2] >= ymin) && (node[2] <= ymax) && (node[3] >= zmin) && (node[3] <= zmax));
}

功能2:检查所有节点，找到zone内的节点，加入zoneNodes

ListPoint.Where(node => IsBounded(node, xmin, ymin, zmin, xmax, ymax, zmax)).ToList().ForEach(node => zoneNodes.Add(Convert.ToInt32(node[0])));

功能3:查找区域内的元素

// Loop over all elements
for (int j = 0; j < ListElement.Count; j++)
{
    int status = 0;
    for (int i = 1; i < ElementList[j].Count; i++)
    {
        // For each element, check how many nodes are inside the zone
        if (zoneNodes.Contains(Convert.ToInt32(ListElement[j][i])))
        {
            status++;
        }
    }

    // If all the nodes of this element are inside the zone then the element is inside the zone
    if (status == ListElement[j].Count - 1)
    {
        zoneElements.Add(Convert.ToInt32(ElementList[j][0]));
    }
}

功能 4:对于区域内的每个元素，我们可以检索数据

但是这个过程非常慢。有什么方法可以改进此过程以获得更快的性能？

谢谢，

Answer 1

我不确定这段代码是你想要的。

请检查。

减少计算时间的一个主要方法是使用字典。

Dictionary 的时间复杂度通常是 O(1)。

public class Sample
{
    // add data to that variables.
    System.Collections.Generic.Dictionary<double, Point> pointPerElement = new System.Collections.Generic.Dictionary<double, Point>();
    System.Collections.Generic.Dictionary<double, Cube> cubePerElement = new System.Collections.Generic.Dictionary<double, Cube>();
    System.Collections.Generic.List<double> elements = new System.Collections.Generic.List<double>();

    private void Calculate()
    {
        foreach (var element in elements)
        {
            if (pointPerElement.ContainsKey(element) == false || cubePerElement.ContainsKey(element) == false)
            {
                continue;
            }
            var point = pointPerElement[element];
            var cube = cubePerElement[element];
            if (cube.IsBouded(point))
            {
                // add point or cube or element to list.
            }
        }
    }
}

private struct Point
{
    public double x;
    public double y;
    public double z;

    public Point(double x, double y, double z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public static Point GetVector(Point from, Point to)
    {
        return new Point(to.x - from.x, to.y - from.y, to.z - from.z);
    }
}

private struct Range
{
    public double min;
    public double max;

    public double length;
    public double center;

    public Range(double min, double max)
    {
        System.Diagnostics.Debug.Assert(min < max);
        this.min = min;
        this.max = max;
        this.length = max - min;
        this.center = length * 0.5;
    }
}

private struct Cube
{
    public Range xRange;
    public Range yRange;
    public Range zRange;

    private Point center;

    public Cube(Range xRange, Range yRange, Range zRange)
    {
        this.xRange = xRange;
        this.yRange = yRange;
        this.zRange = zRange;

        this.center = new Point(xRange.center, yRange.center, zRange.center);
    }

    public bool IsBouded(Point point)
    {
        var v = Point.GetVector(point, this.center);
        var doubledV = new Point(v.x * 2, v.y * 2, v.z * 2);
        return doubledV.x <= this.xRange.length
            && doubledV.y <= this.yRange.length
            && doubledV.z <= this.yRange.length;
    }
}