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 に答える