C # moyen le plus rapide de changer de tableau

Comment puis-je déplacer rapidement tous les éléments d’un tableau vers la gauche, en remplissant la fin par un caractère nul?

Par exemple, [0,1,2,3,4,5,6] deviendrait [1,2,3,4,5,6, null]

Edit: J’ai dit rapidement mais je suppose que je voulais dire efficacement. Je dois le faire sans créer une liste ou une autre structure de données. C’est quelque chose que je dois faire plusieurs centaines de milliers de fois en un minimum de temps.

Voici mon harnais de test …

var source = Enumerable.Range(1, 100).Cast().ToArray(); var destination = new int?[source.Length]; var s = new Stopwatch(); s.Start(); for (int i = 0; i < 1000000;i++) { Array.Copy(source, 1, destination, 0, source.Length - 1); } s.Stop(); Console.WriteLine(s.Elapsed); 

Voici les résultats de performance pour 1 million d'itérations de chaque solution (Intel Xeon E5450 à 3 cœurs à 3 000 GHz)

  100 elements 10000 elements For Loop 0.390s 31.839s Array.Copy() 0.177s 12.496s Aaron 1 3.789s 84.082s Array.ConstrainedCopy() 0.197s 17.658s 

Faites le choix pour vous-même 🙂

La méthode la plus rapide consiste à utiliser Array.Copy , qui, dans l’implémentation finale, utilise une opération de transfert de mémoire en masse (similaire à memcpy):

 var oldArray = new int?[] { 1, 2, 3, 4, 5, 6 }; var newArray = new int?[oldArray.Length]; Array.Copy(oldArray, 1, newArray, 0, oldArray.Length - 1); // newArray is now { 2, 3, 4, 5, 6, null } 

Edité: selon la documentation:

Si sourceArray et destinationArray se chevauchent, cette méthode se comporte comme si les valeurs d’origine de sourceArray étaient conservées dans un emplacement temporaire avant que destinationArray ne soit écrasé.

Donc, si vous ne voulez pas allouer un nouveau tableau, vous pouvez passer le tableau d’origine à la fois à la source et à la destination – bien que j’imagine que le compromis sera un peu plus lent puisque les valeurs passent par une position temporaire.

Je suppose que, comme dans toute enquête de ce genre, vous devriez faire des parsings comparatives rapides.

Voici ma solution, similaire à celle de Task en ce qu’il s’agit d’un simple wrapper Array et qu’il faut du temps O (1) pour déplacer le tableau vers la gauche.

 public class ShiftyArray { private readonly T[] array; private int front; public ShiftyArray(T[] array) { this.array = array; front = 0; } public void ShiftLeft() { array[front++] = default(T); if(front > array.Length - 1) { front = 0; } } public void ShiftLeft(int count) { for(int i = 0; i < count; i++) { ShiftLeft(); } } public T this[int index] { get { if(index > array.Length - 1) { throw new IndexOutOfRangeException(); } return array[(front + index) % array.Length]; } } public int Length { get { return array.Length; } } } 

En cours d’exécution via le code de test de Jason Punyon …

 int?[] intData = Enumerable.Range(1, 100).Cast().ToArray(); ShiftyArray array = new ShiftyArray(intData); Stopwatch watch = new Stopwatch(); watch.Start(); for(int i = 0; i < 1000000; i++) { array.ShiftLeft(); } watch.Stop(); Console.WriteLine(watch.ElapsedMilliseconds); 

Prend environ 29ms, quelle que soit la taille du tableau.

Utilisez la méthode Array.Copy() comme dans

 int?[] myArray = new int?[]{0,1,2,3,4}; Array.Copy(myArray, 1, myArray, 0, myArray.Length - 1); myArray[myArray.Length - 1] = null 

The Array.Copy est probablement la voie, Microsoft voulait que nous Array.Copy éléments de tableau …

Ne pourriez-vous pas utiliser un System.Collections.Generic.Queue au lieu d’un tableau?

Je pense que vous devez effectuer des actions sur votre valeur en la défaussant, donc utiliser une queue semble être plus approprié:

 // dummy initialization System.Collections.Generic.Queue queue = new Queue(); for (int i = 0; i < 7; ++i ) { queue.Enqueue(i); }// add each element at the end of the container // working thread if (queue.Count > 0) doSomething(queue.Dequeue());// removes the last element of the container and calls doSomething on it 

