python 我如何使我的阿拉伯语到罗马的算法更好?

ulydmbyx  于 2023-05-27  发布在  Python
关注(0)|答案(3)|浏览(112)

我自己用Python做了一个阿拉伯语到罗马数字的转换器(还没有用Google搜索过一个例子)

def arabic_to_roman(num: int) -> str:
    roman_dict = {1000: 'M', 500: 'D', 100: 'C', 50: 'L', 10: 'X', 5: 'V', 1: 'I'}
    roman_num = ''
    exp_list = []
    chars = list(roman_dict.values())
    if num > 3999:
        return num

    else:
        for key in roman_dict.keys():
            exp = num // key
            num -= key * (num // key)
            exp_list.append(exp)

        pattern = [[chars[i], exp_list[i]] for i in range(len(chars))]
        print(pattern)

        # algorithm turning IIII into IV, VIIII into IX etc 

        for i in range(len(pattern)):
            for j in range(i - 2, i - 1):
                if pattern[j][1] > 3:
                    if pattern[j - 1][1] == 0:
                        pattern[j][1] = 1
                        pattern[j][0] = pattern[j][0] + pattern[j - 1][0]
                    else:
                        pattern[j][1] = 1
                        pattern[j - 1][1] = 0
                        pattern[j][0] = pattern[j][0] + pattern[j - 2][0]

        print(pattern)
    
        #concatenation the roman num from pattern
        for i in range(len(pattern)):
            roman_num += pattern[i][0][:2] * pattern[i][1]

        return roman_num

我不喜欢在连接中使用切片的部分,因为我的IIII -> IV算法在某些情况下会创建额外的字符,比如XCD而不是XC或XCM而不是XC。我怎样才能改变IIII -> IV部分,使其工作,而不使用切片?

import random, time
start_time = time.time()

def my_test():

    my_list = [random.randint(1, 3999) for _ in range(1000000)]
    my_romanlist = [arabic_to_roman(i) for i in my_list]
    print(my_list[1], my_romanlist[1])
   
my_test()

print(f"{time.time() - start_time} seconds")

这是我的测试,在我的电脑上大约需要16秒。好吃吗?如何优化arabic_to_roman函数以使其工作得更快?
先谢谢你了
好的,现在我做了一个roman_dict = {1000: 'M', 900: 'CM', 500: 'D', 400: 'CD', 100: 'C', 90: 'XC', 50: 'L', 40: 'XL', 10: 'X', 9: 'IX', 5: 'V', 4: 'IV', 1: 'I'}
而不是旧的一个和评论IIII->四部分,但测试仍然需要大约相同的时间。但前面的问题仍然是实际的:)

nfzehxib

nfzehxib1#

在我的机器上运行时间<1.1s的非递归(这并不一定是坏事)版本:

control = [
    (1000, 'M'),
    (900, 'CM'),
    (500, 'D'),
    (400, 'CD'),
    (100, 'C'),
    (90, 'XC'),
    (50, 'L'),
    (40, 'XL'),
    (10, 'X'),
    (9, 'IX'),
    (5, 'V'),
    (4, 'IV'),
    (1, 'I')
]

def int_to_roman(num):
    roman_num = []
    for x, c in control:
        if (r := num // x):
            roman_num.append(f'{c*r}')
            if (num := num - r * x) == 0:
                break
    return ''.join(roman_num)

import time
import random
rnums = [random.randint(1, 3_999) for _ in range(1_000_000)]
start = time.perf_counter()
R = [int_to_roman(rnum) for rnum in rnums]
end = time.perf_counter()
print(f'Duration={end-start:.4f}s')

输出:

Duration=1.0627s
js4nwp54

js4nwp542#

关于你问题的最后一部分:“如何优化arabic_to_roman函数以使其工作得更快?“这是我做的另一种方法,它似乎工作得相当快。

roman_dict = {1000:'M',900:'CM',500:'D',400:'CD',
                  100:'C',90:'XC',50:'L',40:'XL',
                  10:'X',9:'IX',5:'V',4:'CV',1:'I'}
vals = list(roman_dict)

def arabic_to_roman(num:int)->str:
    if num == 0:
        return ''
    for v in vals:
        if num >= v:
            return roman_dict[v] + arabic_to_roman(num-v)

运行您的测试,我发现这个方法比您提出的方法快3倍。

iugsix8n

iugsix8n3#

我的版本:

i= ("", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX")
x= ("", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC")
c= ("", "C", "CC", "CCC", "CL", "D", "DC", "DCC", "DCCC", "CM")

def ArabicToRoman(M):
    I, M= M % 10, M//10
    X, M= M % 10, M//10
    C, M= M % 10, M//10

    return ("M") * M + c[C] + x[X] + i[I]

避免使用字典。

相关问题