3

私はPythonを始めたばかりです。

これはギアレート計算機用です。

367 から 7645373 の範囲の 5000 個の整数と元の分数のリストがあります。1/10 または 34561/43521 から 10/1 の可能性があります。

表に存在する分子と分母から、元の分数に近い値を持つ新しい分数を作成する必要があります。

実際、元の分数からの偏差でソートされた一致のリストが必要です。

私には解決策がありますが、367/3670 または 368/3680 または 4352/43520 のような解決策は同等であるため、値が 1/10 の結果を得るには時間がかかります。

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

1.3に4/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

Pythonで; 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

このソリューションの制限のため、これが役立つかどうかはわかりませんが、少なくとも理論はあなたの問題に非常に当てはまるので、それでも投稿します。

あなたのリストは単なる数字のリストだと思います。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 に答える
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 に答える