Найдите элементы, похожие среди них, в List в C # с вложенными циклами For и Linq.

Question

У меня приведенный ниже код работает нормально, который находит элементы, которые похожи между собой в списке на ± 2. Я хотел бы иметь 2 версии, чтобы проверить, какая из них работает быстрее.

Версия a) с вложенными циклами, как показано ниже. Однако в последней части кода есть! List.Contains (), который я хотел бы заменить другим циклом For, поскольку Contains () добавляет 4500 тиков, в то время как остальные 2 вложенных в циклы занимают только 1500 тиков. Поэтому я был бы признателен, если бы кто-то мог помочь заменить Contains () другим циклом for и получить такой же результат.

Версия b) то же самое, но с LINQ.

В обеих версиях элементы в выходном списке intTestResult должны быть: (1, 2, 8, 9, 10, 12)

        int intOffset = 2;
        List<int> intTest = new List<int> { 1, 2, 5, 8, 9, 10, 12, 15, 19, 24 };
        List<int> intTestResult = new List<int>();

        var S1 = Stopwatch.StartNew();

        for (int a = 0; a < intTest.Count; a++)

            {
                int int1 = intTest[a];

                for (int b = 0; b < intTest.Count; b++)

                {

                int int2 = intTest[b];

                if (int1 + intOffset >= int2 && int1 - intOffset <= int2 && int1 != int2)


                    {

                    if (!intTestResult.Contains(int1))                      

                        intTestResult.Add(int1);

                    }
                }
            }

        S1.Stop();

        Console.WriteLine("Ticks = " + S1.ElapsedTicks);                    

/ * прошедших 6000

Элементы intTestResult (1, 2, 8, 9, 10, 12) * /

Answer 1

Боюсь, что вы измеряете эффективность неправильно.

1. Сначала вы должны выполнить метод несколько раз, например, в цикле. Поскольку первое выполнение всегда будет занимать больше времени, и, вероятно, вы можете исключить первый цикл из расчета.

2. Использовать большой объем данных для обработки. Многие эффективные структуры данных работают медленно с небольшими данными, но очень быстро с большими объемами данных.

3. Если ваше приложение не работает с большим объемом данных, вам вообще не нужно тестировать производительность. Просто напишите код, который будет легко читать и понимать другим разработчикам (себе) . Я бы сказал: «Напишите код, который может быть быстро обработан человеческим мозгом».

Подход с HashSet<int> и Enumerable.Aggregate

// Helper method to check if two numbers within offset
private IEnumerable<int> WithinOffset(int? previous, int current, int offset)
{
    if (previous.HasValue == false)
    {
        yield break;
    }

    var difference = Math.Abs(previous.Value, current);
    if (difference > 0 && difference <= offset)
    {
        yield return previous.Value;
        yield return current;
    }
}

var clock = Stopwatch.Start();

var offset = 2;
var result = 
    givenData.OrderBy(number => number)
             .Aggregate(
                 (All: Enumerable.Empty<int>(), Last: default(int?)),
                 (summary, current) => 
                 {
                     var withinOffset = WithinOffset(summery.Last, current, offset);
                     var all = summary.All.Concat(withinOffset);
                     return (all, current);
                 },
                 (summary) => summary.All.ToHashSet().ToList());
clock.Stop();

var ticks = clock.ElapsedTicks;

Если я буду следовать вашему подходу к измерению, но предоставлю список из 1000 пунктов

var template = new[] { 1, 2, 5, 8, 9, 10, 12, 15, 19, 24 }
var givenData = 
    Enumerable.Range(0, 100)
              .Select(i => i * 100)
              .Select(i => template.Select(number => number + i))
              .SelectMany(number => number)
              .ToList();


// Approach with accepted answer
// Elapsed ticks = 11517000 (1.1517 seconds)

// Approach with HashSet, OrderBy and Aggregate
// Elapsed ticks = 2202000 (0.2202 seconds)

Answer 2

Заменить:

if (!intTestResult.Contains(int1))                      
    intTestResult.Add(int1);

на

bool contains = false;
for(int c = 0; c < intTestResult.Count; c++)
{
    if(int1 == intTestResult[c])
    {
        contains = true;
        break;
    }
}

if(!contains)
    intTestResult.Add(int1);