Блог

Предположим, у вас есть миллион последовательных целых чисел. Возвращает все возможные значения a, b и c такие, что

       a b c<=d.
      d will be provided to you.
      ex: if the numbers are 1,2,3,4,5,6,7
      and d=7
       [1,2,3]
       [1,2,4]
       [1,2,3] will be same as [1,3,2] and [3,2,1]...
  

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

       `a<b<c`
  

Таким образом 3*a<1000 , ==> a<333.33, поэтому я извлекаю a от 1 до 333.

  static void Main(string[] args)
    {
        int d = 519;
        var setA = Enumerable.Range(1, 333);
        IEnumerable<int> value = Enumerable.Range(1, 1000);
        var result =     (from a in setA
                          from b in value
                          from c in value
                          where a!=b amp;amp; a!=c amp;amp; b!=c amp;amp; a   b   c <= d
                          select new {a,b,c}).ToList().Distinct().ToList();
        foreach (var item in result)
        {
            Console.WriteLine(item);
        }
        Console.ReadKey();
    }
  

Это происходит медленно и выдает System.OutOfMemoryException исключение…..

Сужение a до 1...333 — хорошая идея. Вы можете еще больше улучшить свой код, используя тот факт, что a < b < c , so b,c in Enumerable.Range(1, 1000) является неоптимальным.

Вы можете определить нижние и верхние границы для b и c в зависимости от заданных чисел a и b соответственно:

 a < b => b >= a   1, b in Enumerable.Range(a   1, ...)
b < c => c must be in Enumerable.Range(b   1, ...)
  

Кроме того, вы можете определить границы для a и b тому подобное:

• Поскольку b >= a 1 и a b c <= total , a (a 1) ((a 1) 1) <= total также должно иметь значение true . Этого a < total / 3 недостаточно. Это a <= (total - 3) / 3
• Аналогично a b (b 1) <= total , это, b <= (total - a - 1) / 2
• И, конечно же, a b c <= total переводится в c <= total - a - b

Вы можете использовать это, вложив итерации и используя SelectMany для выравнивания списка результатов:

         var result = Enumerable.Range(1, (total - dba - dca) / 3)
            .SelectMany(
                a => Enumerable.Range(a   1, (total - a - dcb) / 2 - a)
                    .SelectMany(
                        b => Enumerable.Range(b   1, (total - a - b) - b)
                            .Select(c => new { a, b, c })));
  

Что касается вашей производительности и проблемы с нехваткой памяти:

Удалите ToList() из вашего запроса LINQ. Это приводит к тому, что все результаты загружаются в память до того, как вы начнете их обрабатывать. Поскольку вы хотите распечатать только кортежи, вам не нужно загружать их все в память. Это большая сила LINQ — он просто возвращает перечислитель без фактического вычисления результата. Если вы удалите ToList() из запроса LINQ, цикл for-each вычислит один результат за итерацию, распечатает его и снова забудет.

В качестве пояснительного ответа на ваши комментарии:

Реализация Enumerable.Range выглядит следующим образом:

 private static IEnumerable<int> RangeIterator(int start, int count)
{
    for (int i = 0; i < count;   i)
        yield return start   i;
}
  

Реализация SelectMany :

 private static IEnumerable<TResult> SelectManyIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
{
  foreach (TSource source1 in source)
  {
    foreach (TResult result in selector(source1))
      yield return result;
  }
}
  

Так, например,

 foreach (var item in Enumerable.Range(1, 10).SelectMany(n => Enumerable.Range(1, n)))
{ /* do something */ }
  

концептуально переводится как:

 for (int i = 0; i < 10;   i)
{
    var n = 1   i;

    for (int j = 0; j < n;   j)
    {
        var result = 1   j;

        /* do something */  // <- processes the current result and forgets it again
    }
}
  

Однако, когда вы добавляете ToList :

 foreach (var item in Enumerable.Range(1, 10).SelectMany(n => Enumerable.Range(1, n)).ToList())
{ /* do something */ }
  

это означает:

 var list = new List<int>();
for (int i = 0; i < 10;   i)
{
    var n = 1   i;

    for (int j = 0; j < n;   j)
    {
        var item = 1   j;
        list.Add(item); // <- puts the current result in a list
    }
}

// list content: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6...

foreach (var item in list)
{ /* do something */ }
  

Вы можете поиграть с index и вашим выбором для каждого из for циклов, предполагая, что входные данные отсортированы. Первый цикл должен составлять одну треть основного массива, второй цикл должен составлять не более половины, но начинаться с индекса первого цикла. что-то вроде этого:

     const int totalElements = 1000;
        const int target = 1000;
        var value = Enumerable.Range(1, totalElements).OrderBy(dd => dd).ToList();
        var sw = new Stopwatch();
        var result = new List<int[]>();
        sw.Start();

        for (int i = 0; i < value.Count / 3; i  )
        {
            var a = value[i];

            for (int j = i   1; j < value.Count / 2; j  )
            {
                var b = value[j];

                for (int k = j   1; k < value.Count; k  )
                {
                    var c = value[k];

                    if (a   b   c <= target)
                    {
                        var newR = new[] { a, b, c };
                        result.Add(newR);
                    }
                }
            }
        }

        sw.Stop();
        Console.WriteLine("Time Taken: "   sw.Elapsed.TotalSeconds);
        Console.WriteLine("Total result count: "   result2.Count);   
  

Для 1000 это занимает 4,9 секунды на моей паршивой машине, где, поскольку LINQ выдает outofmemory exception . Кроме того, вам нужно добавить какое-то сравнение равенства в LINQ, иначе вы получите такие результаты, как 1 2 3 и 3 2 1 , и используя только индекс, вы избавляетесь от этого.

Вы также можете настроить диапазон, выполнив что-то вроде этого:

         for (int i = 0; i < value.Count / 3; i  )
        {
            var a = value[i];

            var index = value.IndexOf(target - a)   1;

            for (int j = i   1; j < index; j  )
            {
                var b = value[j];

                var remainingIndex = value.IndexOf(target - (a   b))   1;

                for (int k = j   1; k < remainingIndex; k  )
                {
                    var c = value[k];

                    if (a   b   c <= target)
                    {
                        var newR = new[] { a, b, c };
                        result.Add(newR);
                    }
                }
            }
        }
  

Возможно, было бы лучше, если бы значения были последовательными, как в этом примере, и вы могли бы легко найти индекс. Если это не так, вам нужно найти индекс по Binary Search , но, вероятно, производительность в любом случае будет аналогичной.

Я предлагаю хранить числа в классе SortedSet . Вы можете сделать следующее (псевдокод):

 For each n in GetViewBetween (1, d)
    For each m in GetViewBetween (n 1, d-n)
        For each k in GetViewBetween (m 1, d-n-m)
            Store or print or callback or return with continuation the Tuple object with n, m, k
        Loop
    Loop
Loop
  

Я бы предложил вам геометрическое представление: представьте, что ваш ‘d’ является суммой границ треугольника. Таким образом, вам нужно найти все подходящие треугольники. В вашем коде вы удваиваете варианты: (a b c) = (b c a), например. Но если вы сделаете 3 цикла для каждой стороны треугольника, тогда это будет быстрее.