28
\$\begingroup\$

So this question is prompted by two things.

  1. I found some code in our source control doing this sort of things.
  2. These SO questions:

So when I thought about this problem this popped into my head almost immediately.

class Util
{
    private static string[] alphabetArray = { string.Empty, "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" };
    public static IEnumerable<string> alphaList = alphabetArray.Cast<string>();

    public static string IntToAA(int value)
    {
        while (Util.alphaList.Count() -1 < value)
        {
            Util.IncreaseList();
        }

        return Util.alphaList.ElementAt(value);
    }

    private static void IncreaseList()
    {
        Util.alphaList = Util.alphabetArray.Take(1).Union(
            Util.alphaList.SelectMany(currentLetter =>
               Util.alphabetArray.Skip(1).Select(innerLetter => currentLetter + innerLetter)
            )
        );
    }
}

My question is this: Is this approach a better solution (performance wise)? or is a recursive / computed value better (eg. this answer )?

\$\endgroup\$
  • 3
    \$\begingroup\$ Using LINQ to perform trivial transformations repeatedly will always hurt you performance-wise. If you specifically want performance, stay away from LINQ. \$\endgroup\$ – Jeff Mercado Jun 27 '12 at 3:20
  • \$\begingroup\$ @JeffMercado jeff I don't see the values going much past 50 something so it would only be hit once/twice. What specifically then should I change? \$\endgroup\$ – James Khoury Jun 27 '12 at 3:29
16
\$\begingroup\$

Calling any function in general will give you a small (miniscule) performance hit. Recursive functions (AFAIK) cannot be inlined so that can't be optimized away. LINQ revolves around calling other functions so that's the worst choice to make if you want to write good performing code. I've said it before, LINQ is not for writing fast code, it's for writing concise code. This is a simple algorithm that doesn't need to be bogged down by that.

* It doesn't help if you don't use LINQ correctly, you have a number of no-no's in your code.

If you want the fastest approach (without resorting to mapping out all possible values in memory), you'd stay away from these and do a more direct conversion. To be the absolutely fastest, you have to get down low-level and use unsafe (unmanaged) code. I won't go there. On the other hand, if you want fastest managed code, you'd want to do this iteratively. In any case, my proposal is not a claim to be the fastest implementation, it could very well not be but I don't know, you would have to profile it to find out.

We're doing a base conversion from base-10 numbers to base-26 "numbers". I don't know if there's a faster algorithm to do this but here's a straight conversion using a StringBuilder as a buffer.

const int ColumnBase = 26;
const int DigitMax = 7; // ceil(log26(Int32.Max))
const string Digits = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static string IndexToColumn(int index)
{
    if (index <= 0)
        throw new IndexOutOfRangeException("index must be a positive number");

    if (index <= ColumnBase)
        return Digits[index - 1].ToString();

    var sb = new StringBuilder().Append(' ', DigitMax);
    var current = index;
    var offset = DigitMax;
    while (current > 0)
    {
        sb[--offset] = Digits[--current % ColumnBase];
        current /= ColumnBase;
    }
    return sb.ToString(offset, DigitMax - offset);
}

On the other hand, since your inputs are constrained to up to 50'ish, you could just use an array (and not an IEnumerable<>) for the lookups.

static readonly string[] Columns = new[]{"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","AA","AB","AC","AD","AE","AF","AG","AH","AI","AJ","AK","AL","AM","AN","AO","AP","AQ","AR","AS","AT","AU","AV","AW","AX","AY","AZ","BA","BB","BC","BD","BE","BF","BG","BH"};
public static string IndexToColumn(int index)
{
    if (index <= 0)
        throw new IndexOutOfRangeException("index must be a positive number");

    return Columns[index - 1];
}
\$\endgroup\$
  • \$\begingroup\$ I'm confused. So if mapping the numbers out into an in memory field is quicker ... why would this be quicker than the approach I suggested? \$\endgroup\$ – James Khoury Jun 27 '12 at 5:45
  • \$\begingroup\$ Well you're doing a form of memoization (very strangely I might add). After calling certain inputs, your code essentially becomes a (linear) lookup. However you are paying a lot just to get that memoization to work. To be able to get the corresponding column for the index 50, you needed to calculate all the values from 1 through 49 (which attributes to an even bigger hit on your first call). Now that might be fine if you're accessing this using indices in incremental order (ignoring the costs of using LINQ), for a utility method to have such a limited use, I'd question its existence. \$\endgroup\$ – Jeff Mercado Jun 27 '12 at 5:59
  • \$\begingroup\$ So keeping it as a List rather than an IEnumerable is better as it is a linear look up? (assuming the values are precalculated?) \$\endgroup\$ – James Khoury Jun 27 '12 at 7:28
  • \$\begingroup\$ @JamesKhoury Almost everything is better than a linear lookup. \$\endgroup\$ – svick Jun 27 '12 at 9:39
  • \$\begingroup\$ @JeffMercado I believe LINQ can be used to write good performing code and I certainly wouldn't call it “worst choice”. Yes, it does have some overhead, but that's going to be negligible most of the time. \$\endgroup\$ – svick Jun 27 '12 at 9:42
28
\$\begingroup\$

Math! Simple math is certainly the nicest way, no lists to deal with, just old fashion ASCII and math. If you want to be able to toggle the capitalization of this method, simply use a ternary operator like this isCapital ? 'A' : 'a' I just left it capital as that is how the OP seemed to want it. Jeff Mercado's Answer explained well enough the differences between calculated, recursive and such... I mostly wanted to provide a simplistic calculated answer that did not involve using lists.

public static string IntToLetters(int value)
{
    string result = string.Empty;
    while (--value >= 0)
    {
        result = (char)('A' + value % 26 ) + result;
        value /= 26;
    }
    return result;
}

Edit: To meet the requirement of A being 1 instead of 0, I've added -- to the while loop condition, and removed the value-- from the end of the loop, if anyone wants this to be 0 for their own purposes, you can reverse the changes, or simply add value++; at the beginning of the entire method.

\$\endgroup\$
  • 1
    \$\begingroup\$ Your version puts 'A' at 0 not 1. How would you propose to acheive this in a simplistic way? \$\endgroup\$ – James Khoury Mar 12 '14 at 1:26
  • 1
    \$\begingroup\$ @JamesKhoury Oh sorry about that, didn't realize... just value-; at the beginning of the entire method, I actually went to extra lengths to make it base 0. \$\endgroup\$ – BenVlodgi Mar 12 '14 at 1:32
  • \$\begingroup\$ Thats great. Does this implementation provide a performance increase over other implementations? \$\endgroup\$ – James Khoury Mar 12 '14 at 22:39
  • \$\begingroup\$ To base 26 string, this simply better \$\endgroup\$ – Tuyen Pham May 6 '15 at 4:15
  • 1
    \$\begingroup\$ You might want to consider using a StringBuilder and initialize it with a capacity of value / 26 + 1. \$\endgroup\$ – HerpDerpington Sep 14 '15 at 18:07

protected by Jamal Mar 11 '14 at 19:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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