Вернуться к основам; циклы for, массивы / векторы / списки и оптимизация

Question

Недавно я работал над некоторым кодом и наткнулся на метод с 3 циклами for, который работал на 2 разных массивах.

По сути, то, что происходило, заключалось в том, что цикл foreach будет проходить через вектор и преобразовывать DateTime из объекта, а затем другой цикл foreach будет преобразовывать длинное значение из объекта. Каждый из этих циклов будет хранить преобразованное значение в списках.

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

Затем, после всего, что сказано и сделано, два последних списка преобразуются в массив с помощью ToArray ().

Хорошо, терпите меня, я наконец-то дошел до своего вопроса.

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

Но затем я прочитал статью Густава Дуарте «Что делает ваш компьютер, пока вы ждете», и начал размышлять об управлении памятью и о том, что делают данные, когда к ним обращаются в цикле for, где два списка доступны одновременно.

Итак, мой вопрос, каков наилучший подход для чего-то подобного? Попробуйте сжать циклы for так, чтобы это происходило как можно меньше, вызывая множественный доступ к данным для разных списков. Или разрешить несколько циклов и позволить системе вводить ожидаемые данные. Эти списки и массивы могут быть потенциально большими и циклически проходить через 3 списка, возможно, 4 в зависимости от того, как реализован ToArray (), может оказаться очень дорогостоящим (O (n ^ 3) ??). Но из того, что я понял в указанной статье и из моих классов CS, необходимость извлечения данных тоже может быть дорогой.

Кто-нибудь хотел бы предоставить какое-либо понимание? Или я полностью ушел из своего рокера и мне нужно заново учить то, что я неучил?

Спасибо

Answer 1

Лучший подход? Напишите наиболее читаемый код, определите его сложность и решите, если это действительно проблема.

Если у каждого из ваших циклов есть O (n), то у вас все еще есть только операция O (n).

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

Answer 2

Для справки,

статья в Что ваш компьютер делает, пока вы ждете - Густав Дуарте

Также есть руководство к обозначению big-O .

---

Невозможно ответить на вопрос, не видя код / ​​псевдокод. Единственный надежный ответ - «использовать профилировщик». Предположение, что ваши циклы делают, является плохой услугой для вас и всех, кто читает этот вопрос.

Answer 3

Ну, у вас есть осложнения, если два вектора имеют разные размеры. Как уже указывалось, это не увеличивает общую сложность проблемы, поэтому я остановлюсь на простейшем коде - который, вероятно, состоит из 2 циклов, а не 1 цикла со сложными условиями тестирования для двух разных длин.

На самом деле, эти тесты длины могут легко сделать две петли быстрее , чем одна петля. Вы также можете улучшить производительность извлечения памяти с помощью 2 циклов - т.е. вы смотрите на непрерывную память - то есть A [0], A [1], A [2] ... B [0], B [1], B [ 2] ..., а не A [0], B [0], A [1], B [1], A [2], B [2] ...

Так что во всех отношениях я бы использовал 2 отдельных цикла; -p

Answer 4

Правильно ли я вас понимаю в этом?

У вас есть эти петли:

for (...){
  // Do A
}

for (...){
  // Do B
}

for (...){
  // Do C
}

И вы преобразовали его в

for (...){
  // Do A
  // Do B
}
for (...){
  // Do C
}

а тебе интересно, что быстрее?

Если нет, какой-нибудь псевдокод был бы хорош, чтобы мы могли видеть, что вы имели в виду. :) Невозможно сказать. Это может пойти в любую сторону. Вы правы, получение данных стоит дорого, но локальность также важна. Первая версия может быть лучше для локальности данных, но, с другой стороны, вторая имеет большие блоки без ветвей, что позволяет более эффективно планировать команды.

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

Мое чувство интуиции говорит, что второе, с большим количеством работы, выполняемой между инструкциями прыжка, было бы более эффективным, но это просто догадка, и это может легко быть неправильно.

Answer 5

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

Чтобы ответить кому-то, кто все еще контролирует этот вопрос;

Да, как сказал Джальф, функция выглядит примерно так:

PrepareData(vectorA, VectorB, xArray, yArray): listA listB foreach(value in vectorA) convert values insert in listA foreach(value in vectorB) convert values insert in listB listC listD for(int i = 0; i < listB.count; i++) listC[i] = listB[i] converted to something listD[i] = listA[i] xArray = listC.ToArray() yArray = listD.ToArray()</p> <p>

Я изменил его на:

PrepareData(vectorA, vectorB, ref xArray, ref yArray): listA listB for(int i = 0; i < vectorA.count && vectorB.count; i++) convert values insert in listA convert values insert in listB listC listD for(int i = 0; i < listB.count; i++) listC[i] = listB[i] converted to something listD[i] = listA[i] xArray = listC.ToArray() yArray = listD.ToArray()

Имея в виду, что векторы могут иметь большое количество элементов. Я подумал, что второй будет лучше, так что программе не придется повторять n раз 2 или 3 раза. Но затем я начал задаваться вопросом о влиянии (эффектах?) Извлечения памяти, или предварительной выборки, или что у вас есть.

Итак, я надеюсь, что это поможет прояснить вопрос, хотя многие из вас дали отличные ответы.

Answer 6

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

Предположим, это ваш код:

// if this compiles down to a raw memory copy with a bitmask...
Date morningOf(Date d) { return Date(d.year, d.month, d.day, 0, 0, 0); }

Date timestamps[N];
Date mornings[N];

// ... then this can be parallelized using SSE or other SIMD instructions
for (int i = 0; i != N; ++i)
    mornings[i] = morningOf(timestamps[i]);

// ... and this will just run like normal
for (int i = 0; i != N; ++i)
    doOtherCrap(mornings[i]);

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

Это то, что Intel рекомендует в своем руководстве по оптимизации C / C ++, и оно действительно может иметь большое значение.

Answer 7

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

for(i=0, i<10, i++ ) {
  myObject object = array[i];
  myObject.functionreallybig1(); // pushes functionreallybig2 out of cache
  myObject.functionreallybig2(); // pushes functionreallybig1 out of cache
}

против

for(i=0, i<10, i++ ) {
  myObject object = array[i];
  myObject.functionreallybig1(); // this stays in the cache next time through loop
}


for(i=0, i<10, i++ ) {
  myObject object = array[i];
  myObject.functionreallybig2(); // this stays in the cache next time through loop
}

Но это была, вероятно, ошибка (обычно этот тип трюка комментируется)

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

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

Answer 8

Спасибо всем за информацию. Мышление с точки зрения Big-O и того, как оптимизировать, никогда не было моей сильной стороной. Я верю, что собираюсь вернуть код к тому, как он был, я должен был доверять тому, как он был написан раньше, а не прыгать на мои начинающие инстинкты. Кроме того, в будущем я добавлю больше ссылок, чтобы каждый мог понять, какого черта я говорю (ясность также не является моей сильной стороной: - /).

Еще раз спасибо.