优化时间线生成

Question

我有许多进程正在不同的虚拟机上执行。所有这些进程都具有StartDate、EndDate和Resource属性。资源是运行在其上的特定虚拟机。我为项目生成了实际的时间线，发现所有这些资源在时间线上都有“漏洞”，可以同时满足在其他机器上运行的其他进程，这意味着我可以用更少的机器生活。所以我现在试着想出一种算法，试图将所有这些过程都与时间线相匹配。它向时间线中添加时间线和第一项，对于下一项，它将检查时间线中最后一项的EndDate是否大于当前项StartDate，如果是这样，则添加新的时间线，否则放到现有时间线中。目前的执行情况：

public List<TimelineDto> GetOptimizedTimeline()
{
    var allItems = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
    if (!allItems.Any())
    {
        return null;
    }
    // Add the first item to first resource
    var firstitem = allItems.FirstOrDefault();
    var timelineCount = 1;
    var timeline = new List<TimelineDto>
    {
        new TimelineDto
        {
            itemId = firstitem.Id,
            Resource = timelineCount.ToString(),
            StartTime = firstitem.StartDate,
            EndTime = firstitem.EndDate
        }
    };
    allItems.Remove(firstitem);

    foreach (var item in allItems)
    {
        var added = false;
        for (var i = 1; i <= timelineCount; i++)
        {
            // as items are ordered by date, take the last item in current resource and see if the new items "fits" to that resource
            var last = timeline.Last(x => x.Resource.Equals(i.ToString()));
            if (item.StartDate > last.EndTime)
            {
                // Add to existing
                timeline.Add(new TimelineDto
                {
                    itemId = item.Id,
                    Resource = i.ToString(),
                    StartTime = item.StartDate,
                    EndTime = item.EndDate
                });
                added = true;
                break;
            }
        }
        // suitable resource already found, cool. 
        if (added)
            continue;
        // Current item did not fit into any existing resource, add a new one. 
        timelineCount++;
        timeline.Add(new TimelineDto
        {
            itemId = item.Id,
            Resource = timelineCount.ToString(),
            StartTime = item.StartDate,
            EndTime = item.EndDate
        });
    }
    return timeline;
}

现在这做了我所需要的，但是对于100 k的项目，它需要几分钟来完成。我每天要处理1万个项目，所以我不能等几分钟，但是优化它是很棒的。我能并行化这个吗？

Answer 1

像firstitem这样的复合词应该是camelCase。

为什么Resource属性TimelineDto是一个string，而你似乎是用ints填充它呢？

allItems是个坏名字，item更糟糕。我不知道这代表什么。

我还必须反对TimelineDto，特别是当timeline = new List<TimelineDto>。

var firstitem = allItems.FirstOrDefault();可以返回一个null，但是您从来不检查这个。

考虑到第一行通过OrDefault对GetInterestingItems()的结果进行排序，您为什么还要使用StartDate版本，如果其中一个条目是null，则会引发异常。

这一切有什么意义吗？

// Add the first item to first resource
var firstitem = allItems.FirstOrDefault();
var timelineCount = 1;
var timeline = new List<TimelineDto>
{
    new TimelineDto
    {
        itemId = firstitem.Id,
        Resource = timelineCount.ToString(),
        StartTime = firstitem.StartDate,
        EndTime = firstitem.EndDate
    }
};
allItems.Remove(firstitem);

除了var timelineCount = 1;之外，我不知道foreach (var item in allItems)内部的逻辑是如何处理的。当然，您需要重新考虑var last = timeline.Last(x => x.Resource.Equals(i.ToString()));和if (item.StartDate > last.EndTime)，但这似乎是一个比向timeline添加第一个条目所需的10+行更优雅的解决方案。

此代码重复三次，因此应该移到方法中：

new TimelineDto
{
    itemId = item.Id,
    Resource = timelineCount.ToString(),
    StartTime = item.StartDate,
    EndTime = item.EndDate
}

WRT您的问题，我不知道您如何能够并行它而不冒重复条目的风险。

我确实想知道，与每次执行Dictionary<int, DateTime>相比，维护var last = timeline.Last(x => x.Resource.Equals(i.ToString()));是否更容易(并提高性能)。那个字典的键是Resource，值是EndTime。

所以你最终会得到这样的结果：

