6
\$\begingroup\$

I have this method that is working perfectly fine, but it's very slow, and sometimes I have to wait 15 minutes to get a good result, which is ok. I'm wondering if I can make it faster.

Basically I'm running best fleet simulations, and I pre-calculate the possible ship combinations for specific voyages, but then I have to get the best fleet combinations for multiple voyages.

Obviously I can't use the same captain or crew in different ships because the voyages take place at the same time, and that's why there's some more conditions in each inner loop.

private static Ship[] GetBestFleet3(IList<Voyage> voyages)
{
    var bestRate = 0;
    var worstVariance = 100.0;
    Ship[] fleet = null;
    foreach (var ship0 in voyages[0].Ships)
    {
        foreach (var ship1 in voyages[1].Ships.Where(s1 => !s1.Equals(ship0)))
        {
            foreach (var ship2 in voyages[2].Ships.Where(s2 => !s2.Equals(ship0) && !s2.Equals(ship1)))
            {
                var variance = Statistics.Variance(ship0, ship1, ship2);
                var rate = ship0.Rate + ship1.Rate + ship2.Rate;
                if (rate >= bestRate || rate == bestRate && variance < worstVariance)
                {
                    bestRate = rate;
                    worstVariance = variance;
                    fleet = new[] { ship0, ship1, ship2 };

                    if (ship0.Rate >= 100 && ship1.Rate >= 100 && ship2.Rate >= 100)
                    {
                        return fleet;
                    }
                }
            }
        }
    }
    return fleet;
}

voyages is basically an array of voyages with possible ship combinations for each voyage.

Gist with all the relevant project files: https://gist.github.com/alfaproject/cb68e6fa1c21e1f93bf7

\$\endgroup\$
  • \$\begingroup\$ How do you compute Ship.Rate? Is Variance computed on the rate? \$\endgroup\$ – mariosangiorgio Aug 3 '14 at 19:54
  • \$\begingroup\$ Each voyage has all possible ships with the rate already calculated, but if it matters, the Rate is the (minimum of 3 ship parameters) / (voyage best 'requirements') \$\endgroup\$ – aLfa Aug 3 '14 at 19:58
  • \$\begingroup\$ Sorry, I think I misunderstood you. The Variance is the standard deviation of the 3 ship rates. \$\endgroup\$ – aLfa Aug 3 '14 at 19:59
  • \$\begingroup\$ I'm wondering if there is any way to avoid generating all the possible ships in advance. Can you tell us how you generate the ships for a given voyage? \$\endgroup\$ – mariosangiorgio Aug 3 '14 at 20:03
  • \$\begingroup\$ I've tried avoiding that as well, but so far pre-calculating them is faster. Maybe I need to rework the whole thing. I will edit my question with that part of the code. \$\endgroup\$ – aLfa Aug 3 '14 at 20:04
3
\$\begingroup\$

I'd try to go with a different approach. At the moment you're evaluating all the possible combinations, while I think it could be useful to evaluate only the meaningful ones. To do that I'd start with a two phase approach. First you can generate all the valid fleets and then you can sort them using a comparator that takes into account their Range/Variance.

This is the code you can use to generate all the possible fleets:

private static IEnumerable<Fleet> PossibleVoyages(IList<Captain> captains, IList<Crew> crews, int voyagesToPrepare, Fleet fleet)
{
    var possibleVoyages = new List<Fleet>();
    if(voyagesToPrepare == 0)
    {
        possibleVoyages.Add(fleet);
    }
    if(captains.Count < voyagesToPrepare || crews.Count < voyagesToPrepare)
    {
        // We cannot find any valid solution here
        return possibleVoyages;
    }
    else
    {
        foreach(var captain in captains)
        {
            foreach(var crew in crews)
            {
                var newFleet = fleet.Add(CreateShip(captain, crew));
                possibleVoyages.AddRange(
                    PossibleVoyages(
                        FreeCaptains(captains, newFleet),
                        FreeCrews(crews, newFleet),
                        voyagesToPrepare - 1,
                        newFleet));
            }
        }
    }
    return possibleVoyages;
}

I have not implemented the methods FreeCaptains, FreeCrews, and CreateShip but they should be obvious. Fleet act as an immutable collection of ships.

Once you get all the possible voyages you can just sort them using a comparator and Linq sort.

I'm not sure this is going to help much, but it is worth giving it a try. A possible way to improve it is to keep track of the best fleet we generated so far and to just compare it with every fleet we generate instead of doing all the comparisons at the end. This could possibly prune a lot of solutions once you find a good one and it is definitely worth trying.

