Набор деревьев не добавляет все элементы?

Я изучал скорости различных типов коллекций Java и наткнулся на что-то странное. Я добавляю 1 000 000 объектов из статического массива в другой тип коллекции и возвращаю требуемое время. Эта часть кода работает нормально.

При дальнейшем исследовании я заметил, что TreeSet получает не все из 1 000 000 объектов, а каждый раз получает различное количество. Ниже приведен способ переноса объектов из массива в TreeSet: 
    public int treeSet(int num)
    {
       Date before = new Date();

       for(int i=0; i<num; i++) 
       {
           treeSet.add(personsArray[i]);
       }

       Date after = new Date();
       return (int) (after.getTime() - before.getTime());
    }
Ниже приведен код, который вызывает метод treeSet () и проверяет его размер. 
    System.out.println("tTree set with 1,000,000 objects--" + t.treeSet(1000000));
    System.out.println("Tree set contains " + t.treeSet.size() + " elements");

Выход из этого: 

    Tree set with 1,000,000 objects--1192
    Tree set contains 975741 elements
Я надеюсь, что кто-нибудь сможет объяснить мне, почему TreeSet получает не все объекты и почему он получает несогласованные суммы.
3 3
treeset

3 ответа:

Вы почти наверняка создаете дубликаты объектов человека.

В своем комментарии вы сказали, что каждый человек генерируется случайным образом из пола, имен и фамилий из текстового файла, содержащего "сотни" имен и возраста. Допустим, есть две возможности для секса, 300 возможностей для каждого имени и фамилии и 100 возможных значений возраста. Это в общей сложности 18 000 000 возможных уникальных людей.

Будем далее считать, что equals() реализуется правильно на этом объекте, то есть, что он проверяет все эти поля правильно.

Вы генерируете 1 000 000 уникальных людей, используя случайные характеристики из пространства 18 000 000 возможностей. Интуитивно вы можете подумать, что существует" мизерный " шанс на дубликаты, но вероятность того, что они есть, на самом деле составляет около 1,0 минус Эпсилон. Это известно какпроблема дня рождения или иногда парадокс дня рождения.

Как указано на этой странице, вероятность столкновения между любыми двумя вариантами составляет около

1 - ((d-1) / d) ^ n(n-1)/2

Где d - число значений в области, а n - число сделанных выборов. Я не совсем уверен, но со значениями d = 18,000,000 и n = 1,000,000 я думаю, что это работает примерно 1.0-1E-323 . (EDIT: правильное значение-около 1.0 - 2.84E-12294. Это чертовски близко к истине.)

Ожидаемое число столкновений при таком выборе задается следующей формулой:

N-d + d * ((d-1) / d) ^ n

Если d = 18 000 000 и n = 1 000 000, то получается примерно 27 000. То есть в среднем вы получите 27 000 столкновений. Это очень близко к числу "отсутствующих" элементов в вашем наборе деревьев, и именно так будут проявляться столкновения. Я признаю, что выбрал свои цифры, чтобы приблизиться к тому, что вы видите, но мои предположения и результаты полностью совпадают. правдоподобный.

Вам нужно переосмыслить способ генерации данных, которые вы храните в наборе.

33

С высокой степенью уверенности я могу сказать, что вы добавляете дубликаты в свой TreeSet. если вы мне не верите, просто добавьте цифры к вашим treeSet, Убедитесь, что цифры от 1 до 1000000, и вы увидите, что получите именно то, что ожидаете.

После того, как вы очистили свои сомнения, давайте попробуем отсортировать ваш класс людей.

Добавьте в свой класс People следующее: 

int id;    //ensure that every people object you create has different id. e.g. 1 to 10m;

@override
public boolean equals(Object o){
  if(this.getClass()!=o.getClass()) return false;
  else return (People (o)).id==this.id;
}

@override
public int hashCode(){
 return id;
}

Теперь начните добавлять вещи в свой набор. :)

Примечание этот код является лишь примером простой подход к созданию различных классов людей. Это хороший подход, чтобы сделать некоторые тесты с treeSet и т.д. но это не рекомендуется для реальных проблем

1

Убедитесь, что метод compareTo() в вашем классе People реализован правильно. В Comparable javadoc говорится следующее:

Настоятельно рекомендуется (хотя и не обязательно), чтобы естественные упорядочения были согласуется с равными. Это происходит потому, что сортированные наборы (и сортированные карты) без явных компараторов ведут себя "странно" , когда они используются с элементы (или ключи), чье естественное упорядочение несовместимо с равными. В в частности, такой сортированный набор (или сортированная карта) нарушает генеральный договор для множества (или карты), которое определяется в терминах equals метод.

Например, если добавить два ключа a и b такие, что (!a.equals(b) && a.compareTo(b) == 0) в сортированный множество, которое не использует явный компаратор, второй add операция возвращает false (при этом размер отсортированного набора не увеличивается) потому что a и b эквивалентны из отсортированного множества перспектива.

0