对字符串的特定部分进行二进制搜索

Question

这是 ArrayList<String> 中的字符串 9*8*0.01548。我需要基于 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));
}

Answer 1

考虑更改此处的核心元素：为什么要使用带字符串的 ArrayList；如果您将有超过一百万个条目；你需要快速获取双打？

为什么不做预计算：当你获取初始记录时；将它们分成两个列表；一个包含完整的字符串......另一个只包含（已经计算和转换）双精度值？哎呀，如果对象的数量没有变化；您甚至可以将它们放在一个数组中（对于一百万个条目，array[double] 的成本比 ArrayList 的成本要小得多）。

意思：有时试图围绕表现不佳的数据构建 "efficient" 算法是浪费时间。相反，更改数据的表示，以便您可以有效地处理它......

当然，这取决于...数据更改的频率...数据需要（重新）计算...这些搜索发生的频率。只是说你不应该专注于 "getting that search right".

Answer 2

二分搜索仅适用于列表，前提是元素按与搜索相同的属性排序。因此搜索将只工作，if 列表按每个 String（浮点值）中的最后一个值排序。

下一个问题很简单，sorting/searching 的相关值是列表的最后一个元素，因此为二进制搜索构造 Comparator 非常困难。最快的方法（就运行时而言）是构建自己的比较循环并以允许更快比较的方式重新组织字符串。例如：使用 "0.01548 * 9 * 8" 代替 "9 * 8 * 0.01548" 来加快搜索速度。

对字符串的特定部分进行二进制搜索

Binary Search on specific part of String

java

string

binary-search

string-split