字符串特定部分的二進制搜索

這是一個字符串9*8*0.01548它在ArrayList<String>。我需要基於Double值進行二分搜索，例如0.01548以找到搜索值的近似匹配。 ArrayList包含大約100萬條記錄。 Split在優化方面似乎不太好。我嘗試了下面的代碼，但它不工作，因爲列表中間值是基於列表大小3計算的。二進制搜索本身是好的我只是增加對問題的清晰，如果只是Double值在arrayListvalues然後二進制搜索做工精細字符串特定部分的二進制搜索

什麼是可能的替代方案？
如何使其工作？

下面是：

public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) { 
int low, high, med, comp; 
     T temp; 
     high = list.size(); 
     low = 0; 
     med = (high + low)/2; 

     while (high != low + 1) { 
      temp = list.get(med); 
      comp = compare.compare(temp, key); 

      if (comp == 0) { 
       return med; 
      } else if (comp < 0) { 
       low = med; 
      } else { 
       high = med; 
      } 

      med = (high + low)/2; 
     } 

     return med; 
    }

比較

public static class doubleComparator implements Comparator<String> { 

@Override 
     public int compare(String s1, String s2) { 
      String[] d1 = s1.split("*"); //this 
      String[] d2 = s2.split("*"); //that 
      if (Double.parseDouble(d1[2]) < Double.parseDouble(d2[2])) { 
       return -1; 
      } else if (Double.parseDouble(d2 [2]) > Double.parseDouble(d2[2])) { 
       return 1; 
      } else { 
       return 0; 
      } 
     } 
    }

主要

public static void main(String[] args) { 
ArrayList<String> strArray= new ArrayList<String>(); 
     strArray.add("1*2*0.1"); 
     strArray.add("3*4*0.5"); 
     strArray.add("5*6*0.6"); 
     strArray.add("7*8*0.7"); 
     strArray.add("9*10*0.8"); 
     strArray.add("11*12*0.9"); 
     int key = binarySearch(strArray, "45*60*0.3", new doubleComparator()); 
     System.out.println("Search for "45*60*0.3:"\tKey:" + key + "\tValue:" + strArray.get(key)); 
}

來源

2015-10-18 Jamal

考慮在這裏改變的核心要素：爲什麼你想要使用的字符串的ArrayList ;如果你將有一百萬條記錄;你需要快速獲取雙打？

爲什麼不做預先計算：當您獲取您的初始記錄;將它們分成兩個列表;一個包含完整的字符串...另一個僅包含（已經計算和投射的）double值？哎，如果物體的數量沒有變化，你甚至可以把它們放在一個數組中（並且對於一百萬個條目，數組[double]的成本比ArrayList的成本要小）。

含義：有時試圖圍繞代表性較差的數據構建「高效」算法是浪費時間。相反，改變數據的表示，以便您可以有效地處理它...

當然，這取決於多久...數據更改...數據需要（重新）計算......那些搜索發生。只是說你不應該專注於「讓搜索正確」。

來源

2015-10-18 21:41:12 GhostCat

同意第二點'爲什麼不做預先計算'。謝謝！ – Jamal

二元搜索僅適用於列表，如果元素是由搜索的相同屬性排序的。因此，搜索將僅工作，如果該列表按每個String（浮點值）中的最後一個值排序。

接下來的問題是簡單的事實，即排序/搜索的相關值是列表的最後一個元素，因此二進制搜索的Comparator的構建相當困難。最快的方法（就運行時而言）將是構建自己的比較循環，並以允許更快比較的方式重新組織字符串。例如：而不是"9 * 8 * 0.01548"，請使用"0.01548 * 9 * 8"加快搜索速度。

來源

2015-10-18 21:42:19 Paul

字符串特定部分的二進制搜索

回答

相關問題