这段代码中有哪些Python优化？

Question

我有两个非常简单的代码片段，我正在大量运行它们；我试图确定是否有任何优化可以加快执行时间。如果有任何明显可以更快完成的事情...

在第一个代码片段中，我们有一个列表fields。我们还有一个列表的列表weights。我们试图找出哪个权重列表乘以fields将产生最大的总和。Fields大约有30k个条目。

def find_best(weights,fields):
  winner = -1
  best = -float('inf')
  for c in range(num_category):
    score = 0
    for i in range(num_fields):
      score += float(fields[i]) * weights[c][i]
    if score > best:
      best = score
      winner = c
  return winner

在第二种情况下，我们试图更新两个重量列表; 一个增加，一个减少。每个元素要增加/减少的数量与fields中的相应元素相等（例如，如果fields [4] = 10.5，则我们希望将weights [toincrease] [4]增加10.5并将weights [todecrease] [4]减少10.5）

 def update_weights(weights,fields,toincrease,todecrease):
   for i in range(num_fields):
     update = float(fields[i])
     weights[toincrease][i] += update
     weights[todecrease][i] -= update
   return weights

希望这不是一个过于具体的问题。

- Fergusmac

---

以 if score > best: 开头的代码块是否应该减少一个缩进级别？ - huon

每一行权重有多长？（与字段长度相同吗？） - huon

你为什么要在字段上调用 float？ - huon

我承认，那可能有点儿傻；我应该早些在别的地方进行浮点数转换。这个列表是由字符串组成的。那可能是一个很好的改进…… - Fergusmac

是的，在创建“fields”列表时，请提前进行转换。 - huon

Answer 1

当你试图进行优化时，你需要做的是分析和测量！Python提供了timeit模块，使得测量变得容易！

这将假定您已经将字段转换为浮点数列表（在这些函数之外），因为字符串→浮点数转换非常缓慢。您可以通过fields = [float(f) for f in string_fields]来完成。

此外，对于数字处理，纯Python并不是很好，因为它每次操作都要进行大量的类型检查（以及其他一些操作）。使用像numpy这样的C库将会带来巨大的改进。

find_best

我已经将其他人的答案（以及更多）合并到一个分析套件中（比如说，test_find_best.py）：

import random, operator, numpy as np, itertools, timeit

fields = [random.random() for _ in range(3000)]
fields_string = [str(field) for field in fields]
weights = [[random.random() for _ in range(3000)] for c in range(100)]

npw = np.array(weights)
npf = np.array(fields)   

num_fields = len(fields)
num_category = len(weights)

def f_original():
  winner = -1
  best = -float('inf')
  for c in range(num_category):
    score = 0
    for i in range(num_fields):
      score += float(fields_string[i]) * weights[c][i]
    if score > best:
      best = score
      winner = c
  
def f_original_no_string():
  winner = -1
  best = -float('inf')
  for c in range(num_category):
    score = 0
    for i in range(num_fields):
      score += fields[i] * weights[c][i]
    if score > best:
      best = score
      winner = c
      
def f_original_xrange():
  winner = -1
  best = -float('inf')
  for c in xrange(num_category):
    score = 0
    for i in xrange(num_fields):
      score += fields[i] * weights[c][i]
    if score > best:
      best = score
      winner = c


# Zenon  https://dev59.com/ZWLVa4cB1Zd3GeqPyKTT#10134298

def f_index_comprehension():
    winner = -1
    best = -float('inf')
    for c in range(num_category):
      score = sum(fields[i] * weights[c][i] for i in xrange(num_fields))
      if score > best:
        best = score
        winner = c  


# steveha  https://dev59.com/ZWLVa4cB1Zd3GeqPyKTT#10134247

def f_comprehension():
  winner = -1
  best = -float('inf')

  for c in xrange(num_category):
    score = sum(f * w for f, w in itertools.izip(fields, weights[c]))
    if score > best:
      best = score
      winner = c

def f_schwartz_original(): # https://en.wikipedia.org/wiki/Schwartzian_transform
    tup = max(((i, sum(t[0] * t[1] for t in itertools.izip(fields, wlist))) for i, wlist in enumerate(weights)),
              key=lambda t: t[1]
             )

