Changeset 15125 for trunk/sources

Timestamp:

07/06/17 01:30:45 (7 years ago)

Author:

abeham

Message:

#2634:

• Improved performance slightly by using binary instead of linear search
• Fixed target value ECDFs by removing aggregate option (only drawn for each budget separately)
• Added utility class for calculating ECDFs in HeuristicLab.Common
• Added option to hide labels
• Improved add result methods

Location:

trunk/sources

Files:

• HeuristicLab.Common/3.3/EnumerableStatisticExtensions.cs (deleted)
• HeuristicLab.Common/3.3/HeuristicLab.Common-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Common/3.3/Point2D.cs (modified) (1 diff)
• HeuristicLab.Common/3.3/Statistics (added)
• HeuristicLab.Common/3.3/Statistics/EmpiricalCumulativeDistributionFunction.cs (added)
• HeuristicLab.Common/3.3/Statistics/EnumerableStatisticExtensions.cs (added)
• HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.Designer.cs (modified) (11 diffs)
• HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs (modified) (30 diffs)

trunk/sources/HeuristicLab.Common/3.3/HeuristicLab.Common-3.3.csproj

@@ -131 +131 @@
     <Compile Include="Constants.cs" />
     <Compile Include="ArrayExtensions.cs" />
+    <Compile Include="Statistics\EmpiricalCumulativeDistributionFunction.cs" />
     <Compile Include="ListExtensions.cs" />
     <Compile Include="Point2D.cs" />
@@ -139 +140 @@
     <Compile Include="DeepCloneable.cs" />
     <Compile Include="Content\IContent.cs" />
-    <Compile Include="EnumerableStatisticExtensions.cs" />
+    <Compile Include="Statistics\EnumerableStatisticExtensions.cs" />
     <Compile Include="IDeepCloneable.cs" />
     <Compile Include="Plugin.cs" />

trunk/sources/HeuristicLab.Common/3.3/Point2D.cs

@@ -54 +54 @@
     }
 
+    public static Point2D<T> Create(T x, T y, object tag = null) {
+      return new Point2D<T>(x, y, tag);
+    }
+
     public static bool operator ==(Point2D<T> left, Point2D<T> right) {
       return left.x.Equals(right.x) && left.y.Equals(right.y) && left.tag == right.tag;

trunk/sources/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.Designer.cs

@@ -45 +45 @@
     private void InitializeComponent() {
       this.components = new System.ComponentModel.Container();
-      System.Windows.Forms.DataVisualization.Charting.ChartArea chartArea1 = new System.Windows.Forms.DataVisualization.Charting.ChartArea();
-      System.Windows.Forms.DataVisualization.Charting.Legend legend1 = new System.Windows.Forms.DataVisualization.Charting.Legend();
+      System.Windows.Forms.DataVisualization.Charting.ChartArea chartArea2 = new System.Windows.Forms.DataVisualization.Charting.ChartArea();
+      System.Windows.Forms.DataVisualization.Charting.Legend legend2 = new System.Windows.Forms.DataVisualization.Charting.Legend();
       this.dataTableComboBox = new System.Windows.Forms.ComboBox();
       this.dataTableLabel = new System.Windows.Forms.Label();
@@ -66 +66 @@
       this.relativeOrAbsoluteComboBox = new System.Windows.Forms.ComboBox();
       this.targetChart = new HeuristicLab.Visualization.ChartControlsExtensions.EnhancedChart();
+      this.showLabelsCheckBox = new System.Windows.Forms.CheckBox();
       this.markerCheckBox = new System.Windows.Forms.CheckBox();
       this.boundShadingCheckBox = new System.Windows.Forms.CheckBox();
@@ -71 +72 @@
       this.byCostViewHost = new HeuristicLab.MainForm.WindowsForms.ViewHost();
       this.budgetLogScalingCheckBox = new System.Windows.Forms.CheckBox();
-      this.aggregateBudgetsCheckBox = new System.Windows.Forms.CheckBox();
       this.generateBudgetsButton = new System.Windows.Forms.Button();
       this.byTableTabPage = new System.Windows.Forms.TabPage();
@@ -202 +202 @@
       this.budgetsTextBox.Location = new System.Drawing.Point(59, 8);
       this.budgetsTextBox.Name = "budgetsTextBox";
-      this.budgetsTextBox.Size = new System.Drawing.Size(309, 20);
+      this.budgetsTextBox.Size = new System.Drawing.Size(391, 20);
       this.budgetsTextBox.TabIndex = 6;
       this.budgetsTextBox.Validating += new System.ComponentModel.CancelEventHandler(this.budgetsTextBox_Validating);
@@ -249 +249 @@
       this.byTargetTabPage.Controls.Add(this.relativeOrAbsoluteComboBox);
       this.byTargetTabPage.Controls.Add(this.targetChart);
+      this.byTargetTabPage.Controls.Add(this.showLabelsCheckBox);
       this.byTargetTabPage.Controls.Add(this.markerCheckBox);
       this.byTargetTabPage.Controls.Add(this.boundShadingCheckBox);
@@ -284 +285 @@
             | System.Windows.Forms.AnchorStyles.Left) 
             | System.Windows.Forms.AnchorStyles.Right)));
