如何有效搜索元素

Question

我有一个

的集合

case class User(id: Int, parentId: Int)
val users = Seq(User(3, 23), User(4, 17), User(22, 23),User(29, 90))

我需要通过" parentid"的搜索高效(小于o(n((：

val testUser = User(23, 999)
val found = users.filter(u => u.parentId == testUser.id)
res: List(User(3,23), User(22,23))

我如何实现这一目标以及要使用的数据结构？

Answer 1

使用groupby将您的SEQ转换为地图，这将为您提供O(1(查找：

case class User(id: Int, parentId: Int)
val users = Seq(User(3, 23), User(4, 17), User(22, 23),User(29, 90))
val usersMap = users.groupBy(_.parentId)
val testUser = User(23, 999)
val found = usersMap.get(testUser.id)