C＃ - MergeSort，內存不足

Question

我實現了在100,000個整數文件上使用的MergeSort算法。它負責分類並收集文件中的反轉。它適用於小型測試陣列，但只要插入實際文件，就會發生內存不足錯誤。我如何解決它？ 歸併過程中出現錯誤，在我的輔助的數組元素的個數12500 這裏是我的代碼：

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace Assignment_1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<int> data = File2Array("IntegerArray.txt"); 
      int[] unsorted = data.ToArray(); 
      List<string> inversions = new List<string>(); 
      Sort(ref unsorted, ref inversions); 
      Console.WriteLine("number of inversions is: " + inversions.Count()); 
      Console.ReadLine(); 
     } 

     public static void Sort(ref int[] unsorted, ref List<string>inversions) 
     { 
      int size = unsorted.Length; 
      if (size == 1) 
       return; 
      int mid = size/2; 
      int leftSize = mid; 
      int rightSize = size - leftSize; 
      int[] left = new int[leftSize]; 
      int[] right = new int[rightSize]; 
      Array.Copy(unsorted, 0, left, 0, leftSize); 
      Array.Copy(unsorted, mid, right, 0, rightSize); 
      Sort(ref left, ref inversions); 
      Sort(ref right, ref inversions); 

      int[] aux = new int[leftSize + rightSize]; 
      for (int i = 0, j = 0, k = 0; k < aux.Length; k++) 
      { 
       if (left[i] < right[j]) 
       { 
        aux[k] = left[i++]; 
        // if left array is exhausted, copy the remaining right array elements over 
        if (i == leftSize) 
        { 
         Array.Copy(right, j, aux, ++k, rightSize - j); 
         unsorted = aux; 
         break; 
        } 
       } 
       else 
       { 
        int temp = i; 
        while (temp < leftSize) 
        { 
         inversions.Add(left[temp++] + "-" + right[j]); 
        } 
        aux[k] = right[j++]; 
        if (j == rightSize) 
        { 
         Array.Copy(left, i, aux, ++k, leftSize - i); 
         unsorted = aux; 
         break; 
        } 
       } 
      } 
     } 

     public static List<int> File2Array(string file) 
     { 
      List<int> data = new List<int>(); 
      using (StreamReader reader = new StreamReader(file)) 
      { 
       int line; 
       do 
       { 
        int.TryParse(reader.ReadLine(), out line); 
        data.Add(line); 
       } 
       while (!reader.EndOfStream); 
      } 
      return data; 
     } 
    } 
} 

Answer 1

下面是一些代碼，你看看。

這從認識到該文件已經是單個元素的集合開始。因此，當我們讀取文件時，我們可以進行第一次分組/排序。由於陣列是爲這一部分，我使用的列表，然後非常不切實際轉換返回到int [] []

static int[][] makearrays(string filename) 
{ 
    List<List<int>> outval = new List<List<int>>(); 
    using(StreamReader sr = new StreamReader(filename)) 
    { 
     while(!sr.EndOfStream) 
     { 
      int a = 0, b = 0; 
      a = int.Parse(sr.ReadLine()); 
      if(!sr.EndOfStream) 
       b = int.Parse(sr.ReadLine()); 
      else 
      { 
       outval.Add(new List<int>() { a }); 
       break; 
      } 
      if(a > b) 
       outval.Add(new List<int>() { b, a }); 
      else 
       outval.Add(new List<int>() { a, b }); 

     } 
    } 
    return outval.Select(x => x.ToArray()).ToArray(); 
} 

利用該陣列就可以開始分組的其餘部分/排序

此使用遞歸但有一個最小的內存佔用：

static int[][] dosort(int[][] input) 
{ 
    if(input.Length == 1) 
     return input; 
    int i = 1, m = 0; 
    for(; i < input.Length; i += 2) 
    { 
     int limit = Math.Min(input[i].Length, input[i - 1].Length); 
     int[] temp = new int[input[i].Length + input[i - 1].Length]; 
     int j = 0, k = 0, l = 0; 
     while(j < input[i].Length && k < input[i - 1].Length) 
     { 
      if(input[i][j] < input[i - 1][k]) 
      { 
       temp[l++] = input[i][j++]; 
      } 
      else 
       temp[l++] = input[i - 1][k++]; 
     } 
     while(l < temp.Length) 
     { 
      if(j < input[i].Length) 
       temp[l++] = input[i][j++]; 
      if(k < input[i - 1].Length) 
       temp[l++] = input[i - 1][k++]; 
     } 
     input[m++] = temp; 
    } 
    if(input.Length % 2 == 1) 
     input[m++] = input.Last(); 
    input = input.Take(m).ToArray(); 
    return dosort(input); 
} 

在我的測試中100000元文件中不到四分之一秒的排序，其中包括將其讀入內存中。