找到不同的時間間隔

鑑於「線程」，其中包含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。

還有一點：僅僅因爲一個線程是活的，它是運行？

來源

2012-04-17 kasavbere

那麼，你必須檢查每一個線程，看看它的運行，即O（N）。如果列表根據開始時間進行了預先排序，唯一的方法可能會更快一些。然後你可以對開始時間大於等於時間t的線程進行二分查找。 – noMAD 2012-04-17 17:25:42

關於正在排序的列表沒有任何說法。 – kasavbere 2012-04-17 17:44:15

我想過預先對列表進行一次排序，然後攤銷成本：由於列表是預先排序的，因此以後所有對該函數的調用都會查找預先排序的列表，並使用二分搜索，成本O（2 * LG N）是O（LG N） – kasavbere 2012-04-17 17:49:15

如果你的列表進行排序，你可以實現比O（n）的任何搜索算法（例如，分而治之）更快。不能達到比爲O（n）爲無序列表更快，因爲你要看看每個項目

來源

2012-04-17 17:25:04 Rado

關於正在排序的列表沒有任何說法。 – kasavbere 2012-04-17 17:44:25

@ kasavbere它也沒有說誰維護線程列表。如果您有權訪問該列表的填充方式，則可以改進該功能。否則沒有辦法讓它比O（n） – Rado 2012-04-17 17:46:47

更快'給定一個「線程」列表似乎表明我不控制列表。如果某些我不控制的客戶端對象必須通過某個API調用使用我的函數，那麼我看不到比O（n）更好的複雜性。否則，如果我的對象具有列表的本地副本，那麼正如我上面提到的那樣，通過預先排序來分攤成本就如我所見。爲嘗試投票。 – kasavbere 2012-04-17 21:58:03

如果他們說「進行優化」，即意味着（我），你被允許預處理列表以加快未來的查詢。在這種情況下，我會使用interval tree（這實際上只是一個二叉搜索樹的應用程序）。

來源

2012-04-18 16:38:32 chepner

在開始時間和結束時間之間，線程何時被認爲正在運行？我看到區間樹的想法，但僅僅因爲一個線程還活着，它正在運行？ – kasavbere 2012-04-18 17:00:53

這是一個非常簡單的問題，給出一個間隔和一個點的列表，找出哪些間隔包含了這個點，沒有什麼比這個「活着」和「跑步」，「現有」和「工作「和什麼 – 2012-04-18 17:21:22

找到不同的時間間隔

回答

相關問題