Réduire la complexité des boucles imbriquées à l'aide de Dictionary (ou d'une autre structure de données) en C #

Il existe de nombreuses astuces vraiment insensées pour réduire la complexité du temps, mais la plupart du temps, en travaillant avec des données, vous devez vous fier à leur ordre initial. Si ce n'est pas commandé, nous pouvons le commander par une clé composite. Dans votre cas, la clé est Tuple où Item1 est le jour de la date et Item2 est l'emplacement. Cela prendrait n * log (n), puis utiliserait un temps linéaire pour parcourir les données produisant des résultats en utilisant le temps linéaire.

Donc, en regardant vos données, elles sont déjà triées. Nous pouvons donc sauter cette partie et passer à travers. Idée de base, nous initialisons un état et vérifions s'il change, nous produisons un résultat. Dans notre cas, l'état est le jour actuel, l'emplacement actuel, et nous suivons les informations dans deux variables: total des animaux, total des mammifères.

public class AnimalObservations
{
    public DateTime DateTime { get; set; }
    public string Location { get; set; }
    public Animal Animal { get; set; }
}

public class Animal
{
    public bool IsMammal { get; set; }
}

Je suppose que

    public static void PrintPopulation(List<AnimalObservations> animalObservations)
    {
        if (animalObservations.Count == 0)
            return;
        var item = animalObservations[0];
        string currentLocation = item.Location;
        DateTime currentDate = item.DateTime.Date;
        int totalAnimals = 1;
        int totalMammals = item.Animal.IsMammal ? 1 : 0;
        for (int i = 1; i < animalObservations.Count; i++)
        {
            item = animalObservations[i];
            if (currentLocation != item.Location ||
                currentDate != item.DateTime.Date)
            {
                PrintResult(currentDate, currentLocation, totalAnimals, totalMammals);
                totalMammals = 0;
                totalAnimals = 0;
                currentLocation = item.Location;
                currentDate = item.DateTime.Date;
            }

            totalAnimals++;
            totalMammals += item.Animal.IsMammal ? 1 : 0;
        }
        PrintResult(currentDate, currentLocation, totalAnimals, totalMammals);
    }

    public static void PrintResult(DateTime date, string location, int totalAnimals, int totalMammals)
    {
        Console.WriteLine($"{date} {location} {(double) totalMammals / totalAnimals}");
    }

Je pense que votre solution a en fait une complexité de O (n ^ 3) car vous faites 3 itérations imbriquées:

1. Chaque jour distinct
2. Chaque emplacement distinct pour la journée en cours
3. Comptez le nombre d'animaux et de mammifères pour la paire jour-lieu - ceci que vous avez indiqué dans une expression Linq, ce n'est donc pas si évident

Étant donné que vous avez la structure de classe suivante:

public class DayLocationComparer : EqualityComparer<ValueTuple<DateTime, string>> {
    public override bool Equals(ValueTuple<DateTime, string> x, ValueTuple<DateTime, string> y) => x.Item1.Date == y.Item1.Date && x.Item2 == y.Item2;
    public override int GetHashCode(ValueTuple<DateTime, string> x) => x.Item1.GetHashCode();
}

Vous pouvez le faire dans O (n) en utilisant deux dictionnaires --- un pour les animaux et un pour les mammifères --- qui ont une paire jour-lieu comme clé et un compteur comme valeur

    IDictionary<ValueTuple<DateTime, string>, int> animals = new Dictionary<ValueTuple<DateTime, string>, int>(new DayLocationComparer());
    IDictionary<ValueTuple<DateTime, string>, int> mammals = new Dictionary<ValueTuple<DateTime, string>, int>(new DayLocationComparer());
    foreach (AnimalObservation ao in aos) {
        ValueTuple<DateTime, string> dayLocation = new ValueTuple<DateTime, string>(ao.DateTime, ao.Location);

        if (!animals.ContainsKey(dayLocation)) {
            animals.Add(dayLocation, 1);
        } else {
            animals[dayLocation] = animals[dayLocation] + 1;
        }


        if (!mammals.ContainsKey(dayLocation) && ao.Animal.IsMammal) {
            mammals.Add(dayLocation, 1);
        } else if (!mammals.ContainsKey(dayLocation) && !ao.Animal.IsMammal) {
            mammals.Add(dayLocation, 0);
        } else if (mammals.ContainsKey(dayLocation) && ao.Animal.IsMammal) {
            animals[dayLocation] = animals[dayLocation] + 1;
        }
    }

    foreach (ValueTuple<DateTime, string> dayLocation in animals.Keys) {
        int nrOfAnimals = animals[dayLocation];
        int nrOfMammals = mammals[dayLocation];
        Console.WriteLine((double)nrOfMammals / nrOfAnimals * 100);
    }