-      chartArea1.AxisX.IsStartedFromZero = false;
-      chartArea1.AxisX.MinorGrid.Enabled = true;
-      chartArea1.AxisX.MinorGrid.LineColor = System.Drawing.Color.WhiteSmoke;
-      chartArea1.AxisX.MinorGrid.LineDashStyle = System.Windows.Forms.DataVisualization.Charting.ChartDashStyle.Dash;
-      chartArea1.AxisY.Maximum = 1D;
-      chartArea1.AxisY.Minimum = 0D;
-      chartArea1.AxisY.MinorGrid.Enabled = true;
-      chartArea1.AxisY.MinorGrid.LineColor = System.Drawing.Color.WhiteSmoke;
-      chartArea1.AxisY.MinorGrid.LineDashStyle = System.Windows.Forms.DataVisualization.Charting.ChartDashStyle.Dash;
-      chartArea1.Name = "ChartArea1";
-      this.targetChart.ChartAreas.Add(chartArea1);
-      legend1.Alignment = System.Drawing.StringAlignment.Center;
-      legend1.Docking = System.Windows.Forms.DataVisualization.Charting.Docking.Top;
-      legend1.Name = "Legend1";
-      this.targetChart.Legends.Add(legend1);
+      chartArea2.AxisX.IsStartedFromZero = false;
+      chartArea2.AxisX.MinorGrid.Enabled = true;
+      chartArea2.AxisX.MinorGrid.LineColor = System.Drawing.Color.WhiteSmoke;
+      chartArea2.AxisX.MinorGrid.LineDashStyle = System.Windows.Forms.DataVisualization.Charting.ChartDashStyle.Dash;
+      chartArea2.AxisY.Maximum = 1D;
+      chartArea2.AxisY.Minimum = 0D;
+      chartArea2.AxisY.MinorGrid.Enabled = true;
+      chartArea2.AxisY.MinorGrid.LineColor = System.Drawing.Color.WhiteSmoke;
+      chartArea2.AxisY.MinorGrid.LineDashStyle = System.Windows.Forms.DataVisualization.Charting.ChartDashStyle.Dash;
+      chartArea2.Name = "ChartArea1";
+      this.targetChart.ChartAreas.Add(chartArea2);
+      legend2.Alignment = System.Drawing.StringAlignment.Center;
+      legend2.Docking = System.Windows.Forms.DataVisualization.Charting.Docking.Top;
+      legend2.Name = "Legend1";
+      this.targetChart.Legends.Add(legend2);
       this.targetChart.Location = new System.Drawing.Point(6, 34);
       this.targetChart.Name = "targetChart";
@@ -308 +309 @@
       this.targetChart.MouseDown += new System.Windows.Forms.MouseEventHandler(this.chart_MouseDown);
       this.targetChart.MouseMove += new System.Windows.Forms.MouseEventHandler(this.chart_MouseMove);
+      // 
+      // showLabelsCheckBox
+      // 
+      this.showLabelsCheckBox.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Bottom | System.Windows.Forms.AnchorStyles.Left)));
+      this.showLabelsCheckBox.AutoSize = true;
+      this.showLabelsCheckBox.Checked = true;
+      this.showLabelsCheckBox.CheckState = System.Windows.Forms.CheckState.Checked;
+      this.showLabelsCheckBox.Location = new System.Drawing.Point(329, 364);
+      this.showLabelsCheckBox.Name = "showLabelsCheckBox";
+      this.showLabelsCheckBox.Size = new System.Drawing.Size(81, 17);
+      this.showLabelsCheckBox.TabIndex = 6;
+      this.showLabelsCheckBox.Text = "show labels";
+      this.showLabelsCheckBox.UseVisualStyleBackColor = true;
+      this.showLabelsCheckBox.CheckedChanged += new System.EventHandler(this.showLabelsCheckBox_CheckedChanged);
       // 
       // markerCheckBox