def f_schwartz_opt(): # https://en.wikipedia.org/wiki/Schwartzian_transform
    tup = max(((i, sum(f * w for f,w in itertools.izip(fields, wlist))) for i, wlist in enumerate(weights)),
              key=operator.itemgetter(1)
             )

def fweight(field_float_list, wlist):
    f = iter(field_float_list)
    return sum(f.next() * w for w in wlist)
        
def f_schwartz_iterate():
     tup = max(
         ((i, fweight(fields, wlist)) for i, wlist in enumerate(weights)),
         key=lambda t: t[1]
      )
                                        
# Nolen Royalty  https://dev59.com/ZWLVa4cB1Zd3GeqPyKTT#10134147 
                           
def f_numpy_mult_sum():
   np.argmax(np.sum(npf * npw, axis = 1))


# me

def f_imap():
  winner = -1
  best = -float('inf')

  for c in xrange(num_category):
    score = sum(itertools.imap(operator.mul, fields, weights[c]))
    if score > best:
      best = score
      winner = c

def f_numpy():
   np.argmax(npw.dot(npf))



for f in [f_original,
          f_index_comprehension,
          f_schwartz_iterate,
          f_original_no_string,
          f_schwartz_original,
          f_original_xrange,
          f_schwartz_opt,
          f_comprehension,
          f_imap]:
   print "%s: %.2f ms" % (f.__name__, timeit.timeit(f,number=10)/10 * 1000)
for f in [f_numpy_mult_sum, f_numpy]:
   print "%s: %.2f ms" % (f.__name__, timeit.timeit(f,number=100)/100 * 1000)

运行python test_find_best.py给我返回：

f_original: 310.34 ms
f_index_comprehension: 102.58 ms
f_schwartz_iterate: 103.39 ms
f_original_no_string: 96.36 ms
f_schwartz_original: 90.52 ms
f_original_xrange: 89.31 ms
f_schwartz_opt: 69.48 ms
f_comprehension: 68.87 ms
f_imap: 53.33 ms
f_numpy_mult_sum: 3.57 ms
f_numpy: 0.62 ms

因此，使用 .dot（抱歉，我目前无法找到相关文档）的 numpy 版本是最快的。如果您正在进行大量的数值运算（似乎是这样），那么在创建 fields 和 weights 时尽早将它们转换为 numpy 数组可能会更值得。

update_weights

Numpy 可能会为 update_weights 提供类似的加速，做类似以下的操作：

def update_weights(weights, fields, to_increase, to_decrease):
  weights[to_increase,:] += fields
  weights[to_decrease,:] -= fields
  return weights

（顺便说一下，我没有测试或分析过那个，你需要自己去做。）

- huon

---

这绝对是最好的答案。我很高兴看到numpy表现得很好（并不意外），但更开心的是看到如此全面的关于如何分析您的代码的答案。 - Nolen Royalty

这是一个非常棒的答案。我需要一些时间来完全消化它。 :) - Fergusmac

@Fergusmac，我已经添加了其他人建议的一些新内容。 - huon

当我运行你的代码时，它告诉我一个ndarray没有.dot()方法。有numpy.dot(vect1, vect2)。但显然你已经运行了代码...我的numpy拷贝可能旧了吗（不是我的系统）？我不确定如何找出。 - Fergusmac

@Fergusmac，import numpy.version; print(numpy.version.version)（版本1.5.1和1.6.1在我的系统上都有.dot）。虽然numpy.dot是等效的。 - huon

啊，它是1.4.1版本。无论如何，这些都非常有帮助，现在运行速度更快，结果仍然正确。 - Fergusmac

Answer 2

我认为你可以使用 numpy 获得相当大的速度提升。非常简单的例子：

>>> fields = numpy.array([1, 4, 1, 3, 2, 5, 1])
>>> weights = numpy.array([[.2, .3, .4, .2, .1, .5, .9], [.3, .1, .1, .9, .2, .4, .5]])
>>> fields * weights
array([[ 0.2,  1.2,  0.4,  0.6,  0.2,  2.5,  0.9],
       [ 0.3,  0.4,  0.1,  2.7,  0.4,  2. ,  0.5]])
