logo标签列表

转换为任意进制的C#函数的高效反转方法是什么？

c#algorithm
3
5个回答
4

Joel Mueller的回答应该能指导你处理base-64的情况。

针对你在你自己的回答中提供的初步代码，你可以通过改变代码实现你的for循环（实际上是一个O(N)的IndexOf）来提高效率，使用哈希查找（这应该使它成为O(1)）。

我基于以下假设进行此操作：baseChars是你在类构造函数中初始化的字段。如果正确，请进行以下调整：

private Dictionary<char, int> baseChars;

// I don't know what your class is called.
public MultipleBaseNumberFormatter(IEnumerable<char> baseCharacters)
{
    // check for baseCharacters != null and Count > 0

    baseChars = baseCharacters
        .Select((c, i) => new { Value = c, Index = i })
        .ToDictionary(x => x.Value, x => x.Index);
}

然后在你的StringToInt方法中：
char next = encodedString[currentChar];

// No enumerating -- we've gone from O(N) to O(1)!
if (!characterIndices.TryGetValue(next, out nextCharIndex))
{
    throw new ArgumentException("Input includes illegal characters.");
}
使用字典是一个很好的主意。 - ashes999
3

我这里有一个初步的可用版本，但我不确定它的效率如何。

public static int StringToInt(string encodedString, char[] baseChars)
    {
        int result = 0;
        int sourceBase = baseChars.Length;
        int nextCharIndex = 0;

        for (int currentChar = encodedString.Length - 1; currentChar >= 0; currentChar--)
        {
            char next = encodedString[currentChar];

            // For loop gets us: baseChar.IndexOf(char) => int
            for (nextCharIndex = 0; nextCharIndex < baseChars.Length; nextCharIndex++)
            {
                if (baseChars[nextCharIndex] == next)
                {
                    break;
                }
            }

            // For character N (from the end of the string), we multiply our value
            // by 64^N. eg. if we have "CE" in hex, F = 16 * 13.
            result += (int)Math.Pow(baseChars.Length, encodedString.Length - 1 - currentChar) * nextCharIndex;
        }

        return result;
    }
baseChars是用来干什么的？我能不能使用我想要转换的进制的输入来替换它？ - springathing
2

以下是使用 Linq 功能和 .NET Framework 4.0 的 Zip 扩展来执行计算的版本。

public static int StringToInt(string encodedString, char[] baseChars) {
    int sourceBase = baseChars.Length;

    var dict = baseChars
        .Select((c, i) => new { Value = c, Index = i })
        .ToDictionary(x => x.Value, x => x.Index);

    return encodedString.ToCharArray()
        // Get a list of positional weights in descending order, calcuate value of weighted position
        .Zip(Enumerable.Range(0,encodedString.Length).Reverse(), (f,s) => dict[f] * (int)Math.Pow(sourceBase,s)) 
        .Sum();
}

提醒一下，如果需要大量转换，事先在函数外计算字典会更有效率。

1
这里有一个完整的解决方案，可以将十进制数转换为K进制并进行反向转换：
public class Program
{
    public static void Main()
    {
        int i = 100;

        Console.WriteLine("Int:               " + i);

        // Default base definition. By moving chars around in this string, we can further prevent
        // users from guessing identifiers.
        var baseDefinition = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        //var baseDefinition = "WBUR17GHO8FLZIA059M4TESD2VCNQKXPJ63Y"; // scrambled to minimize guessability

        // Convert base10 to baseK
        var newId = ConvertToBaseK(i, baseDefinition);
        Console.WriteLine(string.Format("To base{0} (short): {1}", baseDefinition.Length, newId));

        // Convert baseK to base10
        var convertedInt2 = ConvertToBase10(newId, baseDefinition);
        Console.WriteLine(string.Format("Converted back:    {0}", convertedInt2));
    }

    public static string ConvertToBaseK(int val, string baseDef)
    {
        string result = string.Empty;
        int targetBase = baseDef.Length;

        do
        {
            result = baseDef[val % targetBase] + result;
            val = val / targetBase;
        } 
        while (val > 0);

        return result;
    }

    public static int ConvertToBase10(string str, string baseDef)
    {
        double result = 0;
        for (int idx = 0; idx < str.Length; idx++)
        {
            var idxOfChar = baseDef.IndexOf(str[idx]);
            result += idxOfChar * System.Math.Pow(baseDef.Length, (str.Length-1) - idx);
        }

        return (int)result;
    }
}
1
@ashes999 好的，链接已移除，答案已用代码替换。 - tbehunin
很棒的解决方案，你有没有想过这种转换是否高效？ - Krishnan Venkiteswaran
0
如果你真的需要 base-64 而不是“任何基数”，那么你所需要的一切都已经内置在框架中了：
int orig = 1337;
byte[] origBytes = BitConverter.GetBytes(orig);
string encoded = Convert.ToBase64String(origBytes);
byte[] decoded = Convert.FromBase64String(encoded);
int converted = BitConverter.ToInt32(decoded, 0);
System.Diagnostics.Debug.Assert(orig == converted);
这比C丑多了，不知道为什么人们如此狂热地赞扬这个C#。 - ldog
1
@ldog：哈哈，我无法想象任何曾经对C#大加赞扬的人会选择将字符串转换为任意进制的整数作为它真正闪耀的场景。总的来说，将C#与C进行比较似乎毫无意义。事实上，如果我抱怨在C中快速开发丰富的GUI应用程序有多么困难，并问为什么有人喜欢它，那也是一样的。 - Dan Tao
看起来好像没有起作用。原始函数将(1, 2, 3, 4)映射到(b, c, d, e); 而这个函数将它们映射到(AqAAAA, AgAAAA, AwAAAA, BAAAAA)。这不是最初的意图，即使用更少的字符表示数字。 - ashes999
你说你想要base-64编码。这是标准的base-64编码，适用于组成整数的4个字节（即1=[0x1, 0x0, 0x0, 0x0]）。不幸的是，Convert.ToBase64String只接受字节数组。 - Joel Mueller
原始的Stack Overflow帖子将其描述为转换为“任何基础int”。这就是我想要的。谢谢。 - ashes999
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接