Sni.DelWoods Ответов: 4

Фильтр c# медленно на массив строк (аттракцион LINQ и петли)

Строковый массив с 8000 элементами должен быть отфильтрован в элементы, начинающиеся с " а " (=600 элементов).

Использование LINQ происходит очень медленно
Использование простой петли происходит очень быстро.

Есть ли способ улучшить производительность LINQ в этом случае?

Что я уже пробовал:

string[] items = { ... 8000 items from csv ...};
var foo = new List<string>();

// 3 seconds..
foo.AddRange(items.Where(item => item.StartsWith("a")))

// <1 second
foreach (var item in items)
    if (item.StartsWith("a")) foo.Add(item);

Maciej Los

Удалять AddRange() метод и попробуйте это:

List<string>() foo = items.Where(item => item.StartsWith("a")).ToList();

Sni.DelWoods

AddRange() не замедляет процесс, это выражение LINQ.

4 Ответов

Рейтинг:
8

Sni.DelWoods

Спасибо за ваши очень хорошие комментарии.

Я понял, что медленное изгнание вызвано непосредственным окном:

? System.DateTime.Now.ToLongTimeString() + " | n=" + arrPlz.Where(x => x.StartsWith("0")).Count() + " | " + System.DateTime.Now.ToLongTimeString()

"12:02:20 | n=624 | 12:02:24"
Использование одного и того же выражения LINQ в коде класса работает идеально (даже со списком< & gt;):
string[8000] items = new[] {"01234", "123123", ...};

items = items.Where(item => item.StartsWith("0")).ToArray();
var lst = items.Where(item => item.StartsWith("0")).ToList();
items = lst.ToArray();
Таким образом, немедленное окно сильно замедляет этот процесс.

Рейтинг:
36

F-ES Sitecore

Linq не предназначен для производительности, он предназначен для простоты использования. Если вы имеете дело с большим количеством данных и производительность важна, то используйте цикл foreach.

Sni.DelWoods

Похоже, что LINQ абсолютно не оптимизирует производительность.
Я бы предположил, что LINQ немного медленнее работает на больших сложных объектах, но не на простом строковом массиве.

Неважно, приятно это знать, поэтому я создаю метод расширения для этого случая.
Спасибо.

Dave Kreskowiak

Это связано с тем, что LINQ должен использовать перечислимые интерфейсы, предоставляемые коллекциями, над которыми он работает. Это дополнительный код, который добавляет накладные расходы на доступ к элементам из коллекции. Предложение Where будет проходить через каждый отдельный элемент в коллекции и вызывать вашу оценку по ним, ища любой элемент, который удовлетворяет условию. Это же тонна накладных расходов.

Рейтинг:
22

Richard Deeming

Я подозреваю, что что-то еще происходит с вашим кодом или с вашим компьютером. Три секунды для фильтрации массива из 8000 элементов невероятно медленно.

С помощью Benchmark.NET[^] чтобы проверить следующий код:

public class LinqBenchmark
{
    private readonly string[] _data;

    public LinqBenchmark()
    {
        _data = new string[8000];

        var rnd = new Random();
        for (int i = 0; i < _data.Length; i++)
        {
            _data[i] = rnd.Next(0, 1000).ToString();
        }
    }

    [Benchmark]
    public List<string> For()
    {
        var result = new List<string>();
        for (int i = 0; i < _data.Length; i++)
        {
            if (_data[i].StartsWith("1"))
            {
                result.Add(_data[i]);
            }
        }

        return result;
    }

    [Benchmark]
    public List<string> ForEach()
    {
        var result = new List<string>();
        foreach (string item in _data)
        {
            if (item.StartsWith("1"))
            {
                result.Add(item);
            }
        }

        return result;
    }

    [Benchmark]
    public List<string> AddRange()
    {
        var result = new List<string>();
        result.AddRange(_data.Where(i => i.StartsWith("1")));
        return result;
    }

    [Benchmark]
    public List<string> ToList()
    {
        return _data.Where(i => i.StartsWith("1")).ToList();
    }
}
Результат: 
BenchmarkDotNet=v0.11.1, OS=Windows 10.0.17134.285 (1803/April2018Update/Redstone4)
Intel Core i7-4770K CPU 3.50GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
Frequency=3417969 Hz, Resolution=292.5714 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3163.0
  DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3163.0


   Method |     Mean |     Error |    StdDev |
--------- |---------:|----------:|----------:|
      For | 772.1 us | 10.709 us | 10.017 us |
  ForEach | 766.5 us |  1.323 us |  1.238 us |
 AddRange | 796.3 us |  2.858 us |  2.534 us |
   ToList | 798.5 us | 12.835 us | 12.005 us |

// * Hints *
Outliers
  LinqBenchmark.AddRange: Default -> 1 outlier  was  removed

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 us   : 1 Microsecond (0.000001 sec)

Как вы можете видеть, ни один из методов не занял в среднем больше одной миллисекунды. Разница между ними составляет менее 30 микросекунд.

