如何在此LinkedList的工具上提高性能? [英] How to make improve performance on my implement of this LinkedList?

问题描述

问题如下

TrainComposition是通过将货车从左右两侧，有效地节省了时间.

例如，如果我们首先从左侧附加旅行车7通过再次从左侧连接货车13，我们得到了两辆马车(从左到右分别为13和7).现在，第一辆可以旅行的货车从右边分离的是7，第一个可以分离的从左边是13.

实施模拟此问题的TrainComposition.

关于如何解决项目列表的排序，该问题可能仍与之相关.最初，我针对Testdome练习中提出的此类问题提交了答案.虽然答案在逻辑上是正确的，但它缺乏性能要求.因此，我在这里问了这个问题.

我更新的问题如下:

我查看了不同的集合类型，但仍在如何通过我的LinkedList实现改进性能.

我需要的行为是LinkedList集合的行为，但是性能较弱.您看到我可以做些什么来提高性能吗?也许还有另一种类型的集合可以提供链表的功能并提高性能.我仍然在解决这个问题.感谢您的帮助.

 使用系统；使用System.Collections.Generic;使用System.Linq;公共课TrainComposition{公共TrainComposition(){Wagons = new LinkedList< int>();}私有LinkedList< int>货车；公共无效AttachWagonFromLeft(int wagonId){Wagons.AddFirst(wagonId);}公共无效AttachWagonFromRight(int wagonId){Wagons.AddLast(wagonId);}public int DetachWagonFromLeft(){var wagon = Wagons.First.Value;Wagons.Remove(wagon);回车}public int DetachWagonFromRight(){var wagon = Wagons.Last.Value;Wagons.Remove(wagon);回车}公共静态无效的Main(string [] args){TrainComposition树=新的TrainComposition();tree.AttachWagonFromLeft(7);tree.AttachWagonFromLeft(13);Console.WriteLine(tree.DetachWagonFromRight());//7Console.WriteLine(tree.DetachWagonFromLeft());//13}} 

在此处提出了类似的问题，但使用的是Java而不是C#.因此，这些库有所不同，我认为这是一个尚未解决的问题.

编辑

为清楚起见，请参阅上述的 Testdome 问题说明.

如果可能的话，将我的代码放在上面，然后将其插入Testdome客户端代码编辑框中，以运行测试并查看结果，如下所示:

• 示例:正确答案

• 几辆马车:正确的答案
• 性能测试，涉及大量货车:超过了时间限制

编辑

使用列表，如下所示，我也无法通过性能要求:

  public TrainComposition(){Wagons = new List< int>();}私有列表< int>货车；public void AttachWagonFromLeft(int wagonId)//插入索引0{Wagons.Insert(0，wagonId);}public void AttachWagonFromRight(int wagonId)//将项目添加到最后/结尾{Wagons.Add(wagonId);}public int DetachWagonFromLeft()//删除第一项(索引= 0){var wagon = Wagons [0];Wagons.RemoveAt(0);回车}public int DetachWagonFromRight()//删除最后一项(索引=计数-1){var lastWagonIndex = Wagons.Count()-1;var wagon = Wagons [lastWagonIndex];Wagons.RemoveAt(lastWagonIndex);回车} 

最新更新

敬请期待，我正在努力更新此问题以提供密码笔...

解决方案

最后，有效的方法是here, but using java and not C#. Therefore, the libraries differ and I think it is an unasked question.

EDIT

For clarity, please refer to the above stated Testdome problem description.

If it possible, take my code above, and plunk it into the Testdome client code edit box to run the tests and see results, as follows:

• Example case: Correct answer

• Several wagons: Correct answer
• Performance test with a large number of wagons: Time limit exceeded

EDIT

Using a List, as follows, I also am unable to pass performance requirement:

    public TrainComposition()
    {
        Wagons = new List<int>();
    }

    private List<int> Wagons;

    public void AttachWagonFromLeft(int wagonId) // insert at index 0
    {
        Wagons.Insert(0, wagonId);
    }

    public void AttachWagonFromRight(int wagonId) // add item to last/end 
    {
        Wagons.Add(wagonId);
    }

    public int DetachWagonFromLeft() // remove first item (index = 0)
    {
        var wagon = Wagons[0];
        Wagons.RemoveAt(0);
        return wagon;
    }

    public int DetachWagonFromRight() // remove last item (index = count - 1)
    {
        var lastWagonIndex = Wagons.Count() - 1;
        var wagon = Wagons[lastWagonIndex];
        Wagons.RemoveAt(lastWagonIndex);
        return wagon;
    }

LATEST UPDATE

Stay tuned, I am working on updating this question to provide codepen...

解决方案

In the end, what worked was Steven Cleary's C# implement of Deque, and the following:

public TrainComposition()
{
    Wagons = new Deque<int>();
}

private Deque<int> Wagons;

public void AttachWagonFromLeft(int wagonId)
{
    Wagons.AddToBack(wagonId);
}

public void AttachWagonFromRight(int wagonId)
{
    Wagons.AddToFront(wagonId);
}

public int DetachWagonFromLeft()
{
    return Wagons.RemoveFromBack();
}

public int DetachWagonFromRight()
{
    return Wagons.RemoveFromFront();
}

Is there a simpler solution, than implementing the entirety of Cleary's C# Deque?

As Ivan had commented below, it is possible to achieve the same goals with LinkedList, and calling to RemoveFirst(), and RemoveLast(), as follows:

public TrainComposition()
{
    Wagons = new LinkedList<int>();
}

private LinkedList<int> Wagons;

public void AttachWagonFromLeft(int wagonId)
{
    Wagons.AddFirst(wagonId);
}

public void AttachWagonFromRight(int wagonId)
{
    Wagons.AddLast(wagonId);
}

public int DetachWagonFromLeft()
{
    var wagon = Wagons.First.Value;
    Wagons.RemoveFirst();
    return wagon;
}

public int DetachWagonFromRight()
{
    var wagon = Wagons.Last.Value;
    Wagons.RemoveLast();
    return wagon;
}

这篇关于如何在此LinkedList的工具上提高性能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！