scala – 对索引集合进行二进制搜索(已排序的索引序列)

发布时间：2020-12-16 10:03:11 所属栏目：安全来源：网络整理

导读：我有一个类型A的索引集合(它必须被索引)： var coll: IndexedSeq[A] 我希望根据一些订购[A]对coll进行排序,但我经常在其中添加/删除项目.这样做的明显机制是： def binarySearch[A : Ordering](a: IndexedSeq[A],elem: A): Intdef add(a: A) { val idx = bin

我有一个类型A的索引集合(它必须被索引)：

var coll: IndexedSeq[A]

我希望根据一些订购[A]对coll进行排序,但我经常在其中添加/删除项目.这样做的明显机制是：

def binarySearch[A : Ordering](a: IndexedSeq[A],elem: A): Int
def add(a: A) {
  val idx = binarySearch(coll,a)
  coll = (coll take idx) :+ a +: (coll drop idx)
}

但是标准库中既没有binarySearch(奇怪的是,因为有scala.util.Sorting.quickSort),并且没有我能找到的数据类型,它都是索引和排序的(我猜这是一个低效的结构).

解决方法

我认为TreeSet上的切片效率相当高(并且可以将它与单元素范围一起使用),但是你是对的 – 奇怪的是没有索引排序的数据结构.它足够有效;如果跟踪孩子的数量,大多数任何排序的树都可以这样使用.我认为这只是一种疏忽而已.

如果用一个只允许引用相等的标记包装它们,你总是可以使用一个重复元素的集合,并且你可以确保它们是有序的：

class Tag[A](val value: A)(implicit ord: Ordering[A]) extends Ordered[Tag[A]] {
  def compare(ta: Tag[A]) = {
    val c = ord.compare(value,ta.value)
    if (c != 0) c
    else if (this eq ta) 0
    else System.identityHashCode(this) compare System.identityHashCode(ta)
  }
  override def toString = value.toString+"'"
  override def hashCode = value.hashCode
  override def equals(a: Any) = a.asInstanceOf[AnyRef] eq this
}

scala> collection.immutable.TreeSet[Tag[Int]]() ++ List(1,2,3,1).map(i => new Tag(i))
res1: scala.collection.immutable.TreeSet[Tag[Int]] = TreeSet(1',1',2',3')

scala> res1.slice(2,3).head
res2: Tag[Int] = 2'

然而,这确实为相对简单的任务增加了大量开销.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!