Java: .contains и .equals

Question

Я пытаюсь выполнить программу, чтобы сравнить элементы в двух связанных списках друг с другом.Один из способов сделать это - выполнить два цикла for и повторить оба списка, сравнивая каждый элемент в list1 с list2, используя .equals ().Другой способ заключается в том, чтобы просто выполнить итерацию по первому списку и проверить, есть ли list1.contains (list1.get (i)). В документации Java говорится, что .contains выполняет .equals внутри.если это так, как же у меня больше времени для первого по сравнению со вторым?Я неправильно истолковал документацию?Если я сделал, как именно происходит внутреннее сравнение, когда я использую содержит?

            using equals:
            for (int i = 0; i < list_one.size(); i++) {
              for (int j = 0; j < list_one.size(); j++) {
                  if (list_one.get(i).equals(list_two.get(j))) { count++; }

            using contains:
            for (int i = 0; i < list_one.size(); i++) {
                 if (list_two.contains(list_one.get(i)) == true) { count++; }

Answer 1

Реализация contains прекратит итерацию, как только equals вернет true, поэтому она не будет перебирать весь список, если искомый элемент находится где-то в начале списка. Если ваша версия этого не делает, это объясняет, почему она медленнее.

PS: В любом случае время выполнения все равно будет квадратичным. Существуют более разумные способы решения этой проблемы, которые не включают в себя повторение второго списка для каждого элемента в первом списке (например, сначала сортируя два списка или используя набор).

Answer 2

Я думаю, увидев get(i), что вы используете get(j) в обоих циклах. В связанном списке это неэффективно. for (String s1 : list1) for (String s2 : list2) ... должен иметь ту же скорость, что и contains.

Например, get (3) нужно начинать с первого элемента, взять ссылку на следующие три раза. Принимая во внимание, что for-each использует итератор, указывающий на следующий элемент.