Есть ли более эффективный метод пропуска для экземпляров цикла

Question

Если у меня есть стандарт для цикла, есть ли более эффективный способ пропустить определенные вхождения?

Например:

A:

        for (int i = 0; i < n; i++)
        {
            if (i != n / 2 && i != n / 3 && i != n / 4)
            {
                val += DoWork(i);
            }
            else
            {
                continue;
            }
        }

B

        for (int i = 0; i < n / 4; i++)
        {
            val += DoWork(i); ;
        }
        for (int i = n / 4 + 1; i < n / 3; i++)
        {
            val += DoWork(i);
        }
        for (int i = n / 3 + 1; i < n / 2; i++)
        {
            val += DoWork(i);
        }
        for (int i = n / 2 + 1; i < n; i++)
        {
            val += DoWork(i);
        }

С:

        for (int i = 0; i < n; i++)
        {
            if (i == n / 2 || i == n / 3 || i == n / 4)
            {
                continue;
            }
            else
            {
                val += DoWork(i);
            }
        }

Для n = int.MaxValue результаты были следующими: A Результаты: 57498 миллисекунд. B Результаты: 42204 миллисекунды. C Результаты: 57643 миллисекунды.

РЕДАКТИРОВАТЬ НА ОСНОВЕ ОТВЕТА ЧЕРКА. Я добавил еще один метод теста D следующим образом:

D

        for (int i = 0; i < n; i =  (i != n / 2 -1 && i != n / 3 -1  && i != n / 4-1) ? i+1: i+2)
        {
            val += DoWork(i);
        }

и получил следующие результаты:

A Результаты: 56355 миллисекунд. Результаты B: 40612 миллисекунд. C Результаты: 56214 миллисекунды. D Результаты: 51810 миллисекунд.

Edit2: после предварительного вычисления значений для n / 2 n / 3 и n / 4 вне цикла получим:

A Результаты: 50873 миллисекунд. Результаты B: 39514 миллисекунд. C Результаты: 51167 миллисекунд. D Результаты: 42808 миллисекунд.

Кажется, что петля D снова близка к «разворачиванию» B, а A и C все еще занимают значительно больше времени.

Что касается того, что я ожидал, что касается сравнений между каждым из методов.

Мой вопрос: есть ли более эффективный способ сделать это?

Answer 1

Это немного зависит от контекста. Один из вариантов во многих сценариях - обман. Поэтому вместо того, чтобы опускать числа, просто включите их, а затем отмените результат на числа, которые вам не нужны:

    for (int i = 0; i < n; i++) 
    { 
        val += DoWork(i); 
    } 
    val -= DoWork(i/2);
    val -= DoWork(i/3);
    val -= DoWork(i/4);

Время, сэкономленное на сравнениях, может перевесить результаты вычисления некоторых чисел дважды, в зависимости от того, насколько дорогой является операция DoWork.

Answer 2

Внедрить в вас ваше вторичное условие для цикла

Не проверено:

for (int i = 0; i < n || (i != n / 2 && i != n / 3 && i != n / 4); i++)
  val += DoWork(i);
}

Я думаю, что это будет работать, пока одно из этих условий истинно и будет продолжать работать

Answer 3

Во-первых, просто сделайте паузу несколько раз в течение этих 40-60 секунд, чтобы вы получили четкое представление о том, какая доля времени составляет DoWork. Если бы вы могли сделать так, чтобы ваш цикл занял совсем без , вам все равно пришлось бы потратить эту часть.

Теперь посмотрим на ваши сравнения. Каждый задает вопрос. Если ответ на вопрос почти всегда является верным или почти всегда ложным, это возможность ускориться. (Все алгоритмы log (n) и n * log (n) работают так, что их точки принятия решений больше похожи на честные монеты.)

Итак, вы можете понять, почему ваш B быстрее. В среднем он задает меньше вопросов за цикл. Вы можете сделать это еще быстрее, развернув петли (задавая вопросы еще реже).

(Я знаю, я знаю, что компиляторы могут развертывать циклы. Ну, может быть . Сделайте это сами, и вам не придется делать на это ставку.)

Answer 4

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

  int skip1 = n/2;
  int skip2 = n/3;
  int skip3 = n/4;
  for (int i = 0; i < n; i++)
  {
      if (i != skip1 && i != skip2 && i != skip3)
      {
         val += DoWork(i);
      }
  }

Не уверен, что это сэкономит достаточно миллисекунд, чтобы стоить.

Обновление: Iтолько что заметил, что @surfen предложил это в комментариях.

Answer 5

Я бы не стал усложнять код такими модификациями (как многие уже прокомментировали ваш вопрос)

Вместо этого вы можете запустить DoWork одновременно в нескольких потоках, используя Pararell.ForEach . Это будет иметь гораздо большее влияние на производительность, если ваш DoWork () что-то сделает.

Answer 6

Вы можете считать операции ...

Вариант А:
n проверяет i в цикле for, а затем 3 проверки для каждого i, который не является этим значением ... так что для проверок есть 4n операций.

вариант B:
Вы просто перебираете интервалы, поэтому выполняете n-3 операций.

вариант C:
То же, что и в варианте A, операции 4n.

Answer 7

Если DoWork() не является узким местом, это достаточно маленький метод для встраивания в цикл, поэтому вам не понадобится вызов, который сам по себе стоит времени.Если DoWork() выполняет большую часть работы, вы теряете время :)