C# List object being reused when not debugging

Question

I am currently having a problem where I an trying to generate a list of random Tour objects (Travelling Salesman). When I debug through the code, everything works fine, but when I just run the code (or even run over this section of the code) my list is full of all of the same object.

for (int i = 0; i < populationSize; i++)
{
    var newTour = new Tour(distanceCalculator);
    newTour.GenerateIndividual();
    this.Tours[i] = newTour;
    newTour = null;
}

The GenerateIndividual method is a method on the Tour object which fills the tour with cities, then randomizes it:

public void GenerateIndividual()
{
        Path = new List<Location>(new Location[GenericGraph.NumberOfLocations()]);

        // Loop through all our destination cities and add them to our tour
        for (int cityIndex = 0; cityIndex < GenericGraph.NumberOfLocations(); cityIndex++)
        {
            SetLocation(cityIndex, GenericGraph.LocationList[cityIndex]);
        }

        // Randomly reorder the tour
        Path = Path.Shuffle().ToList();
    }

I know the shuffle is working because the Path is always in a random order. The problem is the Tour in the Path is only updated if I debug into the for-loop. For example, if my populationSize is 10, and I debug through 5 times, I will have a population with 5 randomized Tours, then the final 5 tours will be the same as the last I debugged over. What is happening here? Is the newTour object only being reset when I debug, but when I run C# is using the same object over and over?

score 1 · Answer 1 · answered Sep 28 '17 at 02:49

1

"then the final 5 tours will be the same as the last I debugged over" seems to point to Shuffle method not working.

My guess is that the Shuffle methods calls new Random() each time it's invoked and because this code is very short it generates the same results every time. In debug you slow things down, and Shuffle seems to be working OK, I don't think it is.

(The curious thing is why the last 5 are the same as the 5th element, and I'm not sure what goes on there).

answered Sep 28 '17 at 02:49

tymtam

31,798
8
86
126

Thank you for your help, this led me to the answer. The Random() object was indeed giving the same results every time, and I resolved it by creating a private static Random() in the class. – Jon Ferguson Sep 28 '17 at 03:00

score 0 · Answer 2 · answered Sep 28 '17 at 02:59

0

The issue was indeed in my Shuffle method. As @mayu pointed out, I was using a new Random object each call which was using the same seed, giving me the same random numbers each time. By instead using a private static Random rando = new Random(); in my class, the issue was resolved. New Shuffle method is:

    /// <summary>
    /// Shuffles the List.
    /// </summary>
    /// <typeparam name="T">Type in the list</typeparam>
    /// <param name="list">The list.</param>
    /// <returns>Shuffled list</returns>
    public static List<T> Shuffle<T>(this List<T> list)
    {
        List<T> randomList = new List<T>();


        while (list.Any())
        {
            var randomIndex = rando.Next(0, list.Count());
            randomList.Add(list[randomIndex]); //add it to the new, random list
            list.RemoveAt(randomIndex); //remove to avoid duplicates
        }

        return randomList; //return the new random list
    }

answered Sep 28 '17 at 02:59

Jon Ferguson

11
1

This is a terrible `Shuffle` function - it's destructive on the input list. Just try doing `return list.OrderBy(x => rando.Next()).ToList();` instead. – Enigmativity Sep 28 '17 at 03:04
I read that OrderBy is less efficient for larger lists, which is a part of this project. Do you think this function is much more efficient than Orderby or worth the destruction of the input list for large collections? – Jon Ferguson Sep 28 '17 at 03:07
It's more efficient than your method by a lot. You're causing your list to move half the elements each time you remove an element - so it's doing `n * n / 2` operations. A sort is typically `n * log n*` in complexity. If you have a list with 1,000 elements then your method is 50 times more expensive. If you have 100,000 elements then yours is 3,000 times more expensive. – Enigmativity Sep 28 '17 at 03:12
You should always do some timings to test. I wrote a quick test app comparing the two methods. For lists around 10,000 the time taken was similar. For lists around 1,000 your method was faster (1.3ms vs 2.3ms - yes, it saved 1ms). For lists of 100,000 in size my method was 10x faster. When I set the list to 1,000,000 elements the `Shuffle` method just kept running and I stopped the test, but the `.OrderBy` method returned a result in about half a second. – Enigmativity Sep 28 '17 at 03:22
And I got a result. The latest run on 1,000,000 elements took 75,900ms for `Shuffle` versus 643ms for `OrderBy`. – Enigmativity Sep 28 '17 at 03:27
https://stackoverflow.com/questions/273313/randomize-a-listt – tymtam Sep 28 '17 at 03:32
@mayu - `OrderBy` performs as well as Fisher-Yates. – Enigmativity Sep 28 '17 at 04:47
1

@Enigmativity - as well as = equal which probably is not true. ;) I didn't mean to suggest your code is slower, the link I provided is just another idea. – tymtam Sep 28 '17 at 05:05

C# List object being reused when not debugging

2 Answers2