C#에서 int64 인덱스를 사용하여 배열의 일부를 정렬하는 방법은 무엇입니까?
문제
.Net 프레임워크에는 정렬 작업의 시작 및 끝 인덱스를 지정할 수 있는 Array.Sort 오버로드가 있습니다.그러나 이러한 매개변수는 32비트에 불과합니다.따라서 정렬 범위를 설명하는 표시가 64비트 숫자를 사용해서만 지정할 수 있는 경우 큰 배열의 일부를 정렬하는 방법이 없습니다.프레임워크의 정렬 구현을 복사하고 수정할 수 있다고 생각하지만 이는 이상적이지 않습니다.
업데이트:
저는 이러한 문제와 기타 대규모 배열 문제를 해결하는 데 도움이 되는 두 가지 클래스를 만들었습니다.또 다른 문제는 메모리 제한에 도달하기 오래 전에 OutOfMemoryException이 발생하기 시작한다는 것입니다.요청한 메모리가 사용 가능하지만 연속적이지 않기 때문이라고 가정합니다.그래서 이를 위해 일반적이고 동적으로 크기를 조정할 수 있는 배열 목록인 BigArray 클래스를 만들었습니다.프레임워크의 일반 목록 클래스보다 메모리 공간이 더 작으며 전체 배열이 연속적일 필요가 없습니다.성능 저하를 테스트하지는 않았지만 거기에 있다고 확신합니다.
public class BigArray<T> : IEnumerable<T>
{
private long capacity;
private int itemsPerBlock;
private int shift;
private List<T[]> blocks = new List<T[]>();
public BigArray(int itemsPerBlock)
{
shift = (int)Math.Ceiling(Math.Log(itemsPerBlock) / Math.Log(2));
this.itemsPerBlock = 1 << shift;
}
public long Capacity
{
get
{
return capacity;
}
set
{
var requiredBlockCount = (value - 1) / itemsPerBlock + 1;
while (blocks.Count > requiredBlockCount)
{
blocks.RemoveAt(blocks.Count - 1);
}
while (blocks.Count < requiredBlockCount)
{
blocks.Add(new T[itemsPerBlock]);
}
capacity = (long)itemsPerBlock * blocks.Count;
}
}
public T this[long index]
{
get
{
Debug.Assert(index < capacity);
var blockNumber = (int)(index >> shift);
var itemNumber = index & (itemsPerBlock - 1);
return blocks[blockNumber][itemNumber];
}
set
{
Debug.Assert(index < capacity);
var blockNumber = (int)(index >> shift);
var itemNumber = index & (itemsPerBlock - 1);
blocks[blockNumber][itemNumber] = value;
}
}
public IEnumerator<T> GetEnumerator()
{
for (long i = 0; i < capacity; i++)
{
yield return this[i];
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
그리고 정렬이라는 원래 문제로 돌아가서...나에게 정말로 필요한 것은 배열의 각 요소에 대해 순서대로 작업을 수행하는 방법이었습니다.그러나 이렇게 큰 배열을 사용하면 데이터를 복사하고, 정렬하고, 그에 따라 작업을 수행한 다음 정렬된 복사본을 삭제하는 것이 불가능합니다(원래 순서가 유지되어야 함).그래서 정렬되지 않은 배열의 각 요소에 대해 정렬된 순서로 임의의 작업을 수행할 수 있는 정적 클래스 OrderedOperation을 만들었습니다.그리고 낮은 메모리 공간으로 그렇게 합니다(여기서 실행 시간에 대한 메모리 거래).
public static class OrderedOperation
{
public delegate void WorkerDelegate(int index, float progress);
public static void Process(WorkerDelegate worker, IEnumerable<int> items, int count, int maxItem, int maxChunkSize)
{
// create a histogram such that a single bin is never bigger than a chunk
int binCount = 1000;
int[] bins;
double binScale;
bool ok;
do
{
ok = true;
bins = new int[binCount];
binScale = (double)(binCount - 1) / maxItem;
int i = 0;
foreach (int item in items)
{
bins[(int)(binScale * item)]++;
if (++i == count)
{
break;
}
}
for (int b = 0; b < binCount; b++)
{
if (bins[b] > maxChunkSize)
{
ok = false;
binCount *= 2;
break;
}
}
} while (!ok);
var chunkData = new int[maxChunkSize];
var chunkIndex = new int[maxChunkSize];
var done = new System.Collections.BitArray(count);
var processed = 0;
var binsCompleted = 0;
while (binsCompleted < binCount)
{
var chunkMax = 0;
var sum = 0;
do
{
sum += bins[binsCompleted];
binsCompleted++;
} while (binsCompleted < binCount - 1 && sum + bins[binsCompleted] <= maxChunkSize);
Debug.Assert(sum <= maxChunkSize);
chunkMax = (int)Math.Ceiling((double)binsCompleted / binScale);
var chunkCount = 0;
int i = 0;
foreach (int item in items)
{
if (item < chunkMax && !done[i])
{
chunkData[chunkCount] = item;
chunkIndex[chunkCount] = i;
chunkCount++;
done[i] = true;
}
if (++i == count)
{
break;
}
}
Debug.Assert(sum == chunkCount);
Array.Sort(chunkData, chunkIndex, 0, chunkCount);
for (i = 0; i < chunkCount; i++)
{
worker(chunkIndex[i], (float)processed / count);
processed++;
}
}
Debug.Assert(processed == count);
}
}
두 클래스는 함께 작동할 수 있지만(저는 그렇게 사용합니다) 반드시 그럴 필요는 없습니다.다른 사람이 유용하다고 생각하기를 바랍니다.하지만 인정하겠습니다. 그들은 비주류 사례 수업입니다.질문을 환영합니다.그리고 내 코드가 형편없다면 팁도 듣고 싶습니다.
마지막 생각:OrderedOperation에서 볼 수 있듯이 저는 long이 아닌 int를 사용하고 있습니다.현재 내가 가졌던 원래 질문에도 불구하고 그것은 나에게 충분합니다(당신이 알 수 없는 경우를 대비해 신청서는 유동적입니다).그러나 필요한 경우 클래스는 긴 시간도 처리할 수 있어야 합니다.
해결책
64비트 프레임워크에서도 배열의 최대 요소 수는 int.MaxValue
.
가져오거나 반환하는 기존 메서드 Int64
그냥 캐스팅해 long
가치를 Int32
내부적으로 매개변수의 경우 ArgumentOutOfRangeException
만약 long
매개변수가 사이에 있지 않습니다. int.MinValue
그리고 int.MaxValue
.
예를 들어 LongLength
다음을 반환하는 속성 Int64
, 단지 값을 캐스팅하고 반환합니다. Length
재산:
public long LongLength
{
get { return (long)this.Length; } // Length is an Int32
}
그래서 내 제안은 당신을 캐스팅하는 것입니다 Int64
표시 Int32
그런 다음 기존 중 하나에 전화를 겁니다. Sort
과부하.
다른 팁
Array.Copy는 Int64 매개변수를 사용하므로 정렬해야 하는 섹션을 꺼내서 정렬한 다음 다시 넣을 수 있습니다.물론 2^32개 미만의 요소를 정렬한다고 가정합니다.
2^32개 이상의 요소를 정렬하는 경우에는 어쨌든 자신만의 보다 효율적인 정렬 알고리즘을 작성하는 것이 가장 좋습니다.