@@ -339 +354 @@
       this.byCostTabPage.Controls.Add(this.byCostViewHost);
       this.byCostTabPage.Controls.Add(this.budgetLogScalingCheckBox);
-      this.byCostTabPage.Controls.Add(this.aggregateBudgetsCheckBox);
       this.byCostTabPage.Controls.Add(this.generateBudgetsButton);
       this.byCostTabPage.Controls.Add(this.budgetsLabel);
@@ -379 +393 @@
       this.budgetLogScalingCheckBox.UseVisualStyleBackColor = true;
       this.budgetLogScalingCheckBox.CheckedChanged += new System.EventHandler(this.logScalingCheckBox_CheckedChanged);
-      // 
-      // aggregateBudgetsCheckBox
-      // 
-      this.aggregateBudgetsCheckBox.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
-      this.aggregateBudgetsCheckBox.AutoSize = true;
-      this.aggregateBudgetsCheckBox.Checked = true;
-      this.aggregateBudgetsCheckBox.CheckState = System.Windows.Forms.CheckState.Checked;
-      this.aggregateBudgetsCheckBox.Location = new System.Drawing.Point(374, 10);
-      this.aggregateBudgetsCheckBox.Name = "aggregateBudgetsCheckBox";
-      this.aggregateBudgetsCheckBox.Size = new System.Drawing.Size(74, 17);
-      this.aggregateBudgetsCheckBox.TabIndex = 10;
-      this.aggregateBudgetsCheckBox.Text = "aggregate";
-      this.aggregateBudgetsCheckBox.UseVisualStyleBackColor = true;
-      this.aggregateBudgetsCheckBox.CheckedChanged += new System.EventHandler(this.aggregateBudgetsCheckBox_CheckedChanged);
       // 
       // generateBudgetsButton
@@ -496 +496 @@
     private System.Windows.Forms.TabPage byCostTabPage;
     private System.Windows.Forms.TabPage byTableTabPage;
-    private System.Windows.Forms.CheckBox aggregateBudgetsCheckBox;
     private System.Windows.Forms.Button generateBudgetsButton;
     private System.Windows.Forms.CheckBox budgetLogScalingCheckBox;
@@ -507 +506 @@
     private System.Windows.Forms.CheckBox markerCheckBox;
     private System.Windows.Forms.ComboBox relativeOrAbsoluteComboBox;
+    private System.Windows.Forms.CheckBox showLabelsCheckBox;
   }
 }

trunk/sources/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs

@@ -81 +81 @@
     private double[] budgets;
     private bool targetsAreRelative = true;
+    private bool showLabelsInTargetChart = true;
     private readonly BindingList<ProblemInstance> problems;
 
@@ -96 +97 @@
       targetChart.ChartAreas[0].CursorX.Interval = 1;
       targetChart.SuppressExceptions = true;
