Неожиданно большое время вычислений с пакетом неопределенностей

Question

Рассмотрим следующий фрагмент кода:

import random
from uncertainties import unumpy, ufloat

x = [random.uniform(0,1) for p in range(1,8200)]
y = [random.randrange(0,1000) for p in range(1,8200)]
xerr = [random.uniform(0,1)/1000 for p in range(1,8200)]
yerr = [random.uniform(0,1)*10 for p in range(1,8200)]

x = unumpy.uarray(x, xerr)
y = unumpy.uarray(y, yerr)
diff = sum(x*y)
u = ufloat(0.0, 0.0)
for k in range(len(x)):
    u+= (diff-x[k])**2 * y[k]  

print(u)

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

Если вы этого не знаете, это - репозиторий библиотеки неопределенностей.

Answer 1

Я могу воспроизвести это, печать - это то, что нужно вечно. Или, скорее, это преобразование в строку, неявно вызываемое print. Я использовал line_profiler для измерения времени __format__ функции AffineScalarFunc. (Он вызывается __str__, который вызывается печатью) Я уменьшил размер массива с 8200 до 1000, чтобы он работал немного быстрее. Это результат (сокращен для удобства чтения):

Timer unit: 1e-06 s

Total time: 29.1365 s
File: /home/veith/Projects/stackoverflow/test/lib/python3.6/site-packages/uncertainties/core.py
Function: __format__ at line 1813

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  1813                                               @profile
  1814                                               def __format__(self, format_spec):

  1960                                           
  1961                                                   # Since the '%' (percentage) format specification can change
  1962                                                   # the value to be displayed, this value must first be
  1963                                                   # calculated. Calculating the standard deviation is also an
  1964                                                   # optimization: the standard deviation is generally
  1965                                                   # calculated: it is calculated only once, here:
  1966         1          2.0      2.0      0.0          nom_val = self.nominal_value
  1967         1   29133097.0 29133097.0    100.0          std_dev = self.std_dev
  1968                                           

Вы можете видеть, что почти все время занято в строке 1967 года, где вычисляется стандартное отклонение. Если вы покопаетесь немного глубже, вы обнаружите, что свойство error_components является проблемой, где свойство derivatives является проблемой, в которой проблема _linear_part.expand(). Если вы профилируете это, вы начнете понимать причину проблемы. Большая часть работы здесь распределена равномерно:

Function: expand at line 1481

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
  1481                                               @profile
  1482                                               def expand(self):
  1483                                                   """
  1484                                                   Expand the linear combination.
  1485                                           
  1486                                                   The expansion is a collections.defaultdict(float).
  1487                                           
  1488                                                   This should only be called if the linear combination is not
  1489                                                   yet expanded.
  1490                                                   """
  1491                                           
  1492                                                   # The derivatives are built progressively by expanding each
  1493                                                   # term of the linear combination until there is no linear
  1494                                                   # combination to be expanded.
  1495                                           
  1496                                                   # Final derivatives, constructed progressively:
  1497         1          2.0      2.0      0.0          derivatives = collections.defaultdict(float)
  1498                                           
  1499  15995999    4942237.0      0.3      9.7          while self.linear_combo:  # The list of terms is emptied progressively
  1500                                           
  1501                                                       # One of the terms is expanded or, if no expansion is
  1502                                                       # needed, simply added to the existing derivatives.
  1503                                                       #
  1504                                                       # Optimization note: since Python's operations are
  1505                                                       # left-associative, a long sum of Variables can be built
  1506                                                       # such that the last term is essentially a Variable (and
  1507                                                       # not a NestedLinearCombination): popping from the
  1508                                                       # remaining terms allows this term to be quickly put in
  1509                                                       # the final result, which limits the number of terms
  1510                                                       # remaining (and whose size can temporarily grow):
  1511  15995998    6235033.0      0.4     12.2              (main_factor, main_expr) = self.linear_combo.pop()
  1512                                           
  1513                                                       # print "MAINS", main_factor, main_expr
  1514                                           
  1515  15995998   10572206.0      0.7     20.8              if main_expr.expanded():
  1516  15992002    6822093.0      0.4     13.4                  for (var, factor) in main_expr.linear_combo.items():
  1517   7996001    8070250.0      1.0     15.8                      derivatives[var] += main_factor*factor
  1518                                           
  1519                                                       else:  # Non-expanded form
  1520  23995993    8084949.0      0.3     15.9                  for (factor, expr) in main_expr.linear_combo:
  1521                                                               # The main_factor is applied to expr:
  1522  15995996    6208091.0      0.4     12.2                      self.linear_combo.append((main_factor*factor, expr))
  1523                                           
  1524                                                       # print "DERIV", derivatives
  1525                                           
  1526         1          2.0      2.0      0.0          self.linear_combo = derivatives

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

В __init__ из AffineScalarFunc:

# In order to have a linear execution time for long sums, the
# _linear_part is generally left as is (otherwise, each
# successive term would expand to a linearly growing sum of
# terms: efficiently handling such terms [so, without copies]
# is not obvious, when the algorithm should work for all
# functions beyond sums).

В std_dev из AffineScalarFunc:

#! It would be possible to not allow the user to update the
#std dev of Variable objects, in which case AffineScalarFunc
#objects could have a pre-calculated or, better, cached
#std_dev value (in fact, many intermediate AffineScalarFunc do
#not need to have their std_dev calculated: only the final
#AffineScalarFunc returned to the user does).

В expand из LinearCombination:

   # The derivatives are built progressively by expanding each
    # term of the linear combination until there is no linear
    # combination to be expanded.

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