logo标签列表

更快的用于计算活跃呼叫的算法

javaalgorithmoptimization
4
我们正在为呼叫中心实施密度报告。结果必须以表格形式显示，每天一行，显示当天同时活动的最大通话数。
我们正在构建UI后面的库。合同规定，我们收到当天通话次数和两个整数数组，一个包含每个通话的开始时间，另一个包含每个通话的结束时间，例如：
对于某一天，只接收到两个通话：一个从20到30的通话，另一个从10到20的通话。同时通话的最大数量为1。
另一方面，对于另一天，也收到了两个通话，一个从10到45，另一个从15到40，则同时通话的最大数量为2。
Web服务的合同如下。
public static int GetMaxDensity(int N, int[] X, int[] Y)

数据看起来像这样（假设那一天有3个电话）。第一个从10点到25点，第二个从12点到30点，第三个从20点到23点。

N = 3, 
X = {10, 12, 20}
Y = {25, 30, 23}

返回结果必须是：3。
我已经实现了这个解决方案：
public static int GetMaxDensity(int N, int[] X, int[] Y) 
{
  int result = 0;
  for (int i = 0; i < N; i++) 
  {
      int count = 0, t = X[i];
      for (int j = 0; j < N; j++) 
      {
        if (X[j] <= t && t < Y[j])
        count++;
      }
      result = Math.max(count, result);
   }
   return result;
}

当呼叫数量少于1000次（周末）时，它的效果非常好。但是在工作日，呼叫数量很大，计算时间很长（> 5分钟）。我知道原因可能是我的解决方案使用了两个嵌套循环，但我对复杂算法没有太多经验，因此我的问题是：

考虑到我只需要同时通话的最大数量（而不是时间或呼叫者），如果有更快的计算方法，那么该怎么做？

如果第一通电话是从10到40，第二通电话是从20到45，密度应该是多少？我认为是2，对吗？ - mprabhat
@mprabhat 是的。因为从20到40有两个调用处于活动状态。 - Erre Efe
2
我刚刚复制了你的代码，并对两个长度为50,000的数组进行了五次测试。每个数组都是随机生成的值，其中x小于100，y小于相应的x + 100。它们分别用时24、12、12、24、18秒。这是在我的笔记本电脑上完成的。你是否清理了代码以便在这里发布？如果是这样，也许循环不是问题所在。你的分析器揭示了什么？ - dbrown0708
@dbrown0708 - 这是一个有趣的观察。我只有 C# 方便，但看到与你相似的数字（N=50,000 时为 29,000 毫秒）。 - hatchet - done with SOverflow
@dbrown0708 合同规定的最差时间（服务质量要求）必须不超过每10万次分析中的10秒。 - Erre Efe
你试图达到的目标如何影响性能差异？N=50,000的30秒与N>1,000的5分钟相差甚远。 - dbrown0708
7个回答
5
随着N的增长，你的时间急剧增加(N*N)。一个简单的解决方案(如果你的时间间隔是从午夜开始的分钟数)，是创建一个包含每天每分钟通话次数变化的1440个整数的数组。接下来，你只需要循环一次从0到N-1，并对于每个元素，通过在通话开始时增加该时间点的通话次数差值计数，并在通话结束时减少该计数。之后，只需查看计数以获得最大值。这对于较大的N值应该会更快。
由于1440是一个常量(用于最后一步)，而且输入不需要排序，因此这个算法的时间复杂度应该为线性。该算法的运行时间不受平均通话长度的影响。
public static int GetMaxDensity(int N, int[] X, int[] Y) {
    int rangeStart = Integer.MAX_VALUE;
    int rangeEnd = Integer.MIN_VALUE;
    for(int i=0; i<N; i++) {
        if (X[i] < rangeStart) rangeStart = X[i];
        if (Y[i] > rangeEnd) rangeEnd = Y[i];
    } 
    int rangeSize = rangeEnd - rangeStart + 1;
    int[] histogram = new int[rangeSize];
    for (int t = 0; t < rangeSize; t++) histogram[t] = 0;
    for (int i = 0; i < N; i++) {
        histogram[X[i]-rangeStart]++;
        histogram[Y[i]-rangeStart]--;
    }
    int maxCount = 0;
    int count = 0;
    for (int t = 0; t < rangeSize; t++) {
        count += histogram[t];
        if (count > maxCount) maxCount = count;
    }
    return maxCount;        
}

与之相比，当N=50,000时且随机的呼叫长度介于1到40分钟之间，本问题中的算法使用了29,043毫秒，而这个算法只用了8毫秒。我在c＃中运行了这些测试，但它们应该与Java产生的结果相当。