LINQ может быть не самым эффективным вариантом, но разница обычно не так велика, как времена, которые вы цитируете.

Maciej Los

Фантастический ответ, Ричард!
Что касается самого AddRange() и ToList() метод... Насколько я помню, а ToList() метод использует, на самом деле, AddRange() Вот в чем причина очень похожего времени исполнения. ;)

Richard Deeming

Список[^] использует то List<T> конструктор[^], который не вызывает то AddRange метод[^] вообще. :)

Maciej Los

Вы проверяли с помощью IlSpy?

Richard Deeming

Шоу DotPeek:

[__DynamicallyInvokable]
public static List<TSource> ToList<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
        throw Error.ArgumentNull(nameof (source));
    return new List<TSource>(source);
}

И:
[__DynamicallyInvokable]
public List(IEnumerable<T> collection)
{
    if (collection == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
    ICollection<T> objs = collection as ICollection<T>;
    if (objs != null)
    {
        int count = objs.Count;
        if (count == 0)
        {
            this._items = List<T>._emptyArray;
        }
        else
        {
            this._items = new T[count];
            objs.CopyTo(this._items, 0);
            this._size = count;
        }
    }
    else
    {
        this._size = 0;
        this._items = List<T>._emptyArray;
        foreach (T obj in collection)
            this.Add(obj);
    }
}

Richard Deeming

Я подозреваю, что большая часть времени будет потрачена на изменение размера внутренней памяти устройства. List<T> класс. Если бы вы могли выделить достаточно места в самом начале, это, вероятно, было бы значительно быстрее. :)

Рейтинг:
16

Eric Lynch

Действительно поздно отвечать здесь, но мне было любопытно, что даст немного более тщательное исследование. Метод, используемый для анализа/выбора вашей популяции, для такой небольшой популяции (8K элементов), с таким простым фильтром (начинается с "а"), должен быть в значительной степени неуместен. Даже с населением в 100 миллионов предметов худшее, что я мог сделать, было около 2 секунд.

Вместо этого гораздо более вероятно, что ваша проблема связана с генерацией/чтением ваших элементов.

Я предполагаю, что у вас должен быть исключительно медленный читатель CSV. Даже для сравнительно небольшого размера элемента 8K, если у вас нет огромного размера символов на элемент, я ожидаю быстрой производительности даже от самого худшего читателя CSV (о котором я знаю).

Следуют результаты и тестовая упряжь...

Результаты:

StartsWithA: 00:00:31.3843456
GetMatchesIndexCount: 00:00:00.4149453
GetMatchesIndexListAdHoc: 00:00:00.4930803
GetMatchesIndexListPreAllocated: 00:00:00.4762712
GetMatchesIndexListTruncated: 00:00:00.4896025
GetMatchesForeachCount: 00:00:00.4298655
GetMatchesForeachListAdHoc: 00:00:00.4599720
GetMatchesForeachListPreAllocated: 00:00:00.4488830
GetMatchesForeachListTruncated: 00:00:02.0583127
GetMatchesLinqArray: 00:00:00.5453610
GetMatchesLinqList: 00:00:00.4848105

Программа:

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;

namespace PrefixBenchmark
{
  public class Program
  {
    public const int OddsOfA = 26; // 1:26 odds of starting with "a".
    public const int SampleCount = 100000000; // Number of strings to use while testing
    public const int MaximumLength = 5; // Maximum string length

    public static void Main(string[] args)
    {
      var stopwatch = new Stopwatch();

      stopwatch.Restart();
      string[] sequence = StartsWithA(SampleCount, new Random(), OddsOfA, MaximumLength);
      stopwatch.Stop();
      Console.WriteLine($"{nameof(StartsWithA)}: {stopwatch.Elapsed}");

      Time(nameof(GetMatchesIndexCount), stopwatch, sequence, GetMatchesIndexCount);
      Time(nameof(GetMatchesIndexListAdHoc), stopwatch, sequence, GetMatchesIndexListAdHoc);
      Time(nameof(GetMatchesIndexListPreAllocated), stopwatch, sequence, GetMatchesIndexListPreAllocated);
      Time(nameof(GetMatchesIndexListTruncated), stopwatch, sequence, GetMatchesIndexListTruncated);
      Time(nameof(GetMatchesForeachCount), stopwatch, sequence, GetMatchesForeachCount);
      Time(nameof(GetMatchesForeachListAdHoc), stopwatch, sequence, GetMatchesForeachListAdHoc);
      Time(nameof(GetMatchesForeachListPreAllocated), stopwatch, sequence, GetMatchesForeachListPreAllocated);
      Time(nameof(GetMatchesForeachListTruncated), stopwatch, sequence, GetMatchesForeachListTruncated);
      Time(nameof(GetMatchesLinqArray), stopwatch, sequence, GetMatchesLinqArray);
      Time(nameof(GetMatchesLinqList), stopwatch, sequence, GetMatchesLinqList);
    }


