1

我想查询特定点的指数加权移动平均线的值。一种低效的方法如下。l是事件的时间列表，并且queries有我想要这个平均值的时间。

a=0.01
l = [3,7,10,20,200]
y = [0]*1000
for item in l:
        y[int(item)]=1
s = [0]*1000
for i in xrange(1,1000):
    s[i] = a*y[i-1]+(1-a)*s[i-1]

queries = [23,68,103]

for q in queries:
        print s[q]

输出：

0.0355271185019
0.0226018371526
0.0158992102478

在实践l中将非常大，并且值的范围l也将很大。您如何才能更有效地找到有时的值queries，尤其是在不显式计算潜在巨大列表的情况y下s。我需要它在纯 python 中，所以我可以使用 pypy。

是否有可能及时解决问题，len(l) 而不是max(l)（假设len(queries) < len(l)）？

4

3 回答 3

1

如果 l 已排序，我认为您可以在 ln(l) 时间内完成。基本思想是 EMA 的非递归形式是 a*s_i + (1-a)^1 * s_(i-1) + (1-a)^2 * s_(i-2) ...。

这意味着对于查询 k，您会在 l 中找到小于 k 的最大数，对于估计限制，请使用以下内容，其中 v 是 l 中的索引，l[v] 是值

(1-a)^(kv) *l[v] + ....

然后，您在搜索中花费 lg(len(l)) 时间 + 一个常数倍数来评估您的估计深度。如果你想要的话，我会在稍后（下班后）提供一个代码示例，只是想在我思考的时候把我的想法拿出来

这是代码 - v 是给定时间的值字典；如果每次都只是 1，则替换为 1...

import math
from bisect import bisect_right

a = .01
limit = 1000
l = [1,5,14,29...]

def find_nearest_lt(l, time):
    i = bisect_right(a, x)
    if i:
        return i-1
    raise ValueError

def find_ema(l, time):
    i = find_nearest_lt(l, time)
    if l[i] == time:
        result = a * v[l[i]
        i -= 1
    else:
        result = 0
    while (time-l[i]) < limit:
        result += math.pow(1-a, time-l[i]) * v[l[i]]
        i -= 1
    return result

如果我的想法正确，那么最近的查找是 l(n)，那么 while 循环是 <= 1000 次迭代，保证，所以它在技术上是一个常数（虽然是一种大的）。find_nearest 从 bisect 的页面上被盗 - http://docs.python.org/2/library/bisect.html

于 2013-08-19T19:45:21.680 回答
1

这是我这样做的代码：

def ewma(l, queries, a=0.01):
  def decay(t0, x, t1, a):
    from math import pow
    return pow((1-a), (t1-t0))*x

  assert l == sorted(l)
  assert queries == sorted(queries)

  samples = []
  try:
    t0, x0 = (0.0, 0.0)
    it = iter(queries)
    q = it.next()-1.0

    for t1 in l:
      # new value is decayed previous value, plus a
      x1 = decay(t0, x0, t1, a) + a
      # take care of all queries between t0 and t1
      while q < t1:
        samples.append(decay(t0, x0, q, a))
        q = it.next()-1.0
      # take care of all queries equal to t1
      while q == t1:
        samples.append(x1)
        q = it.next()-1.0
      # update t0, x0
      t0, x0 = t1, x1

    # take care of any remaining queries
    while True:
      samples.append(decay(t0, x0, q, a))
      q = it.next()-1.0
  except StopIteration:
    return samples

我还上传了此代码的完整版本，其中包含单元测试和对 pastebin 的一些评论：http: //pastebin.com/shhaz710

编辑：请注意，这与 Chris Pak 在他的回答中建议的内容相同，他必须在我输入此内容时发布。我没有详细了解他的代码，但我认为我的代码更笼统一些。l此代码支持和中的非整数值queries。它也适用于任何类型的迭代，而不仅仅是列表，因为我不做任何索引。

于 2013-08-19T20:42:04.617 回答
0

看起来这y是一个二进制值——0 或 1——取决于l. 为什么不使用y = set(int(item) for item in l)？这是存储和查找数字列表的最有效方式。

您的代码将在第一次通过此循环时导致错误：

s = [0]*1000
for i in xrange(1000):
    s[i] = a*y[i-1]+(1-a)*s[i-1]

因为i-1是-1当 i=0 （循环的第一遍）并且两者y[-1]和s[-1]都是列表的最后一个元素，而不是前一个元素。也许你想要xrange(1,1000)？

这段代码怎么样：

a=0.01
l = [3.0,7.0,10.0,20.0,200.0]
y = set(int(item) for item in l)
queries = [23,68,103]

ewma = []
x = 1 if (0 in y) else 0
for i in xrange(1, queries[-1]):
    x = (1-a)*x
    if i in y:
        x += a
    if i == queries[0]:
        ewma.append(x)
        queries.pop(0)

完成后，ewma应该有每个查询点的移动平均值。

编辑包括 SchighSchagh 的改进。

于 2013-08-19T19:25:37.880 回答