@RandolfRincón-Fadul - 时间单位是什么？如果时间以整数值给出，并且您需要计算最大呼叫次数的时间范围，则应该能够使用此解决方案。直方图的大小将只是起始和结束范围之间的时间间隔数，而不是固定为1440。如果您仍然认为这不是这种情况，请在问题中提供更现实的示例可能会有所帮助。 - hatchet - done with SOverflow
@RandolfRincón-Fadul - 我已经编辑了我的回答，以考虑输入中存在的一段相当任意的时间范围，以展示我所说的它仍然适用的含义。唯一的警告是输入中出现的范围不应该很大。如果您可能拥有巨大的时间范围（许多百万个单位），那么其他答案的方法是对开头和结尾进行排序，然后同时在两个数组中遍历（使用较低时间的数组前进），并随着遍历过程计数。 - hatchet - done with SOverflow
@hatchet 实际上这是不可能的（因为 Web 服务期望一个整数数组）。我刚刚实现了你的解决方案，速度惊人！我的方法需要 47750.562 毫秒才能完成 100,000 次调用，而你的只需要 10.245 毫秒。现在的问题是这将占用多少空间，但现在并不重要。 - Erre Efe
int[] X ={11,12,15,17,18,13}; int[] Y ={16,34,24,19,19,18}; int N = 6; 使用这个算法，结果为4。这正确吗？@18处有5个活动呼叫。 - ejb_guy
这个更改导致了数组越界异常。需要进行一些微调。int rangeSize = rangeEnd - rangeStart + 1+1; 为什么要额外加上+1，不确定。 - ejb_guy
显示剩余5条评论
2

我建议使用不同的算法。考虑到一天最多有24*60=1440分钟，为什么不创建一个直方图数组来计算每分钟同时通话的数量。

public static int GetMaxDensity(int N, int[] X, int[] Y) 
{
  int[] h = new int[1440];
  // loop through all calls
  for (int i=0; i<N ; i++){
    addIt(X[i], Y[i], h);
  }

  // find max
  int m = 0;
  for(int i =0 ; i<1440; i++){
    if (h[i]>m)
      m = h[i];
  }
  return m;
}

// counting for one call
public static void addIt(int x, int y, int[] h){
  for ( int i=x;i<y;i++){
    h[i]++;
  }
}

复杂度为O(m*n)，其中m是一个调用的平均长度。由于调用次数可能远超过1000，因此运气好的话，这个算法在实践中会更快。
@ejb_guy 在这种情况下：24*3600 = 86400 分钟。如果调用次数非常非常大，这仍然是一个很好的解决方案。:) - Xi 张熹
@ejb_guy 当然，在那种情况下性能会很差。对于算法来说，一切都取决于问题的规模，不是吗？我相信在某些情况下，即使是原始帖子中的O(n^2)算法也会有最佳性能。 - Xi 张熹
不知怎么的，我觉得矩阵操作在这个高效算法中扮演了一定的角色。让我好好琢磨琢磨。 - ejb_guy
@ejb_guy - 这种方法可以进行优化，以消除调用长度对运行时间的影响。您可以在我类似的（更早的）答案中看到我的意思，在那里我已经做出了这个改变。 - hatchet - done with SOverflow
@XiZhang 正如之前所评论的，我无法在一天内以那种方式填补这个差距。对于我的问题，我将其作为一个例子，但实际上报告必须是动态生成的，例如从周二的13:00到周五的16:00之间，并且在这段时间内开始呼叫和结束呼叫的数量不受任何特定整数（如本例中的一天中的分钟数）的限制。 - Erre Efe
显示剩余2条评论
1

你的算法非常慢，因为它实际上测试了所有可能的情况，这是O(n^2)。

假设你接收到的调用是有序的，这里有一个O(n)的算法： [编辑：第二个数组应该被排序]

    int max;
    int i=0,j=0,count=0;
    while(i<n && j<n){
        if(x[i]<y[j]){ //new call received
            count++;
            max = count>max? count:max;
            i++;
        }else if(x[i]==x[j]){ //receive new call at the same time of end call
            i++;
            j++;
        }else { //call ended
            count--;
            j++;
        }
    }
    return max;
  }

[注意：这段代码很可能会抛出数组索引超出范围的错误，但应该足以演示想法，以便您可以实现其余部分]

如果调用未排序，则算法为O（n lg n）：

array_of_calldata a = x union y
a.sort();
foreach(calldata d in a){
    if (d is new call) count++;
    else count--;
}
return max_value_of_count;
我认为第一种方法不会奏效。考虑这个案例{{12,25}{20,21}{22,23}}，使用你的算法结果仍然是3，而实际上应该是2。 - Selim
@kayson 感谢您的回复。您能详细说明一下调用未排序的情况吗？因为我的问题就在于这一点。 - Erre Efe
1

按开始时间对所有通话进行排序。遍历列表并保持一个“活动通话”列表，按结束时间排序。应该看起来类似于这样：

public class DensityReport {

  static int count;

  static class Call {
    public Call(int x, int y) {
      double f = 0.1/(++count);
      start = x + f;
      end = y + f;
    }
    double start;
    double end;
  }

