Блог

Я фильтрую набор на основе других значений того же набора, точнее, отфильтровываю наборы, которые полностью включены в другой набор

 Set(Set(1, 2), Set(1, 3), Set(1, 4), Set(1, 2, 3))
  

Это приведет к :

 Set(Set(1, 4), Set(1, 2, 3))
  

1,2 и 2,3 полностью включены в последний набор (в принципе, мне нужны только самые большие подмножества партии)

Я придумал этот фрагмент кода, который делает трюк :

 def filterIncluded(data: Set[Set[Int]]): Set[Set[Int]] = {  
  data.filterNot{ s =>
    data.exists(x => x.size > s.size amp;amp; s.forall(x.contains))
  }
}
  

Это отлично работает, за исключением одной проблемы: это крайне неэффективно, мой фактический набор данных будет содержать миллионы наборов, каждый из которых может иметь от 2 до 100 значений в каждом

Есть ли какой-нибудь способ ускорить это? (Использование другого типа коллекции, другие вызовы методов, изменение способа выполнения циклов и т. Д.)

В общем, вы не можете работать лучше, чем N ^ 2, потому что вы ищете столкновения в гораздо большем пространстве, которое не ограничено каким-либо обычным способом.

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

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

 data.toList.flatMap(_.toList).groupBy(identity).map{ 
  case (k,vs) => k -> vs.length
}
// Gives counts: 1 -> 4, 2 -> 2, 3 -> 2, 4 -> 1
// Pick out the set with a 4: it is unique
// Pick out sets with a 2: Set(1, 2), Set(1, 2, 3)
// Run your algorithm to discard Set(1,2)
// Pick out sets with a 3: Set(1, 3), Set(1, 2, 3)
// Run your algorithm to discard Set(1,3)
// Pick out sets with a 1: only Set(1, 2, 3) remains, keep it
  

В качестве альтернативы, если у вас может быть любой Int, но на практике, как правило, имеет кучу похожих чисел, вы можете построить set эквивалент дерева суффиксов. Начните с набора, который представляет собой объединение всех ваших чисел. Затем для каждого элемента перечислите все наборы, в которых есть этот элемент. Затем в этом списке снова разбейте его на второй элемент. Каждый раз, когда вы достигаете уровня, на котором у вас фактически есть полный набор, а список непустой, вы можете отказаться от полного набора.

 1 -> Set(1, 2, 3), Set(1, 2), Set(1, 3), Set(1, 4)
  2 -> Set(1, 2, 3), Set(1, 2)
    But we're _at_ 1,2 so
      throw away Set(1, 2)
      only Set(1, 2, 3) is left--keep it
  3 ->  Set(1, 2, 3); Set(1, 3)
    We're at 1,3 so
      throw away Set(1, 3)
      the other set is already kept
  4 -> Set(1, 4)
    Oh, there's only one.  Keep it.
  

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

 def filterIncluded(data: Set[Set[Int]]): Set[Set[Int]] = {
    val undecided = data.toList.sortBy(_.size).reverse

    undecided.foldLeft(List.empty[Set[Int]]){ case (goodSets, s) =>
        if(goodSets.forall(goodSet => !s.forall(goodSet contains _))) s :: goodSets
        else goodSets
    }.toSet
  }
  

Сортировка — это NLogN, но тогда вам нужно сравнивать каждый элемент только с теми, которые уже зарекомендовали себя хорошо, поскольку вы можете быть только правильным подмножеством набора, который больше или того же размера. Я думаю, что это все еще N ^ 2, но немного более эффективно, чем ваш оригинал.

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

   def filterIncluded(data: Set[Set[Int]]): Set[Set[Int]] = {
    def isGood(s: Set[Int], goodSets: Map[Int, Set[Set[Int]]]): Boolean = goodSets.get(s.head) match {
      case None => true
      case Some(sets) => _isGood(s.tail, sets, goodSets)
    }

    def _isGood(s: Set[Int], potentialSupersets: Set[Set[Int]], goodSets: Map[Int, Set[Set[Int]]]): Boolean = {
      // println(s"s($s)npotentialSupersets($potentialSupersets)ngoodSets($goodSets)n")
      goodSets.get(s.head) match {
        case None => true
        case Some(sets) =>
          (s.tail.isEmpty, potentialSupersets amp; sets) match {
            case (true, remaining) if remaining.nonEmpty => false
            case (false, remaining) if remaining.nonEmpty => _isGood(s.tail, remaining, goodSets)
            case _ => true
          }
        }
    }

    def addToGoodSets(s: Set[Int], goodSets: Map[Int, Set[Set[Int]]]): Map[Int, Set[Set[Int]]] = {
      s.foldLeft(goodSets){case (g, i) => g   (i -> (g.getOrElse(i, Set.empty) s))}
    }

    val undecided = data.toList.sortBy(_.size).reverse
    // println("UNDECIDED: " undecided)

    undecided.foldLeft(Map.empty[Int, Set[Set[Int]]]){ case (goodSets, s) =>
      if(isGood(s, goodSets)) addToGoodSets( s, goodSets)
      else goodSets
    }.values.flatten.toSet
  }
  

Честно говоря, у меня небольшая проблема с анализом, когда это лучше, чем что-либо еще, но вот и все. Можете ли вы сказать, что мне скучно?