Эмпирически оценивая эффективность большого времени

Ответ 1

Чтобы начать работу, вы должны сделать пару предположений.

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

В частности, (3) трудно достичь в соответствии с (1). Таким образом, вы можете получить что-то с экспоненциальным худшим случаем, но никогда не сталкиваетесь с этим худшим случаем и, таким образом, думаете, что ваш алгоритм намного лучше, чем в среднем.

С учетом этого все, что вам нужно, это любая стандартная библиотека подбора кривой. Apache Commons Math имеет полностью адекватный. Затем вы создаете функцию со всеми общими терминами, которые вы хотите протестировать (например, константа, log n, n, n log n, nn, nn * n, e ^ n), или вы берете журнал своих данных и экспонента, а затем, если вы получите показатель, не близкий к целому числу, посмотрите, лучше ли вбрасывание в log n.

(Более подробно, если вы поместили C*x^a для C и a, или более легко log C + a log x, вы можете получить показатель a; во всех общих терминах-в-одном схемы, вы получите веса для каждого термина, поэтому, если у вас n*n + C*n*log(n), где C велико, вы также подберете этот термин.)

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

Изменить: Вот код Scala, который делает все это для вас. Вместо того, чтобы объяснять каждый маленький кусочек, я оставлю его вам для расследования; он реализует вышеприведенную схему, используя C * x ^ a fit, и возвращает ((a, C), (нижняя граница для a, верхняя граница для a)). Оценки довольно консервативны, как вы можете видеть из нескольких вещей. Единицы измерения C равны секундам (a без единиц), но не верьте, что слишком много, так как есть некоторые накладные расходы на цикл (а также некоторый шум).

class TimeLord[A: ClassManifest,B: ClassManifest](setup: Int => A, static: Boolean = true)(run: A => B) {
  @annotation.tailrec final def exceed(time: Double, size: Int, step: Int => Int = _*2, first: Int = 1): (Int,Double) = {
    var i = 0
    val elapsed = 1e-9 * {
      if (static) {
        val a = setup(size)
        var b: B = null.asInstanceOf[B]
        val t0 = System.nanoTime
        var i = 0
        while (i < first) {
          b = run(a)
          i += 1
        }
        System.nanoTime - t0
      }
      else {
        val starts = if (static) { val a = setup(size); Array.fill(first)(a) } else Array.fill(first)(setup(size))
        val answers = new Array[B](first)
        val t0 = System.nanoTime
        var i = 0
        while (i < first) {
          answers(i) = run(starts(i))
          i += 1
        }
        System.nanoTime - t0
      }
    }
    if (time > elapsed) {
      val second = step(first)
      if (second <= first) throw new IllegalArgumentException("Iteration size increase failed: %d to %d".format(first,second))
      else exceed(time, size, step, second)
    }
    else (first, elapsed)
  }

  def multibench(smallest: Int, largest: Int, time: Double, n: Int, m: Int = 1) = {
    if (m < 1 || n < 1 || largest < smallest || (n>1 && largest==smallest)) throw new IllegalArgumentException("Poor choice of sizes")
    val frac = (largest.toDouble)/smallest
    (0 until n).map(x => (smallest*math.pow(frac,x/((n-1).toDouble))).toInt).map{ i => 
      val (k,dt) = exceed(time,i)
      if (m==1) i -> Array(dt/k) else {
        i -> ( (dt/k) +: (1 until m).map(_ => exceed(time,i,first=k)).map{ case (j,dt2) => dt2/j }.toArray )
      }
    }.foldLeft(Vector[(Int,Array[Double])]()){ (acc,x) =>
      if (acc.length==0 || acc.last._1 != x._1) acc :+ x
      else acc.dropRight(1) :+ (x._1, acc.last._2 ++ x._2)
    }
  }

  def alpha(data: Seq[(Int,Array[Double])]) = {
    // Use Theil-Sen estimator for calculation of straight-line fit for exponent
    // Assume timing relationship is t(n) = A*n^alpha
    val dat = data.map{ case (i,ad) => math.log(i) -> ad.map(x => math.log(i) -> math.log(x)) }
    val slopes = (for {
      i <- dat.indices
      j <- ((i+1) until dat.length)
      (pi,px) <- dat(i)._2
      (qi,qx) <- dat(j)._2
    } yield (qx - px)/(qi - pi)).sorted
    val mbest = slopes(slopes.length/2)
    val mp05 = slopes(slopes.length/20)
    val mp95 = slopes(slopes.length-(1+slopes.length/20))
    val intercepts = dat.flatMap{ case (i,a) => a.map{ case (li,lx) => lx - li*mbest } }.sorted
    val bbest = intercepts(intercepts.length/2)
    ((mbest,math.exp(bbest)),(mp05,mp95))
  }
}

