将空格分隔的数字转换为整数数组的最有效方法是什么?

本文关键字：有效 方法 数组 是什么 分隔 空格 数字 转换 整数 | 更新日期: 2023-09-27 18:12:07

我的问题很简单:我在尝试做像

这样的转换时有一个真正的(不是想象的)性能错误
"1273 912 84" --> {1273, 912, 84}

所以我想知道如何尽快完成它

总是有3个数字，前2个总是在[1,3000]的范围内，最后一个总是在[1,100000]的范围内。

背景:我正在研究一个HackerRank问题，我的解决方案是在一个测试用例上超时。我读了关于这个问题的讨论，其中一个家伙说，每个人最后一个测试用例失败的原因都是因为他们如何解析巨大的输入。

我试图解决这个性能问题的方法是创建一个像 这样的类
class IntParser
{
    private Dictionary<string, int> _Map = new Dictionary<string, int>();
    public IntParser(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            _Map[i.ToString()] = i;
        }
    }
    public int[] ParseVals(string line)
    {
        return Array.ConvertAll(line.Split(' '), ParseVal);
    }
    public int ParseVal(string s)
    {
        int retval;
        try
        {
            retval = _Map[s]; 
        }
        catch(KeyNotFoundException)
        {
            retval = Int32.Parse(s);
            _Map[s] = retval;
        }
        return retval;
    }
}
用 初始化
var parser = new IntParser(100000);

然后像

一样使用
int[] triplet = parser.ParseVals(Console.ReadLine());

令人惊讶的是，这仍然不够有效。

将空格分隔的数字转换为整数数组的最有效方法是什么?

您可以在O (N)时间和O (N)空间中完成此操作。您只需要创建一个遍历字符的函数，并实现一个小状态机。你只能处于三种状态:

1)我正在阅读空格2)我在读一个数字3)到达列表的末尾

可能的转换有:1)直接读一个数字1)从读空间到读数字2)从读取数字到读取空格或到达列表末尾

你只需要调整你的代码并记住当你进入状态1)时。每当你从状态1)退出时，你必须将你所读到的数字添加到列表中。

不进行分析很难判断，但有几件事要记住:

  1. String.Split产生垃圾
  2. 异常在。net中是昂贵的，所以最好使用TryGetValue作为缓存。
  3. 通过简单地迭代数字，你可以解析一个比Int32.Parse更快的整数。
  4. 与解析的成本相比，插入大量项后字典查找可能会增加。

然而，"3,000,000+行"对我来说似乎不是一个大问题，所以我不确定解析是否是真正的罪魁祸首。

为什么不是profile?Visual Studio 2015 Community自带CPU分析器。

(更新)

我试着改进@Jamiec的答案一点，通过完全删除String.Substring并在同一方法内做所有解析，并提出:

static public int[] ParserInPlace(string s)
{
    var result = new int[3];
    var x = 0;
    for (var i = 0; i < s.Length; i++)
    {
        if (s[i] == ' ')
        {
            x++;
            continue;
        }
        result[x] = result[x] * 10 + (s[i] - '0');
    }
    return result;
}

在我的机器上，这似乎比@Jamiec的随机数解决方案快2倍，比OP的原始代码快10倍(发布模式，x86, Works On my machine™):

<>之前随机输入ParserBasic : 2068.4759毫秒OP的解析器:1520.8422毫秒ParserNoSplit : 1300.3933毫秒女士ParserNoSplitNoIntParse: 322.271ParserInPlace : 125.0064毫秒最小输入(1 1 1)ParserBasic : 1715.9653毫秒OP的解析器:702.8926毫秒ParserNoSplit : 1006.344毫秒女士ParserNoSplitNoIntParse: 203.4511ParserInPlace : 59.2876毫秒最大输入(3000 3000 100000)ParserBasic : 1971.8206毫秒OP的解析器:827.6612毫秒ParserNoSplit : 1256.9101毫秒女士ParserNoSplitNoIntParse: 274.5071ParserInPlace : 111.802毫秒之前

如果您需要一次解析一行，那么也许您不需要在每次迭代中分配相同的int[] result数组(但您确实需要将其设置为零)，因此您可以通过这种方式进一步减少垃圾。

