Удалить дубликаты из большого целочисленного массива, используя Java

Question

Известен ли вам какой-нибудь эффективный по времени способ удаления дублированных значений из очень большого целочисленного массива с использованием Java?Размер массива зависит от пользователя, вошедшего в систему, но всегда будет превышать 1500000 несортированных значений с некоторыми дубликатами.Каждое целое число содержит число от 100000 до 9999999.

Я пытался преобразовать его в список, но куча на моем сервере не позволяет этот объем данных (мой провайдер ограничил его).И обычный цикл for внутри цикла for занимает более 5 минут.

Размер массива без дубликатов тот, который я буду хранить в моей базе данных.

Помощь будет принята!

Answer 1

Вы могли бы использовать набор битов?Я не знаю, насколько эффективен Java BitSet.Но 9999999 возможных значений будут принимать только 9999999/8 = 1250000 байт = чуть более 1 МБ.При прохождении массива значений установите соответствующий бит в значение true.Затем вы можете пройтись по установленному биту и вывести соответствующее значение всякий раз, когда обнаружите, что бит установлен в значение true.

1 МБ уместится в кэш ЦП, поэтому это может быть весьма эффективным в зависимости от реализации набора битов.

У этого также есть побочный эффект сортировки данных.

И ... это алгоритм O (n), так как он требует одного прохода над входными данными, операций набораравны O (1) (для такого набора на основе массива), и выходной проход также равен O (m), где m - количество уникальных значений и, по определению, должно быть <= n. </p>

Answer 2

Set<Integer> set = new HashSet<Integer>();
Collections.addAll(set, array);

вам просто понадобится массив Integer[] вместо int[].

Answer 3

Я бы сделал хешсет, в котором я храню все значения, содержащиеся в списке, прежде чем я начну добавлять элементы в список. Затем просто проверьте, не содержит ли хешсет значение, которое вы хотите добавить.

Answer 4

Вы можете сначала попытаться отсортировать массив:

int arr[] = yourarray;
Arrays.sort(arr);
// then iterate arr and remove duplicates

Answer 5

По-настоящему отчаявшийся мог записать массив на диск и отключить sort | uniq | wc -l <infile.txt и захватить вывод. Это понадобится, если память все еще будет слишком тесной или доменное пространство целых чисел увеличится. Мне это не нравится (он даже работает под Unix!), Но я хочу сказать, что есть много способов выполнить задачу.

Другое наблюдение состоит в том, что минимальное значение составляет 100 000. Таким образом, мы можем вычесть 100 000 из максимального значения 9 999 999, сократив пространство домена и, таким образом, сэкономив немного памяти. Возможно, 100k / 8 битов - это арахис в схеме вещей, но это по сути бесплатно.

Answer 6

int[] a;
Arrays.sort(a);
int j = 0;
for (int i = 1; i < a.length; ++i) {
  if (a[i] != a[j]) {
    ++j;
    a[j] = a[i];
  }
}
// now store the elements from 0 to j (inclusive - i think)

Answer 7

Если вы уверены, что целые числа имеют разумно малые значения (например, всегда больше нуля и меньше 1000 или 10000), вы можете попробовать такой трюк:

    final int MAX = 100; 
    int[] arrayWithRepeats = {99, 0, 10, 99, 0, 11, 99};

    //we are counting here integers with the same value
    int [] arrayOfValues = new int[MAX+1];
    int countOfUniqueIntegers = 0;
    for(int i : arrayWithRepeats) {
        if(arrayOfValues[i] == 0) {
            countOfUniqueIntegers++;
        }
        arrayOfValues[i]++;
    }

    // you can use arrayOfValues (smaller) or convert it
    // to table of unique values (more usable)

    int[] arrayOfUniqueValues = new int[countOfUniqueIntegers];
    int index = 0;
    for(int i = 0; i<arrayOfValues.length; i++) {
        if(arrayOfValues[i] != 0) {
            arrayOfUniqueValues[index] = i;
            index++;
        }
    }

    //and now arrayOfUniqueValues is even sorted
    System.out.println( Arrays.toString(arrayOfUniqueValues) );

Вывод: [0, 10, 11, 99]

Answer 8

Может быть, хэш-набор, который работает с примитивами вместо объектов, сделает эту работу? Существуют бесплатные реализации (раньше они не использовались, но, возможно, это работает):

http://trove4j.sourceforge.net/

http://trove4j.sourceforge.net/javadocs/gnu/trove/TIntHashSet.html

Тогда будет выглядеть так:

int[] newArray = new TIntHashSet(yourArray).toArray();

Answer 9

Может быть, вы могли бы сделать несколько проходов по данным?Например, если вы сделали десять проходов над данными и применили одно из предложенных выше наборов к меньшему подмножеству данных (скажем, когда значение mod pass # == 0).Таким образом:

for (int i = 0 to 9) {
  set = new Set()
  for (each entry in the data set) {
    if (entry % i == 0) {
      set.add(entry)
    }
  }
  output set
}

Таким образом вы потратите время на обмен памяти (увеличьте количество проходов для меньшего количества памяти / больше времени и наоборот).