0

给定一个“线程”列表，其中包含 2 个变量 - 开始时间和结束时间 - 实现一个函数，该函数将在某个时间 t 返回所有正在运行的线程。优化它。（比 O(n) 快）

我的解决方案是遍历列表——即 O(n)。有谁知道如何在这里实现比 O(n) 更快的速度？

class MyThread{
Thread thread;
long start;
long end;
}//the object in the list

//function to find "threads"
public List<Thread> matchingInterval(List<MyThread> list) {
    List<Thread> found = new ArrayList<Thread>();
    Set<Thread> runningThreads = Thread.getAllStackTraces().keySet();
    long instant = System.currentTimeMillis();
    for(MyThread el: list)
        if(el.start <= instant && el.end >= instant && runningThreads.contains(el.thread))
            found.add(el.thread);
    return found;
}

编辑：

目标是return all running threads at some time t.我的解决方案假定time t是调用我的函数的时间（加/减错误），因此我long instant = System.currentTimeMillis();的调用者是否有可能指定一些任意时间？如果是，那么我观察到这个问题实际上与线程本身无关，所以我不需要抓住实际的runningThreads.

还有一点：仅仅因为一个线程是活着的，它就在运行吗？

4

2 回答 2

1

如果您的列表已排序，您可以使用任何搜索算法（例如分而治之）实现比 O(n) 更快的速度。对于未排序的列表，不能比 O(n) 更快，因为您必须查看每个项目

于 2012-04-17T17:25:04.973 回答
0

如果他们说“优化它”，这意味着（对我来说）您可以预处理列表顺序以加快未来的查询。在这种情况下，我会使用区间树（实际上只是二叉搜索树的一个应用程序）。

于 2012-04-18T16:38:32.387 回答