C# - MergeSort, à court de mémoire

Question

J'ai implémenté l'algorithme MergeSort utilisé sur un fichier de 100 000 entiers. Il s'occupe du tri et recueille les inversions qui sont dans le fichier. Cela fonctionne avec de petites baies de test, mais dès que je branche le fichier réel, je n'ai plus d'erreur de mémoire. Comment je le répare? L'erreur se produit au cours de mergesort, et le nombre d'éléments dans mon tableau est aux 12500 Voici mon code:

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

Voici un code pour vous de regarder.

Cela commence par reconnaître que le fichier est déjà une collection d'éléments individuels. Par conséquent, nous pouvons faire le premier regroupement/tri lorsque nous lisons le fichier. Étant donné que les tableaux sont très peu pratique pour cette partie je listes puis jeter le retour à l'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(); 
} 

Avec ce tableau, nous pouvons commencer le reste du groupement/tri

Il utilise récursion mais a une empreinte mémoire minimale:

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); 
} 

dans mes tests, le fichier élément 100000 a été trié en moins d'un quart de seconde, y compris la lecture en mémoire.