Как разработчик программного обеспечения, вы должны понимать, как наилучшим образом использовать свое оборудование, чтобы предоставить пользователю наилучшие возможности работы с вашей программой. Чтобы сделать это, вам нужно знать, как писать эффективный код и как писать исполняющий код.
(Я смотрел это видео cppCon, предоставленное Чендлером Каррутом, которое помогло мне понять эти концепции.)
- Эффективность — объем работы, который вам нужно сделать.
- Производительность — как быстро вы можете сделать эту работу
- Эффективность — зависит от вашего алгоритма
- Производительность — зависит от ваших структур данных.
Эффективность и производительность не зависят друг от друга.
Из этого следует, что вы можете быть эффективными, не проявляя при этом производительности, вы выполняете очень мало работы, чтобы выполнить работу, но выполняете ее медленно, например, вы улитка и вам нужно пройти 10 метров от точки X до Y. Вы выбираете самый прямой маршрут, но скользите чрезвычайно медленно.
Из этого также следует, что вы можете быть эффективными, не будучи эффективными, вы выполняете много работы, чтобы выполнить работу, но делаете это очень быстро, например, вы супермен и вам нужно проехать 10 м от X до Y. Вы летите прямо вокруг земного шара, чтобы получить там, но идти очень быстро.
То, к чему мы, конечно, стремимся, — это быть эффективными и эффективными одновременно!
Эффективность наших алгоритмов обычно измеряется с помощью системы обозначений Big O, которая измеряет масштаб алгоритма в зависимости от размера ввода. На уроках информатики нас учат стремиться к Святому Граалю O (1) и пугаться, когда мы видим O ( n 2 ) или хуже.
На чем мы фокусируемся меньше, так это на самом деле, как работает алгоритм. Одной из самых больших проблем, влияющих на производительность, является то, как данные хранятся в структуре данных. Вообще говоря, мы хотим, чтобы данные, которые используются вместе, хранились близко друг к другу в памяти, чтобы не допустить промахов кэша ЦП. (См . Первое правило оптимизации производительности, где я затрагиваю эту проблему). Если мы получим доступ к данным предсказуемым образом, аппаратное обеспечение будет предварительно извлекать данные для нас в кэш, что может сэкономить огромное количество времени за счет случайного доступа к данным со всей памяти и извлечения их в кэш-память «по мере необходимости». ,
Один из худших виновников — старый добрый LinkedList. Он имеет O (n) для доступа и поиска и в сочетании с O (1) для вставки и удаления, может считаться очень хорошей структурой данных для использования в программе. Хотя, конечно, я не списываю эту важную структуру данных, проблема в том, что связанные узлы не удерживаются вместе в памяти, и поэтому это не самая производительная структура данных для прохождения, поскольку вы не можете не получить много дорогого кеша промахов.
Возможно, лучший пример различия и компромисса между эффективностью и производительностью рассматривает алгоритмы сортировки.
Нас учат, что пузырчатого типа следует избегать любой ценой. В конце концов, это O (n ^ 2). Мы должны скорее пойти на двоичную сортировку, которая приходит с гораздо более приемлемым O (n log (n)).
Однако, чтобы быть эффективными, вам иногда приходится платить накладные расходы, которые замедляют вас в краткосрочной перспективе. Например, если вам нужно отредактировать кучу файлов, вы можете сделать это вручную, один за другим. В качестве альтернативы вы можете потратить время на создание сценария для редактирования. В какой-то момент дополнительная работа по редактированию вручную будет медленнее, чем создание сценария.
Пузырьковая сортировка является производительной, она выполняет свою работу очень быстро, она не платит штраф за то, что двоичная сортировка платит, чтобы быть более эффективной для больших объемов. Таким образом, пока мы сохраняем низкие цифры (ниже около 60 пунктов), сортировка по пузырькам будет превосходить любой другой тип поиска.
Фактически, если вы посмотрите на реализацию java.util.Array.sort (), вы найдете в классе java.util.DualPivotQuicksort несколько стратегий сортировки, которые запускаются при разных пороговых значениях. Опять эффективность против производительности.
|
1
2
3
4
5
|
/** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. */private static final int QUICKSORT_THRESHOLD = 286;/** * If the length of an array to be sorted is less than this * constant, insertion sort is used in preference to Quicksort. */private static final int INSERTION_SORT_THRESHOLD = 47;/** * If the length of a byte array to be sorted is greater than this * constant, counting sort is used in preference to insertion sort. */private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29; |
Я написал быстрый тест JMH, который хорошо это демонстрирует.
С 5000 элементов бинарная сортировка с большей эффективностью намного быстрее:
| эталонный тест | Режим | Cnt | Гол | ошибка | Единицы измерения |
|---|---|---|---|---|---|
| Sorter.binarySearchForValue | thrpt | 5 | 90011.861 | ± 6423,543 | OPS / с |
| Sorter.bubbleSort | thrpt | 5 | 114931.583 | ± 6423,543 | OPS / с |
С 50-элементной пузырьковой сортировкой, с большей производительностью быстрее:
| эталонный тест | Режим | Cnt | Гол | ошибка | Единицы измерения |
|---|---|---|---|---|---|
| Sorter.binarySearchForValue | thrpt | 5 | 90011.861 | ± 2051,384 | OPS / с |
| Sorter.bubbleSort | thrpt | 5 | 114931.583 | ± 6423,543 | OPS / с |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
package util;import org.openjdk.jmh.annotations.Benchmark;import org.openjdk.jmh.annotations.Scope;import org.openjdk.jmh.annotations.State;import org.openjdk.jmh.runner.Runner;import org.openjdk.jmh.runner.options.Options;import org.openjdk.jmh.runner.options.OptionsBuilder;@State(Scope.Benchmark)public class Sorter { private static int arraySize = 50; public static int[] theArray = new int[arraySize]; private void randomise(){ for (int i = 0; i < arraySize; i++) { theArray[i] = (int) (Math.random() * 100); } } @Benchmark public void bubbleSort() { randomise(); // i starts at the end of the Array // As it is decremented all indexes greater // then it are sorted for (int i = arraySize - 1; i > 1; i--) { // The inner loop starts at the beginning of // the array and compares each value next to each // other. If the value is greater then they are // swapped for (int j = 0; j < i; j++) { if (theArray[j] > theArray[j + 1]) { //swap the values int temp = theArray[j]; theArray[j] = theArray[(j + 1)]; theArray[(j + 1)] = temp; } } } } @Benchmark public void binarySearchForValue() { randomise(); int value = 50; int lowIndex = 0; int highIndex = arraySize - 1; while (lowIndex <= highIndex) { int middleIndex = (highIndex + lowIndex) / 2; if (theArray[middleIndex] < value) lowIndex = middleIndex + 1; else if (theArray[middleIndex] > value) highIndex = middleIndex - 1; else { lowIndex = highIndex + 1; } } } public static void main(String[] args) throws Exception { Options opt = new OptionsBuilder() .include(Sorter.class.getSimpleName()) .warmupIterations(5) .measurementIterations(5) .threads(4) .forks(1) .build(); new Runner(opt).run(); }} |
Резюме
Хотя обозначение Big O невероятно полезно для прогнозирования эффективности (объема работы) алгоритма, мы также должны обратить внимание на производительность структур данных, с которыми работают эти алгоритмы. В определенных ситуациях менее эффективный, но более производительный алгоритм может привести к большей скорости в целом.
| Ссылка: | Разница между эффективностью и производительностью — это не все о Big O от нашего партнера по JCG Дэниела Шая из блога Rational Java . |