>>> result = _
>>> numpy.argmax(numpy.sum(result, axis=1))
1
>>> result[1]
array([ 0.3,  0.4,  0.1,  2.7,  0.4,  2. ,  0.5])

- Nolen Royalty

---

或者你也可以利用Python内置的数组模块（http://docs.python.org/library/array.html），它对于数值类型非常高效。 - Preet Kukreti

Numpy有很多优点，其中之一是使用较少的函数调用，因为通过单个矩阵操作，您可以使用单个调用执行许多逐元素操作。 - heltonbiker

现在我有一个字段数组和另一个权重数组（它是二维的）。权重为39 x 30473，而字段为30473（我使用len(weights[0])进行了测试）。然而，fields * weights一直报错TypeError: unsupported operand type(s) for *: 'numpy.ndarray' and 'numpy.ndarray'。我已经做了一些谷歌搜索，但不确定为什么会出现这种情况。你上面给出的例子运行良好。 - Fergusmac

@Fergusmac，我从谷歌搜索结果中得知这可能与浮点数和float64有关。我知道你对浮点数有一些有趣的转换：也许去掉它们会有所帮助。 - Nolen Royalty

还要注意，您将希望使用点积（我知道有比我的更好的方法！），但这可能会引发相同的错误。 - Nolen Royalty

Answer 3

如果您正在运行Python 2.x，我建议使用xrange()而不是range()，因为它使用的内存较少，因为它不生成一个列表。假设您想保持当前的代码结构。

- Levon

Answer 4

首先，如果你正在使用Python 2.x，你可以使用xrange()代替range()来提高一些速度。在Python 3.x中没有xrange()，但是内置的range()基本上与xrange()相同。

接下来，如果我们要追求速度，我们需要写更少的代码，更多地依赖于Python内置功能（这些功能是为了速度而用C编写的）。

你可以通过在sum()中使用生成器表达式来加快速度，像这样：

from itertools import izip

def find_best(weights,fields):
    winner = -1
    best = -float('inf')
    for c in xrange(num_category):
        score = sum(float(t[0]) * t[1] for t in izip(fields, weights[c]))
        if score > best:
            best = score
            winner = c
    return winner

再次应用相同的思路，让我们尝试使用max()来找到最佳结果。我认为这段代码看起来很丑陋，但如果你对其进行基准测试并且速度足够快，那么它可能是值得的：

from itertools import izip

def find_best(weights, fields):
    tup = max(
        ((i, sum(float(t[0]) * t[1] for t in izip(fields, wlist))) for i, wlist in enumerate(weights)),
        key=lambda t: t[1]
    )
    return tup[0]

啊！但如果我没有犯任何错误，这个代码也可以实现同样的功能，并且应该会大量依赖于Python中的C机制。测试一下它是否更快。

因此，我们在调用max()函数。我们给它一个生成器表达式，它将从生成器表达式返回的值中找到最大值。但你想要最佳值的索引，所以生成器表达式返回一个元组：索引和权重值。因此，我们需要将生成器表达式作为第一个参数传递，而第二个参数必须是一个键函数，该键函数查看元组中的权重值并忽略索引。由于生成器表达式不是max()的唯一参数，因此它需要在括号中。然后，它构建了一个元组，其中包含i和通过上面使用的相同的sum()计算出来的权重值。最后，一旦我们从max()获得一个元组，我们就可以通过索引来获取索引值，并将其返回。

如果我们拆分一个函数，那么这将大大减少丑陋的程度。这会增加函数调用的开销，但是如果你测量一下，我敢打赌它不会慢太多。另外，现在我想到了，构建一个fields值列表，已经预先强制转换为float，这样我们就可以多次使用它。此外，不要使用izip()来同时迭代两个列表，让我们创建一个迭代器并明确地请求它的值。在Python 2.x中，我们使用.next()方法函数来请求值；在Python 3.x中，您将使用内置函数next()。

def fweight(field_float_list, wlist):
    f = iter(field_float_list)
    return sum(f.next() * w for w in wlist)

