Подсчет каждого отдельного вхождения массива в список массивов с дубликатами - PullRequest
Новая
       6

Подсчет каждого отдельного вхождения массива в список массивов с дубликатами

0 голосов
/ 03 октября 2018

ПРОБЛЕМА

У меня есть список массивов, и я хочу подсчитать вхождения дубликатов.

Например, если у меня есть это: 

{{1,2,3},
 {1,0,3},
 {1,2,3},
 {5,2,6},
 {5,2,6},
 {5,2,6}}

Мне нужна карта (или любая соответствующая коллекция), подобная этой: 

{ {1,2,3} -> 2,
  {1,0,3} -> 1,
  {5,2,6} -> 3 }

Я могу даже потерять значения массивов, меня интересуют только кардиналы (например, 2, 1 и 3 здесь).

МОЕ РЕШЕНИЕ

Я использую следующий алгоритм:

  • Сначала хешируем массивы и проверяем каждый хешнаходится в HashMap<Integer, ArrayList<int[]>>, назовем его diverHash , где ключом является хеш, а значением является ArrayList, назовем его rowList , содержащим различные массивы для этого хеша (чтобы избежать коллизий).

  • Если хеш не находится в diverHash , поместите его со значением 1 в другой HashMap<int[], Long>, который считает каждое вхождение, давайте назовем его differentElements .

  • Тогда, если хеш находится в diverHash , проверьте, соответствует ли соответствующий массив is содержится в rowList .Если это так, увеличьте значение в differentElements , связанное с идентичным массивом, найденным в rowList .(Если вы используете новый массив в качестве ключа, вы создадите другой ключ, поскольку их ссылки различны).

Вот код, возвращаемый логическим значением, сообщает, был ли найден новый отдельный массивЯ последовательно применяю эту функцию ко всем моим массивам: 

    HashMap<int[], Long> distinctElements;
    HashMap<Integer, ArrayList<int[]>> distinctHash;

    private boolean addRow(int[] row) {

        if (distinctHash.containsKey(hash)) {
            int[] indexRow = distinctHash.get(hash).get(0);
            for (int[] previousRow: distinctHash.get(hash)) {
                if (Arrays.equals(previousRow, row)) {
                    distinctElements.put(
                            indexRow,
                            distinctElements.get(indexRow) + 1
                    );
                    return false;
                }
            }
            distinctElements.put(row, 1L);

            ArrayList<int[]> rowList = distinctHash.get(hash);
            rowList.add(row);
            distinctHash.put(hash, rowList);

            return true;

        } else {
            distinctElements.put(row, 1L);

            ArrayList<int[]> newValue = new ArrayList<>();
            newValue.add(row);
            distinctHash.put(hash, newValue);

            return true;
        }
    }

ВОПРОС

Проблема в том, что мой алгоритм слишком медленный для моих потребностей (40 с для 5 000 000и 2h-3h для 20 000 000 массивов).Профилирование с помощью NetBeans говорит мне, что хеширование занимает 70% времени выполнения (с использованием хеш-функции Google Guava murmur3_128).

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

Ответы [ 3 ]

0 голосов
/ 03 октября 2018

Вы можете сделать это так, 

Map<List<Integer>, Long> result = Stream.of(source)
        .map(a -> Arrays.stream(a).boxed().collect(Collectors.toList()))
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

А вот вывод, 

{[1, 2, 3]=2, [1, 0, 3]=1, [5, 2, 6]=3}
0 голосов
/ 03 октября 2018

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

0 голосов
/ 03 октября 2018

Оберните int[] в класс, который реализует equals и hashCode, затем создайте Map класса-оболочки для подсчета экземпляров. 

class IntArray {
    private int[] array;
    public IntArray(int[] array) {
        this.array = array;
    }
    @Override
    public int hashCode() {
        return Arrays.hashCode(this.array);
    }
    @Override
    public boolean equals(Object obj) {
        return (obj instanceof IntArray && Arrays.equals(this.array, ((IntArray) obj).array));
    }
    @Override
    public String toString() {
        return Arrays.toString(this.array);
    }
}

Test 

int[][] input = {{1,2,3},
                 {1,0,3},
                 {1,2,3},
                 {5,2,6},
                 {5,2,6},
                 {5,2,6}};
Map<IntArray, Long> map = Arrays.stream(input).map(IntArray::new)
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
map.entrySet().forEach(System.out::println);

Выход 

[1, 2, 3]=2
[1, 0, 3]=1
[5, 2, 6]=3

Примечание: Приведенное выше решение работает быстрее и использует меньше памяти, чем решение по Равиндре Ranwala , но это требует создания дополнительного класса, так что спорно, что лучше.

1024 * Для небольших массивов, использовать более простое решение ниже по Равиндре Ranwala.
Для увеличениямассивы, вышеупомянутое решение, вероятно, лучше. 
 Map<List<Integer>, Long> map = Stream.of(input)
         .map(a -> Arrays.stream(a).boxed().collect(Collectors.toList()))
         .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
...