Обратите внимание, что метод multibench, как ожидается, займет около времени sqrt (2) nm * для запуска, считая, что данные статической инициализации используются и относительно дешевы по сравнению с тем, что вы используете. Вот несколько примеров с параметрами, выбранными для запуска ~ 15 секунд:

val tl1 = new TimeLord(x => List.range(0,x))(_.sum)  // Should be linear
// Try list sizes 100 to 10000, with each run taking at least 0.1s;
// use 10 different sizes and 10 repeats of each size
scala> tl1.alpha( tl1.multibench(100,10000,0.1,10,10) )
res0: ((Double, Double), (Double, Double)) = ((1.0075537890632216,7.061397125245351E-9),(0.8763463348353099,1.102663784225697))

val longList = List.range(0,100000)
val tl2 = new TimeLord(x=>x)(longList.apply)    // Again, should be linear
scala> tl2.alpha( tl2.multibench(100,10000,0.1,10,10) )
res1: ((Double, Double), (Double, Double)) = ((1.4534378213477026,1.1325696181862922E-10),(0.969955396265306,1.8294175293676322))

// 1.45?!  That not linear.  Maybe the short ones are cached?
scala> tl2.alpha( tl2.multibench(9000,90000,0.1,100,1) )
res2: ((Double, Double), (Double, Double)) = ((0.9973235607566956,1.9214696731124573E-9),(0.9486294398193154,1.0365312207345019))

// Let try some sorting
val tl3 = new TimeLord(x=>Vector.fill(x)(util.Random.nextInt))(_.sorted)
scala> tl3.alpha( tl3.multibench(100,10000,0.1,10,10) )
res3: ((Double, Double), (Double, Double)) = ((1.1713142886974603,3.882658025586512E-8),(1.0521099621639414,1.3392622111121666))
// Note the log(n) term comes out as a fractional power
// (which will decrease as the sizes increase)

// Maybe sort some arrays?
// This may take longer to run because we have to recreate the (mutable) array each time
val tl4 = new TimeLord(x=>Array.fill(x)(util.Random.nextInt), false)(java.util.Arrays.sort)
scala> tl4.alpha( tl4.multibench(100,10000,0.1,10,10) )
res4: ((Double, Double), (Double, Double)) = ((1.1216172965292541,2.2206198821180513E-8),(1.0929414090177318,1.1543697719880128))

// Let time something slow
def kube(n: Int) = (for (i <- 1 to n; j <- 1 to n; k <- 1 to n) yield 1).sum
val tl5 = new TimeLord(x=>x)(kube)
scala> tl5.alpha( tl5.multibench(10,100,0.1,10,10) )
res5: ((Double, Double), (Double, Double)) = ((2.8456382116915484,1.0433534274508799E-7),(2.6416659356198617,2.999094292838751))
// Okay, we're a little short of 3; there constant overhead on the small sizes

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

(Кстати, здесь нет явного шага прогрева, надежная подгонка оценщика Theil-Sen должна сделать его ненужным для разумно больших эталонных показателей. Именно поэтому я не использую никаких других рамок для скамейки; просто теряет силу от этого теста.)

Изменить еще раз: если вы замените метод alpha следующим образом:

  // We'll need this math
  @inline private[this] def sq(x: Double) = x*x
  final private[this] val inv_log_of_2 = 1/math.log(2)
  @inline private[this] def log2(x: Double) = math.log(x)*inv_log_of_2
  import math.{log,exp,pow}

  // All the info you need to calculate a y value, e.g. y = x*m+b
  case class Yp(x: Double, m: Double, b: Double) {}

  // Estimators for data order
  //   fx = transformation to apply to x-data before linear fitting
  //   fy = transformation to apply to y-data before linear fitting
  //   model = given x, slope, and intercept, calculate predicted y
  case class Estimator(fx: Double => Double, invfx: Double=> Double, fy: (Double,Double) => Double, model: Yp => Double) {}
  // C*n^alpha
  val alpha = Estimator(log, exp, (x,y) => log(y), p => p.b*pow(p.x,p.m))
  // C*log(n)*n^alpha
  val logalpha = Estimator(log, exp, (x,y) =>log(y/log2(x)), p => p.b*log2(p.x)*pow(p.x,p.m))

  // Use Theil-Sen estimator for calculation of straight-line fit
  case class Fit(slope: Double, const: Double, bounds: (Double,Double), fracrms: Double) {}
  def theilsen(data: Seq[(Int,Array[Double])], est: Estimator = alpha) = {
    // Use Theil-Sen estimator for calculation of straight-line fit for exponent
    // Assume timing relationship is t(n) = A*n^alpha
    val dat = data.map{ case (i,ad) => ad.map(x => est.fx(i) -> est.fy(i,x)) }
    val slopes = (for {
      i <- dat.indices
      j <- ((i+1) until dat.length)
      (pi,px) <- dat(i)
      (qi,qx) <- dat(j)
    } yield (qx - px)/(qi - pi)).sorted
    val mbest = slopes(slopes.length/2)
    val mp05 = slopes(slopes.length/20)
    val mp95 = slopes(slopes.length-(1+slopes.length/20))
    val intercepts = dat.flatMap{ _.map{ case (li,lx) => lx - li*mbest } }.sorted
    val bbest = est.invfx(intercepts(intercepts.length/2))
    val fracrms = math.sqrt(data.map{ case (x,ys) => ys.map(y => sq(1 - y/est.model(Yp(x,mbest,bbest)))).sum }.sum / data.map(_._2.length).sum)
    Fit(mbest, bbest, (mp05,mp95), fracrms)
  }

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