\$\endgroup\$
  • \$\begingroup\$ I will have a look at this aproach and let you know as soon as I have some data. It's already late here, so I'm not sure if I can get back to you today, but I will get back for sure. I've also added a Gist in the original post with my current hobby project if you want to play around. (; \$\endgroup\$ – aLfa Aug 3 '14 at 21:15
  • \$\begingroup\$ I just installed Xamarin studio to do some tests. I'm going to have a look at the gists, and maybe I'll implement the alternative approach using yield returns \$\endgroup\$ – mariosangiorgio Aug 3 '14 at 21:16
  • \$\begingroup\$ I just had a quick look, and I think this is similar to my first approach. The problem was that the voyages are very different in the requirements, and I ended up creating too many possible ships to go through, but maybe I missed something, and I'll have a proper look in the meanwhile. Thanks! \$\endgroup\$ – aLfa Aug 3 '14 at 21:31
  • \$\begingroup\$ I'm not sure if I'm missing something, but it looks like that with your current approach you're generating all the possible ships for all the possible voyages and then you filter them only later. Isn't it? \$\endgroup\$ – mariosangiorgio Aug 3 '14 at 21:34
  • \$\begingroup\$ Yes, that is my latest approach indeed. My first approach was months ago. (; \$\endgroup\$ – aLfa Aug 3 '14 at 21:43
0
\$\begingroup\$

I have implemented some code to compare two ships. By doing this, you will avoid using that long statement of filtering of data. There was also a condition which was wrong.

I am still not sure why you need the explicit three loops (you know your requirements better).

var totalRate = 0;
var previousStdDev = 100.0;
Ship[] fleet = null;
IEnumerable<Ship> firstShips = voyages[0].Ships.ToList();
IEnumerable<Ship> secondShips = voyages[1].Ships.ToList();
IEnumerable<Ship> thirdShips = voyages[2].Ships.ToList();
var shipCompare = new ShipComparer();
IEnumerable<Ship> filteredFirstShips = firstShips;
IEnumerable<Ship> filteredSecondShips = secondShips.Except(filteredFirstShips, shipCompare).ToList();
IEnumerable<Ship> filteredThirdShip = thirdShips.Except(secondShips, shipCompare).ToList();
filteredThirdShip = filteredThirdShip.Except(firstShips).ToList();


foreach (var firstShip in filteredFirstShips)
{
    foreach (var secondShip in filteredSecondShips)
    {
        foreach (var thirdShip in filteredThirdShip)
        {
            var stdDev = Statistics.Variance(firstShip, secondShip, thirdShip);
            var tempSum = firstShip.Rate + secondShip.Rate + thirdShip.Rate;
            if (tempSum >= totalRate && stdDev < previousStdDev)
            {
                totalRate = tempSum;
                previousStdDev = stdDev;
                fleet = new[] { firstShip, secondShip, thirdShip };

                if (firstShip.Rate >= 100 && secondShip.Rate >= 100 && thirdShip.Rate >= 100)
                {
                    return fleet;
                }
            }
        }
    }
}

return fleet;

internal class ShipComparer : IEqualityComparer<Ship>
{
    public bool Equals(Ship x, Ship y)
    {
        return x.Captain == y.Captain && x.Crew.Intersect(y.Crew).Any();
    }

    public int GetHashCode(Ship ship)
    {
        //TODO create a unique hash code
        return int.MaxValue;
    }
}
\$\endgroup\$
  • \$\begingroup\$ The explicit 3 loops was actually me trying to optimize this for a 3 voyage scenario which is the most common and it's the one I care about the most, but it could be any amount of voyages if it helps in any way. I'm liking the pre-calculation of 'exceptions'. I'll try that and tell you exactly how many seconds I save. \$\endgroup\$ – aLfa Aug 3 '14 at 20:18
  • \$\begingroup\$ Unfortunately your changes don't return any ships at all even if I change the equality comparer. I think it is because of the prefiltering. You are removing ships from the combinations that might be useful. \$\endgroup\$ – aLfa Aug 3 '14 at 20:37
  • \$\begingroup\$ you need to provide test data so I can test it \$\endgroup\$ – paritosh Aug 3 '14 at 20:49
  • \$\begingroup\$ I have added a Gist in the original post. Thanks! \$\endgroup\$ – aLfa Aug 3 '14 at 21:04
  • \$\begingroup\$ I have updated the Gist with a small optimization based on your example, and actually shaved some seconds from GetBestFleet3 which was nice. (: \$\endgroup\$ – aLfa Aug 4 '14 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.