배열을 이동하는 C # 가장 빠른 방법
배열의 모든 항목을 왼쪽으로 빠르게 이동하고 끝을 null로 채우는 방법은 무엇입니까?
예를 들어 [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);
다음은 각 솔루션의 100 만 회 반복에 대한 성능 결과입니다 (8 Core Intel Xeon E5450 @ 3.00GHz).
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가 겹치는 경우이 메서드는 destinationArray를 덮어 쓰기 전에 sourceArray의 원래 값이 임시 위치에 보존 된 것처럼 작동합니다.
따라서 새 배열을 할당하지 않으려면 원본과 대상 모두에 대해 원래 배열을 전달할 수 있습니다. 값이 일시적인 유지 위치를 통과하기 때문에 성능이 다소 느려질 것이라고 생각합니다.
이런 종류의 조사에서와 마찬가지로 몇 가지 빠른 벤치마킹을 수행해야한다고 생각합니다.
다음은 간단한 Array 래퍼이고 배열을 왼쪽으로 이동하는 데 O (1) 시간이 걸린다는 점에서 Task와 유사한 내 솔루션입니다.
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; } }
}
Jason Punyon의 테스트 코드를 통해 실행 ...
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);
어레이 크기에 관계없이 ~ 29ms가 걸립니다.
다음과 같이 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아마 방법, 마이크로 소프트는 우리가 배열 요소를 복사하고 싶어 ...
배열 대신 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
절대적 경우 가 배열로, 나는 가능한 가장 확실한 코드를 추천 할 것입니다.
for (int index = startIndex; index + 1 < values.Length; index++)
values[index] = values[index + 1];
values[values.Length - 1] = null;
이렇게하면 최적화 프로그램이 설치된 대상 플랫폼에 상관없이 최적의 방법을 찾을 수있는 가장 많은 기회가 주어집니다.
편집하다:
방금 Jason Punyon의 테스트 코드를 빌 렸는데 그가 옳다고 생각합니다. 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 ~ 150ms가 걸립니다.
for 루프는 내 컴퓨터에서 269 ~ 338ms가 걸립니다.
이 스레드를 찾고 높은 등급의 답변 중 하나를 구현하려는 모든 부어 영혼을 위해. 그들 모두는 쓰레기입니다. 왜 그런지 잘 모르겠습니다. 아마도 Dested는 처음에 새로운 어레이 구현을 요청했거나 이제 질문에서 제거 된 것을 요청했을 것입니다. 단순히 배열을 이동하고 새 배열이 필요하지 않은 경우 tdaines의 답변과 같은 답변을 참조하십시오. 그리고 Circular Buffer / Ring Buffer 같은 것들을 읽어 보세요 : http://en.wikipedia.org/wiki/Circular_buffer . 실제 데이터를 이동할 필요가 없습니다. 어레이 이동의 성능해야 하지 배열의 크기에 연결 될 수있다.
당신은 할 수 없습니다
1000 개의 추가 요소로 배열 할당
정수 변수가 있습니다
int base = 0액세스에
a[i]액세스하는 대신a[base+i]교대를하려면
base++
그런 다음이 작업을 1000 번 수행 한 후 아래로 복사하고 다시 시작하십시오.
이렇게하면 1000 교대 당 한 번만 복사 할 수 있습니다.
오래된 농담 :
Q : 레지스터를 1 비트 이동하려면 몇 개의 IBM 360이 필요합니까?
A : 33. 32는 비트를 제자리에 고정하고 1은 레지스터를 이동합니다. (또는 그런 ...)
빠른 내부 복사를 위해 소스 및 대상과 동일한 어레이를 사용할 수 있습니다.
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;
}
다음과 같이 할 수 있습니다.
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
나는 이것이 오래된 질문이라는 것을 알고 있지만 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;
}
이 시도! 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]이됩니다.
메모리를 소유하고 있다면 안전하지 않은 코드 와 좋은 구식 포인터 사용을 고려할 수 있습니다.
자신을 메모리 스트림으로 만들고 잠 그거나 Marshal.AllocHGlobal시작과 끝에 약간의 패딩을 사용하여 모든 배열을 구성하십시오. 모든 배열 포인터를 한 번에 늘리거나 줄입니다. 여전히 루프백하고 null을 설정해야합니다.
배열을 선택적으로 늘리거나 줄이려면 배열 사이에 패딩을 추가해야합니다.
배열은 매우 낮은 수준의 데이터 구조이며, 낮은 수준의 방식으로 처리하면 큰 성능을 얻을 수 있습니다.
이를 수행하는 baytrail은 모든 복사 8 Core Intel Xeon E5450 @ 3.00GHz로 Jason을 능가 할 수 있습니다.
이 코드를 테스트하지는 않았지만 모든 값을 오른쪽으로 하나씩 이동해야합니다. 마지막 세 줄의 코드는 배열을 효율적으로 이동하는 데 필요한 전부입니다.
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;
배열 복사는 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)
특정 문제를 구현하기 전에 문제 에 대한 모든 다른 종류 의 솔루션 을 생각하는 것이 도움 이 될 수 있으며, 아마도 이것이이 예제가 보여줄 수있는 가장 중요한 것일 수 있습니다.
도움이 되었기를 바랍니다!
부정확하고 약간 재미있는 답변 (감사합니다, 밤새도록 여기있을 게요!)
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);
그러나 다른 옵션보다 빠르지는 않습니다.
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;
}
}
}
The best and most efficient method I believe is using Buffer.BlockCopy function. You will set both source and destination to your array, the offset of the source is 1. Depending on your array type (I assume it is int), 1 int = 4 bytes, so you must pass in 4 as the second parameter of this function. Note that the offset is byte offset.
So it looks like this:
int bytes2copy = yourArray.length - 4;
Buffer.BlockCopy(yourArray, 4, yourArray, 0, bytes2copy);
yourArray[yourArray.length-1] = null;
See C# code below to remove space from string. That shift character in array. Performance is O(n). No other array is used. So no extra memory either.
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();
}
ReferenceURL : https://stackoverflow.com/questions/2381245/c-sharp-quickest-way-to-shift-array
'programing' 카테고리의 다른 글
| 보기에 Android 스케일 애니메이션 (0) | 2021.01.16 |
|---|---|
| Android-애니메이션을 사용하여 왼쪽 여백 변경 (0) | 2021.01.16 |
| Ubuntu에 설치된 OpenCV 버전 찾기 (0) | 2021.01.16 |
| 배열에서 모든 거짓 값 제거 (0) | 2021.01.16 |
| PostgreSQL을 설치할 수 없음 : Windows XP에서 Microsoft VC ++ 런타임 설치 프로그램을 실행하는 동안 오류가 발생했습니다. (0) | 2021.01.16 |