C＃代码效率太低，导致hackerrank超时 [英] C# code is too inefficient, causing timeout on hackerrank

问题描述

嘿伙计们，



我有一些额外的时间，所以我正在做HackerRank的编码挑战，并且在挑战的第8天无论多么努力我试过我不能让代码运行更有效，因为一些测试用例总是TimeOut。



如果你们可以节省2分钟查看我的代码并看到哪里效率低，请告诉我:)



基本上，在第一个for循环中，我正在读取Key Value Pairs，在第二个for循环中我正在读取潜在的密钥，如果它们有一个值，则输出key = value，否则输出Not found。变量n告诉我我正在读的有多少个键值对以及我正在读的有多少个潜在的键。

Hey Guys,

I had some extra time to spare, so I was doing the coding challenge by HackerRank and on Day 8 of the challenge no matter how hard I tried I cant make the code run more efficiently as some of the test cases always "TimeOut".

If you guys could spare 2 minutes looking at my code and seeing where it is inefficient please let me know :)

Basically, in the first for loop I am reading in Key Value Pairs, in the second for loop I am reading in potential keys, if they have a value then output key=value, else output "Not found". the variable "n" tells me how many key value pairs i am reading in and how many potential keys I am reading in as well.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Collections;

class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int n = int.Parse(Console.ReadLine());
        string Word1 = "";
        Dictionary<string, int> list = new Dictionary<string, int>();
        
        for(int i = 0; i <n; i++)
        {
            Word1 = Console.ReadLine();
            string[] array = Word1.Split(null);
            list.Add(array[0], int.Parse(array[1]));
        }
        for(int i = 0; i<n; i++)
        {
            Word1 = Console.ReadLine();
            if(list.ContainsKey(Word1))
            {
                var keyValuePair = list.Single(x => x.Key == Word1);
                Console.WriteLine(Word1 + "=" + keyValuePair.Value);
            }
            else
            {
                Console.WriteLine("Not found");
            }
        }
        
        
    }
}

我尝试了什么：



这个解决方案肯定比我使用foreach循环的第一个解决方案更有效...但是我在这种情况下不知道任何比LINQ

What I have tried:

This solution is definitely more efficient than my first one where I was using foreach loops... but I dont know of anything in this case that would be faster than LINQ

推荐答案

更快的东西你正在以低效的方式查找'Word1'，试试这个（'标准方式' ）：

You are looking up 'Word1' in an inefficient way, try this ('the standard way'):

for(int i = 0; i < n; i++)
{
    int val;

    Word1 = Console.ReadLine();
    if (list.TryGetValue(Word1, out val))
    {
        Console.WriteLine(Word1 + " = " + val);
    }
    else
    {
        Console.WriteLine(Word1 + " not found");
    }
}

或简而言之：

or in short:

for(int i = 0; i < n; i++)
{
    int val;

    Word1 = Console.ReadLine();
    Console.WriteLine(Word1 + (list.TryGetValue(Word1, out val) ? " = " + val : " not found"));
}

在速度优化方面，首选的工具是分析器。

分析器可以告诉您在代码的每个部分花费了多少时间以及检测瓶颈。

编制（计算机编程） - 维基百科 [ ^ ]

When it comes to speed optimization, the tool of choice is the profiler.
the profiler is there to tell you how much time you spend in each part of your code and to detect bottlenecks.
Profiling (computer programming) - Wikipedia[^]

一行如

A line like

list.Single(x => x.Key == Word1);

是低效的，因为Linq-to-object无法理解它正在用字键搜索字典。所以它基本上会枚举字典中的所有项目，直到找到匹配为止。



另一方面， TryGetValue 专门用于在字典上进行有效搜索。



对于此类操作，容器方法会更快。



Linq-to-Entities或Linq-to-SQL是不同的，因为SQL代码是通过自己分析表达式生成的。



同样使用`Single`意味着你要检查所有元素以确保存在单个元素。平均使用`First`会快两倍，因为字典无论如何都不能包含重复键，它会得到相同的结果。

is inefficient because Linq-to-object has no way to understand that it is searching a dictionary with its key. So it will essentially enumerate all items in the dictionary until it find a match.

On the other hand, TryGetValue is specifically written to do an efficient search on the dictionary.

For such operations, container methods would be faster.

Linq-to-Entities or Linq-to-SQL are different as SQL code is generated by analysing the expression themselves.

Also using `Single` imply that you would check all elements to ensure that a single one exists. On average using `First` would be twice as fast and since a dictionary cannot contains duplicate keys anyway, it would give the same result.

这篇关于C＃代码效率太低，导致hackerrank超时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！