Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15511 for branches


Ignore:
Timestamp:
12/11/17 23:06:32 (6 years ago)
Author:
abeham
Message:

#1614: Improved performance by switching from Dictionary to Array

Location:
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs

    r15510 r15511  
    9090      var slack = evaluation.Slack.ToArray();
    9191
    92       foreach (var kvp in move.NewAssignments) {
    93         int equip = kvp.Key;
    94         int newLoc = kvp.Value;
     92      foreach (var equip in move.Indices) {
     93        int newLoc = move.Reassignments[equip] - 1; // locations are given 1-based
    9594        int oldLoc = assignment[equip];
    9695        var equipDemand = problemInstance.Demands[equip];
    … …  
    9897        installationCosts += problemInstance.InstallationCosts[equip, newLoc];
    9998        for (int j = 0; j < assignment.Length; j++) {
    100           if (!move.NewAssignments.ContainsKey(j)) {
     99          var reassignedLoc = move.Reassignments[j] - 1; // 0 indicates that this equipment is not reassigned
     100          if (reassignedLoc < 0) {
    101101            flowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, assignment[j]];
    102102            flowCosts -= problemInstance.Weights[equip, j] * problemInstance.Distances[oldLoc, assignment[j]];
    … …  
    104104            flowCosts -= problemInstance.Weights[j, equip] * problemInstance.Distances[assignment[j], oldLoc];
    105105          } else {
    106             flowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, move.NewAssignments[j]];
     106            flowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, reassignedLoc];
    107107            flowCosts -= problemInstance.Weights[equip, j] * problemInstance.Distances[oldLoc, assignment[j]];
    108108          }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMove.cs

    r15504 r15511  
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
     23using System.Linq;
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
    26 using HeuristicLab.Encodings.IntegerVectorEncoding;
    2726using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2827
    … …  
    3231  public class NMove : Item {
    3332    [Storable]
    34     public Dictionary<int, int> NewAssignments { get; private set; }
     33    private int[] reassignments;
     34    /// <summary>
     35    /// Contains for each equipment the newly assigned location.
     36    /// </summary>
     37    /// <remarks>
     38    /// Locations are 1-based. A 0 indicates that this equipment is not reassigned.
     39    /// </remarks>
     40    public IReadOnlyList<int> Reassignments {
     41      get { return reassignments; }
     42    }
    3543    [Storable]
    36     public IntegerVector OriginalVector { get; private set; }
     44    private List<int> indices;
     45    /// <summary>
     46    /// Which indices (=equipments) are reassigned.
     47    /// </summary>
     48    /// <remarks>
     49    /// Equipments are 0-based.
     50    /// </remarks>
     51    public IReadOnlyList<int> Indices {
     52      get { return indices; }
     53    }
    3754
    38     public int N { get { return NewAssignments.Count; } }
     55    public int N { get { return Indices.Count; } }
    3956
    4057    [StorableConstructor]
    … …  
    4259    protected NMove(NMove original, Cloner cloner)
    4360      : base(original, cloner) {
    44       NewAssignments = new Dictionary<int, int>(original.NewAssignments);
    45       if (original.OriginalVector != null)
    46         OriginalVector = cloner.Clone(original.OriginalVector);
     61      reassignments = original.reassignments.ToArray();
     62      indices = original.indices.ToList();
    4763    }
    48     public NMove() : this(new int[0], new int[0], null) { }
    49     public NMove(int[] equipments, int[] locations) : this(equipments, locations, null) { }
    50     public NMove(int[] equipments, int[] locations, IntegerVector originalVector)
     64    public NMove(int[] reassignments, List<int> indices)
    5165      : base() {
    52       if (equipments == null) throw new ArgumentNullException("equipments", "NMove: Equipments must not be null.");
    53       if (locations == null) throw new ArgumentNullException("locations", "NMove: Locations must not be null.");
    54       if (equipments.Length != locations.Length) throw new ArgumentException("NMove: Length of equipments and locations is not identical.");
    55       NewAssignments = new Dictionary<int, int>();
    56       for (int i = 0; i < equipments.Length; i++)
    57         NewAssignments[equipments[i]] = locations[i];
    58       OriginalVector = originalVector;
     66      this.reassignments = reassignments;
     67      this.indices = indices;
    5968    }
    6069

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMoveAbsoluteAttribute.cs

    r15504 r15511  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using HeuristicLab.Common;
    … …  
    3233
    3334    [Storable]
    34     public Dictionary<int, int> OldAssignments { get; private set; }
     35    public List<Tuple<int, int>> OldAssignments { get; private set; }
    3536    [Storable]
    3637    public double MoveQuality { get; private set; }
    … …  
    4142    public NMoveAbsoluteTabuAttribute(NMove move, IntegerVector assignment, double moveQuality)
    4243      : base() {
    43       OldAssignments = new Dictionary<int, int>();
    44       foreach (var kvp in move.NewAssignments)
    45         OldAssignments.Add(kvp.Key, assignment[kvp.Key]);
     44      OldAssignments = new List<Tuple<int, int>>(move.N);
     45      foreach (var equip in move.Indices)
     46        OldAssignments.Add(Tuple.Create(equip, assignment[equip]));
    4647      MoveQuality = moveQuality;
    4748    }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMoveMaker.cs

    r15504 r15511  
    7171
    7272    public static void Apply(IntegerVector vector, NMove move) {
    73       foreach (var kvp in move.NewAssignments)
    74         vector[kvp.Key] = kvp.Value;
     73      for (var i = 0; i < move.N; i++) {
     74        var equip = move.Indices[i];
     75        vector[equip] = move.Reassignments[equip] - 1; // location is given 1-based in reassignments
     76      }
    7577    }
    7678

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMoveTabuChecker.cs

    r15504 r15511  
    111111          isTabu = true;
    112112          foreach (var kvp in attribute.OldAssignments) {
    113             if (move.NewAssignments.ContainsKey(kvp.Key)) {
    114               if (move.NewAssignments[kvp.Key] != kvp.Value) {
    115                 isTabu = false;
    116                 break;
    117               }
     113            var assignedLoc = move.Reassignments[kvp.Item1] - 1; // location is given 1-based
     114            if (assignedLoc >= 0 && assignedLoc != kvp.Item2) {
     115              isTabu = false;
     116              break;
    118117            }
    119118          }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs

    r15504 r15511  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
     24using System.Linq;
    2325using HeuristicLab.Common;
    2426using HeuristicLab.Core;
    … …  
    2830using HeuristicLab.Parameters;
    2931using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     32using HeuristicLab.Random;
    3033
    3134namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
    … …  
    5558
    5659    public static NMove GenerateExactlyN(IRandom random, IntegerVector assignment, int n, DoubleArray capacities) {
    57       int[] equipments = new int[n], locations = new int[n];
    58       HashSet<int> chosenEquipments = new HashSet<int>();
    59       for (int i = 0; i < n; i++) {
     60      if (capacities.Length <= 1) throw new ArgumentException("There must be at least two locations.");
     61      var dim = assignment.Length;
     62      var reassignment = new int[dim];
     63      var equipments = Enumerable.Range(0, dim).SampleRandomWithoutRepetition(random, n, dim).ToList();
     64      for (var i = 0; i < n; i++) {
     65        var equip = equipments[i];
    6066        do {
    61           equipments[i] = random.Next(assignment.Length);
    62         } while (chosenEquipments.Contains(equipments[i]));
    63         chosenEquipments.Add(equipments[i]);
    64         do {
    65           locations[i] = random.Next(capacities.Length);
    66         } while (locations[i] == assignment[equipments[i]]);
     67          reassignment[equip] = random.Next(capacities.Length) + 1;
     68        } while (reassignment[equip] == assignment[equip] + 1);
    6769      }
    68       return new NMove(equipments, locations);
     70      return new NMove(reassignment, equipments);
    6971    }
    7072

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

    r15507 r15511  
    126126         
    127127          var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
    128           evaluations += move.NewAssignments.Count * deltaEvaluationFactor;
     128          evaluations += move.Indices.Count * deltaEvaluationFactor;
    129129          double moveQuality = problemInstance.ToSingleObjective(moveEval);
    130130
Note: See TracChangeset for help on using the changeset viewer.