S’il doit absolument être dans un tableau, alors je recommanderais le code le plus évident possible.

 for (int index = startIndex; index + 1 < values.Length; index++) values[index] = values[index + 1]; values[values.Length - 1] = null; 

Cela donne à l'optimiseur le plus de possibilités de trouver le meilleur moyen, quelle que soit la plate-forme cible sur laquelle le programme est installé.

MODIFIER:

Je viens d'emprunter le code de test de Jason Punyon, et j'ai bien peur qu'il ait raison. Array.Copy gagne!

  var source = Enumerable.Range(1, 100).Cast().ToArray(); int indexToRemove = 4; var s = new Stopwatch(); s.Start(); for (int i = 0; i < 1000000; i++) { Array.Copy(source, indexToRemove + 1, source, indexToRemove, source.Length - indexToRemove - 1); //for (int index = indexToRemove; index + 1 < source.Length; index++) // source[index] = source[index + 1]; } s.Stop(); Console.WriteLine(s.Elapsed); 

Array.Copy prend entre 103 et 150 ms sur ma machine.

pour la boucle prend entre 269 et 338 ms sur ma machine.

Pour toute âme cherchant ce fil et sur le sharepoint mettre en œuvre l’une des réponses les mieux notées. Tous sont des déchets, je ne sais pas pourquoi. Peut-être que Dested a demandé une nouvelle implémentation de tableau au début ou quelque chose qui a maintenant été supprimé de la question. Eh bien, si vous voulez simplement déplacer le tableau sans en avoir besoin d’un nouveau, voyez une réponse comme celle de tdaines. Et lisez des choses comme le tampon circulaire / anneau tampon: http://en.wikipedia.org/wiki/Circular_buffer . Aucun déplacement des données réelles n’est nécessaire. Les performances de décalage d’un tableau ne doivent pas être liées à la taille du tableau.

Vous ne pouvez pas

  • allouer le tableau avec 1000 éléments supplémentaires

  • avoir une variable entière int base = 0

  • au lieu d’accéder à a[i] accéder à a[base+i]

  • pour faire votre quart, dites simplement base++

Ensuite, après 1000 opérations, copiez-le et recommencez.
De cette façon, vous ne faites la copie qu’une fois par 1000 quarts de travail.


Vieille blague:
Q: Combien d’IBM 360 faut-il pour déplacer un registre d’un bit?
A: 33. 32 pour maintenir les bits en place et 1 pour déplacer le registre. (ou une telle …)

Vous pourriez le faire comme ceci:

 var items = new int?[] { 0, 1, 2, 3, 4, 5, 6 }; // Your array var itemList = new List(items); // Put the items in a List<> itemList.RemoveAt(1); // Remove the item at index 1 itemList.Add(null); // Add a null to the end of the list items = itemList.ToArray(); // Turn the list back into an array 

Bien sûr, il serait plus efficace de se débarrasser entièrement du tableau et d’utiliser simplement une liste <>. Vous pourriez alors oublier la première ligne et la dernière ligne et le faire comme ceci:

 var itemList = new List { 0, 1, 2, 3, 4, 5, 6 }; itemList.RemoveAt(1); // Remove the item at index 1 itemList.Add(null); // Add a null to the end of the list 

Vous pouvez utiliser le même tableau comme source et destination pour une copie rapide sur place:

 static void Main(ssortingng[] args) { int[] array = {0, 1, 2, 3, 4, 5, 6, 7}; Array.ConstrainedCopy(array, 1, array, 0, array.Length - 1); array[array.Length - 1] = 0; } 

Je sais que c’est une vieille question mais venant de Google, il n’y avait pas d’exemple simple, donc grâce à cela, le moyen le plus simple de réorganiser une liste, et vous n’avez pas à fournir le type qui fonctionnera à l’exécution,

  private static List reorderList(List list){ List newList = new List(); list.ForEach(delegate(T item) { newList.Add(item); }); return newList; } 

Essaye ça! en utilisant Linq. Pas besoin de second tableau.

  var i_array = new int?[] {0, 1, 2, 3, 4, 5, 6 }; i_array = i_array.Select((v, k) => new { v = v, k = k }). Where(i => ik > 0).Select(i => iv).ToArray(); Array.Resize(ref i_array, i_array.Length + 1); 

Sortie: [0,1,2,3,4,5,6] deviendrait [1,2,3,4,5,6, null]

Si vous possédez la mémoire, vous pouvez envisager d’utiliser un code non sécurisé et de bons pointeurs à l’ancienne.

Créez-vous un stream de mémoire et verrouillez-le ou utilisez Marshal.AllocHGlobal Construisez tous vos tableaux avec un peu de remplissage au début et à la fin. incrémenter ou décrémenter tous les pointeurs de tableau à la fois. Vous aurez toujours besoin de boucler et de définir vos valeurs NULL.

Si vous devez incrémenter ou décrémenter sélectivement les tableaux, vous devrez append un remplissage entre eux.

Les tableaux sont des structures de données de niveau incroyablement bas, si vous les traitez de manière simplifiée, vous pouvez en tirer d’énormes performances.

Un baytrail faisant cela pourrait surpasser celui de Jason avec tous ses processeurs Intel Xeon E5450 à 3.00 GHz

Non testé ce code, mais il devrait déplacer toutes les valeurs à droite par un. Notez que les trois dernières lignes de code sont tout ce dont vous avez besoin pour déplacer efficacement le tableau.

 public class Shift : MonoBehaviour { //Initialize Array public int[] queue; void Start () { //Create Array Rows queue = new int[5]; //Set Values to 1,2,3,4,5 for (int i=0; i<5;i++) { queue[i] = i + 1; } //Get the integer at the first index int prev = queue[0]; //Copy the array to the new array. System.Array.Copy(queue, 1, queue, 0, queue.Length - 1); //Set the last shifted value to the previously first value. queue[queue.Length - 1] = prev; 

La copie de tableaux est une opération O (n) et crée un nouveau tableau. Bien que la copie de tableaux puisse être effectuée rapidement et efficacement, le problème que vous avez déclaré peut être résolu de manière totalement différente sans (comme vous l’avez demandé) créer une nouvelle structure de tableau / données et ne créer qu’une petite instance d’object tableau:

 using System; using System.Text; public class ArrayReindexer { private Array reindexed; private int location, offset; public ArrayReindexer( Array source ) { reindexed = source; } public object this[int index] { get { if (offset > 0 && index >= location) { int adjustedIndex = index + offset; return adjustedIndex >= reindexed.Length ? "null" : reindexed.GetValue( adjustedIndex ); } return reindexed.GetValue( index ); } } public void Reindex( int position, int shiftAmount ) { location = position; offset = shiftAmount; } public override ssortingng ToSsortingng() { SsortingngBuilder output = new SsortingngBuilder( "[ " ); for (int i = 0; i < reindexed.Length; ++i) { output.Append( this[i] ); if (i == reindexed.Length - 1) { output.Append( " ]" ); } else { output.Append( ", " ); } } return output.ToString(); } } 

En encapsulant et en contrôlant l'access au tableau de cette manière, nous pouvons maintenant démontrer comment le problème a été résolu avec un appel de méthode O (1) ...

 ArrayReindexer original = new ArrayReindexer( SourceArray ); Console.WriteLine( " Base array: {0}", original.ToSsortingng() ); ArrayReindexer reindexed = new ArrayReindexer( SourceArray ); reindexed.Reindex( 1, 1 ); Console.WriteLine( "Shifted array: {0}", reindexed.ToSsortingng() ); 

Produira la sortie:

Tableau de base: [0, 1, 2, 3, 4, 5, 6]
Tableau décalé: [0, 2, 3, 4, 5, 6, null]

Je suis prêt à parier qu'il y aura une raison pour laquelle une telle solution ne fonctionnera pas pour vous, mais je crois que cela correspond à vos exigences initiales. 8)

Il est souvent utile de réfléchir à tous les différents types de solutions à un problème avant d'en implémenter un, et cela pourrait être la chose la plus importante que cet exemple puisse démontrer.

J'espère que cela t'aides!

Réponse incorrecte et légèrement amusante (merci, je serai là toute la nuit!)

 int?[] test = new int?[] {0,1,2,3,4,5,6 }; int?[] t = new int?[test.Length]; t = test.Skip(1).ToArray(); t[t.Length - 1] = null; 

Dans l’esprit de continuer à utiliser Skip (ne me demandez pas, je connais le pire usage des méthodes d’extension LINQ jamais), la seule façon de le réécrire serait

  int?[] test = new int?[] { 0, 1, 2, 3, 4, 5, 6 }; int?[] t = new int?[test.Length]; Array.Copy(test.Skip(1).ToArray(), t, t.Length - 1); 

Mais ce n’est PAS PLUS rapide que les autres options.

 using System; using System.Threading; namespace ShiftMasortingx { class Program { static void Main(ssortingng[] args) { MasortingxOperation objMasortingxOperation = new MasortingxOperation(); //Create a masortingx int[,] mat = new int[,] { {1, 2}, {3,4 }, {5, 6}, {7,8}, {8,9}, }; int type = 2; int counter = 0; if (type == 1) { counter = mat.GetLength(0); } else { counter = mat.GetLength(1); } while (true) { for (int i = 0; i < counter; i++) { ShowMatrix(objMatrixOperation.ShiftMatrix(mat, i, type)); Thread.Sleep(TimeSpan.FromSeconds(2)); } } } public static void ShowMatrix(int[,] matrix) { int rows = matrix.GetLength(0); int columns = matrix.GetLength(1); for (int k = 0; k < rows; k++) { for (int l = 0; l < columns; l++) { Console.Write(matrix[k, l] + " "); } Console.WriteLine(); } } } class MatrixOperation { public int[,] ShiftMatrix(int[,] origanalMatrix, int shift, int type) { int rows = origanalMatrix.GetLength(0); int cols = origanalMatrix.GetLength(1); int[,] _tmpMatrix = new int[rows, cols]; if (type == 2) { for (int x1 = 0; x1 < rows; x1++) { int y2 = 0; for (int y1 = shift; y2 < cols - shift; y1++, y2++) { _tmpMatrix[x1, y2] = origanalMatrix[x1, y1]; } y2--; for (int y1 = 0; y1 < shift; y1++, y2++) { _tmpMatrix[x1, y2] = origanalMatrix[x1, y1]; } } } else { int x2 = 0; for (int x1 = shift; x2 < rows - shift; x1++, x2++) { for (int y1 = 0; y1 < cols; y1++) { _tmpMatrix[x2, y1] = origanalMatrix[x1, y1]; } } x2--; for (int x1 = 0; x1 < shift; x1++, x2++) { for (int y1 = 0; y1 < cols; y1++) { _tmpMatrix[x2, y1] = origanalMatrix[x1, y1]; } } } return _tmpMatrix; } } } 

Je pense que la méthode la plus efficace et la plus efficace consiste à utiliser la fonction Buffer.BlockCopy. Vous définissez à la fois la source et la destination sur votre tableau, le décalage de la source est 1. Selon votre type de tableau (je suppose qu’il est int), 1 int = 4 octets, vous devez donc passer en 4 comme second paramètre de cette fonction. Notez que le décalage est un décalage d’octet.

Alors ça ressemble à ça:

 int bytes2copy = yourArray.length - 4; Buffer.BlockCopy(yourArray, 4, yourArray, 0, bytes2copy); yourArray[yourArray.length-1] = null; 

Voir le code C # ci-dessous pour supprimer l’espace de la chaîne. Ce caractère de décalage dans le tableau. La performance est O (n). Aucun autre tableau n’est utilisé. Donc pas de mémoire supplémentaire non plus.

  static void Main(ssortingng[] args) { ssortingng strIn = System.Console.ReadLine(); char[] chraryIn = strIn.ToCharArray(); int iShift = 0; char chrTemp; for (int i = 0; i < chraryIn.Length; ++i) { if (i > 0) { chrTemp = chraryIn[i]; chraryIn[i - iShift] = chrTemp; chraryIn[i] = chraryIn[i - iShift]; } if (chraryIn[i] == ' ') iShift++; if (i >= chraryIn.Length - 1 - iShift) chraryIn[i] = ' '; } System.Console.WriteLine(new ssortingng(chraryIn)); System.Console.Read(); }