Двоичный поиск по определенной части строки

Question

Это строка 9*8*0.01548, которая находится в ArrayList<String>. Мне нужен двоичный поиск на основе значения Double i.e 0.01548, чтобы найти точное совпадение для значения поиска. ArrayList содержит около 1 миллиона записей. Split не кажется хорошим вариантом с точки зрения оптимизации. Я пробовал следующий код, хотя он не работает, потому что среднее значение списка вычисляется на основе размера списка 3. Бинарный поиск сам по себе прекрасно, я просто добавить для ясности вопроса, если только Double значения в arrayListvalues то бинарный поиск работает нормально

1. Каковы возможные альтернативы?
2. Как это сделать?

Ниже:

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 со строками ; если у вас будет миллион + записей; и вам нужно быстро взять партию?

Почему бы не сделать предварительное вычисление: при получении первоначальных записей; разделить их на два списка; один из которых содержит полную строку ... другой содержит только (уже вычисленные и отличные) двойные значения? Heck, если количество объектов не меняется; вы можете даже помещать их в массив (и для миллиона записей стоимость для массива [double] разумнее меньше, чем для ArrayList).

Смысл: иногда это пустая трата времени, чтобы попытаться построить «эффективные» алгоритмы вокруг плохо представленных данных. Вместо этого измените представление данных так, чтобы вы могли эффективно его обрабатывать ...

Конечно, это зависит от того, как часто ... изменения данных ... данные должны быть (пересчитаны) ... те происходит поиск. Просто говорю, что вы не должны фокусироваться на «правильном поиске».

Answer 2

Бинарный поиск работает только для списков, если элементы упорядочены по тому же найденному свойству. Таким образом, поиск будет работать только: , если список сортируется по последнему значению в каждом String (значение с плавающей запятой).

Следующая проблема заключается в том, что соответствующее значение для сортировки/поиска является последним элементом списка, что делает конструкцию Comparator для двоичного поиска довольно сложной задачей. Самый быстрый подход (с точки зрения времени выполнения) заключается в создании собственного цикла для сравнения и реорганизации строк таким образом, чтобы обеспечить более быстрое сравнение. Например, вместо "9 * 8 * 0.01548" используйте "0.01548 * 9 * 8" для ускорения поиска вверх.