2
\$\begingroup\$

I just have the free account at leetcode. I've been practicing some coding there in preparation for interviews. But I can't see the solution logic behind the IntegerToRoman conversion function. I solved both the leetcode Roman Numbers problems (Arabic -> roman, and roman -> Arabic). I made a solution of my own but its slower than most accepted leetcode solutions.

I would appreciate any feedback code review-wise on the solutions but the main goal is to make them faster somehow. Especially the IntToRoman seemed trickier when I got to coding it. The RomanToInt was tricky as well, but when I realized the reversal it seemed OK. I started to code it with a stack originally instead of the oldval, but variable is enough and stack isn't needed as such.

The main code:

int fasterRomanToInt(std::string s)
{
    int romanSum{ 0 };
    if (s.size() == 1)
    {
        return oneSizeRomans(s[0]);
    }
    else
    {
        int oldval = 0;
        int i = s.length() - 1;
        while (i >= 0)
        {
            char current = s[i];
            int curval = oneSizeRomans(current);
            if (curval >= oldval)
            {
                romanSum += curval;
            }
            else
            {
                romanSum -= curval;
            }
            oldval = curval;
            --i;
        }
        return romanSum;
    }
}


std::string intToRoman(int num)
{
    std::map<int, std::string> ArabicvalueToRomans
    {
        {1000, "M"},
        {900, "CM"},
        {500, "D"},
        {400, "CD"},
        {100, "C"},
        {90, "XC"},
        {50, "L"},
        {40, "XL"},
        {10, "X"},
        {9, "IX"},
        {8, "VIII"},
        {7, "VII"},
        {6, "VI"},
        {5, "V"},
        {4, "IV"},
        {3, "III"},
        {2, "II"},
        {1, "I"}
    };

    std::vector<int> romanSpecials{ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 8,7,6,5,4,3,2,1 };

    int arabic = num;
    std::string result = "";
    while (arabic > 0)
    {
        int d = seekLargestPossible(romanSpecials, arabic);
        int r = arabic % d;
        std::string characters = processToRoman(d, ArabicvalueToRomans);
        arabic -= d;
        result += characters;
    }
    return result;
}

Here's a couple helper functions for intToRoman:

int seekLargestPossible(std::vector<int>& vecRef, int a)
{

    // input bigger than biggest divisor so use 1000
    if (a >= 1000)
    {
        return 1000;
    }



    // seek the biggest divisor that is smallerorequal than the A inputvalue
    
    for (auto iter = vecRef.begin(); iter != vecRef.end(); iter++)
    {
        auto key = *(iter);
        if (key <= a)
        {
            return key;
        }
    }
    throw "something went bad in seekLargestPossible";
}

    std::string processToRoman(int value, std::map<int, std::string>& mapRef)
{
    // if cannot access romanstr in map with key, throws which is good
    // shuldnt be happening tho
    std::string s = mapRef.at(value);
    return s;
}

And here's a helper function for RomanToInt:

