1

長い投稿で申し訳ありませんが、最後まで時間を割いてフィードバックをくれた人に感謝します。

リストと配列の操作に関するパフォーマンス関連の質問があります。

一連のセンサーから収集されたデータに対していくつかの操作を実行するソフトウェアを作成しました。より高速に実行するために、現在、いくつかの最適化を作成しようとしています。

収集されたデータは、Double の N 行 M 列の配列です (実際には を拡張するクラスとして実装されList<List<double>>ます)。i の任意の値に対して常にthis.Count() == Nandがあります。this[i].Count() == M基本的に、それは長方形の配列です。

この配列の各データ ポイントは、X 行 Y 列のマップ上のいくつかのポイントに関連付けられています。基本的に、これは私がデータから作成した画像であり、すばやく明確に表現できると想像してください。したがって、各データ ポイントに対して、List<int[]>それが関連するマップ ポイントの a があります。この事実は で表されList<int[]>[,] pointsLocalます。また、これと同じ情報を格納する場所に static を保持しますList<int[]>[,]。このようにpointsLocalして、精緻化ループで余暇に変更し、次にこれらのメソッドが呼び出されたときに新しいコピーを作成できます。同じセンサーは常に同じポイントに関連付けられます。そのため、そのローカル配列があります。一部のポイント (実際にはほとんどのポイント) は複数のセンサーに関連しているため、多くのリストに含まれています。

私のコードの他の部分では、アレイの一部のセンサーに問題があり、データにエラーが含まれているという事実を正しく識別できます。これは で表されprivate List<List<bool>> faultyDataます。センサーが誤った出力を出す場合、それが関連付けられているすべてのポイントが障害に苦しむ可能性があると想定する必要があるため、それらのマップポイントでのさらなる分析の結果は気にしません。

私のコードの計算部分は、各マップポイントの配列内のすべてのセンサーからのデータを集約します。私がやろうとしているのは、分析を実行する必要のないマップポイントのサブセットを事前に決定することです。

このクラスPointsEqualityComparerは のカスタム比較演算子ですint[]。マップ ポイントは 2D 座標で識別されるため、これを使用します。

public class Sinogram : List<List<double>>
{
    //various enums
   private List<List<bool>> faultyData; //faultyData[i][j] is true if there is an error in the data
    //constructors
    //some methods
    public void dataAnalysis()
    {
        List<int[]>[,] pointsLocal = new List<int[]>[this.Count(), this[0].Count()];
        List<int[]> faultyPoints = new List<int[]>();
        //Fill pointsLocal with the correlated points from the static array
        PointsEqualityComparer myComparer = new PointsEqualityComparer();
        //Point selection parts (see later for the two different implementations)
        //Actual analysis parts (not here because it is not relevant to my question, but it works)
    }
}

比較クラスは次のとおりです。GetHashCodeパフォーマンスを向上させるには、メソッドが可能な限り一意の結果を返さなければならないことがわかったので、このスニペットに示すように実装しました。

 public class PointsEqualityComparer : IEqualityComparer<int[]>
 {
    public bool Equals(int[] p1, int[] p2)
    {
        bool result = (p1.Count() == p2.Count()) && (p1.Count() == 2) && (p1[0] == p2[0]) && (p1[1] == p2[1]);
        return result;
    }

    public int GetHashCode(int[] obj)
    {
        return ((obj[0] + obj[1]) * (obj[0] + obj[1] + 1) + obj[1]);
    }
}

トリッキーな部分は次のとおりです。興味深いマップポイントを実際に選択するコードの部分には、2 つの異なる実装があります。興味深いのは、センサーからのデータを集約する必要があるマップポイントです。エラーが発生しやすいポイントを実際に特定し、リストから削除して選択します。

私の最初の実装では、マップ ポイントのすべてのリストをループします。対応するセンサーが故障している場合は、それらのポイントを故障したポイントのリストに追加します (重複を避けます)。すべてのポイントをループして、問題のあるポイントの完全なリストを生成したら、allPairsLocalそれらを削除して更新します。faultyPoints のリストは、特に多くのセンサーがエラーを報告する場合にかなり大きくなる可能性があります (すべてのセンサーがエラーを報告し、プロットする 1920*1080 マップを作成しようとしている場合、理論上の最大サイズは 2000000 要素を超えます)。 HD 画像として)

for (int i = 0; i <this.Count; i++)
{
    for (int j = 0; j < this[i].Count; j++)
    {
        if (faultyData[i][j])
        {
            faultyPoints = faultyPoints.Union<int[]>(allPairsLocal[i, j], myComparer).ToList();
        }
    }
}
for (int i = 0; i <this.Count; i++)
{
    for (int j = 0; j < this[i].Count; j++)
    {
        allPairsLocal[i, j] = allPairsLocal[i, j].Except(faultyPoints, myComparer).ToList();
    }
}

2 番目の実装では、より小さな faultyPoints リストを作成しようとしました。したがって、私が行うことは、エラーを報告するセンサーごとに、そのリストを使用して、他のすべてのマップポイント (およびそれ自体) からマップポイントを削除することです。これにより、リストの次元が小さく維持されますが、より多くの削除されたループが犠牲になります。

for (int i = 0; i <this.Count; i++)
{
    for (int j = 0; j < this[i].Count; j++)
    {
        if (faultyData[i][j])
        {
            faultyPoints = allPairsLocal[i, j]. ToList();
            for (int x = 0; x < this.Count; x++)
            {
                for (int y = 0; y < this[x].Count; y++)
                {
                    allPairsLocal[x, y] = allPairsLocal[x, y].Except(faultyPoints, myComparer).ToList();
                }
            }
        }
    }
}

これらの実装は両方とも非常に遅く、これは少なくとも部分的にはデータ セットのサイズが原因であると思います。どちらも、データセット全体でデータ分析手順を実行するよりも時間がかかります。同様の操作をより高速に実装する方法はありますか? 一部のステップはおそらく並行して行うことができますが、それによって実質が変わることはありません。UnionとExceptでここで行っていることを実装するためのO(1)メソッドを持つデータ構造はありますか?

繰り返しますが、私の投稿全体を読んでいただきありがとうございます。完全な回答でなくても、フィードバックをいただければ幸いです。また、できる限りの点を明確にすることができます。

4

2 に答える 2