C # Увеличение производительности массива Find Loop

Question

У меня есть массив Datapoint[] file = new Datapoint[2592000]. Этот массив заполнен временными метками и случайными значениями. Создание их стоит мне как 2s. Но в другой функции prepareData(); я готовлю 240 значений для другого массива TempBuffer. В функции prepareData() я ищу соответствующие значения в массиве file. Если я не могу найти ничего, я беру метку времени и устанавливаю значение 0, иначе я беру найденное значение + та же метка времени.

Функция выглядит так:

public void prepareData()
{  
    stopWatch.Reset();
    stopWatch.Start();
    Int32 unixTimestamp = (Int32)(DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1))).TotalSeconds;

    for (double i = unixTimestamp; unixTimestamp - 240 < i; i--)
    {
        bool exists = true;

        if (exists != (Array.Exists(file, element => element.XValue == i)))
        {
            TempBuffer = TempBuffer.Skip(1).Concat(new DataPoint[] { new DataPoint(UnixTODateTime(i).ToOADate(), 0) }).ToArray();
        }
        else
        {
            DataPoint point = Array.Find(file, element => element.XValue == i);
            TempBuffer = TempBuffer.Skip(1).Concat(new DataPoint[] { new DataPoint(UnixTODateTime(i).ToOADate(), point.YValues) }).ToArray();
        }
    }

    stopWatch.Stop();
    TimeSpan ts = stopWatch.Elapsed;
}

Теперь проблема в том количестве данных в file (2'592'000), которое требуется функции за 40 секунд! С меньшими суммами, такими как 10'000, это не проблема и работает нормально и быстро. Но как только я установил размер file на мои предпочтительные 2'592'000 точек, процессор поднялся до 99% производительности, и функция стала слишком длинной.

Значение примера TempBuffer:
X = преобразовано UnixTimeStamp в DateTime, а DateTime преобразовано в AODate
{X = 43285.611087963, Y = 23}

Пример файла:
X = Unixtimestamp
{X = 1530698090, Y = 24}

Важно, чтобы значения временного буфера были преобразованы в AODate, поскольку данные в массиве временных буферов отображаются в виде диаграммы.

Есть ли способ улучшить мой код, чтобы у меня была лучшая производительность?

Answer 1

Это наиболее эффективный способ для вашей задачи (это всего лишь шаблон, а не финальный код):

public void prepareData()
{
    // it will be initialized with null values
    var tempbuffer = new DataPoint[240];

    var timestamp = (int)(DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1))).TotalSeconds;
    var oldest = timestamp - 240 + 1;

    // fill tempbuffer with existing DataPoints
    for (int i = 0; i < file.Length; i++)
    {
        if (file[i].XValue <= timestamp && file[i].XValue > timestamp - 240)
        {
            tempbuffer[file[i].XValue - oldest] = new DataPoint(file[i].XValue, file[i].YValues);
        }
    }

    // fill null values in tempbuffer with 'empty' DataPoints
    for (int i = 0; i < tempbuffer.Length; i++)
    {
        tempbuffer[i] = tempbuffer[i] ?? new DataPoint(oldest + i, 0);
    }
}

у меня около ~ 10 мс

Обновление от комментариев:

Если вы хотите получить несколько DataPoint's и получить результат, используя некоторую функцию (например, среднее), тогда:

public void prepareData()
{
    // use array of lists of YValues
    var tempbuffer = new List<double>[240];

    // initialize it
    for (int i = 0; i < tempbuffer.Length; i++)
    {
        tempbuffer[i] = new List<double>(); //set capacity for better performance
    }

    var timestamp = (int)(DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1))).TotalSeconds;
    var oldest = timestamp - 240 + 1;

    // fill tempbuffer with existing DataPoint's YValues
    for (int i = 0; i < file.Length; i++)
    {
        if (file[i].XValue <= timestamp && file[i].XValue > timestamp - 240)
        {
            tempbuffer[file[i].XValue - oldest].Add(file[i].YValues);
        }
    }

    // get result
    var result = new DataPoint[tempbuffer.Length];
    for (int i = 0; i < result.Length; i++)
    {
        result[i] = new DataPoint(oldest + i, tempbuffer[i].Count == 0 ? 0 : tempbuffer[i].Average());
    }
}

Answer 2

Array.Exists () и Array.Find () - операции O (N), вы выполняете их x M (240) раз.

Попробуйте вместо LINQ Join:

DataPoint[] dataPoints; // your "file" variable
var seekedTimestamps = Enumerable.Range(0, 240).Select(i => unixTimestamp - i);
var matchingDataPoints = dataPoints.Join(seekedTimestamps, dp => dp.XValue, sts => sts, (dp, sts) => dp);
var missingTimestamps = seekedTimestamps.Except(matchingDataPoints.Select(mdp => mdp.XValue));
// do your logic with found and missing here
// ...

LINQ Join использует хеширование (для выбранных «ключей») и близко к O (n)

В качестве альтернативы, предполагая, что временные метки на входе являются уникальными, и вы планируете выполнять несколько операций над входом, создайте Dictionary<int (Timestamp), DataPoint> (дорогой), который даст вам O (1) получение требуемой точки данных: var dataPoint = dict[wantedTimestamp];

Answer 3

Вы не предоставили нам полную картину своего кода. В идеале я хотел бы получить пример данных и полные определения классов. Но, учитывая доступную информацию о лимитах, я думаю, вы найдете что-то вроде этого:

public void prepareData()
{ 
    Int32 unixTimestamp = (Int32)(DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1))).TotalSeconds;

    var map = file.ToLookup(x => x.XValue);

    TempBuffer =
        Enumerable
            .Range(0, 240)
            .Select(x => unixTimestamp - x)
            .SelectMany(x =>
                map[x]
                    .Concat(new DataPoint(UnixTODateTime(x).ToOADate(), 0)).Take(1))
            .ToArray();
}

Answer 4

Если DataPoint уникален (нет 2 экземпляров с одинаковыми значениями), вам следует переключить список file на словарь. Поиск в словаре намного быстрее, чем итерация потенциально всех членов массива.

Конечно, вам нужно реализовать GetHashCode и Equals или определить уникальный ключ для каждого Datapoint.