Je viens de lire quelques posts sur List<T> vs LinkedList<T> J'ai donc décidé d'évaluer moi-même certaines structures. J'ai évalué Stack<T> , Queue<T> , List<T> y LinkedList<T> en ajoutant des données et en supprimant des données de/vers le front/end. Voici le résultat du benchmark :
Pushing to Stack... Time used: 7067 ticks
Poping from Stack... Time used: 2508 ticks
Enqueue to Queue... Time used: 7509 ticks
Dequeue from Queue... Time used: 2973 ticks
Insert to List at the front... Time used: 5211897 ticks
RemoveAt from List at the front... Time used: 5198380 ticks
Add to List at the end... Time used: 5691 ticks
RemoveAt from List at the end... Time used: 3484 ticks
AddFirst to LinkedList... Time used: 14057 ticks
RemoveFirst from LinkedList... Time used: 5132 ticks
AddLast to LinkedList... Time used: 9294 ticks
RemoveLast from LinkedList... Time used: 4414 ticksCode :
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace Benchmarking
{
static class Collections
{
public static void run()
{
Random rand = new Random();
Stopwatch sw = new Stopwatch();
Stack<int> stack = new Stack<int>();
Queue<int> queue = new Queue<int>();
List<int> list1 = new List<int>();
List<int> list2 = new List<int>();
LinkedList<int> linkedlist1 = new LinkedList<int>();
LinkedList<int> linkedlist2 = new LinkedList<int>();
int dummy;
sw.Reset();
Console.Write("{0,40}", "Pushing to Stack...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
stack.Push(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Poping from Stack...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = stack.Pop();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Enqueue to Queue...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
queue.Enqueue(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Dequeue from Queue...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = queue.Dequeue();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Insert to List at the front...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
list1.Insert(0, rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveAt from List at the front...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = list1[0];
list1.RemoveAt(0);
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "Add to List at the end...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
list2.Add(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveAt from List at the end...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = list2[list2.Count - 1];
list2.RemoveAt(list2.Count - 1);
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "AddFirst to LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
linkedlist1.AddFirst(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveFirst from LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = linkedlist1.First.Value;
linkedlist1.RemoveFirst();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "AddLast to LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
linkedlist2.AddLast(rand.Next());
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks", sw.ElapsedTicks);
sw.Reset();
Console.Write("{0,40}", "RemoveLast from LinkedList...");
sw.Start();
for (int i = 0; i < 100000; i++)
{
dummy = linkedlist2.Last.Value;
linkedlist2.RemoveLast();
dummy++;
}
sw.Stop();
Console.WriteLine(" Time used: {0,9} ticks\n", sw.ElapsedTicks);
}
}
}Les différences sont les suivantes donc dramatique !
Comme vous pouvez le constater, les performances de Stack<T> y Queue<T> sont rapides et comparables, c'est normal.
Para List<T> l'utilisation de l'avant et de l'arrière a tellement de différences ! Et à ma grande surprise, la performance de l'ajout/suppression à partir de la fin est en fait comparable à la performance de l'ajout/suppression à partir de la fin. Stack<T> .
Para LinkedList<T> la manipulation avec l'avant est rapide (-er que List<T> ) mais en fin de compte, il est incroyablement lent à retirer. manipuler avec la fin est aussi.
Alors... des experts peuvent-ils nous dire.. :
- la similitude des performances de l'utilisation
Stack<T>et la fin deList<T>, - les différences dans l'utilisation de l'avant et de l'extrémité de la
List<T>et -
la raison pour laquelle l'utilisation de la fin de(sans objet, car il s'agit d'une erreur de codage due à l'utilisation de la méthode de LinqLinkedList<T>est donc lentLast(), Merci à CodesInChaos ) ?
Je pense que je sais pourquoi List<T> ne gère pas si bien le front... parce que List<T> doit déplacer la liste entière d'avant en arrière quand il fait ça. Corrigez-moi si je me trompe.
P.S. Mon System.Diagnostics.Stopwatch.Frequency est 2435947 Le programme est conçu pour le profil client .NET 4 et compilé avec C# 4.0, sur Windows 7 Visual Studio 2010.
9 votes
Sans vouloir vous offenser, vous devriez d'abord apprendre ce que sont ces structures de données et quelle est la complexité (notation du grand O) de chaque opération sur chaque structure de données. Malheureusement, MSDN ne vous aidera pas dans ce domaine, mais il ne devrait pas être difficile de trouver suffisamment d'informations sur Wikipedia.
6 votes
@EmperorOrionii Oui, je comprends ces structures. J'étais juste perplexe sur la raison pour laquelle une liste à double lien prend autant de temps pour accéder à la fin mais il s'est avéré que c'était une erreur de codage.