3

我刚刚开始使用 Python。

这是一个齿轮率计算器。

我有一个 367 到 7645373 范围内的 5000 个整数的列表和一个原始分数，它可以是 1/10 或 34561/43521 到 10/1。

我需要创建一个新分数，其值与原始分数接近，由表中存在的分子和分母组成。

事实上，我想要一个按与原始分数的偏差排序的匹配列表。

我有一个解决方案，但需要很长时间才能给出值为 1/10 的结果，因为 367/3670 或 368/3680 或 4352/43520 等解决方案是等效的。

Pythonist 会怎么做呢？

请不要告诉我这是 C 库的情况！:D

干杯
安东尼奥

def searcharatio(l, a):
    b = []
    mx = l[-1][0]
    ln = l[0][0]
    ld = l[0][0]
    i = max(int(ln/a.numerator-1), int(ld/a.denominator)-1)
    print i
    while 1:
        n = a.numerator * i
        d = a.denominator * i

        if n > mx or d > mx:
            return sorted(b)
        if n > 0.9*ln and d > 0.9*ld:
            # enumerate es lista 2 elem 0=num orden, 1=elemento
            ri = (min(enumerate(l), key=lambda x:abs(x[1][0]-n)))
            ro = (min(enumerate(l), key=lambda x:abs(x[1][0]-d)))
            ln = ri[1][0]
            ld = ro[1][0]

            e = [abs(1.0 - ((float(ln)/ld) / (float(n)/d))), i, ri, ro]
            b.append(e)
        i+=1
4

5 回答 5

2

Python 在迭代时往往很慢；使用 NumPy 的矢量化解决方案可能会更快。

def search_ratio(l, a):
    l = np.array(l)
    t = l.astype(float).reshape(-1, 1) / l.reshape(1, -1)
    i = np.unravel_index(np.argsort(np.where(t > a, t / a, a / t).flat), t.shape)
    return l[i[0]], l[i[1]]

例如，search_ratio(range(2, 6), 1.3)将给出：

(array([4, 5, 3, 5, 2, 3, 4, 5, 4, 4, 3, 5, 2, 3, 2, 2]),
 array([3, 4, 2, 3, 2, 3, 4, 5, 2, 5, 4, 2, 3, 5, 4, 5]))

是4/3最接近 1.3 的比率，5/4是下一个最接近的比率，等等。

请注意，t为了提高效率，可以缓存可用比率表。

于 2013-01-08T15:26:16.190 回答
1 
from __future__ import division
import itertools

def searchratio(input_range):
    my_ratios=set()
    for x in itertools.combinations(input_range, 2):
        y=x[0]/x[1]
        if y==1/10 or (10/1>y>34561/43521):
            my_ratios.add(x)
    return my_ratios

if __name__=='__main__':
    from time import time
    t1=time()
    nk=len(searchratio(xrange(4000)))
    t2=time()
    print t2-t1, nk

在蟒蛇中； pypy中的4000项目列表需要 6.5 秒；项目
列表需要 3.25 秒， 如果您想进一步减少它；您必须选择或将您的代码并行处理。简单的步骤就是在( ) 中运行您的代码；你可以立即看到时间减少。4000
cythonipythonpypy-chttps://pypy.org/50%

于 2013-01-08T15:43:03.327 回答
0

我结束了使用 bisect 和排序列表。

import bisect
import random
import time
def searchratio(t,n,d):
  #n must be <= d if it's not he case swap ,and swap the results returned
  b=[]
  a=float(n)/d
  t0=t[0]
  x1=bisect.bisect(t,t0/a)
  print a,x1,t0
  lm=len(t)-2
  for ti in t[x1:lm]:
      x1=bisect.bisect_left(t,ti*a)
      b.append([t[x1],ti])
      b.append([t[x1+1],ti])
  b.sort(key = lambda x:abs(x[0]/float(x[1])-a))
  return b   

#-----test program--------------------------------------------------   
l=[random.randrange(100000,10000000) for i in xrange(100000)]
l.sort()
n=3
d=100
t=time.clock()
r=searchratio(l,n,d)
t=time.clock() - t
print t, len(r), float(n)/d 
for x in r:
    print x, x[0]/float(x[1])
于 2013-01-23T14:22:04.507 回答
0

计算所有结果并在之后排序。

from collections import namedtuple
import random

fraction_target = 1 / 10.0
limit_left = fraction_target * 0.9
limit_right = fraction_target * 1.1

result = namedtuple('result', 'val1 val2 fraction')

values = [random.randint(367, 7645373) for _ in range(5000)]

fraction_results = []
for value_1 in values:
    for value_2 in values:
        fraction = value_1 / float(value_2)
        if limit_left < fraction < limit_right:
            fraction_results.append(result(value_1, value_2, fraction))

fraction_results.sort(key=lambda x: abs(x.fraction - fraction_target))

print(fraction_results[0:10])

我将存储的结果限制在所需分数的 90% 到 110% 之间。

于 2013-01-08T15:21:13.847 回答
0

由于此解决方案的局限性，我不确定这是否有帮助，但我仍然发布它，因为该理论至少非常适用于您的问题。

我假设您的列表只是一个数字列表。所以让我们先把它设为 a set，因为我们会反复检查成员资格，而使用 set 会更快：

integers = set(integers)

现在，fractions.Fractions该类有一个名为 的漂亮方法limit_denominator，它可能对您有所帮助。它基于欧几里得算法，可用于构造任何实数的连分数。然后可以使用数字的连分数来构造具有给定分母约束的该数字的最佳有理近似值。

因此，要将其应用于您的问题，我们从Fraction您希望表示的开始，并limit_denominator以略低于前一个近似值的分母的极限重复调用，直到我们找到一个分子和分母都在 中的分数integers。由于较大的分母意味着更好的近似值，因此第一个匹配是最好的。

import fractions

def best_approximation(numerator, denominator, integers):
    min_int = min(integers)
    max_int = max(integers)
    org_frac = fractions.Fraction(numerator, denominator)
    if org_frac > 1:
        # the numerator is larger than the denominator, so our maximum 
        # denominator must be adjusted down accordingly, since we also
        # want the numerator to be below max_int
        curr_max = int(max_int / org_frac)
    else:
        curr_max = max_int
    while True:
        fr = org_frac.limit_denominator(max_int)
        if fr.numerator < min_int or fr.denominator < min_int:
            return None
        if fr.numerator in integers and fr.denominator in integers:
            return fr
        max_int = fr.denominator - 1

我已经用一个整数列表测试了它，它只是 367 和 7645373 之间的质数，我得到了这个输出：

>>> print best_approximation(34561, 43521, integers)
4513/5683

这仍然没有尽可能快，因为limit_denominator方法构建的内部结构可以被重用。您可以通过复制源代码并修改它来解决这个问题，或者使用维基百科文章从头开始实现算法。

我提到的限制是：使用这种方法可能找不到最佳近似值。如果整数列表太稀疏，这可能是个问题。在我的主要列表的特定情况下，使用从 7645373 到 17645373 的随机分子和分母，它只适用于大约一半的情况，这显然不够好。另一方面，当您得到答案时，您会知道这是一个非常好的近似值。

于 2013-01-09T09:23:55.027 回答