val tl3 = new TimeLord(x=>Vector.fill(x)(util.Random.nextInt))(_.sorted)
val timings = tl3.multibench(100,10000,0.1,10,10)

// Regular n^alpha fit
scala> tl3.theilsen( timings )
res20: tl3.Fit = Fit(1.1811648421030059,3.353753446942075E-8,(1.1100382697696545,1.3204652930525234),0.05927994882343982)

// log(n)*n^alpha fit--note first value is closer to an integer
//   and last value (error) is smaller
scala> tl3.theilsen( timings, tl3.logalpha )
res21: tl3.Fit = Fit(1.0369167329732445,9.211366397621766E-9,(0.9722967182484441,1.129869067913768),0.04026308919615681)

(Edit: исправлено вычисление RMS, так что оно на самом деле среднее, плюс продемонстрировало, что вам нужно только выполнить тайминги один раз и затем попробовать оба варианта.)

Ответ 2

Я не думаю, что ваш подход будет работать в целом.

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

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

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

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

Followup

В ответ на этот комментарий:

Ваша оценочная значимость значительно улучшит все более и более используемые вами образцы.

Это правда, хотя я хочу сказать, что вы (Daniel) не учитывали это.

Кроме того, функции выполнения обычно имеют особые характеристики, которые могут быть использованы; например, алгоритмы, как правило, не изменяют свое поведение при некотором огромном n.

Для простых случаев да.

Для сложных случаев и случаев реального мира это сомнительное предположение. Например:

• Предположим, что в некотором алгоритме используется хеш-таблица с большим массивом первичных хешей с фиксированным размером и использует внешние списки для борьбы с коллизиями. Для N (== количество записей) меньше размера первичного хеш-массива, поведение большинства операций будет выглядеть как O(1). Истинное поведение O(N) может быть обнаружено только при подгонке кривой, когда N становится намного больше.

• Предположим, что алгоритм использует много памяти или пропускную способность сети. Как правило, он будет работать до тех пор, пока вы не нажмете ограничение на ресурс, а затем производительность сильно снизится. Как вы это объясняете? Если это часть "эмпирической сложности", как вы убедитесь, что дошли до точки перехода? Если вы хотите исключить его, как вы это делаете?

Ответ 3

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

например. если отношение 1000 операций к 10000 операций (10x) (проверьте более длинный первый). Вам нужно сделать реалистичное количество операций, чтобы увидеть, какой порядок для диапазона у вас.

• 1x = > O (1)
• 1.2x = > O (ln ln n)
• ~ 2-5x = > O (ln n)
• 10x = > O (n)
• 20-50x = > O (n ln n)
• 100x = > O (n ^ 2)

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

например. Многие люди пытались доказать эмпирически, что ПИ - это доля. Когда они измеряли отношение окружности к диаметру для кругов, которые они делали, она всегда была фракцией. В конце концов, было общепризнано, что PI не является долей.

Ответ 4

То, что вы ищете, невозможно вообще. Даже тот факт, что алгоритм когда-либо остановится, не может быть доказан в общем случае (см. Проблема с остановкой). И даже если он останавливается на ваших данных, вы все равно не можете определить сложность, запустив его. Например, сортировка пузырьков имеет сложность O (n ^ 2), а на уже отсортированных данных она выполняется так, как если бы она была O (n). Невозможно выбрать "подходящие" данные для неизвестного алгоритма для оценки его наихудшего случая.

Ответ 5

В последнее время мы внедрили инструмент, который выполняет полуавтоматический средний анализ времени выполнения для JVM-кода. Вам даже не нужно иметь доступ к источникам. Он еще не опубликован (по-прежнему гладит некоторые недостатки юзабилити), но скоро, надеюсь.

