首页 文章

二进制搜索String的特定部分

提问于
浏览 次
1

这是一个字符串 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));
}
java string binary-search string-split

2 回答

  • 1

    考虑在这里更改核心元素：为什么要使用带有字符串的ArrayList;如果你有一百万条款;你需要快速取双打吗？

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

    含义：有时候尝试围绕表示不佳的数据构建“高效”算法是浪费时间 . 相反，更改数据的表示，以便您可以有效地处理它...

    当然，这取决于......数据变化的频率......数据需要（重新）计算......这些搜索发生 . 只是说你不应该专注于“正确搜索” .

    回复于
  • 1

    二进制搜索仅适用于列表，如果元素按搜索的相同属性排序 . 因此搜索只会起作用， if 列表按每个 String 中的最后一个值（浮点值）排序 .

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

    回复于

相关问题