int oneSizeRomans(char c)
{
    /*  I             1
        V             5
        X             10
        L             50
        C             100
        D             500
        M             1000*/
    switch (c)
    {
    case 'I': return 1;
    case 'V': return 5;
    case 'X': return 10;
    case 'L': return 50;
    case 'C':return 100;
    case 'D':return 500;
    case 'M':return 1000;

    default:
        throw "bad things one size romans func";
        break;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ std::map is slow unless your benchmark shows it to be faster than say std::vector. Only ever use it where it performs better, or when it makes code simpler but the performance hit doesn't matter much. For small maps that would fit into a couple of cache lines if they were a vector, the vector always wins: less page misses, less data cache misses, less code cache misses since the code is smaller, less branch mispredictions. \$\endgroup\$ Sep 13 at 13:58
3
\$\begingroup\$

A couple of minor things that haven't been pointed out explicitly elsewhere:

copying strings is slow

int fasterRomanToInt(std::string s) This copies a string.

It's possible that the string is short enough that this copy doesn't involve memory allocation. It's also possible that we're moving from the input string, so that it becomes just a copy of a pointer and size. But we can't count on either of those things.

So we should pass the std::string by reference, or instead pass a std::string_view (effectively just a pointer and a size) by value:

int fasterRomanToInt(std::string const& s)
int fasterRomanToInt(std::string_view sv)

Note that you can change the function signature in LeetCode's class Solution too!


use (reverse) iterators for iteration:

The overall algorithm for romanToInt looks decent, but it could be presented more neatly.

For example, we can iterate backwards through a std::string (or std::string_view) using reverse iterators:

constexpr int roman_to_int(std::string_view sv)
{
    auto total = 0;
    auto prev = 0;
    
    for (auto c = sv.rbegin(); c != sv.rend(); ++c)
    {
        auto value = get_roman_value(*c); // switch statement...
        total += (value >= prev) ? value : -value;
        prev = value;
    }
    
    return total;
}

avoid extra work:

while (arabic > 0)
{
    int d = seekLargestPossible(romanSpecials, arabic);
    int r = arabic % d;
    std::string characters = processToRoman(d, ArabicvalueToRomans);
    arabic -= d;
    result += characters;
}

seekLargestPossible searches the entire map every loop. Note that once we've dealt with the largest value, the next one must be equal or smaller, so we can search a smaller subset.

r appears to be unused! (I'm guessing you were going to create a repeating string where necessary - note however, that only 1 values are repeated, and only up to 3 times, so perhaps there's not much point in doing an extra division, compared to simply continuing with the loop).

write the simplest possible code first:

Given the very restricted set of inputs, and the fact that the next number we deal with is always smaller, we could write everything out long-hand:

std::string int_to_roman(int num)
{
    assert(num > 0);
    assert(num <= 3999);
    
    auto out = std::string();
    
    for (; num >= 1000; num -= 1000) { out += 'M'; }
    
    if (num >= 900) { num -= 900; out += "CM"; }
    if (num >= 500) { num -= 500; out += 'D'; }
    if (num >= 400) { num -= 400; out += "CD"; }
    for (; num >= 100; num -= 100) { out += 'C'; }
    
    if (num >= 90) { num -= 90; out += "XC"; }
    if (num >= 50) { num -= 50; out += 'L'; }
    if (num >= 40) { num -= 40; out += "XL"; }
    for (; num >= 10; num -= 10) { out += 'X'; }
    
    if (num >= 9) { num -= 9; out += "IX"; }
    if (num >= 5) { num -= 5; out += 'V'; }
    if (num >= 4) { num -= 4; out += "IV"; }
    for (; num >= 1; num -= 1) { out += 'I'; }
    
    return out;
}

And... this is probably fast enough ("0ms" according to leetcode)! We could of course factor out the obvious grouping pattern of N * (9, 5, 4, 1), but there's not really any need (and we actually have to be careful to avoid making it slower).

Another (perhaps even simpler) approach is to notice that we're still dealing with a decimal system, and we don't have to care at all about the logic of how the characters are calculated! We can get them directly from a size-10 lookup table:

using chars_t = std::array<std::string_view, 10>;
auto static constexpr thousands = chars_t{ "M", "MM", "MMM", "_", "_", "_", "_", "_", "_" };
auto static constexpr hundreds = chars_t{ "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
auto static constexpr tens = chars_t{ "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
auto static constexpr ones = chars_t{ "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

std::string int_to_roman(int num)
{
    assert(num >= 1);
    assert(num <= 3999);
    
    auto out = std::string();
    
    if (num >= 1000) { auto const index = num / 1000; num -= index * 1000; out += thousands[index-1]; }
    if (num >= 100)  { auto const index = num / 100;  num -= index * 100;  out += hundreds[index-1]; }
    if (num >= 10)   { auto const index = num / 10;   num -= index * 10;   out += tens[index-1]; }
    if (num >= 1)    { auto const index = num / 1;    num -= index * 1;    out += ones[index-1]; }
    
    return out;
}

Again, this is super fast (I suspect faster).

\$\endgroup\$
2
\$\begingroup\$
if (s.size() == 1)
{
    return oneSizeRomans(s[0]);
}

There is nothing special with a size of 1. Yes, you can return early of course, but all the other values will have to go through this spurious if statement as well.

If well programmed you could even get away with a length of zero (hint)!


int i = s.length() - 1;
while (i >= 0)

What's wrong with a for loop? I'm not sure if this makes any difference when a smart compiler handles things, but I am pretty sure that the for won't be slower.


int curval = oneSizeRomans(current);

Note that calling methods always has a performance penalty. You could use a macro or inline call instead. Or you could actually inline the code.


return romanSum;

Well, for a performance race this is fine, but this will definitely allow invalid roman numerals. If I would see this code in a library I would certainly reprimand the person who wrote the function. Even in a race, I would definitely like invalid Roman values such as "IC" to be rejected; otherwise testing for those would take any performance advantage.

One ugly trick is to re-encode the resulting integer and then compare. In that case you will always have a valid input string. Yes, this does imply a performance penalty, but one that is necessary.


std::string intToRoman(int num)

You are recreating a Map and a Vector within a function. I definitely hope your compiler saves you from this, but I honestly don't think so. Do you notice that these will never change between function calls?

Personally I would be vary wary of using any kind of collections. I can easily program this by using a single character array, no higher level collections whatsoever. Even just calculating the hash value for the map is going to kill performance. It may well take more time than the whole conversion in the first place!

Note that performing calculations on current CPU's is blistering fast. De-referencing data structures generally is not that fast.


std::string s = mapRef.at(value);

Definitely can do without a method surrounding it.


 int oneSizeRomans(char c)

Alright, but that comment is really not necessary. You need comments in case it is not clear what the code is doing or how it is doing that. Neither do apply here.

Hints

All in all, try to code this using just one array containing the roman literals. You will be surprised how fast you can search through a tiny array of just 7 elements using a simple for loop.


In Java, which is particularly C-like, I could do:

int toValue(char numeral) {
    int value = 1;
    for (int i = 0; i < NUMERALS.length; i++) {
        if (NUMERALS[i] == numeral) {
            return value;
        }
        value = value * (i % 2 == 0 ? 5 : 2);
    }
    return 0;
}

You can of course optimize away the ?, this is a useful exercise in itself. Processors are even less fond of branching than of de-referencing.


You may use the values 0 to 9 in a switch / case statement for fast encoding to Roman literals.


Pre-calculate anything you can before going into the functions


Please make sure your code rejects incorrect values: correctness should always trump performance!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Yes I forgot to tell but it actually said in the leetcode problem originally that input validation as such wasnt required for roman number converting (it was assumed to be correctly formed inputs). For RomanStr-> int input was said to be (s is a valid roman numeral in the range [1, 3999].). but Definitely the correctness in terms of validation could be improved. For the case of IntToRoman, the input was said to be 1 <= num <= 3999 \$\endgroup\$
    – Late347
    Sep 12 at 18:43
  • \$\begingroup\$ Alright. Please check if you have any questions about my answer, I won't have much time tomorrow. Main issue is of course intToRoman, I expect that this has the most problems w.r.t. speed. \$\endgroup\$ Sep 12 at 18:45
  • \$\begingroup\$ Writing library quality code would of course be very commendable in leetcode I have to admit. Sometimes well voted solutions on codewars look like that could be it. But rarely is there much input validation in these kind of small problems \$\endgroup\$
    – Late347
    Sep 12 at 18:47
  • \$\begingroup\$ Well, I can remember that I got exactly this assignment in my first year at uni, a long time ago. I'm pretty sure that they only looked at these kind of things, not performance. Took some time to get used to everything back then. Now I can program this just in half an hour. I surprised the teaching assistant with my check that simply computed the roman numerals again, but it was accepted. \$\endgroup\$ Sep 12 at 18:51
  • \$\begingroup\$ yea that romanSpecials I made it to constexpr int array inside seekLargestPossible. And removed the map thing and vector thing. processToRoman could be converted easily to switch case which probably would make it faster. Process to roman could be refactored a bit so it doesnt return a new string by value... I gota admit its been a while since I did the whole char arrays thing back in C. It would take careful attention to make everything use char arrays again rather than c++ string (I suspect that c++ string usage it the main problem now) \$\endgroup\$
    – Late347
    Sep 12 at 19:27
1
\$\begingroup\$

Adding to Maarten Bodewes' answer:

Prefer range-for where possible

In seekLargestPossible(), you can replace the for-loop with this one:

for (auto& key: vecRef)
{
    if (key <= a)
        return key;
}

Naming things

Avoid naming things after their type, instead always try to give them a name that describes what they represent. For example, vecRef and mapRef are bad names; that just repeats their type, but doesn't tell you anything about what's in the vector or map their are referencing. For vecRef for example, you could use romanSpecials as the name as that's what you are seeking in, or if you want to keep it more generic, then I suggest values, as vecRef just references a collection of values.

Make use of STL algorithms

The standard library comes with lots of algorithms that you can use instead of writing your own. For example, seekLargestPossible() could be replaced with a call to std::lower_bound():

int d = arabic >= 1000 ? 1000 : *std::lower_bound(romanSpecials.begin(), romanSpecials.end(), arabic, std::greater<int>());

Although it is perhaps overkill here.

Avoid writing unnecessary code

The function processToRoman is not very useful. You can write the following directly inside intToRoman():

std::string characters = ArabicValueToRomans.at(d);

Be consistent

Why do you have a std::map to go from values to roman numerals, but have a function with a switch-statement to go from roman numerals to values? You can use the same technique for both directions.

Don't throw raw strings

Instead of just throwing a string when something goes wrong, I strongly recommend that you throw one of the standard exception types instead, or possibly create your own exception class that derives from one of the standard types. It's quite simple to use them:

#include <stdexcept>
...
int seekLargestPossible(...)
{
    ...
    throw std::logic_error("Could not find largest possible roman numeral");
}

The type adds more information about the kind of error, and this allows the caller to distinguish between different errors by using different catch statements.

\$\endgroup\$
2
  • \$\begingroup\$ yea I think sometimes you get unlucky on the execution speed at leetcode(???). Like I managed to find the C++ solution for one guy from the discussions page and it didnt really run as fast as he claimed, consistently. It would be intersting to see solution without any cpp strings except the return value when it gets returned as std::string the romanStr. They way I coded the solution was that first I scribbled a bit on paper and then started coding it. I didnt prove how to solve it like mathematical proof or anything like that. \$\endgroup\$
    – Late347
    Sep 12 at 21:09
  • 1
    \$\begingroup\$ I suspect that char array use and consexpr arrays (esp the romanSpecials style) if necessary would be useful. \$\endgroup\$
    – Late347
    Sep 12 at 21:11
-1
\$\begingroup\$

Performance

Performance code is not always good code.

Improving performance can also make the code more complex and thus harder to maintain. One must balance ones experience against the need for performance.

Roman To Int

In this example we can combine the data (Roman numerals) with the code creating a function that reads the characters one by one and contains all the roman characters as part of the code. This lets use conditional search roman numerals depending on the one we have just encountered.

We also know that only M C and X will be repeated so we check for repeats only after finding one of them.

Tracking the string read position can also be ignored when the remaining value is <= 9 (<= IX). That means we do lose track of just how many digits are read, but I don't see that is a requirement in this case.

Example 2

The result is not pretty

Be careful with the pointer to i

unsigned romanValueAt(unsigned *i, std::string s) {
    unsigned val;
    switch (s[(*i)++]) {
        case 'D': return 500;
        case 'L': return 50;
        case 'I':
            switch (s[(*i)++]) {
                case 'X': return 9;
                case 'V': return 4;
                case 'I': 
                    if (s[(*i)++] == 'I') { return 3; }
                    else { return 2; }
                default: { return 1; }              
            }
        case 'V': {
            if (s[(*i)++] == 'I') {
                if (s[(*i)++] == 'I') {
                    if (s[(*i)++] != 'I') { return 7; } /* Warning i could be past
                    return 8;                              end of string */
                } 
                return 6;
            } 
            return 5;
        }
        case 'M': {
            val = 1000;
            while (s[(*i)++] == 'M') { val += 1000; }
            (*i)--;
            return val;
        }
        case 'C':
            switch (s[*i]) {
                case 'M': { (*i)++; return 900; }
                case 'D': { (*i)++; return 400; }
                default: {
                    val = 100;
                    while (s[(*i)++] == 'C') { val += 100; }
                    (*i)--;
                    return val;
                }
            }
        case 'X':
            switch (s[*i]) {
                case 'C': { (*i)++; return 90; }
                case 'L': { (*i)++; return 40; }
                default: {
                    val = 10;
                    while (s[(*i)++] == 'X') { val += 10; }
                    (*i)--;
                    return val;
                }               
            }
    }
    return 0;
}
unsigned romanToUint(std::string roman) {
    unsigned value = 0, i = 0, len = roman.length();
    while (i < len) { value += romanValueAt(&i, roman); }
    return value;
}

Int to Roman

Converting from number to roman also has some room for optimizations.

log10 to count digits

We can use the 'log10' of a number to quickly know how many digits it contains, That means we don't need to wast time checking the value against higher values than needed.

Divide for sequences

For the sequences eg XXX or MMXXX we can also do them in one step if we divide by the roman value we get the number of repeats. EG 3992 / 1000 = 3 (as int) which is the number of M it contains MMMCMXCII

Use hash map for large data sets

Avoid using map as each time you lookup an item it needs to run a hash function and for small maps the overhead outweighs any time complexity gain.

Example 2

In this case you only need to iterate at max 9 values, everything else is just direct array indexing. Values under 10 are looked up directly.

#include <math.h> 
std::string UintToRoman(unsigned value) {
    const std::string digits[9] = {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    const std::string copies[9][2] = {{"MM", "MMM"},{},{},{},{"CC","CCC"},{},{},{},{"XX","XXX"}};
    const std::string romB[9] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X"};
    const unsigned rom[9] = {1000, 900, 500, 400, 100, 90, 50, 40, 10};
    const unsigned starts[4] = {9, 5, 1, 0}; 
   
    std::string res = "";
    unsigned i = starts[(unsigned) log10((double) value)];
    while (i < 9 && value >= 10) {
        const unsigned v = rom[i];
        if (value >= v) {
            const int c = value / v;
            value -= c * v;
            res += c == 1 ? romB[i] : copies[i][c - 2];
        }
        i++;
    }
    return  value > 0 ? res + digits[value - 1] : res;
}

Improvements

Do the above example provide an performance benefit. I am unsure as I am not a member of leetcode so have no environment to compare against.

There are also many more ways to improve the examples.

Constraints

Roman numerals have a very limited range 1 to 3999. The examples give in the answer are only valid to this range.

It is assumed inputs are correctly formatted and within range.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.