C#에서 int64 인덱스를 사용하여 배열의 일부를 정렬하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/850468

문제

.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개 이상의 요소를 정렬하는 경우에는 어쨌든 자신만의 보다 효율적인 정렬 알고리즘을 작성하는 것이 가장 좋습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top