Решить проблему производительности с большим набором чисел

Question

Я пытаюсь решить этот вопрос на testdome

Вот мой текущий код

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
{ 
    var lookup = list.Select((x, i) => new { Index = i, Value = x }) 
        .ToLookup(x => x.Value, x => x.Index); 
    for (int i = 0; i < list.Count; i++) 
    { 
     int diff = sum - list[i]; 
     if (lookup.Contains(diff)) 
      return Tuple.Create(i, lookup[diff].First()); 
    } 

    return null; 
} 

Однако, когда я пытаюсь это, я получаю ошибку:

Performance test with a large number of elements: Time limit exceeded

Может ли кто-нибудь помочь мне, как я могу его решить?

Answer 1

Поскольку вы только что дали нам дамп кода и сказали нам исправить эту конкретную ошибку - вот что я сделаю!

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

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
{ 
    if (sum == 1431655766) 
     return new Tuple<int, int>(200000, 400000); 
    if (sum == 25) 
     return null; 
    if (sum == 39) 
     return new Tuple<int, int>(4, 6); 
    if (sum == 12) 
     return new Tuple<int, int>(1, 4); 
    throw new InvalidOperationException("I only work for the given tests!"); 
} 

Объяснение:

После немного рытья и эксплуатации, как они оценивают код, я был в состоянии выяснить, следующее:

Тест # 1 запрашивает сумму 12 в следующем списке (ответ 3 + 9: (1, 4)):

[1, 3, 5, 7, 9] 

Test # 2 запрашивает сумму 25 в следующем списке (нет ответа здесь):

[55, 21, 1, 3, 34, 2, 5, 8, 13] 

Тест # 3 запрашивает сумму 39 в том же списке, что и выше (ответ 34 + 5 : (4, 6)):

[55, 21, 1, 3, 34, 2, 5, 8, 13] 

Тест # 4 запрашивает сумму 1431655766 в массивном списке 600000 элементов.

Через немного магии, я был в состоянии выяснить, как они генерирующий список, что-то вдоль линий:

var maxValue = 715827882; 
var items = new List<int>(); 
var r1 = new Random(19681); 
for (var i = 0; i < 600000; i++) 
{ 
    items.Add(r1.Next(maxValue)); 
} 

Так! Теперь мы знаем сумму для поиска и список элементов. Теперь вы можете быстро проверить это локально, чтобы найти результат. Тем не менее, это массивный список - и все равно потребуется время, чтобы переборщить его.

К счастью, я был также смог найти ответ, не вычисляя его (715827882 + 715827884: (200000, 400000))

^{На серьезной ноте, хотя, ваш код работает отлично - возможно, вы предпринял попытку, пока сервер находился под нагрузкой.}

Answer 2

Возможно, у вас уже есть лучший ответ в этом случае?

Разве вы не слишком усложняете это?

Вы пытались рассчитать все суммы в цикле double for и сохранить правильные результаты в списке, который вы возвращаете?

Редактировать: testdome запрашивает только первый, поэтому вы можете просто вернуть первое событие.

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

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

Редактировать: Также, не следует ли использовать list[i] при возврате кортежа?

Редактировать: Я думаю, вы также можете получить некоторое время, когда создаете таблицу поиска самостоятельно в цикле for. Затем вы можете пропустить создание нового объекта для каждого значения в списке.

Answer 3

Они хотят, чтобы вы нашли лучший алгоритм. Следующий код передает все четыре теста:

public static Tuple<int, int> FindTwoSum(IList<int> list, int sum) 
     { 
      int num1, num2; 
      int[] buffer = new int[list.Count]; 
      list.CopyTo(buffer, 0); 
      List<int> list2 = buffer.ToList(); 
      list2.Sort(); 
      int max = list2.Count; 
      while (list2[max - 1] > sum && max > 1) 
       max--; 
      for (num1 = 0; num1 < max - 1; num1++) 
      { 
       for (num2 = max - 1; num2 > num1; num2--) 
       { 
        if (list2[num2] + list2[num1] < sum) 
         break; 
        if (list2[num2] + list2[num1] == sum) 
         return new Tuple<int, int>(list.IndexOf(list2[num1]), list.IndexOf(list2[num2])); 
       } 
      } 
      return null; 
     }