Просматривая Programcreek, я наткнулся на несколько очень подробных, но бесценных тем. Например: как проверить, содержит ли массив Java определенное значение? Подобные душераздирающие темы заслуживают более пристального внимания.
Кроме того, я хочу вам сказать, что мы, программисты, не должны недооценивать эти базовые знания. Поскольку баллы базовых знаний являются общей основой различных технологий верхнего уровня, только досконально освоив эти баллы базовых знаний, мы сможем лучше понять принцип работы программы и сделать более оптимизированные продукты.
яОднажды я поделился очень простой статьей на техническом форуме, но меня бесчисленное количество раз высмеивали: «Такой статьей о воде не стоит делиться». , но он оставил много следов в блогах других людей, большинство из которых циничны. Мне просто интересно, не должны ли все технические специалисты быть такими же сдержанными и скромными, как я? Как можно быть таким враждебным!
Ладно, приступим к делу. Как проверить, содержит ли массив (несортированный) определенное значение? Это очень полезная и часто используемая операция. Я думаю, что есть несколько решений, которые всплыли в голове у каждого, и временная сложность этих решений может быть очень разной.
Позвольте мне сначала предоставить четыре различных метода, давайте посмотрим, насколько они эффективны.
1) Использовать список
public static boolean useList(String[] arr, String targetValue) {
return Arrays.asList(arr).contains(targetValue);
}
В классе массива есть внутренний класс класса.Arrays.asList(arr)создать экземпляр), которыйcontains()Исходный код метода показан ниже.
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
E[] a = this.a;
if (o == null) {
for (int i = 0; i < a.length; i++)
if (a[i] == null)
return i;
} else {
for (int i = 0; i < a.length; i++)
if (o.equals(a[i]))
return i;
}
return -1;
}
Как видно из исходного кода выше,contains()метод называетсяindexOf()метод, если он возвращает -1, это означает, что ArrayList не содержит указанный элемент, иначе содержит. вindexOf()Метод используется для получения нижнего индекса элемента в ArrayList. Если элемент имеет значение null, используйте для оценки оператор "==", в противном случае используйтеequals()метод судить.
PS: Что касается оператора "==" иequals()метод, вы можете обратиться к другой моей статье "Как сравнить строки в Java?》
2) Использовать набор
public static boolean useSet(String[] arr, String targetValue) {
Set<String> set = new HashSet<String>(Arrays.asList(arr));
return set.contains(targetValue);
}
HashSet на самом деле реализуется через HashMap, при использованииnew HashSet<String>(Arrays.asList(arr))После создания и инициализации объекта HashSet значение массива фактически помещается в ключ HashMap, но значение HashMap является отображаемым объектом по умолчанию. Если вам интересно, вы можете проверить исходный код HashSet.
Давайте сосредоточимся на HashSetcontains()Исходный код метода.
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
Как видно из исходного кода выше,contains()Метод вызывает HashMapcontainsKey()Метод, который возвращает значение true, если указанный элемент находится в ключе HashMap; в противном случае — значение false.
3) Используйте простой цикл
public static boolean useLoop(String[] arr, String targetValue) {
for (String s : arr) {
if (s.equals(targetValue))
return true;
}
return false;
}
используется в цикле for-eachequals()Метод оценки. Этот код напоминает мне несколько слов, а именно: простота, эффективность и ясность.
4) ИспользованиеArrays.binarySearch()
public static boolean useArraysBinarySearch(String[] arr, String targetValue) {
int a = Arrays.binarySearch(arr, targetValue);
if (a > 0)
return true;
else
return false;
}
но,binarySearch()Подходит только для поиска уже отсортированных массивов.
Поскольку мы не уверены, что массив уже отсортирован, давайте сравним временную сложность первых трех методов. Поскольку время одного звонка слишком мало, чтобы быть статистически значимым, мы моделируем вызов 100 000 раз.Конкретный тестовый код выглядит следующим образом.
String[] arr = new String[]{"沉", "默", "王", "二", "真牛逼"};
// 使用 List
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useList(arr, "真牛逼");
}
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("useList: " + duration / 1000000);
// 使用 Set
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useSet(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useSet: " + duration / 1000000);
// 使用一个简单的循环
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useLoop(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useLoop: " + duration / 1000000);
PS:nanoTime()Получение осуществляется в наносекундах, чтобы время расчета было более точным, и, наконец, деление на 1000000 составляет миллисекунды. Единицы преобразования следующие: 1 секунда = 1000 миллисекунд, 1 миллисекунда = 1000 микросекунд и 1 микросекунда = 1000 наносекунд.
Статистические результаты следующие:
useList: 6
useSet: 40
useLoop: 2
Если мы увеличим длину массива до 1000, давайте снова посмотрим на статистику.
String[] arr = new String[1000];
Random s = new Random();
for(int i=0; i< 1000; i++){
arr[i] = String.valueOf(s.nextInt());
}
В искомом массиве нет ни одного элемента. Для сравнения мы кстати добавили бинарный поиск в пункт статистики.
// 使用二分查找
startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
useArraysBinarySearch(arr, "真牛逼");
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("useArraysBinarySearch: " + duration / 1000000);
Статистические результаты следующие:
useList: 91
useSet: 1460
useLoop: 70
useArraysBinarySearch: 4
Затем мы корректируем длину массива до 10000.
String[] arr = new String[10000];
Random s = new Random();
for(int i=0; i< 10000; i++){
arr[i] = String.valueOf(s.nextInt());
}
Статистические результаты следующие:
useList: 1137
useSet: 15711
useLoop: 1115
useArraysBinarySearch: 5
Из приведенных выше статистических результатов очевидно, что использование простого цикла for более эффективно, чем использование List и Set. Это связано с тем, что чтение элементов из массива и добавление их в коллекцию занимает определенное время, а простой цикл for экономит эту часть времени.
Прежде чем прийти к этому выводу, если честно, мой любимый способ — это первый «использовать список», потому что требуется только одна строка кода.Arrays.asList(arr).contains(targetValue)Просто сделай это.
Хотя бинарный поиск (Arrays.binarySearch()) занимает значительно меньше времени, но этот вывод не заслуживает доверия. Потому что бинарный поиск явно требует, чтобы массив был отсортирован, иначе результаты поиска бессмысленны. Взгляните на официальный Javadoc.
Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the natural ordering of its elements (as by the sort(Object []) method) prior to making this call. If it is not sorted, the results are undefined.
Фактически, чтобы эффективно определить, существует ли значение в массиве или коллекции, алгоритмическая сложность отсортированного списка составляетO(logn), в то время как HashSetO(1).
Давайте снова погрузимся в размышления: как понятьO(logn)иO(1)Шерстяная ткань?
O(logn)Сложность алгоритма , типичным примером является бинарный поиск. Например, предположим, что стопка контрольных работ расставлена в порядке убывания баллов. Теперь я хочу узнать, есть ли контрольная работа на 79 баллов, что мне делать? Можно начинать сначала со среднего, так как по 100-балльной работе разница между 79 баллами должна быть в средней позиции (если средний балл ниже 79, значит, хороших учеников меньше). Оценка среднего листа: Если он равен 83, это означает, что лист с 79 баллами находится в нижней половине, а верхнюю половину можно отложить в сторону. Затем повторяйте то же самое, каждый раз начиная с середины, пока не найдете 79-балльную бумагу (конечно, 79-балльной оценки может и не быть).
Если бумаг 56, ищите один раз, осталось 28 экземпляров, ищите снова, осталось 14 экземпляров, снова ищите, осталось 7 экземпляров, ищите снова, осталось 2 или 3 экземпляра. Если 2 копии, ищите еще раз, и осталась только 1 копия, если 3 копии, нужно искать еще 2 раза.
мы знаем, журнал2(32) = 5, лог.2(64) = 6, а 56 находится между 32 и 64. То есть бинарный поиск занимает около log2(n) раз до «найдено» или «не найдено». В сложности алгоритма константы часто игнорируются, поэтому независимо от того, является ли это основанием 2 или основанием 3, оно записывается в виде log (n).
Давай поговорим об этомO(1), типичным примером является хэш-таблица (HashSet реализуется HashMap). Хэш-таблицы отображаются с помощью хэш-функций, поэтому, если вы получите ключевое слово и преобразуете его с помощью хеш-функции, вы сможете напрямую получить соответствующее значение из таблицы — один прямой доступ.
Ну что же, читатели и друзья, вышеизложенное и есть все содержание этой статьи.Все, что вы можете здесь увидеть, это таланты, второй брат должен дать вам большой палец вверх👍. Если вам это не нравится и вы хотите увидеть больше, я порекомендую вам еще несколько статей.
Душевная пытка: как работает Java substring()?
Пытка души: почему строки Java неизменяемы?
Душевная пытка: создайте строку Java, используйте "" или конструктор
Если у вас есть какие-либо вопросы и вам нужна моя помощь или вы хотите распылить меня, пожалуйста, оставьте сообщение.
сформировать хорошую привычку! Если вы нашли эту статью полезной,Ставьте лайки, подписывайтесь, делитесь, оставляйте сообщения, это будет сильнейшей мотивацией для меня написать! Если вы хотите впервые увидеть обновленные статьи второго брата, вы можете отсканировать QR-код ниже, подписаться на мою официальную учетную запись, ответить на «java» и отправить вам подарочный пакет избранных электронных книг, включая 10 лет I прочитал лучшую книгу по Java. До встречи в нашей следующей статье!