找到下一個最小的鍵（需要性能建議）

我需要一些性能方面的建議。我有一個Map<DateTime, String>。我需要這樣的東西下面的方法：找到下一個最小的鍵（需要性能建議）

Map<DateTime, BigDecimal> map; // about 50 entries. Btw: Which impl to choose? 

BigDecimal findNextSmaller(DateTime input) { 

    DateTime tmp = null; 

    for(DateTime d : map.keySet()) { 
     if(tmp == null && d < input) { 
      tmp = d; 
     } 
     if(d < input && d > tmp) { 
      tmp = d; 
     } 
    } 

    return map.get(tmp); 
}

所以基本上我只是遍歷我Map的密鑰集，並設法找到它是下一個最小相比input的關鍵。

此方法將連續被調用約1,000,000次：

BigDecimal sum; 

List<Item> items; // about 1.000.000 Items 

for(Item i : items) { 
    sum = sum.add(findNextSmaller(i.getDateTime())); 
}

現在我正在尋找一種方法，使事情更快。

我的第一個想法是在Map的keySet中輸入OrderedList。所以平均來說，我只需要重複DateTime的一半。然後，只需執行map.get(dateTimeFromOrderedList)即可獲取匹配值。

但是，我能做些什麼嗎？

來源

2014-02-07 Benjamin M

您可以使用對一個built-in method一個TreeMap：

TreeMap<DateTime, BigDecimal> map = new TreeMap<>(); 
//populate the map 

BigDecimal findNextSmaller(DateTime input) { 
    return map.ceilingEntry(input).getValue(); //add exception checking as required 
}

注意：您可能要取決於你是否希望ceilingEntry或higherEntry>=或>（RESP）。

來源

2014-02-07 16:54:26 assylias

看一看NavigableMap。這似乎正是你需要的。

當您正在搜索最接近並且嚴格小於輸入的DateTime時，我會選擇floorEntry（key）進行查找。但請確保您正確處理空值。地圖中可能沒有一個鍵比輸入小很多！如果您嘗試向BigDecimal添加空引用，則會拋出NullPointerException。

來源

2014-02-07 16:54:16 Pyranja

找到下一個最小的鍵（需要性能建議）

回答

相關問題