3
\$\begingroup\$

Given the following code:

namespace AtBash
{
  class Program
 {
    static List<string> letters = new List<string> {
        "Aleph", "Beis", "Gimmel", "Daled", "Hei", "Vav", "Zayin", "Chies", "Teis",
        "Yud", "Chof", "Lamed", "Mem", "Nun", "Samech", "Ayin", "Pei", "Tzadik",
        "Kuf", "Reish", "Shin", "Taf"
    };
    static string AtBash(int index) => letters[Math.Abs((index + 1) - letters.Count)];

    static void Main(string[] args)
    {
        foreach (var item in letters)
        {
            Console.WriteLine(letters.IndexOf(item));
            Console.WriteLine($"{item} -> {AtBash(letters.IndexOf(item))}");
        }
    }
  }
}

Where the purpose is:

Given an index (say 0) return the corresponding item from the other end of the array (for our example 22).

This is the part of the code that actually does anything:

static string AtBash(int index) => letters[Math.Abs((index + 1) - letters.Count)];

The code works but I am interested in knowing if it can be made faster/more efficient. I would also like to know if there is an official term for this kind of algorithm.

\$\endgroup\$
  • 2
    \$\begingroup\$ Atbash cipher? \$\endgroup\$ – Raystafarian May 16 '16 at 16:24
  • 1
    \$\begingroup\$ Yes. This prep for a library I want to build to make dealing with the hebrew alphabet easier \$\endgroup\$ – Mord Zuber May 16 '16 at 16:29
  • 2
    \$\begingroup\$ Outside of the scope of this question, but if you're writing something bigger to deal with the hebrew alphabet, you should consider using an enum for the letters so the strings are not repeated all over the code. \$\endgroup\$ – Erik Ambrož May 16 '16 at 21:57
  • \$\begingroup\$ @ErikAmbrož I want to actually print the letter in the original alphabet so actually I have to use Unicode as they look like so א,ב,ג ect. which don't print so nicely on all systems. But your advice is good, and I would probably create a class with consts for each letter \$\endgroup\$ – Mord Zuber May 17 '16 at 5:34
11
\$\begingroup\$

If the entire goal is absolute performance of the AtBash() request, I would simply reverse the letters at startup. I'm speaking outside the context of this particular program and more towards your library where I am making the assumption that the AtBash() method calls vs. startup ratio is much higher to infinite.

If that's the case and we can eat some startup time, and you really want that per-access performance on AtBash(), simply eat a tiny bit of memory to get there:

static List<string> letters = new List<string> {
    "Aleph", "Beis", "Gimmel", "Daled", "Hei", "Vav", "Zayin", "Chies", "Teis",
    "Yud", "Chof", "Lamed", "Mem", "Nun", "Samech", "Ayin", "Pei", "Tzadik",
    "Kuf", "Reish", "Shin", "Taf"
};
static List<string> lettersReversed = letters.AsEnumerable().Reverse().ToList();
static string AtBash(int index) => lettersReversed[index];

Compare the IL in the initial accessor, letters[Math.Abs((index + 1) - letters.Count)]:

IL_0000:  ldsfld      UserQuery+Program.letters
IL_0005:  ldarg.0     
IL_0006:  ldc.i4.1    
IL_0007:  add         
IL_0008:  ldsfld      UserQuery+Program.letters
IL_000D:  callvirt    System.Collections.Generic.List<System.String>.get_Count
IL_0012:  sub         
IL_0013:  call        System.Math.Abs
IL_0018:  callvirt    System.Collections.Generic.List<System.String>.get_Item
IL_001D:  ret   

To the improved accessor, letters[letters.Count - (index + 1)]:

IL_0000:  ldsfld      UserQuery+Program.letters
IL_0005:  ldsfld      UserQuery+Program.letters
IL_000A:  callvirt    System.Collections.Generic.List<System.String>.get_Count
IL_000F:  ldarg.0     
IL_0010:  ldc.i4.1    
IL_0011:  add         
IL_0012:  sub         
IL_0013:  callvirt    System.Collections.Generic.List<System.String>.get_Item
IL_0018:  ret    

To the fastest accessor, lettersReversed[index]:

IL_0000:  ldsfld      UserQuery+Program.lettersReversed
IL_0005:  ldarg.0     
IL_0006:  callvirt    System.Collections.Generic.List<System.String>.get_Item
IL_000B:  ret  

Given your very minimal amount of actual memory in the example (which I don't think is likely to increase), I think this is a perfectly reasonable approach for any high-throughput library.

Feel free to benchmark this. The more accesses per startup, the better the payoff. You should already see payoff pretty quickly because sorting an array of a few dozen items is very fast and that's all the time we're adding to get the long-term benefits here. I wouldn't be surprised if your program even with trivial levels of access already performs better with this approach.

\$\endgroup\$
  • \$\begingroup\$ Why even write code to reverse the list? The values are limited and well-defined, so we could just manually reverse the list for zero additional overhead. \$\endgroup\$ – cbojar May 17 '16 at 2:32
  • 2
    \$\begingroup\$ @cbojar absolutely, though that assumes: a) the forward list is never used and b) increased maintenance cost is worth the tradeoff in saved startup cost. I wouldn't be sure of either. \$\endgroup\$ – Nick Craver May 17 '16 at 2:52
  • \$\begingroup\$ True, especially in such a case as this where the code overhead is very low. \$\endgroup\$ – cbojar May 17 '16 at 2:53
  • \$\begingroup\$ Nice! Besides for the answer for this case, I can apply this to a bunch of the other ciphers that exist for the hebrew alphabet. \$\endgroup\$ – Mord Zuber May 17 '16 at 5:29
  • \$\begingroup\$ As for @cbojar point, I would probably have some of the more interesting ciphers hard coded - for example the one where the first letter corresponds to the 12th, 2nd to the 13th and so on \$\endgroup\$ – Mord Zuber May 17 '16 at 5:39
10
\$\begingroup\$

In letters[Math.Abs((index + 1) - letters.Count)];, you use Math.Abs, but you don't need it if you rewrite that line this way:

letters[letters.Count - (index + 1)];

It seems there's no reason for index to be greater than letters.count.

\$\endgroup\$
1
\$\begingroup\$

Try the reverse

letters.Count - index

Abs(n) where n is negative = -n

Assuming index + 1 <= count,

Math.Abs((index + 1) - letters.Count) 

equals -(i+1-c)

-1 * (i + 1 + -c)

(-1*i) + (-1*1) + (-1*-c)

(-i) + -1 + c

c + -i + -1

c - i - 1

Not sure why you have the 1 in there

\$\endgroup\$
  • 1
    \$\begingroup\$ letters.Count is equal to the items in the array (22 in this case). The index is zero based, so for the first item the result would be (22 - 0) = 22 which is an invalid index \$\endgroup\$ – Mord Zuber May 16 '16 at 16:49
0
\$\begingroup\$

Just wanted to mention, that you can do it with LINQ only (without creating additional collections):

letters.Reverse().Skip(index).First();

But I think letters[letters.Count - (index + 1)], suggested by thesyndarn is by far the best solution.

\$\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.