4

我有两个相当简单的代码片段,而且我都运行了很多次;我正在尝试确定是否可以进行任何优化来加快执行时间。如果有什么突出的东西可以更快地完成......

在第一个中,我们有一个列表,字段。我们还有一个列表和权重列表。我们试图找出哪个权重列表乘以字段将产生最大总和。字段大约有 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

在第二个中,我们试图更新我们的两个权重列表;一个增加一个减少。增加/减少每个元素的量等于字段中的相应元素(例如,如果字段[4] = 10.5,那么我们希望将权重[toincrease][4] 增加 10.5 并减少权重[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

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

4

6 回答 6

7

当您尝试优化时,您要做的就是分析和衡量!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  http://stackoverflow.com/a/10134298/1256624

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  http://stackoverflow.com/a/10134247/1256624

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  http://stackoverflow.com/a/10134147/1256624 

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(对不起,我找不到 atm 的文档)的 numpy 版本是最快的。如果您正在执行大量数值运算(您似乎是这样),则可能值得在创建它们后立即将其转换fieldsweightsnumpy 数组。

更新权重

Numpy 可能会为 提供类似的加速update_weights,例如:

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

(顺便说一句,我没有测试或分析过,你需要这样做。)

于 2012-04-13T02:19:19.920 回答
4

我认为您可以使用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])
于 2012-04-13T01:28:35.403 回答
3

如果您正在运行 Python 2.x,我会使用 xrange() 而不是 range(),因为它不会生成列表,所以使用更少的内存

这是假设您要保留当前的代码结构。

于 2012-04-13T01:21:31.570 回答
3

首先,如果您使用的是 Python 2.x,则可以通过使用xrange()而不是range(). 在 Python 3.xxrange()中没有.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()值可能会在速度上取得巨大的胜利。

编辑:我错过了一个技巧。而不是lambda函数,我应该operator.itemgetter()像接受答案中的一些代码一样使用。此外,接受的答案是定时的,看起来函数调用的开销很大。但是 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()所以,这里我们直接迭代字段值,而不是迭代一个。我们有一条强制浮动的线。

请注意,如果权重值已经是浮动的,我们实际上不需要强制在此处浮动,我们可以通过删除该行来节省时间。

您的代码对权重列表进行了四次索引:两次进行增量,两次进行减量。此代码只执行第一个索引(使用toincreaseor 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

测量测量测量。看看我的建议有多快,或者不是。

于 2012-04-13T01:44:20.750 回答
2

一个简单的优化是使用xrange而不是range. xrange是一个生成器函数,yields当您对其进行迭代时,它会一一生成;而range首先将整个(30,000 项)列表创建为临时对象,使用更多的内存和 CPU 周期。

于 2012-04-13T01:21:48.690 回答
2

正如@Levon 所说,xrange()在 python2.x 中是必须的。此外,如果您在 python2.4+ 中,您可以使用generator expression(thanks @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 wiki 上有这个很棒的页面,介绍了简单但有效的优化技巧!

于 2012-04-13T01:51:06.827 回答