变量的惰性评估
Lazy evaluation of variables
我想按字典顺序比较两个列表,但列表中的值应该在需要时计算。例如,对于这两个列表
a = list([1, 3, 3])
b = list([1, 2, 2])
(a < b) == False
(b < a) == True
我希望列表中的值是函数,在 a
和 b
的情况下,index=2 处的值(即函数)不会被评估为index=1 (a[1]==3, b[1]==2
) 处的值已经足以确定 b < a
.
一个选择是手动比较元素,当我找不到允许我使用列表比较器的解决方案时,我可能会这样做,但我发现手动循环有点慢比列表的内置比较器更重要,这就是我要使用它的原因。
更新
这是一种完成我正在尝试做的事情的方法,但我想知道是否有任何内置函数可以更快地完成此操作(并且利用了列表的这一特性)。
def lex_comp(a, b):
for func_a, func_b in izip(a, b):
v_a = func_a()
v_b = func_b()
if v_a < v_b: return -1
if v_b > v_a: return +1
return 0
def foo1(): return 1
def foo2(): return 1
def bar1(): return 1
def bar2(): return 2
def func1(): return ...
def func2(): return ...
list_a = [foo1, bar1, func1, ...]
list_b = [foo2, bar2, func2, ...]
# now you can use the comparator for instance to sort a list of these lists
sort([list_a, list_b], cmp=lex_comp)
下面是一种使用惰性求值的方法:
>>> def f(x):
... return 2**x
...
>>> def g(x):
... return x*2
...
>>> [f(x) for x in range(1,10)]
[2, 4, 8, 16, 32, 64, 128, 256, 512]
>>> [g(x) for x in range(1,10)]
[2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> zipped = zip((f(i) for i in range(1,10)),(g(i) for i in range(1,10)))
>>> x,y = next(itertools.dropwhile(lambda t: t[0]==t[1],zipped))
>>> x > y
True
>>> x < y
False
>>> x
8
>>> y
6
>>>
试试这个(函数的额外参数仅用于说明目的):
import itertools
def f(a, x):
print "lazy eval of {}".format(a)
return x
a = [lambda: f('a', 1), lambda: f('b', 3), lambda: f('c', 3)]
b = [lambda: f('d', 1), lambda: f('e', 2), lambda: f('f', 2)]
c = [lambda: f('g', 1), lambda: f('h', 2), lambda: f('i', 2)]
def lazyCmpList(a, b):
l = len(list(itertools.takewhile(lambda (x, y): x() == y(), itertools.izip(a, b))))
if l == len(a):
return 0
else:
return cmp(a[l](), b[l]())
print lazyCmpList(a, b)
print lazyCmpList(b, a)
print lazyCmpList(b, c)
生产:
lazy eval of a
lazy eval of d
lazy eval of b
lazy eval of e
-1
lazy eval of d
lazy eval of a
lazy eval of e
lazy eval of b
1
lazy eval of d
lazy eval of g
lazy eval of e
lazy eval of h
lazy eval of f
lazy eval of i
0
请注意,代码假定函数列表的长度相同。可以增强它以支持不相等的列表长度,您必须定义逻辑是什么,即 cmp([f1, f2, f3], [f1, f2, f3, f1])
应该产生什么?
我没有比较过速度,但考虑到您更新的代码,我想任何加速都将是微不足道的(循环在 C 代码中完成,而不是 Python)。该解决方案实际上可能更慢,因为它更复杂并且涉及更多内存分配。
鉴于您正尝试通过评估函数来对函数列表进行排序,因此函数将被评估,即 O(nlogn) 次,因此您最好的加速可能是考虑使用 memoization 来避免反复重估功能。
我做了一些测试,发现@juanpa 的回答和我更新的版本是最快的版本:
import random
import itertools
import functools
num_rows = 100
data = [[random.randint(0, 2) for i in xrange(10)] for j in xrange(num_rows)]
# turn data values into functions.
def return_func(value):
return value
list_funcs = [[functools.partial(return_func, v) for v in row] for row in data]
def lazy_cmp_FujiApple(a, b):
l = len(list(itertools.takewhile(lambda (x, y): x() == y(), itertools.izip(a, b))))
if l == len(a):
return 0
else:
return cmp(a[l](), b[l]())
sorted1 = sorted(list_funcs, lazy_cmp_FujiApple)
%timeit sorted(list_funcs, lazy_cmp_FujiApple)
# 100 loops, best of 3: 2.77 ms per loop
def lex_comp_mine(a, b):
for func_a, func_b in itertools.izip(a, b):
v_a = func_a()
v_b = func_b()
if v_a < v_b: return -1
if v_a > v_b: return +1
return 0
sorted2 = sorted(list_funcs, cmp=lex_comp_mine)
%timeit sorted(list_funcs, cmp=lex_comp_mine)
# 1000 loops, best of 3: 930 µs per loop
def lazy_comp_juanpa(a, b):
x, y = next(itertools.dropwhile(lambda t: t[0]==t[1], itertools.izip(a, b)))
return cmp(x, y)
sorted3 = sorted(list_funcs, cmp=lazy_comp_juanpa)
%timeit sorted(list_funcs, cmp=lex_comp_mine)
# 1000 loops, best of 3: 949 µs per loop
%timeit sorted(data)
# 10000 loops, best of 3: 45.4 µs per loop
# print sorted(data)
# print [[c() for c in row] for row in sorted1]
# print [[c() for c in row] for row in sorted2]
# print sorted3
我想创建中间列表会影响@FujiApple 版本的性能。当 运行 我的比较器版本在原始 data
列表上并将运行时与 Python 的本机列表排序进行比较时,我注意到我的版本慢了大约 10 倍(501 µs vs 45.4 µs环形)。我想没有简单的方法可以接近 Python 的本机实现的性能...
我想按字典顺序比较两个列表,但列表中的值应该在需要时计算。例如,对于这两个列表
a = list([1, 3, 3])
b = list([1, 2, 2])
(a < b) == False
(b < a) == True
我希望列表中的值是函数,在 a
和 b
的情况下,index=2 处的值(即函数)不会被评估为index=1 (a[1]==3, b[1]==2
) 处的值已经足以确定 b < a
.
一个选择是手动比较元素,当我找不到允许我使用列表比较器的解决方案时,我可能会这样做,但我发现手动循环有点慢比列表的内置比较器更重要,这就是我要使用它的原因。
更新
这是一种完成我正在尝试做的事情的方法,但我想知道是否有任何内置函数可以更快地完成此操作(并且利用了列表的这一特性)。
def lex_comp(a, b):
for func_a, func_b in izip(a, b):
v_a = func_a()
v_b = func_b()
if v_a < v_b: return -1
if v_b > v_a: return +1
return 0
def foo1(): return 1
def foo2(): return 1
def bar1(): return 1
def bar2(): return 2
def func1(): return ...
def func2(): return ...
list_a = [foo1, bar1, func1, ...]
list_b = [foo2, bar2, func2, ...]
# now you can use the comparator for instance to sort a list of these lists
sort([list_a, list_b], cmp=lex_comp)
下面是一种使用惰性求值的方法:
>>> def f(x):
... return 2**x
...
>>> def g(x):
... return x*2
...
>>> [f(x) for x in range(1,10)]
[2, 4, 8, 16, 32, 64, 128, 256, 512]
>>> [g(x) for x in range(1,10)]
[2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> zipped = zip((f(i) for i in range(1,10)),(g(i) for i in range(1,10)))
>>> x,y = next(itertools.dropwhile(lambda t: t[0]==t[1],zipped))
>>> x > y
True
>>> x < y
False
>>> x
8
>>> y
6
>>>
试试这个(函数的额外参数仅用于说明目的):
import itertools
def f(a, x):
print "lazy eval of {}".format(a)
return x
a = [lambda: f('a', 1), lambda: f('b', 3), lambda: f('c', 3)]
b = [lambda: f('d', 1), lambda: f('e', 2), lambda: f('f', 2)]
c = [lambda: f('g', 1), lambda: f('h', 2), lambda: f('i', 2)]
def lazyCmpList(a, b):
l = len(list(itertools.takewhile(lambda (x, y): x() == y(), itertools.izip(a, b))))
if l == len(a):
return 0
else:
return cmp(a[l](), b[l]())
print lazyCmpList(a, b)
print lazyCmpList(b, a)
print lazyCmpList(b, c)
生产:
lazy eval of a
lazy eval of d
lazy eval of b
lazy eval of e
-1
lazy eval of d
lazy eval of a
lazy eval of e
lazy eval of b
1
lazy eval of d
lazy eval of g
lazy eval of e
lazy eval of h
lazy eval of f
lazy eval of i
0
请注意,代码假定函数列表的长度相同。可以增强它以支持不相等的列表长度,您必须定义逻辑是什么,即 cmp([f1, f2, f3], [f1, f2, f3, f1])
应该产生什么?
我没有比较过速度,但考虑到您更新的代码,我想任何加速都将是微不足道的(循环在 C 代码中完成,而不是 Python)。该解决方案实际上可能更慢,因为它更复杂并且涉及更多内存分配。
鉴于您正尝试通过评估函数来对函数列表进行排序,因此函数将被评估,即 O(nlogn) 次,因此您最好的加速可能是考虑使用 memoization 来避免反复重估功能。
我做了一些测试,发现@juanpa 的回答和我更新的版本是最快的版本:
import random
import itertools
import functools
num_rows = 100
data = [[random.randint(0, 2) for i in xrange(10)] for j in xrange(num_rows)]
# turn data values into functions.
def return_func(value):
return value
list_funcs = [[functools.partial(return_func, v) for v in row] for row in data]
def lazy_cmp_FujiApple(a, b):
l = len(list(itertools.takewhile(lambda (x, y): x() == y(), itertools.izip(a, b))))
if l == len(a):
return 0
else:
return cmp(a[l](), b[l]())
sorted1 = sorted(list_funcs, lazy_cmp_FujiApple)
%timeit sorted(list_funcs, lazy_cmp_FujiApple)
# 100 loops, best of 3: 2.77 ms per loop
def lex_comp_mine(a, b):
for func_a, func_b in itertools.izip(a, b):
v_a = func_a()
v_b = func_b()
if v_a < v_b: return -1
if v_a > v_b: return +1
return 0
sorted2 = sorted(list_funcs, cmp=lex_comp_mine)
%timeit sorted(list_funcs, cmp=lex_comp_mine)
# 1000 loops, best of 3: 930 µs per loop
def lazy_comp_juanpa(a, b):
x, y = next(itertools.dropwhile(lambda t: t[0]==t[1], itertools.izip(a, b)))
return cmp(x, y)
sorted3 = sorted(list_funcs, cmp=lazy_comp_juanpa)
%timeit sorted(list_funcs, cmp=lex_comp_mine)
# 1000 loops, best of 3: 949 µs per loop
%timeit sorted(data)
# 10000 loops, best of 3: 45.4 µs per loop
# print sorted(data)
# print [[c() for c in row] for row in sorted1]
# print [[c() for c in row] for row in sorted2]
# print sorted3
我想创建中间列表会影响@FujiApple 版本的性能。当 运行 我的比较器版本在原始 data
列表上并将运行时与 Python 的本机列表排序进行比较时,我注意到我的版本慢了大约 10 倍(501 µs vs 45.4 µs环形)。我想没有简单的方法可以接近 Python 的本机实现的性能...