Où DayLocationComparer est un comparateur qui ignore la partie Time du DateTime

public class AnimalObservation {
    public DateTime DateTime { get; set; }
    public string Location { get; set; }
    public Animal Animal { get; set; }
}

public class Animal {
    public string Species { get; set; }
    public bool IsMammal { get; set; }
}

Bien sûr, je recommanderais d'utiliser peut-être une classe pour la journée -paire de localisation pour un code plus lisible.

Une solution consiste à utiliser un dictionnaire , avec un type de clé comprenant le jour et le lieu et un type de valeur contenant le nombre de mammifères / non-mammifères.

Essayez le code ci-dessous. Vous devrez pointer la constante de chaîne vers le haut vers l'emplacement du fichier JSON. Vous devrez également ajouter la bibliothèque NewtonSoft JSON à votre projet. Notez que j'ai remplacé les méthodes Equals et GetHashCode dans la classe utilisée comme type de clé du dictionnaire.

namespace Mammals
{
    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;

    using Newtonsoft.Json.Linq;

    class Program
    {
        static void Main(string[] args)
        {
            const string filePath = "C:\\temp\\mammals.json";

            // Read input from JSON:
            string jsonInput;
            using (var file = new StreamReader(new FileStream(filePath, FileMode.Open)))
            {
                jsonInput = file.ReadToEnd();
            }

            var json = JArray.Parse(jsonInput);
            var sightings = json.Select(j => j.ToObject<Sighting>());

            // Set up dictionary, using day/location as key:
            var sightingDictionary = new Dictionary<SightingDayAndPlace, SightingCounter>();

            // Loop through sightings in O(n):
            foreach (var sighting in sightings)
            {
                var sightingTimeAndPlace = sighting.GetSightingDayAndPlace;
                if (!sightingDictionary.ContainsKey(sightingTimeAndPlace))
                {
                    sightingDictionary.Add(sightingTimeAndPlace, new SightingCounter());
                }

                if (sighting.IsMammal)
                {
                    sightingDictionary[sightingTimeAndPlace].MammalCount++;
                }
                else
                {
                    sightingDictionary[sightingTimeAndPlace].NonMammalCount++;
                }
            }

            // Print output:
            var currentDay = default(DateTime);
            foreach (var item in sightingDictionary)
            {
                var key = item.Key;
                if (key.Day != currentDay)
                {
                    Console.WriteLine($"Day: {key.Day:dd.MM.yyyy}");
                }

                Console.WriteLine($"Location: {key.Location}");
                Console.WriteLine($"Percentage of Mammals in location and day: {item.Value.MammalPercentage:F}%");
            }

            Console.ReadKey();
        }

        private class SightingDayAndPlace
        {
            public SightingDayAndPlace(DateTime day, string location)
            {
                this.Day = day;
                this.Location = location;
            }

            public DateTime Day { get; }

            public string Location { get; }

            public override bool Equals(object obj)
            {
                if (obj == null || !(obj is SightingDayAndPlace that))
                {
                    return false;
                }

                return this.Day == that.Day
                       && this.Location == that.Location;
            }

            public override int GetHashCode()
            {
                // Consider a different implementation if memory or performance is relevant.
                return new { this.Day, this.Location }.GetHashCode();
            }
        }

        private class Sighting
        {
            public DateTime DateTime { get; set; }
            public string Location { get; set; }
            public Animal Animal { get; set; }
            public string Species => Animal.Species;
            public bool IsMammal => Animal.IsMammal;
            public DateTime Day => DateTime.Date;

            public SightingDayAndPlace GetSightingDayAndPlace => new SightingDayAndPlace(this.Day, this.Location);
        }

        private class Animal
        {
            public string Species { get; set; }
            public bool IsMammal { get; set; }
        }

        private class SightingCounter
        {
            public int MammalCount { get; set; }
            public int NonMammalCount { get; set; }

            public double MammalPercentage => (MammalCount / ((double)MammalCount + NonMammalCount)) * 100;
        }
    }
}