Как я могу быстро перенести все элементы в массиве один влево, заполнив конец нулевым значением?
Например, [0,1,2,3,4,5,6] станет [1,2,3,4,5,6, null]
Редактировать: Я сказал быстро, но я предполагаю, что имел в виду эффективнее. Мне нужно сделать это без создания списка или какой-либо другой структуры данных. Это то, что мне нужно сделать несколько сотен тысяч раз за максимально короткий промежуток времени.
Здесь моя тестовая упряжь...
var source = Enumerable.Range(1, 100).Cast<int?>().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);
Ниже приведены результаты работы для 1 миллиона итераций каждого решения (8 Core Intel Xeon E5450 @3,00 ГГц)
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
Сделайте выбор самостоятельно:)
Самый быстрый способ сделать это - использовать Array.Copy, который в последней реализации использует операцию передачи объемной памяти (похожую на 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 }
Отредактировано: согласно документации:
Если sourceArray и destinationArray перекрываются, этот метод ведет себя так, как если бы исходные значения sourceArray были сохранены во временном местоположении до того, как файл destinationArray будет перезаписан.
Итак, если вы не хотите выделять новый массив, вы можете передать исходный массив как для источника, так и для назначения - хотя я думаю, что компромисс будет несколько более медленным, поскольку значения проходят через временную позицию удержания.
Я полагаю, что, как и в любом исследовании такого рода, вы должны сделать быстрый бенчмаркинг.
Вот мое решение, похожее на Task, в том, что оно является простой оболочкой Array и требуется время O (1) для перемещения массива влево.
public class ShiftyArray<T>
{
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; } }
}
Запуск через тестовый код Джейсона Пеньона...
int?[] intData = Enumerable.Range(1, 100).Cast<int?>().ToArray();
ShiftyArray<int?> array = new ShiftyArray<int?>(intData);
Stopwatch watch = new Stopwatch();
watch.Start();
for(int i = 0; i < 1000000; i++)
{
array.ShiftLeft();
}
watch.Stop();
Console.WriteLine(watch.ElapsedMilliseconds);
Принимает ~ 29 мс, независимо от размера массива.
Не удалось ли использовать System.Collections.Generic.Queue вместо массива?
Мне кажется, что вам нужно выполнить действия над своим значением, отбросить его, поэтому использование очереди кажется более подходящим:
// dummy initialization
System.Collections.Generic.Queue<int> queue = new Queue<int>();
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
Используйте метод Array.Copy(), как в
int?[] myArray = new int?[]{0,1,2,3,4};
Array.Copy(myArray, 1, myArray, 0, myArray.Length - 1);
myArray[myArray.Length - 1] = null
Array.Copy, вероятно, так, Microsoft хотела, чтобы мы копировали элементы массива...
Если это абсолютно необходимо в массиве, я бы рекомендовал наиболее очевидный код.
for (int index = startIndex; index + 1 < values.Length; index++)
values[index] = values[index + 1];
values[values.Length - 1] = null;
Это дает оптимизатору больше возможностей найти лучший способ на любой целевой платформе, на которой установлена программа.
EDIT:
Я просто заимствовал тестовый код Джейсона Пеньона, и я боюсь, что он прав. Array.Copy выигрывает!
var source = Enumerable.Range(1, 100).Cast<int?>().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 занимает от 103 до 150 мс на моей машине.
для цикла занимает от 269 до 338 мс на моей машине.
Ибо всякая душа найдет эту нить и собирается реализовать один из высоко оцененных ответов. Все они мусор, я не уверен, почему это так. Возможно, Dested попросил сначала реализовать реализацию массива или что-то, что теперь было удалено из вопроса. Ну, если вы просто хотите перенести массив и не нуждаетесь в новом, см. Ответ, например, ответ tdaines. И читайте на таких вещах, как круговой буфер/кольцевой буфер: http://en.wikipedia.org/wiki/Circular_buffer. Не требуется перемещения фактических данных. Производительность переключения массива должна быть не привязана к размеру массива.
Вы не можете
выделите массив с дополнительными 1000 элементами
имеют целочисленную переменную int base = 0
вместо доступа к a[i] доступ a[base+i]
чтобы сделать ваш сдвиг, просто скажите base++
Затем, после того как вы сделали это 1000 раз, скопируйте его и начните.
Таким образом, вы делаете копию только один раз за 1000 смен.
Старая шутка:
Q: Сколько IBM 360s требуется, чтобы сдвинуть регистр на 1 бит?
A: 33. 32 для хранения бит на месте и 1 для перемещения регистра. (или некоторые такие...)
Вы можете сделать это следующим образом:
var items = new int?[] { 0, 1, 2, 3, 4, 5, 6 }; // Your array
var itemList = new List<int?>(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
Конечно, было бы более эффективно избавиться от массива целиком и просто использовать List < > . Затем вы могли бы забыть первую строку и последнюю строку и сделать это следующим образом:
var itemList = new List<int?> { 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
Вы можете использовать тот же массив, что и источник и место назначения, для быстрой копии на месте:
static void Main(string[] 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;
}
Попробуйте это! используя Linq. Нет необходимости в втором массиве.
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 => i.k > 0).Select(i => i.v).ToArray();
Array.Resize(ref i_array, i_array.Length + 1);
Вывод: [0,1,2,3,4,5,6] станет [1,2,3,4,5,6, null]
Если у вас есть память, вы можете использовать Unsafe Code и добрые старомодные указатели.
Сделайте себе поток памяти и заблокируйте его или используйте Marshal.AllocHGlobal
Постройте все свои массивы в нем с небольшим отступом в начале и в конце.
увеличивать или уменьшать все указатели массива за один раз. Вам все равно нужно будет выполнить обратную связь и установить нулевые значения.
Если вам нужно выборочно увеличивать или уменьшать массивы, вам нужно будет добавить отступы между ними.
Массивы - это структуры с невероятно низким уровнем данных, если вы относитесь к ним на низком уровне, вы можете получить огромную производительность из них.
Байтарная игра, выполняющая это, может превзойти Джейсона со всем его копированием 8 Core Intel Xeon E5450 @3,00 ГГц
Не проверен этот код, но он должен сдвигать все значения вправо на один. Обратите внимание, что последние три строки кода - это все, что вам требуется для эффективного переноса массива.
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;
Неправильный и слегка забавный ответ (спасибо, я буду здесь всю ночь!)
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;
В духе использования Skip (не спрашивайте меня, я знаю худшее использование методов расширения LINQ когда-либо), единственный способ, которым я думал переписывать его, был бы
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);
Но это в НЕТ ПУТЬ быстрее, чем другие варианты.
Копирование массива - это операция O (n) и создает новый массив. Хотя копирование массива, безусловно, может быть сделано быстро и эффективно, проблема, о которой вы заявили, может быть фактически решена совершенно по-другому без (как вы просили) создания новой структуры массива/данных и создания только одного экземпляра экземпляра обертки в массив:
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 string ToString()
{
StringBuilder output = new StringBuilder( "[ " );
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();
}
}
Обернув и контролируя доступ к массиву таким образом, мы теперь можем продемонстрировать, как проблема была решена с помощью вызова метода O (1)...
ArrayReindexer original = new ArrayReindexer( SourceArray );
Console.WriteLine( " Base array: {0}", original.ToString() );
ArrayReindexer reindexed = new ArrayReindexer( SourceArray );
reindexed.Reindex( 1, 1 );
Console.WriteLine( "Shifted array: {0}", reindexed.ToString() );
Произведет вывод:
Базовая матрица: [0, 1, 2, 3, 4, 5, 6]
Сдвинутый массив: [0, 2, 3, 4, 5, 6, null]
Я готов поспорить, что будет причина, по которой такое решение не сработает для вас, но я считаю, что это соответствует вашим первоначальным заявленным требованиям. 8)
Часто бывает полезно подумать обо всех различных решениях проблемы перед реализацией конкретного, и, возможно, это может быть самым важным, что может продемонстрировать этот пример.
Надеюсь, это поможет!
Я знаю, что это старый вопрос, но из Google не было простого примера, поэтому благодаря этому это самый простой способ переупорядочить список, и вам не нужно указывать тип, который он будет работать во время выполнения,
private static List<T> reorderList<T>(List<T> list){
List<T> newList = new List<T>();
list.ForEach(delegate(T item)
{
newList.Add(item);
});
return newList;
}
using System;
using System.Threading;
namespace ShiftMatrix
{
class Program
{
static void Main(string[] args)
{
MatrixOperation objMatrixOperation = new MatrixOperation();
//Create a matrix
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;
}
}
}
Самый лучший и самый эффективный метод, который я считаю, использует функцию Buffer.BlockCopy. Вы установите для источника как источник, так и пункт назначения, смещение источника равно 1. В зависимости от вашего типа массива (я предполагаю, что это int), 1 int = 4 байта, поэтому вы должны пройти в 4 в качестве второго параметра этого функция. Обратите внимание, что смещение является смещением байта.
Итак, это выглядит так:
int bytes2copy = yourArray.length - 4;
Buffer.BlockCopy(yourArray, 4, yourArray, 0, bytes2copy);
yourArray[yourArray.length-1] = null;
Смотрите код С# ниже, чтобы удалить пробел из строки. Этот символ сдвига в массиве. Производительность O (n). Никакой другой массив не используется. Так что никакой дополнительной памяти тоже.
static void Main(string[] args)
{
string 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 string(chraryIn));
System.Console.Read();
}