  public static int getMaxDensity(int n, int[] x, int[] y) {
    // Calls sorted by start time
    TreeSet<Call> calls = new TreeSet<Call>(new Comparator<Call>() {
      public int compare(Call c1, Call c2) {
        return c1.start < c2.start ? -1 : c1.start > c2.start ? 1 : 0;
      }
    });

    // Add all calls to the sorted set.
    for (int i = 0; i < n; i++) {
      calls.add(new Call(x[i], y[i]));
    }

    int max = 0;
    // Active calls sorted by end time
    TreeSet<Call> activeCalls = new TreeSet<Call>(new Comparator<Call>() {
      public int compare(Call c1, Call c2) {
        return c1.end < c2.end ? -1 : c1.end > c2.end ? 1 : 0;
      }
    });

    for (Call call: calls) {
      // Remove all calls that end before the current call starts.
      while(activeCalls.size() > 0 && activeCalls.first().end < call.start) {
        activeCalls.pollFirst();
      }
      activeCalls.add(call);
      if (activeCalls.size() > max) {
        max = activeCalls.size();
      }
    }
    return max;
  }
}

运行时间应该是O(n log n)

附注：如果我们可以假设调用已经按开始时间排序，那么可能可以简化此过程。

感谢您的回复。对于仅一个调用，它似乎可以工作，但从那时起，它会在while循环中卡住：while(activeCalls.size() > 0 && activeCalls.first().end < call.start) { activeCalls.remove(activeCalls.first()); } - Erre Efe
抱歉，修复了比较器并在循环中将remove()替换为pollFirst()。问题在于我认为可以忽略比较器中的equals情况，但这对于remove()不起作用（而且也不是很干净）。 - Stefan Haustein
请注意，我还必须更改Call类以简化比较。 - Stefan Haustein
感谢您的回复。+1，因为我实现了您的解决方案，虽然不如hatchet快，但它比我的快得多。只有一个问题，我对您使用的集合没有太多经验，但我猜您的解决方案在空间复杂度方面比hatchet更好（我错了吗？）。 - Erre Efe
Hatchet的解决方案的空间消耗与第一次调用的开始和最后一次调用的结束之间的距离成线性关系。我的解决方案的内存复杂度与输入大小成线性关系，所以这取决于具体情况。他的解决方案运行时间为O(n * m)，其中m是最长调用的长度。我不喜欢的是你需要做额外的假设，降低了鲁棒性：假设调用很短，总时间有限制。因此，如果有人开始以毫秒为单位测量调用长度，或者时间跨度增加，就会出现问题。 - Stefan Haustein
请尝试一些极端的调用时间，例如[0，Integer.MAX_VALUE]，以查看问题所在。如果您完全确定这永远不会发生，那么显然就没有问题。 - Stefan Haustein
0
使用两个列表，将X[i] Y[i]对添加到这些列表中。第一个列表按呼叫开始时间排序，第二个列表按结束时间排序。仅迭代列表，步进最低时间列表。
class Call {
    int start;
    int end;
}

Call callsSortedOnStart[];
Call callsSortedOnEnd[];

int indexStart = 0;  // Position in the array
int indexEnd = 0;

int nCalls = 0;      // Current density of calls
int maxCalls = 0;    // Maximum density of calls

while(indexStart < callsSortedOnStart.length && indexEnd < callsSortedOnEnd.length) {
    while(callsSortedOnStart[indexStart].start <= callsSortedOnEnd[indexEnd].end) {
        indexStart++;
        nCalls++;
    }
    maxCalls = max(maxCalls, nCalls);

    while(callsSortedOnStart[indexStart].start > callsSortedOnEnd[indexEnd].end) {
        indexEnd++;
        nCalls--;
    }
}
1
如果他对这两个数组进行排序，他将失去每个通话的开始和结束时间，他需要在任何时段内最大通话次数。 - mprabhat
@mprabhat 因此，请将起始-结束对存储在列表中；添加了一些代码以澄清这一点。 - Kasper van den Berg
@KaspervandenBerg 谢谢您的回复。但我想我的英语不是很好，我理解您使用两个列表的意思，但不明白您说“步进最低时间列表”是什么意思。您是指迭代具有最小第一项的列表，因为创建列表将需要 O(N)，而获取所有列表的最小值将需要 O(N^2) AFAIK。并且不是作业，而是工作。有点奇怪，实际上我不是计算机科学家。我是一名律师 :) - Erre Efe
我会展示我的意思，但Hatchet的方法更快。对于“作业”的假设感到抱歉。 - Kasper van den Berg
0
创建一个通话事件的数组。通话事件只是具有时间字段和startend字段的结构，其值为+1或-1，用于通话开始和通话结束。按照时间字段对此数组进行排序（如果时间相等，则使用第二个字段，在开始事件之前使用结束事件）。初始化CurrentCalls = 0。迭代数组，将StartEnd字段添加到CurrentCalls中。在扫描数组期间，CurrentCalls的最大值就是所需的值。
0

按开始时间对您的持续时间进行排序。这样，当内部循环中的开始时间超出外部循环提供的范围时，您可以使用break来中断内部循环。

有一个问题，如果所有的调用都落在范围内（可能由于某些奇怪的行为），那么运行时间会是O(n^2)，我说得对吗？ - Erre Efe
你也可能会很幸运，没有任何调用重叠。你的数据集中没有任何可能导致这种假设的模式。此外，与您原始解决方案相比，此方法不需要分配额外的内存。 - dbrown0708
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接