В чем разница во временной сложности этих двух способов использования циклов в VBA? - PullRequest
Новая
       3

В чем разница во временной сложности этих двух способов использования циклов в VBA?

3 голосов
/ 28 января 2011

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

Скажем, у нас есть эти две части кода. Первый: 

For Each cell In rng1
    collectionOfValues.Add (cell.Value)
Next

For Each cell In rng2
   collectionOfAddresses.Add (cell.Address)
Next

For i = 1 To collectionOfAddresses.Count
   Range(collectionOfAddresses.Item(i)) = collectionOfValues.Item(i)
Next i

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

Вот второй код, который делает то же самое: 

For i = 1 To rng1.Rows.Count
  For j = 1 To rng1.Columns.Count
       rng2.Cells(i, j) = rng1.Cells(i, j)
  Next j
Next i

Итак, вопрос в том, каково время исполнения в обоих случаях? Я имею в виду, что ясно, что второй случай - это O (n ^ 2) (чтобы было проще, предположим, что диапазон квадратный).

А как насчет первого? Для каждого считается вложенным циклом?

А если так, значит ли это, что время первого кода O (n ^ 2) + O (n ^ 2) + O (n ^ 2) = 3 * O (n ^ 2), что делает довольно так же, как и второй код времени?

В общем, отличаются ли эти два кода от того факта, что первый занимает дополнительную память при создании коллекций?

Заранее большое спасибо.

Ответы [ 3 ]

5 голосов
/ 28 января 2011

На самом деле, ваш первый пример: O (n ^ 4) !

Это может звучать удивительно, но это потому, что индексирование в Коллекцию VBA имеет линейный, а не постоянный, сложность .Коллекция VBA по существу имеет характеристики производительности списка - для получения элемента N по индексу требуется время, пропорциональное N. Для итерации всего элемента по индексу требуется время, пропорциональное N^ 2.(Я переключил случаи на вас, чтобы отличить N, количество элементов в структуре данных от вашего n, количество ячеек на стороне квадратного блока ячеек. Так что здесь N = n ^ 2.)

Это одна из причин, почему VBA имеет обозначение For ... Each для итерации коллекций.Когда вы используете For ... Each, VBA использует за кулисами итератор, поэтому проход по всей Коллекции - это O (N), а не O (N ^ 2).

Итак, переключаясь на n, вашпервые два цикла используют For ... Каждый в диапазоне с n ^ 2 ячейками, поэтому каждый из них равен O (n ^ 2).Ваш третий цикл использует For ... Next над коллекцией с n ^ 2 элементами, то есть O (n ^ 4).

На самом деле я точно не знаю о вашем последнем цикле, потому что я неНе знаю точно, как работает свойство Cells в Range - там может быть какая-то дополнительная скрытая сложность.Но я думаю, что у Cells будут характеристики производительности массива, поэтому O (1) для произвольного доступа по индексу, и это сделало бы последний цикл O (n ^ 2).

Это хороший примерто, что Джоэл Спольски назвал «Алгоритм Шлемиэля художника»:

Где-то там должен быть Алгоритм Шлемиэля Художника.Всякий раз, когда что-то кажется, что оно должно иметь линейную производительность, но кажется, что оно имеет производительность в n-квадрате, ищите скрытые Шлемиели.Они часто скрыты вашими библиотеками.

(См. Эту статью еще до того, как был основан stackoverflow: http://www.joelonsoftware.com/articles/fog0000000319.html)

Подробнее о производительности VBA можно узнать на сайте Дуга Дженкинса:

http://newtonexcelbach.wordpress.com/2010/03/07/the-speed-of-loops/

http://newtonexcelbach.wordpress.com/2010/01/15/good-practice-best-practice-or-just-practice/

(я также повторю то, что сказал cyberkiwi о том, что не нужно циклически проходить через диапазоны, просто для копирования содержимого ячейки, если это была «настоящая» программа ине просто учебное упражнение.)

0 голосов
/ 28 января 2011

Не забудьте не путать сложность ВАШЕГО кода со сложностью фоновых функций Excel.За весь объем проделанной работы N ^ 2 в обоих случаях.Тем не менее, в вашем первом примере - ваш код на самом деле только 3N (N для каждого из трех циклов).Тот факт, что один оператор в Excel может заполнить несколько значений, не меняет сложности написанного вами кода.Цикл foreach - это то же самое, что и цикл for - N сложность.Вы получаете N ^ 2 только тогда, когда вкладываете циклы.

Чтобы ответить на ваш вопрос о том, что лучше - обычно предпочтительнее использовать встроенные функции там, где это возможно.Предполагается, что внутренне Excel будет работать более эффективно, чем вы могли бы написать сами.Однако (зная MS) - всегда проверяйте это предположение, если производительность является приоритетом.

0 голосов
/ 28 января 2011

Вы правы, что первым является 3 x O (n ^ 2), но помните, что O-нотация не заботится о константах, поэтому с точки зрения сложности она все еще является O(n^2) algorithm.

Первый не считается вложенным циклом, даже если он работает с тем же размером, что и цикл во втором. Это просто прямая итерация в диапазоне N элементов в Excel. Что делает его N ^ 2, так это то, что вы определяете N как длину стороны, то есть количество строк / столбцов (являющихся квадратными).

Просто заметка Excel VBA, вы не должны ни циклически проходить по ячейкам, ни хранить адреса. Ни один из подходов не является оптимальным. Но я думаю, что они служат, чтобы проиллюстрировать ваш вопрос, чтобы понять О-нотацию. 

rng1.Copy
rng2.Cells(1).PasteSpecial xlValues
Application.CutCopyMode = False
...