在列表列表中有效查找通用值-Scala [英] Efficiently find common values in a map of lists - scala

问题描述

我已经在这里问过类似的问题.但是，我对我的具体案例的判断有误.在我给出的示例中，地图中只有4个键.我实际上正在处理10,000多个键，它们被映射到不同大小的列表.因此，给出的解决方案是正确的，但是我现在正在寻找一种可以更有效地实现此目的的方法.

I asked a similar question already here. However, I misjudged the scale of my specific case. In my example I gave, there were only 4 keys in the map. I am actually dealing with over 10,000 keys and they are mapped to lists of different sizes. So the solution given was correct, but I am now looking for a way that will do this in a more efficient manner.

说我有

val myMap: Map[Int, List[Int]] = Map(
  1 -> List(1, 10, 12, 76, 105), 2 -> List(2, 5, 10), 3 -> List(10, 12, 76, 5), 4 -> List(2, 4, 5, 10), 
  ... -> List(...)
)

想象一下(...)持续进行超过10,000个按键的操作.如果它们各自列表的交集的大小为> = 3 .

Imagine the (...) go on for over 10,000 keys. I want to return a List of Lists containing a pair of keys and their shared values if the size of the intersection of their respective lists is >= 3.

例如:

res0: List[(Int, Int, List[Int])] = List(
      (1, 3, List(10, 12, 76)),
      (2, 4, List(2, 5, 10)),
      (...),
      (...),
      )

我已经坚持了好两天，因此对您的任何帮助表示由衷的感谢.预先谢谢你！

I've been pretty stuck on this for a couple of days, so any help is genuinely appreciated. Thank you in advance!

推荐答案

如果不关心空间，则可以在O(N)中解决问题，其中N是列表中元素的数量.

If space is not the concern then the problem can be solved in the O(N) where N is the number of elements in the list.

算法:

• 从输入映射中创建反向查找映射.在这里，反向查找将列表元素映射到键(Id).
• 对于每个输入映射键
  • 创建一个临时图
  • 遍历列表，并在反向查找中查找值(Id).计算获取的ID发生的次数.
  • 所有出现了等于或大于3次的密钥都是所需的密钥对.

  代码

  import scala.collection.mutable
  import scala.collection.mutable.ArrayBuffer
  
  object Application extends App {
  
    val inputMap = Map(
      1 -> List(1, 2, 3, 4),
      2 -> List(2, 3, 4, 5),
      3 -> List(3, 5, 6, 7),
      4 -> List(1, 2, 3, 6, 7))
    
  /*
    Expected pairs
  
    |  pair | common elements |
    ---------------------------
    (1, 2) -> 2, 3, 4
    (1, 4) -> 2, 3, 4
    (2, 1) -> 2, 3, 4
    (3, 4) -> 3, 5, 6
    (4, 1) -> 1, 2, 3
    (4, 3) -> 3, 5, 6
     */
  
    val reverseMap = mutable.Map[Int, ArrayBuffer[Int]]()
  
    inputMap.foreach {
      case (id, list) => list.foreach(
        o => if (reverseMap.contains(o)) reverseMap(o).append(id) else reverseMap.put(o, ArrayBuffer(id)))
    }
  
    val result = inputMap.map {
      case (id, list) =>
        val m = mutable.Map[Int, Int]()
        list.foreach(o =>
          reverseMap(o).foreach(k => if (m.contains(k)) m.update(k, m(k)+1) else m.put(k, 1)))
        val res = m.toList.filter(o => o._2 >= 3 && o._1 != id).map(o => (id, o._1))
        res
    }.flatten
  
    println(result)
  }
  
  

  这篇关于在列表列表中有效查找通用值-Scala的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！