Блог

Главная - Вопросы по программированию - Эффективное объединение двух списков, в результате чего получается набор новых списков

Эффективное объединение двух списков, в результате чего получается набор новых списков

#scala

Вопрос:

У меня есть два набора списков:

 A: {1 -> B -> 3, 4 -> B -> 5 }
B: { 7 -> 8 }

которые я хочу объединить, что приведет к

 A' : {1 -> 7 -> 8 -> 3, 4 -> 7 -> 8 -> 5 }

Примечание B . В одном списке может быть несколько ссылок.

 A: {B -> 1 -> B}
B: {2,3}
A' : {2 -> 1 -> 2, 2 -> 1 -> 3, 3 -> 1 ->2, 3 -> 1 -> 3}

Мой текущий подход является рекурсивным и работает с каждым из отдельных списков A :

 object dummy {

    trait Step
    // I owe you referencing another set
    case class IOU(ref : String)
    // a simple step within the list
    case class Step(id : Long)

    def recursiveResolve(
                          id: String,
                          to: Set[Seq[Step]],
                          on: Seq[Step]): Set[Seq[Step]] = {
      on match {
          // here we are done and can return the empty set to resolve the recursion tree
        case Nil => Set()
          // we have still work left and now work on the first element remaining
        case mul :: tiple =>
          val step: Set[Seq[Step]] = mul match {
              // if we have an I owe you that references the replace in list
            case x: IOU if x.ref == id =>
              // return the replace in set of lists
              to
            case x => Set(Seq(x))
          }
          val next: Set[Seq[Step]] = recursiveResolve(id, to, tiple)
          // if the next step returned non empty we have to merge
          if (next.nonEmpty) {
            step.flatMap { elem: Seq[Step] =>
              next.map { nextElem: Seq[Step] =>
                elem    nextElem
              }
            } 
          } else {
            step
          }
      }
    }
  }

val A : Set[Seq[Step]] = Set( Seq( Step(1), IOU("B"), Step(3)), Seq( Step(4), IOU("B"), Step(5) ))
val B : Set[Seq[Step]] = Set( Seq(Step(7), Step(8) ) )
val result : Set[Seq[Step]] = A.flatMap(elem => recursiveResolve("B",B,elem))

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

Существует ли более эффективный подход?

Ответ №1:

Ух, да .. это становится дорогим (но все равно полиномиальным — я думаю, это так O(A*N*B^2) )

  def resolve(bs: Set[Seq[Step]])(s: Seq[Step]): Set[Seq[Step]] =  s match {
  case Seq(IOU(_), tail@_*) => bs.flatMap { b =>  resolve(bs)(tail).map(b   : _) }
  case Seq(head, tail@_*) => resolve(bs)(tail).map(head  : _)
  case Seq() => Set(Seq()) 
 }
 
 A.flatMap(resolve(B))

Комментарии:

1. B может быть набором списков. Чтобы пример был простым, я его не демонстрировал.

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

3. Тогда должно было бы появиться еще больше списков A: {1 -> B -> 2} B{1,2} A: {1 -> 1 -> 2, 1 -> 2 -> 2} . Эта проблема имеет потенциал для неполиномиального роста, поэтому мне нужно ее оптимизировать.

4. вы уверены, что resolve используется a flatMap , а не a map . Я получаю ошибку типа.

5. Я думаю, что я нашел проблему с вашим решением A: { B -> 1 -> B } B: {2, 3} , которая должна привести к A': {2 -> 1 -> 2, 2 -> 1 -> 3, 3 -> 1 -> 2, 3 -> 1 -> 3} , но приводит только A':{2 -> 1 -> 2, 3 -> 1 -> 3} к вашему решению.

Метки: ,