public List<TimelineDto> GetOptimizedTimeline()
{
    var items = GetInterestingItems().OrderBy(x => x.StartDate).ToList();
    if (!items.Any())
    {
        return null;
    }

    var timeline = new List<TimelineDto>();
    var endTimeByResource = new Dictionary<int, DateTime>();
    var timelineCount = 1;

    foreach (var item in items)
    {
        var added = false;
        for (var i = 1; i <= timelineCount; i++)
        {
            DateTime endTime;
            if(endTimeByResource.TryGetValue(i, out endTime)
            {
                if (item.StartDate > endTime)
                {
                    timeline.Add(CreateTimelineDto(item, i));
                    endTimeByResource[i] = item.EndTime;
                    added = true;
                    break;
                }
            }
        }

        if (added)
            continue;

        timelineCount++;
        timeline.Add(CreateTimelineDto(item, i));
        endTimeByResource[i] = item.EndTime;
    }

    return timeline;
}

注意:我还没有测试过这段代码，所以可能有部分逻辑丢失了！我怀疑if(endTimeByResource.TryGetValue(i, out endTime)需要一个添加新TimelineDto的else。

我甚至会考虑完全摆脱timelineCount，而去做for (var i = 1; i <= endTimeByResource.Keys.Count; i++)，这样您甚至可以摆脱added，如下所示：

foreach (var item in items)
{
    for (var i = 1; i <= endTimeByResource.Keys.Count; i++)
    {
        DateTime endTime;
        if(endTimeByResource.TryGetValue(i, out endTime)
        {
            if (item.StartDate > endTime)
            {
                timeline.Add(CreateTimelineDto(item, i));
                endTimeByResource[i] = item.EndTime;
                break;
            }
        }
    }
}

再次:这是未经测试的。

我觉得甚至可以说是这样：

    for (var i = 1; i <= endTimeByResource.Keys.Count; i++)
    {
        DateTime endTime;
        endTimeByResource.TryGetValue(i, out endTime);

        if (item.StartDate > endTime)
        {
            timeline.Add(CreateTimelineDto(item, i));
            endTimeByResource[i] = item.EndTime;
            break;
        }
    }

Answer 2

虽然你已经有了一些很好的答案，但我想我还是把重点放在你的关键问题--表现上。让我们来看看您当前的实现。特别是，这一点：

foreach (var item in allItems)
{
    var added = false;
    for (var i = 1; i <= timelineCount; i++)
    {
        var last = timeline.Last(x => x.Resource.Equals(i.ToString()));
        if (item.StartDate > last.EndTime)
        {
            // add to timeline
            added = true;
            break;
        }

让我们考虑一下最好的情况:一切都适合于一种资源。该守则现在有效地：

forearch (var item in allItems)
{
    var last = timeline.Last(x => x.Resource.Equals(1.ToString()));
    if (item.StartDate > last.EndTime)
    {
       // add to timeline
} 

你看到问题了吗？对于您正在执行的每一项，都要执行一个Last，它将迭代您已经处理过的所有项。先迭代0，然后1，2，3，4.一直到最后一次电话的N-1项目。所以我们知道，Last在列表的每一次迭代中都会变得更加昂贵，即使我们在相同的资源上调度所有的东西。

在最坏的情况下，每个项目都需要一个新的资源。您现在正在对已经创建的每个资源id执行一个对Last的调用。但是，您从不搜索最后一个，因为它是在最后一个迭代中创建的。因此，就在最后一次迭代中，您将执行(N-1)*(N-1)操作。唉哟!

我相信，普通情况下创造的“资源”并不多，但值得考虑的是，这绝对是最糟糕的情况。

就在我做这件事的时候--你也在调用i.ToString()负载和很多次。

你已经有一个答案可以帮你改善这个问题了，我就再给你一个答案。您所需要做的就是跟踪您的“资源id”和当前项目结束的日期/时间。这很适合列在一个列表中：

public List<TimelineDto> GetOptimizedTimeline()
{
    var allItems = GetInterestingItems().OrderBy(x => x.StartDate);
    var resources = new List<DateTime>();
    var timeline = new List<TimelineDto>();

    foreach (var item in allItems)
    {
        var freeResourceIndex = resources.FindIndex(endDate => item.StartDate > endDate);
        if (freeResourceIndex == -1)
        {
            // No free resource, add a new one and modify index to point at it.
            resources.Add(item.EndDate);
            freeResourceIndex = resources.Count - 1;
        }
        timeline.Add(new TimelineDto
            {
                itemId = item.Id,
                // 0 based so need to add 1 as you seem to be 1 based
                Resource = (freeResourceIndex + 1).ToString(),
                StartTime = item.StartDate,
                EndTime = item.EndDate
            });
        // track the new end date for this resource.
        resources[freeResourceIndex] = item.EndDate;
    }
    return timeline;
 }

虽然代码还没有经过测试并直接输入到这个答案中(所以可能是不正确的)，但是您应该能够看到，我们已经消除了所有这些操作，在这些操作中，我们一直在搜索我们已经添加到时间线中的所有项，而只是保留一个结束日期的列表(这是我们按照开始日期的顺序所需要的)。

请注意，我也没有急切地对allItems进行评估，并且构造了代码以避免需要检测无项情况。

我故意没有做任何正式的大O分析，所以请原谅我挥手。

更新

我决定看看我建议的改变会产生多大的影响。对于必须在至少5个资源范围内排定的10 000个项目：

我的版本: 2ms

原版:4324

我还尝试了100,000项项目，这些项目至少需要5项资源来安排：

我的版本:44 My

原版: 438834ms (~7.3分钟)

测试平均超过10次，第一次热身每次都没有测量。我还检查了算法是否返回相同的结果(据我所知，它们是相同的)。