Он основан на моделях максимального правдоподобия выполнения программы [1]. Короче говоря, байтовый код дополняется счетчиками затрат. Затем целевой алгоритм запускается (распределяется, если хотите) на кучу входов, управление которыми вы контролируете. Агрегированные счетчики экстраполируются на функции, использующие эвристику (метод наименьших квадратов на трещины, вид). Из них больше науки приводит к оценке средней асимптотики времени выполнения (3.576n - 1.23log(n) + 1.7, например). Например, метод способен воспроизводить строгие классические анализы, выполненные Кнутом и Седжуиком с высокой точностью.

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

И, возможно, функция убийцы --- она ​​поставляется с полным графическим интерфейсом, который проведет вас через весь процесс.

Посмотрите мой ответ на cs.SE для получения более подробной информации и дальнейших ссылок. Вы можете найти предварительный сайт (включая бета-версию инструмента и опубликованные статьи) здесь.

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

• Максимальный анализ правдоподобия алгоритмов и структур данных У. Лаубе и М. Э. Небеля (2010). [preprint]

Ответ 6

Вам следует рассмотреть возможность изменения критических аспектов вашей задачи.

Измените терминологию, которую вы используете, чтобы: "оценить время выполнения алгоритма" или "тестирование регрессии производительности установки"

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

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

Ответ 7

Я не уверен, что получаю 100% от того, что вы хотите. Но я понимаю, что вы тестируете свой собственный код, поэтому можете его изменить, например. вводить наблюдательные заявления. В противном случае вы можете использовать какую-то форму ткачества?

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

Тогда для данного метода, скажем delete(x), вы проверите это со всеми видами автоматически генерируемых наборов данных, пытаясь дать им некоторый перекос и т.д., и соберите подсчеты. Хотя, как указывает Игорь, вы не можете проверить, что структура данных никогда не будет нарушать привязку большого O, вы, по крайней мере, сможете утверждать, что в фактическом эксперименте заданное значение предела никогда не будет превышено (например, спустив node в дереве никогда не делается больше, чем 4 * log(n) раз), поэтому вы можете обнаружить некоторые ошибки.

Конечно, вам понадобятся определенные предположения, например. что вызов метода - это O (1) в вашей компьютерной модели.

Ответ 8

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

Это требование является ключевым. Вы хотите обнаружить выбросы с минимальными данными (потому что тестирование должно быть быстрым, чертовски), и, по моему опыту, подгонять кривые к числовым оценкам сложных рекуррентностей, линейная регрессия и т.д. Будут перерабатывать. Я думаю, что ваша первоначальная идея хорошая.

Что бы я сделал, чтобы выполнить его, подготовьте список ожидаемых функций сложности g1, g2,... и для данных f, проверьте, насколько близко к константе f/gi + gi/f для каждого i. С функцией стоимости наименьших квадратов это просто вычисляет variance этой величины для каждого я и сообщает о наименьшей. Взгляните на отклонения в конце и вручную проверите необычно плохие припасы.

Ответ 9

Для эмпирического анализа сложности программы то, что вы будете делать, - это запустить (и время) алгоритм, заданный элементами ввода 10, 50, 100, 500, 1000 и т.д. Затем вы можете графически отображать результаты и определять оптимальный порядок функций из наиболее распространенных основных типов: константный, логарифмический, линейный, nlogn, квадратичный, кубический, высокополиномиальный, экспоненциальный. Это нормальная часть тестирования нагрузки, которая гарантирует, что алгоритм сначала ведет себя как теоретизированный, а во-вторых, что он отвечает ожиданиям реального мира, несмотря на его теоретическую сложность (алгоритм логарифмического времени, в котором каждый шаг занимает 5 минут потерять все, кроме абсолютных тестов с максимальной мощностью, алгоритму квадратичной сложности, в котором каждый шаг составляет несколько миллисов).

РЕДАКТИРОВАТЬ: Ломать его, алгоритм очень прост:

Определите список N различных мощностей, для которых вы хотите оценить производительность (10 100 1000 10000 и т.д.)

Для каждого элемента X из N:

Создайте подходящий набор тестовых данных с элементами X.

Запустите секундомер или определите и сохраните текущее системное время.

Запустите алгоритм по тестовому набору X-элементов.

Остановите секундомер или снова определите системное время.

Разница между временем начала и остановки - это время выполнения вашего алгоритма над элементами X.

Повторяем для каждого X в N.

Запланируйте результаты; при заданных X элементах (по оси x) алгоритм принимает время T (ось y). Ближайшей основной функцией, определяющей увеличение T при увеличении X, является ваше приближение Big-Oh. Как было сказано Рафаэлем, это приближение в точности таково и не даст вам очень тонких различий, таких как коэффициенты N, которые могли бы сделать разницу между алгоритмом N ^ 2 и алгоритмом 2N ^ 2 (оба являются технически O (N ^ 2), но при том же числе элементов один будет выполняться в два раза быстрее).