Вычисление максимального/минимального значения из массива наиболее эффективно в java

Question

Я рассматриваю два подхода для вычисления максимума/минимума массива.

Первое:

public class Extrema { 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    double[] arr = new double[] { -0.11112, -0.07654, -0.03902, 0.0, 
      0.03902, 0.07654, 0.11112, 0.14142, 0.1663, 0.18478, 0.19616 }; 
    double max = Double.NEGATIVE_INFINITY; 
    // Find out maximum value 
    for (int i = 0; i < arr.length; i++) { 
     if (arr[i] > max) { 
      max = arr[i]; 
     } 
    } 
} 

} 

Второй подход был бы предварительно сортировки массива, а затем получить обр [0] как минимумы и последнего вхождения тэ массива как максимумов.

как я знаю, самые быстрые алгоритмы сортировки равны 0 (n log n). Петля от первого подхода займет 0 (n). Но с n сравнениями и, в худшем случае, n письменными операциями. Поскольку Time-messurement в java на самом деле не заслуживает доверия, необходимо оформить этот вопрос ... Я бы предпочел Первый метод .. я прав? особенно если мне нужны оба экстремума и, следовательно, нужно < = n² записи-операции. На сколько методов вызовы с тем же массивом, что и предварительная сортировка? наилучшими пожеланиями, Jan

Answer 1

Прежде всего, давая достаточно большой вход, измерение времени вполне возможно.

Во-вторых, в вашем примере кода ни сравнения, ни операции записи не имеют значения. Большинство времени будет потрачено на доступ к большому массиву (весь вопрос относится только к большим массивам, содержащим много миллионов элементов) в памяти и перемещая его в кэш ЦП.

В-третьих, если вы хотите, чтобы оба экстремума, лучше всего их получить, пройдя через ваш массив только один раз. Это соответствует 2 * n сравнению (ничего общего с n^2) и по-прежнему значительно доминирует в доступе к данным массива в памяти.

Если вам нужен максимум/мин одного и того же массива много раз, просто сохраните его и не вычисляйте его каждый раз. Если вам не нужен отсортированный верификатор вашего массива в другом месте (или вы можете его дождаться один раз и повторить, что каждый раз, когда программа запускается), нет необходимости в сортировке для получения min/max.

Answer 2

Первый подход имеет вычислительную сложность O(n) и второй имеет O(n*log(n)) так же, как вы говорите. Имейте в виду, однако, что асимптотическая сложность игнорирует постоянные факторы, поэтому может быть легко, что линейный алгоритм на самом деле медленнее, чем n*log(n). В вашем конкретном случае, однако, вы не можете пойти лучше, чем простая итерация, и это на самом деле лучшее решение.

Еще может быть интересно, что существует линейный алгоритм для нахождения k-го элемента в последовательности, основанной на qsort-разбиении. Этот алгоритм встроен в C++ stl. Если интересно, вы можете посмотреть here.

Если массив никогда не изменяется, и у вас много запросов, первый подход может быть как минимум быстрым, как второй - просто кешируйте значения, найденные в первых запросах.

Answer 3

Просто мысль ..

Независимо алгоритм поиска вы выбираете, вы всегда можете воспользоваться многопоточной. Скажем, например, размер массива = 10, вы можете создать два потока 1. thread-1 выполнит поиск в первой половине массива, 2. Thread-2 выполнит поиск во второй половине массива 3. а затем, наконец, вы сравнить результаты этих двух потоков, чтобы решить результат.

Если вы решили рассмотреть многопоточность, чтобы ускорить поиск, вам придется учитывать пары факторов, таких как оптимальное количество потоков (в результате чего большое количество потоков приведет к тому, что большинство времени будет потрачено на коммутаторы контекста), доступность стека и т. Д. .