How can i make my Arabic to roman algorithm better?-CodePudding

I've made an arabic to roman numerals converter in python all the way by myself (havent googled a single example)

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

i dont like the parth where i use slicing in concatenation because my IIII -> IV algorithm creates extra characters in certain cases like XCD instead of XC or XCM instead of XC. How can i change the IIII -> IV part to make it work without using the slicing?

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

And here is my test, it takes about 16 seconds on my PC. is it good? how can i optimize the arabic_to_roman function to make it work faster?

Thanks in advance

okay now i've made a 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'}

instead of older one and commented IIII-> IV part, but the test still takes approx the same amount of time. But the previous questions are still actual:)

CodePudding user response：

Non-recursive (not that that's necessarily a bad thing) version that runs in <2.5s on my machine:

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):
    assert num > 0 and num < 4_000
    roman_num = []
    for x, c in control:
        if (r := num // x):
            roman_num.append(str(c * r))
            if (num := num - r * x) == 0:
                break
    return ''.join(roman_num)

import time
import random
start = time.perf_counter()
R = list(map(int_to_roman, (random.randint(1, 3999) for _ in range(1_000_000))))
end = time.perf_counter()
print(f'Duration={end-start:.4f}s')

CodePudding user response：

Regarding the last part of your question: "how can I optimize the arabic_to_roman function to make it work faster?" Here's an alternative method that I made, which seems to work fairly quickly.

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)

Running your test, I found that this method is about 3X faster than the method you've presented.

CodePudding user response：

My version:

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]

The use of dictionaries is avoided.