变量的惰性评估

Question

我想按字典顺序比较两个列表，但列表中的值应在需要时计算。例如，对于这两个列表

a = list([1, 3, 3]) 
b = list([1, 2, 2]) 

(a < b) == False 
(b < a) == True 

我想在列表中的值是功能和在使索引a和b，该值（即各功能）= 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) 

Answer 1

我做了一些测试，发现@绢帕的回答和我的更新的版本是最快的版本：

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μsvs每个循环45.4μs）。我猜这是没有简单的方法来接近Python的本机实现的性能...

Answer 2

下面是用懒惰的评价的方法：

>>> 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 
>>> 

Answer 3

试试这个（额外的参数功能只是用于说明目的）：

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 

注意th在代码中假设函数列表的长度相同。它可以被增强以支持不相等的列表长度，您必须定义逻辑是什么，即cmp([f1, f2, f3], [f1, f2, f3, f1])应该产生什么？

我没有比较速度，但给出您的更新代码我会想象任何加速将是边缘（循环在C代码而不是Python中完成）。这个解决方案实际上可能会更慢，因为它更复杂并涉及更多的内存分配。

鉴于您试图通过评估函数对函数列表进行排序，函数将进行评估，即O（nlogn）次，所以您最好的加速可能是使用memoization来避免重复函数重估。