Огромная разница в производительности между Vector и HashSet

Question

У меня есть программа, которая выбирает записи из базы данных (используя Hibernate) и заполняет их в Vector. Возникла проблема с производительностью операции, и я провел тест с заменой Vector на HashSet. С 300000 записей, увеличение скорости огромно - от 45 минут до 2 минут!

Итак, мой вопрос: что вызывает эту огромную разницу? В том-то ли дело, что все методы в Vector синхронизированы, или в том, что внутренне Vector использует массив, а HashSet - нет? Или что-то еще?

Код выполняется в одном потоке.

EDIT : Код только вставляет значения в Vector (а в другом случае HashSet).

Answer 1

Если он пытается использовать Vector в качестве набора и проверяет наличие записи перед ее добавлением, тогда заполнение вектора становится операцией O (n ^ 2) по сравнению сO (n) для HashSet.Это также станет операцией O (n ^ 2), если вы вставите каждый элемент в начале вектора, а не в конце.

Если вы просто , используя collection.add(item)тогда я не ожидал бы увидеть такую ​​разницу - синхронизация не , что медленная.

Если вы можете попробовать протестировать ее с различным количеством записей, вы можете увидеть, как каждаяверсия увеличивается с увеличением n - это облегчило бы понимание того, что происходит.

РЕДАКТИРОВАТЬ: Если вы просто используете Vector.add, то это звучит так, как будто что-то еще может происходить - например, ваша база данных былавести себя по-разному между различными тестами.Вот небольшое тестовое приложение:

import java.util.*;

public class Test {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Vector<String> vector = new Vector<String>();
    for (int i = 0; i < 300000; i++) {
      vector.add("dummy value");
    }
    long end = System.currentTimeMillis();
    System.out.println("Time taken: " + (end - start) + "ms");
  }
}

Вывод:

Время выполнения: 38 мс

Теперь, очевидно, это будет не очень точно- System.currentTimeMillis не лучший способ получить точное время - но это явно не занимает 45 минут.Другими словами, вам следует искать проблему в другом месте, если вы действительно просто звоните Vector.add(item).

Теперь измените код выше, чтобы использовать

vector.add(0, "dummy value"); // Insert item at the beginning

имеет огромное значение - это 42 секунд вместо 38 мс.Это явно намного хуже - но это еще далеко от 45 минут - и я сомневаюсь, что мой рабочий стол в 60 раз быстрее вашего.

Answer 2

Вектор устарел и больше не должен использоваться. Профиль с ArrayList или LinkedList (зависит от того, как вы используете список), и вы увидите разницу (синхронизация против несинхронизации). Почему вы вообще используете Vector в однопоточном приложении?

Answer 3

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

Answer 4

import java.util.*;

public class Test {
  public static void main(String[] args) {
    long start = System.currentTimeMillis();
    Vector<String> vector = new Vector<String>();
    for (int i = 0; i < 300000; i++) {
       if(vector.contains(i)) {
         vector.add("dummy value");
       }
     }
    long end = System.currentTimeMillis();
    System.out.println("Time taken: " + (end - start) + "ms");
  }
}

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

Answer 5

При нормальных обстоятельствах абсолютно неправдоподобно , что вставка 300 000 записей в Vector займет на 43 минуты больше времени, чем вставка тех же записей в HashSet.

Однако,Я думаю, что есть возможное объяснение того, что может происходить.

Во-первых, записи, поступающие из базы данных, должны иметь очень высокую долю дубликатов.Или, по крайней мере, они должны быть дубликатами в соответствии с семантикой методов equals / hashcode вашего класса записей.

Далее, я думаю, вы должны быть очень близки к заполнению кучи.

Таким образом, причина того, что решение HashSet намного быстрее, заключается в том, что большинство записей заменяется на операцию set.add.В отличие от этого, решение Vector хранит все записи, и JVM тратит большую часть своего времени, пытаясь сжать эту последнюю 0.05% памяти, запуская GC снова и снова и снова.

Один из способов проверить эту теорию - запустить версию приложения Vector с гораздо большей кучей.

---

Независимо от этого, лучший способ исследовать проблему такого рода - запустить приложение с использованиемпрофилировщик и посмотрите, куда уходит все процессорное время.

Answer 6

Вектор синхронизирован по умолчанию; HashSet нет. Это мое предположение. Получение монитора для доступа требует времени.

Я не знаю, есть ли чтения в вашем тесте, но Vector и HashSet оба равны O (1), если get() используется для доступа к записям Vector.

Answer 7

По словам доктора Хайнца Кабуца, он сказал это в одном из своих информационных бюллетеней .

Старый класс Vector реализует сериализацию наивным способом. Они просто выполняют сериализацию по умолчанию, которая записывает весь поток Object[] как есть в поток. Таким образом, если мы вставим несколько элементов в список, а затем очистим его, разница между Vector и ArrayList будет огромной.

import java.util.*;
import java.io.*;

public class VectorWritingSize {
  public static void main(String[] args) throws IOException {
    test(new LinkedList<String>());
    test(new ArrayList<String>());
    test(new Vector<String>());
  }

  public static void test(List<String> list) throws IOException {
    insertJunk(list);
    for (int i = 0; i < 10; i++) {
      list.add("hello world");
    }
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    ObjectOutputStream out = new ObjectOutputStream(baos);
    out.writeObject(list);
    out.close();
    System.out.println(list.getClass().getSimpleName() +
        " used " + baos.toByteArray().length + " bytes");
  }

  private static void insertJunk(List<String> list) {
    for(int i = 0; i<1000 * 1000; i++) {
      list.add("junk");
    }
    list.clear();
  }
}

Когда мы запускаем этот код, мы получаем следующий вывод:

LinkedList used 107 bytes
ArrayList used 117 bytes
Vector used 1310926 bytes

Vector может использовать ошеломляющее количество байтов при сериализации. Урок здесь? Никогда не используйте Вектор как списки в объектах, которые можно сериализировать . Потенциал для катастрофы слишком велик.