有没有更好的方法同时解析两个列表?

问题描述 投票:0回答:2

我想在两个巨大的列表中猜测两个数字的完美组合。

for x in list_a:
    for y in list_b:
        if round((x * 0.24 + y * 0.13), 2) == value:
            print('success')

这需要花费很多时间,因为我的列表的len超过600.我的第一个想法是将巨大的列表拆分成较小的列表并检查结果。例如,如果x和y <= value - 4的等式移动到下一个列表的集合,直到x和y == value。

1)如何将列表拆分为较小的集群? 2)如何有效地改变集合? 3)有没有办法避免嵌套for循环?

python-3.x numpy
2个回答
2
投票

更新(问题澄清):

无需猜测,因为你可以完全解决(直到数字):

M = np.array([[1, 1], [0.24, 0.13]])
high_taxed, low_taxed = np.linalg.solve(M, [Start_Value, Tax])

更新结束。

您可以使用以下技巧获得O(n + m log n + m)运行时。

  1. 使用因子0.24和0.13对列表a和b进行缩放
  2. 用v-b替换b
  3. 当a_i接近(v-b)_j时,观察到a_i + b_j正好接近v
  4. 考虑到这一点,将a和v-b组合起来,排序,并在不是来自同一子集的所有相邻元素之间进行差异
  5. 找到差异中的最小元素。这相当于最佳匹配

.

import numpy as np

def closest_match(a, b, v, fa=24, fb=13, fv=100):
    ab = np.concatenate([fa*a, fv*v - fb*b])
    idx = ab.argsort(kind='stable')
    ina = idx<len(a)
    swtch, = np.where(ina[1:]^ina[:-1])
    mm = np.diff(ab[idx])[swtch]
    abidx = swtch[np.argmin(np.abs(mm))]
    aidx, bidx = sorted(idx[abidx:abidx+2])
    bidx -= len(a)
    return aidx, bidx

例:

a = np.arange(-10, 10000, 7)
b = np.arange(20, 4000, 3)
v = 99
closest_match(a, b, v)
#(1, 249)
a[1]*24 + b[249]*13
#9899
v*100
#9900

# best match is one off
# validate using brute force

np.abs(np.add.outer(a*24, b*13)-v*100).min()
#1

# yep, one is as good as it gets

时间与蛮力相比:

timeit(lambda: np.unravel_index(np.abs(np.add.outer(a*24, b*13)-v*100).argmin(), (len(a), len(b))), number=1000)
#17.82432043197332
timeit(lambda: closest_match(a, b, v), number=1000)
#0.11731306000729091

加速超过100倍。


2
投票

我不太确定你试图找到哪种最佳条件,但如果你想重现上面的计算而没有两个for循环,我可能会帮忙。尝试计算一个numpy数组中的所有值:

arr = np.around(np.outer(0.24 * np.array(list_A), 0.13 * np.array(list_B)),2)

它将返回一个矩阵,它存储你在for循环中计算的所有值,你可以得到一个布尔矩阵,表明哪一对A和B满足你的条件

boolian_arr = arr == value

(这个解决方案不包括任何花哨的搜索算法,但只是使用numpy的两个慢速for循环的替代方案。)

© www.soinside.com 2019 - 2024. All rights reserved.