Changeset 12580


Ignore:
Timestamp:
07/03/15 12:55:28 (4 years ago)
Author:
mkommend
Message:

#2411: Improved performance of FastNonDominantSort by using different data structures, avoiding LINQ and caching of dictionary entries.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

    r12144 r12580  
    6868    public override IOperation Apply() {
    6969      bool dominateOnEqualQualities = DominateOnEqualQualitiesParameter.ActualValue.Value;
    70       BoolArray maximization = MaximizationParameter.ActualValue;
    71       ItemArray<DoubleArray> qualities = QualitiesParameter.ActualValue;
     70      bool[] maximization = MaximizationParameter.ActualValue.ToArray();
     71      double[][] qualities = QualitiesParameter.ActualValue.Select(x => x.ToArray()).ToArray();
    7272      if (qualities == null) throw new InvalidOperationException(Name + ": No qualities found.");
    7373
     
    8282      for (int pI = 0; pI < populationSize - 1; pI++) {
    8383        IScope p = scope.SubScopes[pI];
    84         if (!dominatedScopes.ContainsKey(p))
    85           dominatedScopes[p] = new List<int>();
     84        List<int> dominatedScopesByp;
     85        if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
     86          dominatedScopes[p] = dominatedScopesByp = new List<int>();
    8687        for (int qI = pI + 1; qI < populationSize; qI++) {
    8788          DominationResult test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
    8889          if (test == DominationResult.Dominates) {
    89             dominatedScopes[p].Add(qI);
     90            dominatedScopesByp.Add(qI);
    9091            dominationCounter[qI] += 1;
    9192          } else if (test == DominationResult.IsDominated) {
     
    111112        ScopeList nextFront = new ScopeList();
    112113        foreach (IScope p in fronts[i]) {
    113           if (dominatedScopes.ContainsKey(p)) {
    114             for (int k = 0; k < dominatedScopes[p].Count; k++) {
    115               int dominatedScope = dominatedScopes[p][k];
     114          List<int> dominatedScopesByp;
     115          if (dominatedScopes.TryGetValue(p, out dominatedScopesByp)) {
     116            for (int k = 0; k < dominatedScopesByp.Count; k++) {
     117              int dominatedScope = dominatedScopesByp[k];
    116118              dominationCounter[dominatedScope] -= 1;
    117119              if (dominationCounter[dominatedScope] == 0) {
     
    140142    }
    141143
    142     private static DominationResult Dominates(DoubleArray left, DoubleArray right, BoolArray maximizations, bool dominateOnEqualQualities) {
    143       if (dominateOnEqualQualities && left.SequenceEqual(right)) return DominationResult.Dominates;
     144    private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
     145      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
     146      if (dominateOnEqualQualities) {
     147        var equal = true;
     148        for (int i = 0; i < left.Length; i++) {
     149          if (left[i] != right[i]) {
     150            equal = false;
     151            break;
     152          }
     153        }
     154        if (equal) return DominationResult.Dominates;
     155      }
    144156
    145157      bool leftIsBetter = false, rightIsBetter = false;
Note: See TracChangeset for help on using the changeset viewer.