Как отсортировать часть массива с индексами 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, я использую целые числа, а не длинные.В настоящее время для меня этого достаточно, несмотря на первоначальный вопрос (приложение находится в стадии разработки, если вы не можете сказать).Но класс также должен иметь возможность обрабатывать длинные значения, если возникнет такая необходимость.
Решение
Вы обнаружите, что даже в 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 элементов, то в любом случае было бы лучше написать свой собственный, более эффективный алгоритм сортировки.