我认为我能想到的最有效的方法是根本不使用String.Split或int.Parse。

我比较了4种不同的方法

  1. 使用基本的String.Split
  2. 使用IntParser
  3. 使用此快速字符串分割答案的变体
  4. 添加@CharlesMager的代码来解析整数为3。

我是这样比较的

我用这个算法创建了3,000,000个字符串来匹配你的输入

static string CreateExampleString()
{
    return String.Join(" ", new[] { rnd.Next(1, 3000), rnd.Next(1, 3000), rnd.Next(1, 100000) });
}

我创建了一个基准测试器

static TimeSpan Test(Func<string,int[]> parser, List<string> inputs)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    foreach (var input in inputs)
        parser(input);
    sw.Stop();
    return sw.Elapsed;
}

然后我定义了四个测试用例，第一个是

static int[] ParserBasic(string input)
{
    return input.Split(' ').Select(int.Parse).ToArray();
}

第二个是你的IntParser，正如我已经说过的，第三个是

static public int[] ParserNoSplit(string s)
{
    int[] result = new int[3];
    int x = 0;
    int b = 0;
    for(var i=0;i<s.Length;i++)
    {
        if(s[i] == ' ')
        {
            result[x++] = int.Parse(s.Substring(b, i - b));
            b = i + 1;
        }
    }
    result[x] = int.Parse(s.Substring(b));
    return result;
}

最后，我采用了上面的代码，并将int.Parse替换为@CharlesMager答案中的解析代码，并获得了最好的结果!

static public int[] ParserNoSplitNoIntParse(string s)
{
    int[] result = new int[3];
    int x = 0;
    int b = 0;
    for (var i = 0; i < s.Length; i++)
    {
        if (s[i] == ' ')
        {
            result[x++] = ParseVal(s.Substring(b, i - b));
            b = i + 1;
        }
    }
    result[x] = ParseVal(s.Substring(b));
    return result;
}
static int ParseVal(string s)
{
    var result = 0;
    for (var i = 0; i < s.Length; i++)
    {
        result = result * 10 + (s[i] - '0');
    }
    return result;
}

实际的测试代码是

var allStrings = Enumerable.Range(0, 3000000).Select(x => CreateExampleString()).ToList();
var result1 = Test(ParserBasic, allStrings);
Console.WriteLine($"Result1: {result1.TotalMilliseconds}ms");
var result2 = Test(parser.ParseVals, allStrings);
Console.WriteLine($"Result2: {result2.TotalMilliseconds}ms");
var result3 = Test(ParserNoSplit, allStrings);
Console.WriteLine($"Result3: {result3.TotalMilliseconds}ms");
var result4 = Test(ParserNoSplitNoIntParse, allStrings);
Console.WriteLine($"Result4: {result4.TotalMilliseconds}ms");

同样的300万个输入通过每一个运行的结果如下:

Result1:编写此表达式2491 ms
Result2: 2132 ms
Result3: 1579 ms
Result4: 861 ms

哪个更好，当然。它可能可以在更多方面得到改进，但避免String.Split可以提高整体性能。

使用这个实现，我的速度提高了43%(每dotTrace):

public int ParseVal(string s)
{
    var result = 0;
    for (var i = 0; i < s.Length; i++)
    {
        result = result*10 + (s[i] - '0');
    }
    return result;
}

大部分时间(70%)现在是在String.Split -快速谷歌出来的东西，这样可能会有所帮助。

试试这个(一定要使用Try Catch，以防你的字符串里面没有可转换字符串):

    string myString = "1234 321 145";
    int[] myInts = Array.ConvertAll(myString.Split(' '), int.Parse);

编辑:我做了一个测试来查看所花费的时间:

    List<String> list = new List<String>();
    Random rnd = new Random();
    for (int i = 0; i < 3000; i++) {
        list.Add(String.Join(" ", new[] { rnd.Next(1, 3000), rnd.Next(1, 3000), rnd.Next(1, 100000) }));
    }
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < 3000; i++) {
        int[] myInts = Array.ConvertAll(list[i].Split(' '), int.Parse);
    }
    sw.Stop();
    MessageBox.Show(sw.Elapsed.ToString());

结果为:00:00:00.0016167

相关文章：