Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14650


Ignore:
Timestamp:
02/07/17 14:05:09 (8 years ago)
Author:
epitzer
Message:

#2727 completely replace basic array with array mapped trie in ValueTypeArray and descendants

Location:
branches/PersistentDataStructures
Files:
6 added
12 edited

Legend:

Unmodified
Added
Removed

  • branches/PersistentDataStructures/HeuristicLab.Data/3.3/HeuristicLab.Data-3.3.csproj

    r13979 r14650  
    146146    <Compile Include="Interfaces\IStringConvertibleMatrix.cs" />
    147147    <Compile Include="Interfaces\IStringConvertibleValue.cs" />
     148    <Compile Include="PersistentDataStructures\Adaptations\HistoryArray.cs" />
     149    <Compile Include="PersistentDataStructures\Adaptations\HistoryList.cs" />
     150    <Compile Include="PersistentDataStructures\Implementations\ArrayMappedTrie.cs" />
    148151    <Compile Include="Plugin.cs" />
    149152    <Compile Include="Properties\AssemblyInfo.cs" />

  • branches/PersistentDataStructures/HeuristicLab.Data/3.3/PercentArray.cs

    r14186 r14650  
    4545      StringBuilder sb = new StringBuilder();
    4646      sb.Append("[");
    47       if (array.Length > 0) {
    48         sb.Append(array[0].ToString("#0.#################### %"));  // percent format
    49         for (int i = 1; i < array.Length; i++)
    50           sb.Append(";").Append(array[i].ToString("#0.#################### %"));  // percent format
     47      if (historyArray.Length > 0) {
     48        sb.Append(historyArray[0].ToString("#0.#################### %"));  // percent format
     49        for (int i = 1; i < historyArray.Length; i++)
     50          sb.Append(";").Append(historyArray[i].ToString("#0.#################### %"));  // percent format
    5151      }
    5252      sb.Append("]");

  • branches/PersistentDataStructures/HeuristicLab.Data/3.3/ValueTypeArray.cs

    r14186 r14650  
    2828using HeuristicLab.Common;
    2929using HeuristicLab.Core;
     30using HeuristicLab.Data.PersistentDataStructures.Adaptations;
    3031using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3132
    … …  
    4041    }
    4142
    42     [Storable]
    43     protected T[] array;
     43    [Storable(AllowOneWay = true, Name = "array")]
     44    protected T[] oldArrayValuePersistence { set { historyArray = new HistoryArray<T>(value); } }
     45
     46    [Storable]
     47    protected HistoryArray<T> historyArray;
    4448
    4549    [Storable]
    … …  
    6064
    6165    public virtual int Length {
    62       get { return array.Length; }
     66      get { return historyArray.Length; }
    6367      #region Mono Compatibility
    6468      // this setter should be protected, but the Mono compiler couldn't handle it
    … …  
    6670        if (ReadOnly) throw new NotSupportedException("Length cannot be set. ValueTypeArray is read-only.");
    6771        if (value != Length) {
    68           Array.Resize<T>(ref array, value);
     72          historyArray.Resize(value);
    6973          while (elementNames.Count > value)
    7074            elementNames.RemoveAt(elementNames.Count - 1);
    … …  
    9094
    9195    public virtual T this[int index] {
    92       get { return array[index]; }
     96      get { return historyArray[index]; }
    9397      set {
    9498        if (ReadOnly) throw new NotSupportedException("Item cannot be set. ValueTypeArray is read-only.");
    95         if (!value.Equals(array[index])) {
    96           array[index] = value;
     99        if (!value.Equals(historyArray[index])) {
     100          historyArray[index] = value;
    97101          OnItemChanged(index);
    98102        }
    … …  
    115119    protected ValueTypeArray(ValueTypeArray<T> original, Cloner cloner)
    116120      : base(original, cloner) {
    117       this.array = (T[])original.array.Clone();
     121      this.historyArray = (HistoryArray<T>)original.historyArray.Clone();
    118122      this.readOnly = original.readOnly;
    119123      this.resizable = original.resizable;
    … …  
    121125    }
    122126    protected ValueTypeArray() {
    123       array = new T[0];
     127      historyArray = new HistoryArray<T>(0);
    124128      readOnly = false;
    125129      resizable = true;
    … …  
    127131    }
    128132    protected ValueTypeArray(int length) {
    129       array = new T[length];
     133      historyArray = new HistoryArray<T>(length);
    130134      readOnly = false;
    131135      resizable = true;
    … …  
    134138    protected ValueTypeArray(T[] elements) {
    135139      if (elements == null) throw new ArgumentNullException();
    136       array = (T[])elements.Clone();
     140      historyArray = new HistoryArray<T>(elements);
    137141      readOnly = false;
    138142      resizable = true;
    … …  
    147151
    148152    public T[] CloneAsArray() {
    149       //mkommend: this works because T must be a value type (struct constraint);
    150       return (T[])array.Clone();
     153      return historyArray.ToArray();
    151154    }
    152155
    153156    public override string ToString() {
    154       if (array.Length == 0) return "[]";
     157      if (historyArray.Length == 0) return "[]";
    155158
    156159      StringBuilder sb = new StringBuilder();
    157160      sb.Append("[");
    158       sb.Append(array[0].ToString());
    159       for (int i = 1; i < array.Length; i++) {
    160         sb.Append(";").Append(array[i].ToString());
     161      sb.Append(historyArray[0].ToString());
     162      for (int i = 1; i < historyArray.Length; i++) {
     163        sb.Append(";").Append(historyArray[i].ToString());
    161164        if (sb.Length > maximumToStringLength) {
    162165          sb.Append("...");
    … …  
    169172
    170173    public virtual IEnumerator<T> GetEnumerator() {
    171       return array.Cast<T>().GetEnumerator();
     174      return historyArray.Cast<T>().GetEnumerator();
    172175    }
    173176

  • branches/PersistentDataStructures/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/BinaryVector.cs

    r14186 r14650  
    4141    public BinaryVector(BoolArray elements)
    4242      : this(elements.Length) {
    43       for (int i = 0; i < array.Length; i++)
    44         array[i] = elements[i];
     43      for (int i = 0; i < historyArray.Length; i++)
     44        historyArray[i] = elements[i];
    4545    }
    4646
    … …  
    5252      if (length > 0) {
    5353        for (int i = 0; i < length; i++)
    54           array[startIndex + i] = random.Next(2) == 0;
     54          historyArray[startIndex + i] = random.Next(2) == 0;
    5555        OnReset();
    5656      }

  • branches/PersistentDataStructures/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/IntegerVector.cs

    r14186 r14650  
    4242    public IntegerVector(IntArray elements)
    4343      : this(elements.Length) {
    44       for (int i = 0; i < array.Length; i++)
    45         array[i] = elements[i];
     44      for (int i = 0; i < historyArray.Length; i++)
     45        historyArray[i] = elements[i];
    4646    }
    4747
    … …  
    5454        int numbers = (int)Math.Floor((max - min) / (double)step);
    5555        for (int i = startIndex; i < startIndex + length; i++) {
    56           array[i] = random.Next(numbers) * step + min;
     56          historyArray[i] = random.Next(numbers) * step + min;
    5757        }
    5858        OnReset();
    … …  
    6565          if (bounds.Columns > 2) step = bounds[i % bounds.Rows, 2];
    6666          int numbers = (int)Math.Floor((max - min) / (double)step);
    67           array[i] = random.Next(numbers) * step + min;
     67          historyArray[i] = random.Next(numbers) * step + min;
    6868        }
    6969        OnReset();

  • branches/PersistentDataStructures/HeuristicLab.Encodings.LinearLinkageEncoding/3.3/LinearLinkage.cs

    r14186 r14650  
    5454    /// <returns>An enumeration of all groups.</returns>
    5555    public IEnumerable<List<int>> GetGroups() {
    56       var len = array.Length;
     56      var len = historyArray.Length;
    5757      var remaining = new HashSet<int>(Enumerable.Range(0, len));
    5858      // iterate from lowest to highest index
    … …  
    6161        var group = new List<int> { i };
    6262        remaining.Remove(i);
    63         var next = array[i];
     63        var next = historyArray[i];
    6464        if (next != i) {
    6565          int prev;
    … …  
    6969              throw new ArgumentException("Array is malformed and does not represent a valid LLE forward encoding.");
    7070            prev = next;
    71             next = array[next];
     71            next = historyArray[next];
    7272          } while (next != prev);
    7373        }
    … …  
    104104    public IEnumerable<int> GetGroupForward(int index) {
    105105      yield return index;
    106       var next = array[index];
     106      var next = historyArray[index];
    107107      if (next == index) yield break;
    108108      int prev;
    … …  
    110110        yield return next;
    111111        prev = next;
    112         next = array[next];
     112        next = historyArray[next];
    113113      } while (next != prev);
    114114    }
    … …  
    130130    public IEnumerable<int> GetGroupBackward(int index) {
    131131      yield return index;
    132       var next = array[index];
     132      var next = historyArray[index];
    133133      // return preceding elements in group
    134134      for (var prev = index - 1; prev >= 0; prev--) {
    135         if (array[prev] != next) continue;
     135        if (historyArray[prev] != next) continue;
    136136        next = prev;
    137137        yield return next;
    … …  
    150150    /// be part of exactly one group.</param>
    151151    public void SetGroups(IEnumerable<IEnumerable<int>> grouping) {
    152       var len = array.Length;
     152      var len = historyArray.Length;
    153153      var remaining = new HashSet<int>(Enumerable.Range(0, len));
    154154      foreach (var group in grouping) {
    155155        var prev = -1;
    156156        foreach (var g in group.OrderBy(x => x)) {
    157           if (prev >= 0) array[prev] = g;
     157          if (prev >= 0) historyArray[prev] = g;
    158158          prev = g;
    159159          if (!remaining.Remove(prev))
    160160            throw new ArgumentException(string.Format("Element {0} is contained at least twice.", prev), "grouping");
    161161        }
    162         if (prev >= 0) array[prev] = prev;
     162        if (prev >= 0) historyArray[prev] = prev;
    163163      }
    164164      if (remaining.Count > 0)
    … …  
    175175    /// <returns>True if the encoding is valid.</returns>
    176176    public bool Validate() {
    177       var len = array.Length;
     177      var len = historyArray.Length;
    178178      var remaining = new HashSet<int>(Enumerable.Range(0, len));
    179179      for (var i = 0; i < len; i++) {
    180180        if (!remaining.Contains(i)) continue;
    181181        remaining.Remove(i);
    182         var next = array[i];
     182        var next = historyArray[i];
    183183        if (next == i) continue;
    184184        int prev;
    … …  
    186186          if (!remaining.Remove(next)) return false;
    187187          prev = next;
    188           next = array[next];
     188          next = historyArray[next];
    189189        } while (next != prev);
    190190      }
    … …  
    216216    public void LinearizeTreeStructures() {
    217217      // Step 1: Convert the array into LLE-e
    218       ToLLEeInplace(array);
     218      ToLLEeInplace(historyArray.ToArray());
    219219      // Step 2: For all groups linearize the links
    220       FromLLEe(array);
     220      FromLLEe(historyArray.ToArray());
    221221    }
    222222
    … …  
    234234    /// <returns>An integer array in LLE-e representation</returns>
    235235    public int[] ToLLEe() {
    236       var result = (int[])array.Clone();
     236      var result = (int[])historyArray.Clone();
    237237      ToLLEeInplace(result);
    238238      return result;
    … …  
    242242      var length = a.Length;
    243243      for (var i = length - 1; i >= 0; i--) {
    244         if (array[i] == i) a[i] = i;
     244        if (historyArray[i] == i) a[i] = i;
    245245        else a[i] = a[a[i]];
    246246      }
    … …  
    257257    /// <param name="llee">The LLE-e representation</param>
    258258    public void FromLLEe(int[] llee) {
    259       var length = array.Length;
     259      var length = historyArray.Length;
    260260      var groups = new Dictionary<int, int>();
    261261      for (var i = length - 1; i >= 0; i--) {
    262262        if (llee[i] == i) {
    263           array[i] = i;
     263          historyArray[i] = i;
    264264          groups[i] = i;
    265265        } else {
    266266          var g = llee[i];
    267           array[i] = groups[g];
     267          historyArray[i] = groups[g];
    268268          groups[g] = i;
    269269        }

  • branches/PersistentDataStructures/HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs

    r14186 r14650  
    7171    public Permutation(PermutationTypes type, IntArray elements)
    7272      : this(type, elements.Length) {
    73       for (int i = 0; i < array.Length; i++)
    74         array[i] = elements[i];
     73      for (int i = 0; i < historyArray.Length; i++)
     74        historyArray[i] = elements[i];
    7575    }
    7676
    … …  
    103103          index2 = startIndex + random.Next(i + 1);
    104104          if (index1 != index2) {
    105             val = array[index1];
    106             array[index1] = array[index2];
    107             array[index2] = val;
     105            val = historyArray[index1];
     106            historyArray[index1] = historyArray[index2];
     107            historyArray[index2] = val;
    108108          }
    109109        }

  • branches/PersistentDataStructures/HeuristicLab.Encodings.RealVectorEncoding/3.3/RealVector.cs

    r14186 r14650  
    4141    public RealVector(DoubleArray elements)
    4242      : this(elements.Length) {
    43       for (int i = 0; i < array.Length; i++)
    44         array[i] = elements[i];
     43      for (int i = 0; i < historyArray.Length; i++)
     44        historyArray[i] = elements[i];
    4545    }
    4646
    … …  
    5353      if (length > 0) {
    5454        for (int i = 0; i < length; i++)
    55           array[startIndex + i] = min + delta * random.NextDouble();
     55          historyArray[startIndex + i] = min + delta * random.NextDouble();
    5656        OnReset();
    5757      }
    … …  
    6363          double min = bounds[i % bounds.Rows, 0];
    6464          double max = bounds[i % bounds.Rows, 1];
    65           array[i] = min + (max - min) * random.NextDouble();
     65          historyArray[i] = min + (max - min) * random.NextDouble();
    6666        }
    6767        OnReset();

  • branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Alba/AlbaEncoding.cs

    r14186 r14650  
    4040
    4141      Tour tour = new Tour();
    42       for (int i = 0; i < this.array.Length; i++) {
    43         if (this.array[i] >= cities) {
     42      for (int i = 0; i < this.historyArray.Length; i++) {
     43        if (this.historyArray[i] >= cities) {
    4444          if (tour.Stops.Count > 0) {
    4545            result.Add(tour);
    … …  
    4848          }
    4949        } else {
    50           tour.Stops.Add(this.array[i] + 1);
     50          tour.Stops.Add(this.historyArray[i] + 1);
    5151        }
    5252      }
    … …  
    7272
    7373        while (vehicleAssignment == -1) {
    74           if (this.array[i] >= ProblemInstance.Cities.Value) {
    75             vehicleAssignment = this.array[i] - ProblemInstance.Cities.Value;
     74          if (this.historyArray[i] >= ProblemInstance.Cities.Value) {
     75            vehicleAssignment = this.historyArray[i] - ProblemInstance.Cities.Value;
    7676          }
    7777

  • branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/General/PermutationEncoding.cs

    r14186 r14650  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
     26using HeuristicLab.Data.PersistentDataStructures.Adaptations;
    2627using HeuristicLab.Encodings.PermutationEncoding;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    … …  
    6970    public PermutationEncoding(Permutation permutation, IVRPProblemInstance problemInstance)
    7071      : base(PermutationTypes.RelativeUndirected) {
    71       this.array = new int[permutation.Length];
    72       for (int i = 0; i < array.Length; i++)
    73         this.array[i] = permutation[i];
     72      this.historyArray = new HistoryArray<int>(permutation.Length);
     73      for (int i = 0; i < historyArray.Length; i++)
     74        this.historyArray[i] = permutation[i];
    7475
    7576      this.ProblemInstance = problemInstance;
    … …  
    8283
    8384    public int IndexOf(int city) {
    84       return Array.IndexOf(this.array, city);
     85      return historyArray.IndexOf(city);
    8586    }
    8687  }

  • branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Prins/PrinsEncoding.cs

    r14186 r14650  
    102102
    103103        //find predecessor / successor in permutation
    104         int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0] - 1) - 1;
     104        int predecessorIndex = historyArray.IndexOf(tour.Stops[0] - 1) - 1;
    105105        if (predecessorIndex >= 0) {
    106106          int predecessor = this[predecessorIndex] + 1;
    … …  
    114114          }
    115115        } else {
    116           int successorIndex = Array.IndexOf(this.array,
     116          int successorIndex = historyArray.IndexOf(
    117117            tour.Stops[tour.Stops.Count - 1] - 1) + 1;
    118118          int successor = this[successorIndex] + 1;

  • branches/PersistentDataStructures/HeuristicLab.Problems.VehicleRouting/3.4/Encodings/Zhu/ZhuEncoding.cs

    r14186 r14650  
    6363
    6464        //find predecessor / successor in permutation
    65         int predecessorIndex = Array.IndexOf(this.array, tour.Stops[0] - 1) - 1;
     65        int predecessorIndex = historyArray.IndexOf(tour.Stops[0] - 1) - 1;
    6666        if (predecessorIndex >= 0) {
    6767          int predecessor = this[predecessorIndex] + 1;
    … …  
    7575          }
    7676        } else {
    77           int successorIndex = Array.IndexOf(this.array,
     77          int successorIndex = historyArray.IndexOf(
    7878            tour.Stops[tour.Stops.Count - 1] - 1) + 1;
    7979          int successor = this[successorIndex] + 1;
Note: See TracChangeset for help on using the changeset viewer.