-      byCostDataTable = new IndexedDataTable<double>("ECDF by Cost", "A data table containing the ECDF of each of a number of groups.") {
+      byCostDataTable = new IndexedDataTable<double>("ECDF by Cost", "A data table containing the ECDF of function values (relative to best-known).") {
         VisualProperties = {
-          YAxisTitle = "Proportion of unused budgets",
+          YAxisTitle = "Proportion of runs",
           YAxisMinimumFixedValue = 0,
           YAxisMinimumAuto = false,
@@ -284 +285 @@
       addTargetsAsResultButton.Enabled = Content != null && targets != null && dataTableComboBox.SelectedIndex >= 0;
       addBudgetsAsResultButton.Enabled = Content != null && budgets != null && dataTableComboBox.SelectedIndex >= 0;
+      generateTargetsButton.Enabled = targets != null;
     }
 
@@ -314 +316 @@
       targetChart.Series.Clear();
       invisibleTargetSeries.Clear();
-
+      
       var table = (string)dataTableComboBox.SelectedItem;
       if (string.IsNullOrEmpty(table)) return;
@@ -424 +426 @@
             if (!labelPrinted && row.Points.Count > 0) {
               var point = row.Points.Last();
-              point.Label = row.Name;
+              if (showLabelsInTargetChart)
+                point.Label = row.Name;
               point.MarkerStyle = MarkerStyle.Cross;
               point.MarkerBorderWidth = 1;
@@ -456 +459 @@
             if (!labelPrinted) {
               var point = row.Points.Last();
-              point.Label = row.Name;
+              if (showLabelsInTargetChart)
+                point.Label = row.Name;
               point.MarkerStyle = MarkerStyle.Cross;
               point.MarkerBorderWidth = 1;
@@ -504 +508 @@
           if (!labelPrinted && row.Points.Count > 0) {
             var point = row.Points.Last();
-            point.Label = row.Name;
+            if (showLabelsInTargetChart)
+              point.Label = row.Name;
             point.MarkerStyle = MarkerStyle.Cross;
             point.MarkerBorderWidth = 1;
@@ -514 +519 @@
         if (!labelPrinted) {
           var point = row.Points.Last();
-          point.Label = row.Name;
+          if (showLabelsInTargetChart)
+            point.Label = row.Name;
           point.MarkerStyle = MarkerStyle.Cross;
           point.MarkerBorderWidth = 1;
@@ -572 +578 @@
     private void GenerateDefaultTargets() {
       targets = new[] { 0.1, 0.095, 0.09, 0.085, 0.08, 0.075, 0.07, 0.065, 0.06, 0.055, 0.05, 0.045, 0.04, 0.035, 0.03, 0.025, 0.02, 0.015, 0.01, 0.005, 0 };
-      suppressTargetsEvents = true;
-      targetsTextBox.Text = string.Join("% ; ", targets.Select(x => x * 100)) + "%";
-      suppressTargetsEvents = false;
+      SynchronizeTargetTextBox();
     }
 
     private Tuple<bool, double> GetEffortToHitTarget(
-        IEnumerable<Tuple<double, double>> convergenceGraph,
+        ObservableList<Tuple<double, double>> convergenceGraph,
         double absTarget, bool maximization) {
-      var hit = false;
-      var effort = double.NaN;
-      foreach (var dent in convergenceGraph) {
-        effort = dent.Item1;
-        hit = maximization && dent.Item2 >= absTarget || !maximization && dent.Item2 <= absTarget;
-        if (hit) break;
-      }
-      if (double.IsNaN(effort)) throw new ArgumentException("Convergence graph is empty.", "convergenceGraph");
-      return Tuple.Create(hit, effort);
+      if (convergenceGraph.Count == 0)
+        throw new ArgumentException("Convergence graph is empty.", "convergenceGraph");
+      
+      var index = convergenceGraph.BinarySearch(Tuple.Create(0.0, absTarget), new TargetComparer(maximization));
+      if (index >= 0) {
+        return Tuple.Create(true, convergenceGraph[index].Item1);
+      } else {
+        index = ~index;
+        if (index >= convergenceGraph.Count)
+          return Tuple.Create(false, convergenceGraph.Last().Item1);
+        return Tuple.Create(true, convergenceGraph[index].Item1);
+      }
     }
 
     private void UpdateErtTables(List<AlgorithmInstance> algorithmInstances) {
       ertTableView.Content = null;
-      var columns = 1 + targets.Length + 1;
-      var matrix = new string[algorithmInstances.Count * algorithmInstances.Max(x => x.GetNumberOfProblemInstances()) + algorithmInstances.Max(x => x.GetNumberOfProblemInstances()), columns];
+      var columns = targets.Length + 1;
+      var totalRows = algorithmInstances.Count * algorithmInstances.Max(x => x.GetNumberOfProblemInstances()) + algorithmInstances.Max(x => x.GetNumberOfProblemInstances());
+      var matrix = new StringMatrix(totalRows, columns);
+      var rowNames = new List<string>();
+      matrix.ColumnNames = targets.Select(x => targetsAreRelative ? (100 * x).ToString() + "%" : x.ToString())
+        .Concat(new[] { "#succ" }).ToList();
       var rowCount = 0;
 
@@ -604 +615 @@
       foreach (var problem in problems) {
         var max = problem.IsMaximization();
-        matrix[rowCount, 0] = problem.ToString();
+        rowNames.Add(problem.ToString());
         var absTargets = GetAbsoluteTargetsWorstToBest(problem);
-        for (var i = 0; i < absTargets.Length; i++) {
-          matrix[rowCount, i + 1] = absTargets[i].ToString(CultureInfo.CurrentCulture.NumberFormat);
-        }
-        matrix[rowCount, columns - 1] = "#succ";
+        if (targetsAreRelative) {
+          // print out the absolute target values
+          for (var i = 0; i < absTargets.Length; i++) {
+            matrix[rowCount, i] = absTargets[i].ToString("##,0.0", CultureInfo.CurrentCulture.NumberFormat);
+          }
+        }
         rowCount++;
 
         foreach (var alg in algorithmInstances) {
-          matrix[rowCount, 0] = alg.Name;
+          rowNames.Add(alg.Name);
           var runs = alg.GetRuns(problem).ToList();
           if (runs.Count == 0) {
@@ -623 +636 @@
           for (var i = 0; i < absTargets.Length; i++) {
             result = ExpectedRuntimeHelper.CalculateErt(runs, tableName, absTargets[i], max);
-            matrix[rowCount, i + 1] = result.ToString();
+            matrix[rowCount, i] = result.ToString();
           }
           matrix[rowCount, columns - 1] = targets.Length > 0 ? result.SuccessfulRuns + "/" + result.TotalRuns : "-";
@@ -629 +642 @@
         }
       }
-      ertTableView.Content = new StringMatrix(matrix);
+      matrix.RowNames = rowNames;
+      ertTableView.Content = matrix;
       ertTableView.DataGridView.AutoResizeColumns(DataGridViewAutoSizeColumnsMode.AllCells);
     }
@@ -658 +672 @@
             var resultsTable = (IndexedDataTable<double>)run.Results[table];
 
-            if (aggregateBudgetsCheckBox.Checked) {
-              CalculateHitsForAllBudgets(hits, resultsTable.Rows.First(), alg.GetNumberOfProblemInstances(), problem, alg.Name, alg.GetNumberOfRuns(problem));
-            } else {
-              CalculateHitsForEachBudget(hits, resultsTable.Rows.First(), alg.GetNumberOfProblemInstances(), problem, alg.Name, alg.GetNumberOfRuns(problem));
-            }
+            CalculateHitsForEachBudget(hits, resultsTable.Rows.First(), problem, alg.Name);
           }
         }
@@ -678 +688 @@
 
           var total = 0.0;
+          var count = list.Value.Count;
           foreach (var h in list.Value) {
             total += h.Value;
-            row.Values.Add(Tuple.Create(h.Key, total));
+            row.Values.Add(Tuple.Create(h.Key, total / (double)count));
           }
 
@@ -697 +708 @@
       var min = runs.Select(x => ((IndexedDataTable<double>)x.Results[table]).Rows.First().Values.Select(y => y.Item1).Min()).Min();
       var max = runs.Select(x => ((IndexedDataTable<double>)x.Results[table]).Rows.First().Values.Select(y => y.Item1).Max()).Max();
-      var points = 20;
+      var points = 3;
       budgets = Enumerable.Range(1, points).Select(x => min + (x / (double)points) * (max - min)).ToArray();
       suppressBudgetsEvents = true;
@@ -704 +715 @@
     }
 
-    private void CalculateHitsForEachBudget(Dictionary<string, SortedList<double, double>> hits, IndexedDataRow<double> row, int groupCount, ProblemInstance problem, string groupName, int problemCount) {
+    private void CalculateHitsForEachBudget(Dictionary<string, SortedList<double, double>> hits, IndexedDataRow<double> row, ProblemInstance problem, string groupName) {
       var max = problem.IsMaximization();
+      var prevIndex = 0;
       foreach (var b in budgets) {
         var key = groupName + "-" + b;
+        var index = row.Values.BinarySearch(prevIndex, row.Values.Count - prevIndex, Tuple.Create(b, 0.0), new CostComparer());
+        if (index < 0) {
+          index = ~index;
+          if (index >= row.Values.Count) break; // the run wasn't long enough to use up budget b (or any subsequent larger one)
+        }
         if (!hits.ContainsKey(key)) hits.Add(key, new SortedList<double, double>());
-        Tuple<double, double> prev = null;
-        foreach (var v in row.Values) {
-          if (v.Item1 >= b) {
-            // the budget may be too low to achieve any target
-            if (prev == null && v.Item1 != b) break;
-            var tgt = ((prev == null || v.Item1 == b) ? v.Item2 : prev.Item2);
-            var relTgt = CalculateRelativeDifference(max, problem.BestKnownQuality, tgt) + 1;
-            if (hits[key].ContainsKey(relTgt))
-              hits[key][relTgt] += 1.0 / (groupCount * problemCount);
-            else hits[key][relTgt] = 1.0 / (groupCount * problemCount);
-            break;
-          }
-          prev = v;
-        }
-        if (hits[key].Count == 0) hits.Remove(key);
-      }
-    }
-
-    private void CalculateHitsForAllBudgets(Dictionary<string, SortedList<double, double>> hits, IndexedDataRow<double> row, int groupCount, ProblemInstance problem, string groupName, int problemCount) {
-      var values = row.Values;
-      if (!hits.ContainsKey(groupName)) hits.Add(groupName, new SortedList<double, double>());
-
-      var i = 0;
-      var j = 0;
-      Tuple<double, double> prev = null;
-      var max = problem.IsMaximization();
-      while (i < budgets.Length && j < values.Count) {
-        var current = values[j];
-        if (current.Item1 >= budgets[i]) {
-          if (prev != null || current.Item1 == budgets[i]) {
-            var tgt = (prev == null || current.Item1 == budgets[i]) ? current.Item2 : prev.Item2;
-            var relTgt = CalculateRelativeDifference(max, problem.BestKnownQuality, tgt) + 1;
-            if (!hits[groupName].ContainsKey(relTgt)) hits[groupName][relTgt] = 0;
-            hits[groupName][relTgt] += 1.0 / (groupCount * problemCount * budgets.Length);
-          }
-          i++;
-        } else {
-          j++;
-          prev = current;
-        }
-      }
-      var lastTgt = values.Last().Item2;
-      var lastRelTgt = CalculateRelativeDifference(max, problem.BestKnownQuality, lastTgt) + 1;
-      if (i < budgets.Length && !hits[groupName].ContainsKey(lastRelTgt)) hits[groupName][lastRelTgt] = 0;
-      while (i < budgets.Length) {
-        hits[groupName][lastRelTgt] += 1.0 / (groupCount * problemCount * budgets.Length);
-        i++;
+        var v = row.Values[index];
+        var relTgt = CalculateRelativeDifference(max, problem.BestKnownQuality, v.Item2) + 1;
+        if (hits[key].ContainsKey(relTgt))
+          hits[key][relTgt]++;
+        else hits[key][relTgt] = 1.0;
+        prevIndex = index;
       }
     }
@@ -762 +738 @@
     private void UpdateCaption() {
       Caption = Content != null ? Content.OptimizerName + " RLD View" : ViewAttribute.GetViewName(GetType());
+    }
+
+    private void SynchronizeTargetTextBox() {
+      if (InvokeRequired) Invoke((Action)SynchronizeTargetTextBox);
+      else {
+        suppressTargetsEvents = true;
+        try {
+          if (targetsAreRelative)
+            targetsTextBox.Text = string.Join("% ; ", targets.Select(x => x * 100)) + "%";
+          else targetsTextBox.Text = string.Join(" ; ", targets);
+        } finally { suppressTargetsEvents = false; }
+      }
     }
 
@@ -814 +802 @@
       errorProvider.SetError(targetsTextBox, null);
       targets = targetsAreRelative ? targetList.Select(x => (double)x).OrderByDescending(x => x).ToArray() : targetList.Select(x => (double)x).ToArray();
-      suppressTargetsEvents = true;
-      try {
-        if (targetsAreRelative)
-          targetsTextBox.Text = string.Join("% ; ", targets.Select(x => x * 100)) + "%";
-        else targetsTextBox.Text = string.Join(" ; ", targets);
-      } finally { suppressTargetsEvents = false; }
-
+
+      SynchronizeTargetTextBox();
       UpdateResultsByTarget();
       SetEnabledStateOfControls();
@@ -848 +831 @@
       }
       targetsAreRelative = (string)relativeOrAbsoluteComboBox.SelectedItem == "relative";
-      SuspendRepaint();
-      suppressTargetsEvents = true;
+      SynchronizeTargetTextBox();
+
       try {
-        if (targetsAreRelative)
-          targetsTextBox.Text = string.Join("% ; ", targets.Select(x => x * 100)) + "%";
-        else targetsTextBox.Text = string.Join(" ; ", targets);
-
+        SuspendRepaint();
         UpdateResultsByTarget();
-      } finally { suppressTargetsEvents = false; ResumeRepaint(true); }
+      } finally { ResumeRepaint(true); }
     }
 
     private void generateTargetsButton_Click(object sender, EventArgs e) {
-      decimal max = 1, min = 0, count = 10;
-      if (targets != null) {
-        max = (decimal)targets.Max();
-        min = (decimal)targets.Min();
-        count = targets.Length;
-      } else if (Content.Count > 0 && dataTableComboBox.SelectedIndex >= 0) {
-        var table = (string)dataTableComboBox.SelectedItem;
-        max = (decimal)Content.Where(x => x.Results.ContainsKey(table)).Select(x => ((IndexedDataTable<double>)x.Results[table]).Rows.First().Values.Max(y => y.Item2)).Max();
-        min = (decimal)Content.Where(x => x.Results.ContainsKey(table)).Select(x => ((IndexedDataTable<double>)x.Results[table]).Rows.First().Values.Min(y => y.Item2)).Min();
-        count = 6;
+      if (targets == null) return;
+      decimal max = 10, min = 0, count = 10;
+      max = (decimal)targets.Max();
+      min = (decimal)targets.Min();
+      count = targets.Length - 1;
+      if (targetsAreRelative) {
+        max *= 100;
+        min *= 100;
       }
       using (var dialog = new DefineArithmeticProgressionDialog(false, min, max, (max - min) / count)) {
         if (dialog.ShowDialog() == DialogResult.OK) {
           if (dialog.Values.Any()) {
-            targets = dialog.Values.Select(x => (double)x).ToArray();
-            suppressTargetsEvents = true;
-            if (targetsAreRelative)
-              targetsTextBox.Text = string.Join("% ; ", targets);
-            else targetsTextBox.Text = string.Join(" ; ", targets);
-            suppressTargetsEvents = false;
-
+            targets = targetsAreRelative
+              ? dialog.Values.OrderByDescending(x => x).Select(x => (double)x / 100.0).ToArray()
+              : dialog.Values.Select(x => (double)x).ToArray();
+
+            SynchronizeTargetTextBox();
             UpdateResultsByTarget();
             SetEnabledStateOfControls();
@@ -896 +872 @@
         var resultsTable = (IndexedDataTable<double>)run.Results[table];
         var values = resultsTable.Rows.First().Values;
-        var i = 0;
-        var j = 0;
         var pd = new ProblemInstance(run);
+        pd = problems.Single(x => x.Equals(pd));
         var max = pd.IsMaximization();
-        var absTargets = GetAbsoluteTargetsWorstToBest(problems.Single(x => x.Equals(pd)));
-        while (i < absTargets.Length && j < values.Count) {
-          var target = absTargets[i];
-          var current = values[j];
-          if (max && current.Item2 >= target || !max && current.Item2 <= target) {
-            run.Results[table + ".Target" + target] = new DoubleValue(current.Item1);
-            i++;
-          } else {
-            j++;
-          }
+        var absTargets = GetAbsoluteTargetsWorstToBest(pd);
+
+        var prevIndex = 0;
+        for (var i = 0; i < absTargets.Length; i++) {
+          var absTarget = absTargets[i];
+          var index = values.BinarySearch(prevIndex, values.Count - prevIndex, Tuple.Create(0.0, absTarget), new TargetComparer(max));
+          if (index < 0) {
+            index = ~index;
+            if (index >= values.Count) break; // the target (and subsequent ones) wasn't achieved
+          }
+          var target = targetsAreRelative ? (targets[i] * 100) : absTarget;
+          run.Results[table + (targetsAreRelative ? ".RelTarget " : ".AbsTarget ") + target + (targetsAreRelative ? "%" : string.Empty)] = new DoubleValue(values[index].Item1);
+          prevIndex = index;
         }
       }
@@ -915 +893 @@
 
     private void markerCheckBox_CheckedChanged(object sender, EventArgs e) {
+      SuspendRepaint();
+      try {
+        UpdateResultsByTarget();
+      } finally { ResumeRepaint(true); }
+    }
+
+    private void showLabelsCheckBox_CheckedChanged(object sender, EventArgs e) {
+      showLabelsInTargetChart = showLabelsCheckBox.Checked;
       SuspendRepaint();
       try {
@@ -931 +917 @@
         double b;
         if (!double.TryParse(ts, out b)) {
-          errorProvider.SetError(budgetsTextBox, "Not all targets can be parsed: " + ts);
+          errorProvider.SetError(budgetsTextBox, "Not all budgets can be parsed: " + ts);
           e.Cancel = true;
           return;
@@ -938 +924 @@
       }
       if (budgetList.Count == 0) {
-        errorProvider.SetError(budgetsTextBox, "Give at least one target value!");
+        errorProvider.SetError(budgetsTextBox, "Give at least one budget value!");
         e.Cancel = true;
         return;
@@ -944 +930 @@
       e.Cancel = false;
       errorProvider.SetError(budgetsTextBox, null);
-      budgets = budgetList.ToArray();
+      budgets = budgetList.OrderBy(x => x).ToArray();
+      try {
+        suppressBudgetsEvents = true;
+        budgetsTextBox.Text = string.Join(" ; ", budgets);
+      } finally { suppressBudgetsEvents = false; }
       UpdateResultsByCost();
       SetEnabledStateOfControls();
-    }
-
-    private void aggregateBudgetsCheckBox_CheckedChanged(object sender, EventArgs e) {
-      SuspendRepaint();
-      try {
-        UpdateResultsByCost();
-      } finally { ResumeRepaint(true); }
     }
 
@@ -966 +949 @@
         min = (decimal)Content.Where(x => x.Results.ContainsKey(table)).Select(x => ((IndexedDataTable<double>)x.Results[table]).Rows.First().Values.Min(y => y.Item1)).Min();
         max = (decimal)Content.Where(x => x.Results.ContainsKey(table)).Select(x => ((IndexedDataTable<double>)x.Results[table]).Rows.First().Values.Max(y => y.Item1)).Max();
-        count = 6;
+        count = 3;
       }
       using (var dialog = new DefineArithmeticProgressionDialog(false, min, max, (max - min) / count)) {
@@ -973 +956 @@
             budgets = dialog.Values.OrderBy(x => x).Select(x => (double)x).ToArray();
 
-            suppressBudgetsEvents = true;
-            budgetsTextBox.Text = string.Join(" ; ", budgets);
-            suppressBudgetsEvents = false;
+            try {
+              suppressBudgetsEvents = true;
+              budgetsTextBox.Text = string.Join(" ; ", budgets);
+            } finally { suppressBudgetsEvents = false; }
 
             UpdateResultsByCost();
@@ -986 +970 @@
     private void addBudgetsAsResultButton_Click(object sender, EventArgs e) {
       var table = (string)dataTableComboBox.SelectedItem;
-      var budgetStrings = budgetsTextBox.Text.Split(new[] { ';', '\t', ' ' }, StringSplitOptions.RemoveEmptyEntries);
-      if (budgetStrings.Length == 0) {
-        MessageBox.Show("Define a number of budgets.");
-        return;
-      }
-      var budgetList = new List<double>();
-      foreach (var bs in budgetStrings) {
-        double v;
-        if (!double.TryParse(bs, out v)) {
-          MessageBox.Show("Budgets must be a valid number: " + bs);
-          return;
-        }
-        budgetList.Add(v);
-      }
-      budgetList.Sort();
 
       foreach (var run in Content) {
@@ -1006 +975 @@
         var resultsTable = (IndexedDataTable<double>)run.Results[table];
         var values = resultsTable.Rows.First().Values;
-        var i = 0;
-        var j = 0;
-        Tuple<double, double> prev = null;
-        while (i < budgetList.Count && j < values.Count) {
-          var current = values[j];
-          if (current.Item1 >= budgetList[i]) {
-            if (prev != null || current.Item1 == budgetList[i]) {
-              var tgt = (prev == null || current.Item1 == budgetList[i]) ? current.Item2 : prev.Item2;
-              run.Results[table + ".Cost" + budgetList[i]] = new DoubleValue(tgt);
-            }
-            i++;
-          } else {
-            j++;
-            prev = current;
-          }
+        var pd = new ProblemInstance(run);
+        pd = problems.Single(x => x.Equals(pd));
+
+        var prevIndex = 0;
+        foreach (var b in budgets) {
+          var index = values.BinarySearch(prevIndex, values.Count - prevIndex, Tuple.Create(b, 0.0), new CostComparer());
+          if (index < 0) {
+            index = ~index;
+            if (index >= values.Count) break; // the run wasn't long enough to use up budget b (or any subsequent larger one)
+          }
+          var v = values[index];
+          var tgt = targetsAreRelative ? CalculateRelativeDifference(pd.IsMaximization(), pd.BestKnownQuality, v.Item2) : v.Item2;
+          run.Results[table + (targetsAreRelative ? ".CostForRelTarget " : ".CostForAbsTarget ") + b] = new DoubleValue(tgt);
+          prevIndex = index;
         }
       }
@@ -1080 +1048 @@
         else pd.BestKnownQuality = double.NaN;
       }
-      //problemComboBox.ResetBindings();
     }
     #endregion
 
     private void ConfigureSeries(Series series) {
-      series.SmartLabelStyle.Enabled = true;
+      series.SmartLabelStyle.Enabled = showLabelsInTargetChart;
       series.SmartLabelStyle.AllowOutsidePlotArea = LabelOutsidePlotAreaStyle.No;
       series.SmartLabelStyle.CalloutLineAnchorCapStyle = LineAnchorCapStyle.None;
@@ -1418 +1385 @@
       }
     }
+
+    private class CostComparer : Comparer<Tuple<double, double>> {
+      public override int Compare(Tuple<double, double> x, Tuple<double, double> y) {
+        return x.Item1.CompareTo(y.Item1);
+      }
+    }
+
+    private class TargetComparer : Comparer<Tuple<double, double>> {
+      public bool Maximization { get; }
+      public TargetComparer(bool maximization) {
+        Maximization = maximization;
+      }
+
+      public override int Compare(Tuple<double, double> x, Tuple<double, double> y) {
+        return Maximization ? x.Item2.CompareTo(y.Item2) : y.Item2.CompareTo(x.Item2);
+      }
+    }
   }
 }