Является ли вызов содержит () для массива неэффективным? - PullRequest
Новая
       58

Является ли вызов содержит () для массива неэффективным?

0 голосов
/ 27 ноября 2018

Мы используем программное обеспечение, чтобы заботиться о качестве кода, и из того, что я сегодня увидел, можно сказать, что вызов contains() для массива неэффективен.И предлагаемый способ (возможно, лучше) - использовать HashSets .

Итак, в отношении этого программного обеспечения это: 

boolean doesContain = (new HashSet<>(arrayList)).contains("something");

более эффективно, чем это: 

boolean doesContain = arrayList.contains("something");

Может ли это быть на самом деле, и если да, то почему?

Ответы [ 2 ]

0 голосов
/ 27 ноября 2018

new HashSet<>(arrayList) занимает O (n) время и O (n) пробел для построения HashSet.

hashSet.contains("something") занимает O (1) время для поиска элемента.

arrayList.contains("something") занимает O (n) время для поиска элемента.

В результате:

(new HashSet<>(arrayList)).contains("something") занимает O (n) + O (1) = O (n) время + O (n) пробел сложность

arrayList.contains("something") занимает O(n) время + 0 пробел сложность

Это означает, что согласно Big O нотации оба выражения имеют O (n) время сложность, но arrayList.contains("something") не занимает дополнительного места вместо вновь созданного HashSet.

PS

В других случаях я не делаю никаких прогнозов, потому что я не знаю других связанных аспектов вашего приложения,Я анализирую только данный фрагмент кода.

0 голосов
/ 27 ноября 2018

Потенциально.Чтобы проверить, есть ли элемент в списке, мы должны последовательно проверять каждый элемент.

Является ли элемент 0 элементом, который мы ищем?Да / нет
Является ли элемент 1 элементом, который мы ищем?Да / нет
...
и т. Д.

Очевидно, вы можете прекратить итерацию, как только найдете ее.

Сложность:

  • Лучший случай: это первый элемент.Это постоянный поиск по времени.O (1)
  • Средний случай: где-то посередине.O (n / 2)
  • В худшем случае: это последний элемент.Мы должны сделать сравнение для каждого элемента.O (n)

HashSet - это всегда поиск с постоянным временем.Вы просто вычисляете хеш-код и вызываете Object::equals.

Относительно того, следует ли использовать набор, оно действительно зависит от того, для чего вы его еще используете.Если вы только делаете contains, набор является наиболее подходящим.В противном случае см. Какую коллекцию Java следует использовать?

...