java查找在收集

最近的（或等於）值，我的線沿線的一類：java查找在收集

public class Observation { 
    private String time; 
    private double x; 
    private double y; 

    //Constructors + Setters + Getters 
}

我可以選擇這些對象存儲在任何類型的集合（標準級或第三方像番石榴）的。我在下面的ArrayList中存儲了一些示例數據，但正如我所說，我願意接受任何其他類型的集合，這些集合都可以實現。因此，一些示例數據如下：

ArrayList<Observation> ol = new ArrayList<Observation>(); 
ol.add(new Observation("08:01:23",2.87,3.23)); 
ol.add(new Observation("08:01:27",2.96,3.17)); 
ol.add(new Observation("08:01:27",2.93,3.20)); 
ol.add(new Observation("08:01:28",2.93,3.21)); 
ol.add(new Observation("08:01:30",2.91,3.23));

該示例假定在Observation中有匹配的構造函數。時間戳存儲爲String對象，因爲我從外部源接收它們，但我很樂意將它們轉換爲其他內容。我按照時間順序收到觀察結果，所以我可以創建並依賴一個有序的觀測集合。時間戳不是唯一的（如示例數據中所示），所以我無法根據time創建唯一的密鑰。

現在來解決問題。我經常需要找到一個（1）觀察與time等於或最接近某個時間，例如，如果我的時間是08:01:29我想獲取示例數據中的第四個觀察，如果時間是08:01:27我想第三個觀察。

我明顯可以遍歷該集合，直到找到我正在尋找的時間，但我需要經常這樣做，並且在一天結束時，我可能會有數百萬次觀察，所以我需要找到一個解決方案我可以高效地找到相關的觀察結果。

我已經看過各種集合類型，包括我可以使用Predicates過濾集合的那些集合類型，但是我沒有找到將返回一個值的解決方案，而不是滿足「< = 「-條件。我基本上在尋找SELECT * FROM ol WHERE time <= t LIMIT 1的SQL等價物。

我相信有一個聰明和簡單的方法來解決我的問題，所以我希望能夠開悟。先謝謝你。

來源

2011-05-10 hgus1294

Try TreeSet提供比較器，用於比較時間。它保留了一個有序集合，你可以要求TreeSet.floor(E)找到最大分鐘（你應該提供一個虛擬的觀察與你正在尋找的時間）。你也有headSet和tailSet的有序子集。

它有O（log n）時間來添加和檢索。我認爲非常適合你的需求。

如果您更喜歡Map，您可以使用類似方法的TreeMap。

來源

2011-05-10 15:58:31 helios

謝謝。這當然有訣竅。我使用Treemap並使用'time'作爲關鍵。此外，我不得不稍微調整比較器以允許非唯一時間作爲鍵。謝謝。 – hgus1294 2011-05-11 13:53:05

太好了。但你用什麼鍵？（或者你使用一個比較時間和「更多」的比較器？） – helios 2011-05-11 14:04:07

我使用字符串格式的'時間'作爲鍵並實現一個評估鍵的比較器，並且總是返回-1或+1，即使鍵是完全相同，即使密鑰不是唯一的，也能夠在TreeMap中保留完整集合。可能還有其他方法可以實現這一目標（？），但最重要的是它起作用。 – hgus1294 2011-05-11 14:22:45

排序您的收藏（ArrayList中可能會工作最好在這裏），並使用BinarySearch返回無論是比賽中的「最近的」可能匹配的一個整數索引，即它返回一個......的

指數搜索關鍵字，如果它包含在列表中;否則，（ - （插入點） - 1）。插入點定義爲密鑰插入列表的位置：大於密鑰的第一個元素的索引，或list.size（），

來源

2011-05-10 15:56:23

讓Observation類實現Comparable並使用TreeSet來存儲對象，這將保持元素排序。TreeSet implements SortedSet，因此您可以使用headSet或tailSet在您搜索的元素之前或之後獲取該集合的視圖。在返回的集合上使用first或last方法獲取您正在尋找的元素。

如果您堅持使用ArrayList，但可以自行排列元素，請使用Collections.binarySearch來搜索元素。如果找到了確切的元素，它將返回一個正數，或者可以使用負數來確定最接近的元素。 http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20java.lang.Object）

來源

2011-05-10 16:00:04 Brigham

如果你很幸運能夠使用Java 6，並且保持SortedSet的性能開銷對你來說不是什麼大問題。看看TreeSetceiling，floor，higher和lower方法。

來源

2011-05-10 16:02:25

java查找在收集

回答

相關問題