Sorry in advance for the long post, and thanks to whoever will take the time to get to the end and give me feedback.

I have performance related questions regarding operations on lists and arrays.

I have written a software to perform some operations on data gathered from an array of sensors. In an attempt to make it run faster, I am currently attempting to write some optimizations.

The data gathered is in a N-by-M array of doubles (actually implemented as a class extending `List<List<double>>`). We always have `this.Count() == N` and `this[i].Count() == M` for any value of i. Basically, it's a rectangular array.

Each data point from this array is correlated to some points on a X-by-Y map. Basically, imagine this to be an image I make out of the data to represent it in a quick and clear manner. Hence there is, for each data point a `List<int[]>` of the map-points it relates to. This fact is represented by `List<int[]>[,] pointsLocal`. I also hold a static `List<int[]>[,]` where I store this same information: this way I can modify `pointsLocal` to my leisure in an elaboration loop, and have a fresh copy the next time these methods are called. The same sensor will always be correlated to the same points, and that is why I have that local array. Some points (most of them actually) are related to more than one sensor, and thus are in many lists.

In other parts of my code I am able to correctly identify the fact that some sensors of the array had some issue, and the data then contains errors. This is represented in `private List<List<bool>> faultyData`. If a sensor gives a faulty output, then I have to assume that all the points is it correlated to may suffer from the fault, thus I don't care for the results of further analysis in those map-points.

The computational part of my code aggregates data from all the sensors in the array for each map-point. What I am trying to do is to predetermine a subset of map-points on which I don't have to perform any analysis.

The class `PointsEqualityComparer` is a custom comparison operator for `int[]`, that I use because map-points are identified by their 2D coordinates.

```
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)
    }
}

```

The comparer class is as follow. I already found out that the `GetHashCode` method had to return results as unique as possible to improve performance, so I implemented it as you see in this snippet.

```
 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]);
    }
}

```

Now for the tricky parts. I have two different implementations for the portion of code where I actually select which map-points are interesting. By interesting I mean the map-points on which I will have to aggregate the data from the sensors. I select them by actually identifying the points subject to errors and removing them from the lists.

In my first implementation I loop through all Lists of map-points. If the corresponding sensor was faulty, I add those points to a list of faulty points (avoiding duplicates). Once I looped through all points and generated the full list of faulty ones, I update `allPairsLocal` by removing them. The list of faultyPoints can become rather big, especially in some cases when a lot of sensors report errors (the maximum theoretical size is more than 2000000 elements, if all the sensors report error and I am trying to create a 1920\*1080 map to plot as an HD image)

```
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();
    }
}

```

In my second implementation I tried to have a smaller faultyPoints list. Thus, what I do is, for each sensor reporting errors, use its list to remove map-points from all the others (and its own as well). This maintains the dimensions of the lists smaller, but at the cost of more annidated loops.

```
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();
                }
            }
        }
    }
}

```

Both of these implementations are very slow, and I guess this is at least partly because of the size of the data sets. Both take way longer that performing the data analysis steps on the whole datasets.
Are there ways to make similar operations but with faster implementations? Some steps can probably be made parallel, but that wouldn't really change the substance. Are there data structures that have O(1) methods to implement what I do here with Union and Except?

Again thank you for having read through my whole post. I appreciate any feedback, even if it is not a full answer, and I am more than available to clarify what points I can.