LinkedHashMap сложность

Question

У меня есть простая проблема, чтобы найти первый уникальный элемент в массиве А. Но меня беспокоит сложность времени с использованием разных методов. Я пробовал эти два метода до сих пор.

Первый способ:

LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>(); 
for (int i = 0; i < A.length; i++) 
{ 
    if (!map.containsKey(A[i])) 
     map.put(A[i], new ArrayList<>()); 
    map.get(A[i]).add(i); 
} 

for (Map.Entry<Integer, List<Integer>> m : map.entrySet()) 
    if (m.getValue().size() == 1) 
     return m.getKey(); 
return -1; 

Второй метод:

for(int i=0; i< A.length; i++){ 
     boolean unique = true; 
     nestedFor:for(int j=0; j< A.length; j++){ 
      if(i != j && A[i] == A[j]){ 
       unique = false; 
       break nestedFor; 
      } 
     } 
     if(unique) 
      return A[i]; 
    } 
    return -1; 

Тестирование с массивом элементов 1000000, первый метод выполняет на ~ 2000 мс, а второй при ~ 10ms. Мой вопрос: не должен ли первый метод выполняться быстрее, так как его сложность O (nLogn) по сравнению со вторым методом, сложность которого равна O (n^2)? Что мне здесь не хватает? Ниже тестовый код:

int[] n = new int[1000000]; 
    for (int i = 0; i < n.length; i++) 
     n[i] = new Random().nextInt(2000000); 

    long start = System.currentTimeMillis(); 
    firstUnique(n); 
    System.err.println("Finished at: " + (System.currentTimeMillis() - start) + "ms"); 

EDIT:

for (int i = 0; i < A.length; i++) 
{ 
    if (!map.containsKey(A[i])) 
     map.put(A[i], new ArrayList<>()); 
    map.get(A[i]).add(i); 
} 

Потребляет 99% времени выполнения, в то время как

for (Map.Entry<Integer, List<Integer>> m : map.entrySet()) 
    if (m.getValue().size() == 1) 
     return m.getKey(); 

всегда 1-3ms. Итак, да, заполнение карты является самой дорогой операцией.

Что вы предложите как наиболее эффективный метод для такого рода проблем?

Answer 1

Я подозреваю, что вы не выбираете входы, которые создают условия «наихудшего случая» для второго случая.

Например, если вы построить массив таким образом, что все миллион элементов имеют дубликат (например A[i] = 2 * i/A.length), то второй метод является путь, путь медленнее, чем первый, так как он должен проверить 10^12 комбинации элементов.

Вы можете сделать это немного быстрее (примерно в два раза быстрее), изменив условие на внутренний цикл, чтобы проверять только j = i + 1, но 10^12/2 по-прежнему довольно большое число.

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

---

2 секунды, взятые для первого метода, слишком длинны. Я могу только думать, что вы не разогреваете свой JIT правильно до теста. Но даже не пытаясь сделать это, ваш первый метод займет у меня 40-50 мс (после нескольких итераций выпадает до 10-15 мс).

Большая часть этого времени будет связана с созданием объекта - как при автообношении ключей и значений, так и при создании экземпляров ArrayList.

Answer 2

Мои наблюдения: Второй способ намного быстрее, потому что он использует Array с объявленной шириной. В первом примере происходят изменения в размерах.

Пожалуйста, попробуйте определить более точный размер LinkedHashMap установить первоначальную мощность, равную 1000000.

Следующая вещь здесь является то, что массив гораздо проще структура, где GC не пытается сделать что-нибудь. Но когда дело доходит до LinkedHashMap, его более сложные и затраты на его создание и манипулирование в некоторых случаях намного сложнее, чем простой элемент получения по конкретному индексу от Array.

Answer 3

Сложность времени игнорирует коэффициенты, потому что часто полезно знать, как функция растет с увеличением размеров ввода. Хотя ваша первая функция имеет более низкую временную сложность, при небольших размерах ввода она будет работать намного медленнее, потому что вы делаете много объектов ArrayList, что является дорогостоящим по вычислительной технологии. Однако ваш второй метод использует только обращения к массиву, что намного дешевле, чем создание экземпляра объекта.

Answer 4

Сложность времени должна пониматься в ее асимптотическом смысле (т. Е. При увеличении входных размеров до googolplex) и ничего больше. Если алгоритм имеет линейную временную сложность, это означает только то, что существует некоторое a, b такое, что время выполнения (примерно !!!) = a * вставляет + b. Он ничего не говорит о фактической величине a и b, и два линейных алгоритма могут по-прежнему иметь большие различия в производительности, поскольку величины их a/b существенно различаются.

(Кроме того, ваш пример является плохим, так как временная сложность алгоритма должна учитывать сложность всех основных операций, таких как создание объекта и т. П. Другие также намекают на это в своих ответах.)

Answer 5

Рассмотрите возможность использования 2 комплекта вместо:

public int returnFirstUnqiue(int[] a) 
{ 
    final LinkedHashSet<Integer> uniqueValues = new LinkedHashSet<Integer>(a.length); 
    final HashSet<Integer> dupValues = new HashSet<Integer>(a.length); 

    for (int i : a) 
    { 
    final Integer obj = i; 
    if (!dupValues.contains(obj)) 
    { 
     if (!uniqueValues.add(obj)) 
     { 
     uniqueValues.remove(obj); 
     dupValues.add(obj); 
     } 
    } 
    } 

    if (!uniqueValues.isEmpty()) 
    { 
    return uniqueValues.iterator().next(); 
    } 
    return -1; 
} 

Answer 6

Во-первых, почему тест не имеет значения:

• Даже если мы будем игнорировать погрешности, вызванные используемым методом ГХ и т.д., выясняя что метод 2 быстрее на миллион записей не скажет вам ничего о том, как он будет работать на миллиард записей
  • Big-O - теоретическая концепция и должна быть доказана теоретикой чески.Большинство эталонных тестов для вас здесь позволяют оценить сложность, и это будет сделано не путем сравнения двух методов на одном входе, а путем сравнения одного метода с несколькими входами, каждый на порядок превышающий предыдущий (и даже то это практически невозможно сделать какие-либо полезные выводы)
• Big-O является наихудшим сложности, но ваш случайный вход, вероятно, будет где-то «в середине» для первого метода (карта), в то время как это будет далеко не наихудший случай для массива - на самом деле у него есть 50% вероятность успеха на первой итерации, в то время как карта должна быть полностью обработана и в среднем будет иметь около полумиллиона записей.
  • самым худшим для метода «карты» будет, вероятно, все элементы разные, но с одинаковым хэш-кодом (поэтому вам нужно будет прочитать весь список добавленных элементов в каждой из n итераций)
  • наихудший случай для «массива» "метод все элементы равны (нужно завершить всю вложенную итерацию)

---

Как найти хороший алгоритм - вы могли бы использовать Map<Integer, Boolean> вместо Map<Integer, List<Integer>, так как вам нужно только сохранить уникальный флаг, а не список значений - добавьте с True, когда увидите элеменов т первый раз, переключиться на False, когда вы столкнулись с двуличия

• LinkedHashMap операции put, containsKey/get имеют большой-O сложность O (N) (в худшем случае), что делает весь алгоритм O (N^2)
• Однако амортизируется сложность из put представляет собой о (1) (изготовление амортизируется сложность всех вставок O (N)) и средняя сложность get постоянна (это зависит от того, насколько хорошо хэш-функция используются работы для введенных данных); уникальный поиск по значению - это то, что O (n)