    private static T Time<T>(string name, Stopwatch stopwatch, string[] sequence,
      Func<string[], T> test)
    {
      stopwatch.Restart();
      T result = test(sequence);
      stopwatch.Stop();
      Console.WriteLine($"{name}: {stopwatch.Elapsed}");
      return result;
    }

    private static int GetMatchesIndexCount(string[] sequence)
    {
      int length = sequence.Length;
      int count = 0;
      for (int index = 0; index < length; index++)
        if (sequence[index].StartsWith('a'))
          count++;
      return count;
    }

    private static List<string> GetMatchesIndexListAdHoc(string[] sequence)
    {
      int length = sequence.Length;
      var list = new List<string>();
      for (int index = 0; index < length; index++)
      {
        string candidate = sequence[index];
        if (candidate.StartsWith('a'))
          list.Add(candidate);
      }
      return list;
    }

    private static List<string> GetMatchesIndexListPreAllocated(string[] sequence)
    {
      int length = sequence.Length;
      var list = new List<string>(length);
      for (int index = 0; index < length; index++)
      {
        string candidate = sequence[index];
        if (candidate.StartsWith('a'))
          list.Add(candidate);
      }
      return list;
    }

    private static List<string> GetMatchesIndexListTruncated(string[] sequence)
    {
      int length = sequence.Length;
      var list = new List<string>(length);
      for (int index = 0; index < length; index++)
      {
        string candidate = sequence[index];
        if (candidate.StartsWith('a'))
          list.Add(candidate);
      }
      list.TrimExcess();
      return list;
    }

    private static int GetMatchesForeachCount(string[] sequence)
    {
      int count = 0;
      foreach (string candidate in sequence)
        if (candidate.StartsWith('a'))
          count++;
      return count;
    }

    private static List<string> GetMatchesForeachListAdHoc(string[] sequence)
    {
      var list = new List<string>();
      foreach (string candidate in sequence)
      if (candidate.StartsWith('a'))
        list.Add(candidate);
      return list;
    }

    private static List<string> GetMatchesForeachListPreAllocated(string[] sequence)
    {
      var list = new List<string>(sequence.Length);
      foreach (string candidate in sequence)
        if (candidate.StartsWith('a'))
          list.Add(candidate);
      return list;
    }

    private static List<string> GetMatchesForeachListTruncated(string[] sequence)
    {
      var list = new List<string>(sequence.Length);
      foreach (string candidate in sequence)
        if (candidate.StartsWith('a'))
          list.Add(candidate);
      list.TrimExcess();
      return list;
    }

    private static string[] GetMatchesLinqArray(string[] sequence) =>
      sequence
        .Where(candidate => candidate.StartsWith('a'))
        .ToArray();

    private static List<string> GetMatchesLinqList(string[] sequence) =>
      sequence
        .Where(candidate => candidate.StartsWith('a'))
        .ToList();

    /// <summary>
    /// Creates a string with a 1:<paramref name="odds"/> likelihood of starting with the letter "a".
    /// </summary>
    /// <param name="sampleCount">The number of samples to generate.</param>
    /// <param name="random">The random number generator.</param>
    /// <param name="odds">The denominator of a 1:<paramref name="odds"/> likelihood of selection.</param>
    /// <param name="maximumLength">The maximum character length of the string.</param>
    /// <returns>A sequence of <paramref name="sampleCount"/> strings with the specified characteristics.</returns>
    protected static string[] StartsWithA(int sampleCount, Random random, int odds,
int maximumLength)
    {
      string[] samples = new string[sampleCount];
      for (int index = 0; index < sampleCount; index++)
        samples[index] = StartsWithA(random, odds, maximumLength);
      return samples;
    }

    /// <summary>
    /// Creates a string with a 1:<paramref name="odds"/> likelihood of starting with the letter "a".
    /// </summary>
    /// <param name="random">The random number generator.</param>
    /// <param name="odds">The denominator of a 1:<paramref name="odds"/> likelihood of selection.</param>
    /// <param name="maximumLength">The maximum character length of the string.</param>
    /// <returns>A string with the specified characteristics.</returns>
    protected static string StartsWithA(Random random, int odds, int maximumLength)
    {
      int length = random.Next(maximumLength) + 1;
      var builder = new StringBuilder(random.Next(maximumLength) + 1);

      builder.Append(IsSelected(random, odds) ? 'a' : 'b');
      for (int index = 0; index < length; index++)
        builder.Append('b');

      return builder.ToString();
    }

    /// <summary>
    /// Evaluates a 1:<paramref name="odds"/> likelihood of selection.
    /// </summary>
    /// <param name="random">The random number generator.</param>
    /// <param name="odds">The denominator of a 1:<paramref name="odds"/> likelihood of selection.</param>
    /// <returns>True, if a 1:<paramref name="odds"/> event occurs; otherwise, false.</returns>
    protected static bool IsSelected(Random random, int odds) =>
      random.Next(odds) == 0;
  }
}

Maciej Los

5ed!