借助C＃中的Dictionary（或其他数据结构）降低嵌套循环的复杂度

问题描述 投票：0回答：2

请您在下面举一个借助字典（可能是其他数据结构）来减少此代码的时间复杂度的示例？

据我所知，我的蛮力解决方案的时间复杂度为O(n^2)，但是可能可以在O(n)中完成（以n倍的非嵌套循环）。

任务是针对每一天和每个位置打印当天和该位置的观察百分比，即哺乳动物的观察值。

foreach (var day in EachDay(GetDateTimeForFirstObservation(animalObservations),
GetDateTimeForLastObservation(animalObservations)))
{
    Console.WriteLine("Day: {0}", day.ToString("dd/MM/yyyy"));

    foreach (var location in EachLocation(animalObservations
        .Where(ao => ao.Datetime.Day == day.Day).ToList()))
    {
        Console.WriteLine("Location: {0}", location);

        numOfAllAnimalsInLocationAndDay = animalObservations
            .Where(aob => aob.Location == location &&
                aob.Datetime.Date == day).Count();

        numOfMammalsAnimalsInLocationAndDay = animalObservations
            .Where(aob => aob.Location == location &&
            aob.Datetime.Date == day && aob.Animal.IsMammal).Count();

        Console.WriteLine("Percentage of Mammals in location and day: {0:N2}%",
            numOfMammalsAnimalsInLocationAndDay/numOfAllAnimalsInLocationAndDay * 100);
    }
}

输入看起来像这样：

[
{"DateTime":"2020-02-22 10:10:15", "Location":"Backyard", "Animal": {"Species":"Camel", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-22 11:10:15", "Location":"Backyard", "Animal": {"Species":"Camel", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-22 12:10:15", "Location":"Backyard", "Animal": {"Species":"Ant", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-22 22:10:15", "Location":"Sky", "Animal": {"Species":"Flamingo", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-22 23:10:15", "Location":"Sky", "Animal": {"Species":"Bee", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-23 13:11:15", "Location":"City", "Animal": {"Species":"Racoon", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-24 15:10:00", "Location":"City", "Animal": {"Species":"Dog", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-24 19:10:00", "Location":"City", "Animal": {"Species":"Fly", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-24 19:10:15", "Location":"City", "Animal": {"Species":"Butterfly", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-24 19:10:20", "Location":"City", "Animal": {"Species":"Cat", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-24 19:10:30", "Location":"City", "Animal": {"Species":"Flee", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-25 21:10:15", "Location":"Village", "Animal": {"Species":"Horse", "IsMammal": "TRUE"}},
{"DateTime":"2020-02-25 22:10:15", "Location":"Village", "Animal": {"Species":"Fly", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-25 23:10:15", "Location":"Village", "Animal": {"Species":"Bee", "IsMammal": "FALSE"}},
{"DateTime":"2020-02-25 10:10:15", "Location":"Home", "Animal": {"Species":"Iguana", "IsMammal": "FALSE"}}
]

和所需的输出：

Day: 22.02.2020
Location: Backyard
Percentage of Mammals in location and day: 66,67%
Location: Sky
Percentage of Mammals in location and day: 50,00%
Day: 23.02.2020
Location: City
Percentage of Mammals in location and day: 100,00%
Day: 24.02.2020
Location: City
Percentage of Mammals in location and day: 40,00%
Day: 25.02.2020
Location: Village
Percentage of Mammals in location and day: 33,33%
Location: Home
Percentage of Mammals in location and day: 0,00%
c# dictionary time-complexity nested-loops
2个回答
0
投票

我认为您的解决方案实际上是O(n^3)的复杂度，因为您要进行3个嵌套的迭代：

  1. 每个不同的日子
  2. 当天的每个不同位置
  3. 日定位对中的动物和哺乳动物的数量---您输入的是Linq表达式，所以不太明显

鉴于您具有以下类结构：

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; }
}

[您可以在O(n)中使用两个字典---一个用于动物，一个用于哺乳动物-，其中有一个日位对作为键，而一个计数器为值]]

    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);
    }

DayLocationComparer是一个比较器，它忽略了DateTime的时间部分
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();
}

当然，我建议对日位置对使用一个类，以获得更易读的代码。
0
投票

有很多真正疯狂的技巧可以减少时间复杂度，但是在大多数情况下，处理数据必须依赖于数据的初始排序方式。如果没有订购，我们可以通过一些组合键订购。在您的情况下，键为Tuple<DateTime, Location>，其中Item1为日期，Item2为位置。这将花费n * log（n），然后使用线性时间遍历数据，并使用线性时间生成结果。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.