эффективный алгоритм для сравнения сходства между наборами чисел? - PullRequest
Новая
       33

эффективный алгоритм для сравнения сходства между наборами чисел?

4 голосов
/ 28 июня 2009

У меня есть большое количество наборов чисел. Каждый набор содержит 10 номеров, и мне нужно удалить все наборы, которые имеют 5 или более номеров (неупорядоченных) совпадений с любым другим набором.

Например: 

set 1: {12,14,222,998,1,89,43,22,7654,23}
set 2: {44,23,64,76,987,3,2345,443,431,88}
set 3: {998,22,7654,345,112,32,89,9842,31,23}

Учитывая, что 3 набора из 10 чисел выше наборов 1 и наборов 3 будут считаться дубликатами, поскольку они имеют 5 совпадающих номеров. Итак, в этом случае я бы удалил набор 3 (потому что он считается похожим на набор 1).

У меня есть более 10000 наборов для сравнения, и я хочу сделать это очень эффективно. Я переворачиваю это, и я просто не могу придумать эффективный способ выполнить это сравнение (было бы здорово сделать это за один проход).

есть идеи? Спасибо!

Mike

Ответы [ 12 ]

0 голосов
/ 28 июня 2009

Предположим, у вас есть класс NumberSet, который реализует ваш неупорядоченный набор (и может перечислять int s, чтобы получить числа). Затем вам понадобятся следующие структуры данных и алгоритм:

  • Map<int, Set<NumberSet>> numberSets
  • Map<Pair<NumberSet, NumberSet>, int> matchCount
  • Pair<X,Y> - это ключевой объект, который возвращает одинаковый хэш-код и равенство для каждого экземпляра с одинаковыми X и Y (независимо от того, поменялись ли они местами)

Теперь для каждого добавляемого / сравниваемого набора сделайте следующее (псевдокод !!!): 

for (int number: setToAdd) {
   Set<NumberSet> numbers = numberSets.get(number);
   if (numbers == null) {
      numbers = new HashSet<NumberSet>();
      numberSets.put(number, numbers);
   } else {
      for (NumberSet numberSet: numbers) {
         Pair<NumberSet, NumberSet> pairKey = new Pair<NumberSet, NumberSet>(numberSet, setToAdd);
         matchCount.put(pairKey, matchCount.get(pairKey)+1); // make sure to handle null as 0 here in real code ;)
      }
   }
   numbers.add(number);
}

В любой момент вы можете пройти через пары, каждая из которых имеет количество 5 или более, показывает дубликат.

Примечание: удаление наборов может быть плохой идеей, потому что, если A считается дубликатом B, а B дубликатом C, то C не обязательно должен быть дубликатом A. Поэтому, если вы удалите B, вы не удалите C, и порядок, в котором вы добавите свои наборы, станет важным.

0 голосов
/ 28 июня 2009

Похоже, вы хотите использовать класс HashSet . Это должно дать вам O(1) время поиска, которое должно дать очень эффективное сравнение, если вы правильно сделали свои циклы. (Я не обсуждаю алгоритм здесь, а просто предлагаю структуру данных на случай, если это поможет.)

Страница:
...