Opened 4 years ago

Closed 4 years ago

#2146 closed defect (done)

Bug in SampleProportionalWithoutRepetition extension method

Reported by: abeham Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.10
Component: Random Version: 3.3.9
Keywords: Cc:

Description

The index variable is incremented twice in each iteration

Change History (15)

comment:1 Changed 4 years ago by abeham

  • Status changed from new to accepted

comment:2 Changed 4 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from accepted to reviewing

r10407: Fixed bug in sample proportional without repetition

comment:3 Changed 4 years ago by gkronber

  • Owner changed from mkommend to gkronber

comment:4 Changed 4 years ago by abeham

I'll also post the code here with the variant that uses free indices instead of chosen indices. The code is somewhat nicer, but I did not use this because I think it's a waste of resources for most cases when you have a large population where you draw only a couple of samples from (the while loop isn't fully executed as it depends on the outer .Take() that is calling this).

SortedSet<int> freeIndices = new SortedSet<int>(Enumerable.Range(0, sourceArray.Length));
while (freeIndices.Any()) {
  var index = freeIndices.GetEnumerator();
  double ball = 0, sum = random.NextDouble() * total;
  while (index.MoveNext()) {
    ball += valueArray[index.Current];
    if (ball >= sum) break;
  };
  yield return sourceArray[index.Current];
  total -= valueArray[index.Current];
  freeIndices.Remove(index.Current);
}
Last edited 4 years ago by abeham (previous) (diff)

comment:5 Changed 4 years ago by abeham

mkommend suggested to use a LinkedList<double> instead of a double[] for values and remove the node after yielding it. This doesn't require a hashset at all, but requires some changes to the helper functions.

comment:6 Changed 4 years ago by gkronber

r10465: implemented unit test for SampleProportionalWithoutRepetition

comment:7 Changed 4 years ago by gkronber

r10466: changed implementation of SampleProportionalWithoutRepetition to use a linked list.

comment:8 Changed 4 years ago by gkronber

  • Owner changed from gkronber to abeham

comment:9 Changed 4 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from reviewing to assigned

comment:10 Changed 4 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from assigned to reviewing

r10503: minor efficiency tweak (removed unnecessary .ToArray() call)

comment:11 Changed 4 years ago by abeham

r10504: fixed bug in biased vrp multi operators that was introduced through the recent changes

comment:12 Changed 4 years ago by mkommend

r10474 using RandomEnumerable.SampleProportional in BiasedMultiVRPOperators. This should also be changed in StochasticMultiOperator but is not easily possible because of plugin dependency HeuristicLab.Random -> HeuristicLab.Operators.

was recorded in ticket #2119, but won't be merged in the stable branch, as it has nothing to do with the operator instrumentation. r10504 fixes a bug introduced with r10474 => it shall be released with this ticket.

comment:13 Changed 4 years ago by abeham

The implementation looks good now. I took a look at the unit tests and noticed that there are redundant asserts. Also I added some tests with a little variation regarding the bool parameters.

r10646: updated unit tests

comment:14 Changed 4 years ago by abeham

  • Status changed from reviewing to readytorelease

I think this can be released

comment:15 Changed 4 years ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed

r10743: merged r10407,r10465,r10466,r10474,r10503,r10504,r10646 into stable

r10474 contained an unrelated change of properties on HeuristicLab.HLScript and HeuristicLab.HLScript.Views which could not be merged into stable as Scripting is not yet part of stable.

Note: See TracTickets for help on using tickets.