scala - fp 风格的做法是什么 "naive hashmap"

Question

我有一个格式对列表 (a: A, x: Int)，并且 x 在列表中不重复。现在我知道 x 在一定范围内 0 until n，我想做一个大小为 n 的数组，其 i 第一个元素的类型是 Option[A]。如果原始列表中有一对(a, i)，则为Some(a)，否则为None。一个简单的例子:

Original List (n = 6):
(a1, 1)
(a2, 2)
(a3, 5)
Desired Output:
(0, None)
(1, Some(a1))
(2, Some(a2))
(3, None)
(4, None)
(5, Some(a3))

当然我们可以得到一个可变数组，遍历原始列表并填充相应的元素。但是，如果时间复杂度不应该是 n 的超线性，那么 fp 风格的做法是什么？也许这是一个简单的问题，但我就是无法理解......希望有人能帮忙。谢谢!

Answer 1

如果你有一个很大的集合和很多/很大的间隙，这会浪费内存。我建议您改为使用 Map[Int,B] 并使用 get 操作，它返回一个 Option[B]。交换可以按如下方式完成:

scala> List("a1"->1, "a2"->2, "a3"->5)
res3: List[(java.lang.String, Int)] = List((a1,1), (a2,2), (a3,5))

// swap the elements and create a Map
scala> res3.map(_.swap).toMap
res4: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a1, 2 -> a2, 5 -> a3)

scala> res3.map(_.swap).toMap.get(3)
res5: Option[java.lang.String] = None

scala> res3.map(_.swap).toMap.get(1)
res6: Option[java.lang.String] = Some(a1)