def find_best(weights, fields):
    flst = [float(x) for x in fields]
    tup = max(
        ((i, fweight(flst, wlist)) for i, wlist in enumerate(weights)),
        key=lambda t: t[1]
    )
    return tup[0]

如果有30K个字段值，则预先计算float()值可能会大大提高速度。

编辑：我错过了一个技巧。 我应该使用operator.itemgetter()而不是lambda函数，就像接受的答案中的一些代码一样。 此外，接受的答案对时间进行了计时，看起来函数调用的开销很大。 但是Numpy的答案要快得多，所以不值得再尝试这个答案了。

至于第二部分，我认为它无法加速太多。 我会尝试：

def update_weights(weights,fields,toincrease,todecrease):
    w_inc = weights[toincrease]
    w_dec = weights[todecrease]
    for i, f in enumerated(fields):
        f = float(f)  # see note below
        w_inc[i] += f
        w_dec[i] -= f

因此，我们不是通过迭代xrange()，而是直接迭代字段值。我们有一行代码将其强制转换为浮点数。

请注意，如果权重值已经是浮点数，则我们不需要在此处强制转换为浮点数，只需删除该行即可节省时间。

您的代码四次索引权重列表：两次执行增量，两次执行减量。此代码仅使用toincrease或todecrease参数进行第一次索引。为了让+=工作，它仍然必须按i进行索引。(我的第一个版本尝试使用迭代器避免这个问题，但是不起作用。我应该在发布之前进行测试。但现在已经修复了。)

最后尝试一种版本：不要在进行增量和减量时逐步改变值，而是使用列表理解构建一个新列表，其中包含我们想要的值：

def update_weights(weights, field_float_list, toincrease, todecrease):
    f = iter(field_float_list)
    weights[toincrease] = [x + f.next() for x in weights[toincrease]]
    f = iter(field_float_list)
    weights[todecrease] = [x - f.next() for x in weights[todecrease]]

假设您已经像上面展示的那样将所有字段值强制转换为浮点数。

这种方式替换整个列表是更快还是更慢？我猜更快，但我不确定。测量一下就知道了！

哦，我应该补充说明：请注意，我上面展示的update_weights()版本不返回weights。这是因为在Python中，不从修改数据结构的函数返回值被认为是一个好习惯，以确保没有人会对哪些函数执行查询和哪些函数改变事物感到困惑。

http://en.wikipedia.org/wiki/Command-query_separation

测量、测量、再测量。看看我的建议有多快，或者有多慢。

- steveha

---

很不幸，权重可能为负数。我非常感谢您花在此答案上的时间。但是，如果表达式可以为负数，其中任何部分仍然适用吗？ - Fergusmac

实际上，我再次查看了您的代码，并且表达式是否可以为负数并不重要。您只需对所有权重求和，而 sum() 是一个完美的方法。我将修改答案，删除关于负权重无法正常工作的部分；我对此是错误的。 - steveha

Answer 5

一个简单的优化是使用xrange代替range。xrange是一个生成器函数，当您迭代它时，它会逐个yield结果；而range首先创建整个（30,000项）列表作为临时对象，使用更多内存和CPU周期。

- Preet Kukreti

Answer 6

正如@Levon所说，Python2.x中的xrange()是必须的。此外，如果你使用的是Python2.4+，你可以使用生成器表达式（感谢@steveha），它们类似于列表推导式（只适用于2.6+），可以在内部循环中简单地使用：

for i in range(num_fields):
      score += float(fields[i]) * weights[c][i]

相当于

score = sum(float(fields[i]) * weights[c][i]) for i in num_fields)

总的来说，Python维基上有一篇关于简单而有效的优化技巧的优化页面！

- Zenon

---

我对不同版本不太熟悉，无法理解方括号的评论。能否请您澄清一下？ - Fergusmac

@Fergusmac 对不起，那不应该出现在这个答案中 :). 我添加了另一个优化提示的链接作为补偿。 - Zenon

你实际上在这里使用的是“生成器表达式”，而不是列表推导式。这是好的和正确的。列表推导式实际上构建了一个列表，但在这里你只想将数字传递给sum()函数。 - steveha