किसी भिन्न को कुशलता से सरल कैसे करें?

Question

मैं अपना स्वयं का फ़्लोटिंग पॉइंट नंबर वर्ग लिख रहा हूं, जो संख्याओं को दो संख्याओं के अंश के रूप में सहेजता है। मैंने भिन्न को सरल बनाने के लिए 3 अलग-अलग कार्य किए हैं, लेकिन वे सभी बहुत अधिक समय लेते हैं। भिन्न की ऊपरी और निचली संख्या का प्रतिनिधित्व करने के लिए वर्ग में दो विशेषताएँ होती हैं, ऊपर और नीचे।

preems = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]
class fractionnum:
    def __init__(self,up,down):
        self.up=up
        self.down=down

    def simplify11(self):
        thmax = max(self.up, self.down) // 2
        for x in preems:
            if x>thmax or 1 in (self.up,self.down):
                break
            while self.up%x==self.down%x==0:
                self.up//=x
                self.down//=x


    def simplify2(self):
        def isdivbyup(preem):
            return not self.up%preem
        def isdivbydown(preem):
            return not self.down%preem
        def divtime(preem):
            #down=self.down
            while  not self.up % preem and not self.down %preem:
                self.up //= preem
                self.down//=preem

        downfacts=list(filter(isdivbydown,preems))
        upfacts = list(filter(isdivbyup, preems))
        genfacts=[_ for _ in downfacts if _ in upfacts]
        [divtime(x) for x in genfacts]
    def simplify3(self):
        up=self.up
        down=self.down
        while down!=0: #euclidian algorithm
            prevup=up
            up=down
            down=prevup%down
        self.up//=up
        self.down//=up

वर्तमान में, इन तीन कार्यों को निष्पादित करने में लगभग समान औसत समय लगता है: 0.034133003 सेकंड। प्रत्येक गणना के बाद फ़ंक्शन को कॉल किया जाता है। 20 पुनरावृत्तियों के साथ एक साइन फ़ंक्शन में 1974 का निष्पादन समय लगता है।

मैं फ़ंक्शन को अधिक कुशलता से कैसे चला सकता हूं?

python class

-1

The_spider 5 सितंबर 2021, 22:44

Answer 1

जैसा कि टिप्पणियों में उल्लेख किया गया है, परिमेय संख्याएं पहले से ही विभिन्न पायथन पुस्तकालयों (fractions, sympy आदि) द्वारा लागू की गई हैं। हालांकि मुझे लगता है कि आप इसे एक अभ्यास के रूप में अपने दम पर करना चाहते हैं। ऐसी स्थिति में, आपकी विधियाँ simplify11() और simplify2() अच्छी नहीं हैं, क्योंकि वे अभाज्य संख्याओं की एक पूर्वगणना की गई सूची पर निर्भर हैं और भिन्नों के लिए गलत परिणाम देंगे जहाँ हर और अंश का एक अभाज्य गुणनखंड है जो इनमें से नहीं है। इन प्राइम्स। इसके शीर्ष पर, simplify2() केवल इसके दुष्प्रभावों के लिए एक सूची समझ [divtime(x) for x in genfacts] का उपयोग करता है, जो अक्षम और बहुत खराब अभ्यास दोनों है।

simplify3() बेहतर है, लेकिन यह यूक्लिडियन एल्गोरिथम को सही ढंग से लागू नहीं करता है। यह कुछ इस तरह होना चाहिए:

def simplify3(self):
    if self.up == 0:
        self.down = 1
    else:
        u, d = abs(self.up), abs(self.down)
        if u < d:
            d, u = u, d
        while d != 0:
            u, d = d, u % d
        self.up //= u
        self.down //= u

यह मानता है कि आपकी कक्षा सुनिश्चित करती है कि self.down 0 के बराबर नहीं है।

math मॉड्यूल से gcd() फ़ंक्शन का उपयोग करना निश्चित रूप से आसान है:

from math import gcd

def simplify3(up, down):
    common = gcd(self.up, self.down)
    self.up //= common
    self.down //= common

1

bb1 5 सितंबर 2021, 23:46

Answer 2

timeit.timeit() का उपयोग करके मैं देख रहा हूं कि simplify11() निम्न प्रकार का प्रदर्शन करता है:

import timeit

test1 = '''
preems = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229]
def simplify11(up, down):
    thmax = max(up, down) // 2
    for x in preems:
        if x>thmax or 1 in (up, down):
            break
        while up%x == down%x == 0:
            up //= x
            down //= x
    return up, down
'''
print(timeit.timeit("simplify11(8,24)", setup=test1, number=10_000_000))

मेरे लैपटॉप पर परिणाम (3 स्थानों तक गोल):

8.197

एक अंतर्निहित विधि है math.gcd() हालांकि हम इसका लाभ उठा सकते हैं:

import timeit

test2 = '''
import math
def simp(x,y):
    the_gcd = math.gcd(x,y)
    return x//the_gcd, y//the_gcd
'''

print(timeit.timeit("simp(8,24)", setup=test2, number=10_000_000))

इसका परिणाम यह होगा:

2.115

लगभग 1/4 समय।

ध्यान दें कि यदि मैं परीक्षण करता हूं कि क्या 'simplify11(i,j) == simp(i,j)' मुझे कुछ विसंगतियां मिलती हैं जो मैं आपको शुद्धता निर्धारित करने के लिए छोड़ दूंगा।

परीक्षण:

for i in range(1, 100):
    for j in range(1, 100):
        if simplify11(i,j) != simp(i,j):
            print(i, j, simplify11(i,j), simp(i,j))

यह मुझे दिखाता है:

2 2 (2, 2) (1, 1)
3 3 (3, 3) (1, 1)
5 5 (5, 5) (1, 1)
7 7 (7, 7) (1, 1)
11 11 (11, 11) (1, 1)
13 13 (13, 13) (1, 1)
....

मुझे लगता है कि नया simp() सही उत्तर दे रहा है।

0

JonSG 5 सितंबर 2021, 23:34

किसी भिन्न को कुशलता से सरल कैसे करें?

2 जवाब

संबंधित सवाल

नए सवाल

python