预先添加scala向量的复杂性

发布时间：2020-12-16 09:56:06 所属栏目：安全来源：网络整理

导读：我指的是官方documentation 它显示将Vector的复杂性作为“有效常量”(eC).但我的理解是,对于向量,前置意味着所有其他索引也需要调整,这将使操作O(n)或L(线性).任何人都可以解释如何在矢量eC(有效常数)前置. 解决方法找到了前置操作的可视化解释,其中每个步

enter image description here

我指的是官方documentation

它显示将Vector的复杂性作为“有效常量”(eC).但我的理解是,对于向量,前置意味着所有其他索引也需要调整,这将使操作O(n)或L(线性).任何人都可以解释如何在矢量eC(有效常数)前置.

解决方法

找到了前置操作的可视化解释,其中每个步骤中都有一个字符.图片仅显示每个块2个插槽以便于解释,但是在矢量的情况下,每个块将有32个插槽. Vector维护起始索引(或图片中的偏移量)以跟踪空位.

enter image description here

以下是Vector.scala的源代码.由于它不移动所有元素,因此它不是O(n).

override def prepended[B >: A](value: B): Vector[B] = {
    if (endIndex != startIndex) {
      val blockIndex = (startIndex - 1) & ~31
      val lo = (startIndex - 1) & 31

      if (startIndex != blockIndex + 32) {
        val s = new Vector(startIndex - 1,endIndex,blockIndex)
        s.initFrom(this)
        s.dirty = dirty
        s.gotoPosWritable(focus,blockIndex,focus ^ blockIndex)
        s.display0(lo) = value.asInstanceOf[AnyRef]
        s
      } else {

        val freeSpace = (1 << (5 * depth)) - endIndex           // free space at the right given the current tree-structure depth
        val shift = freeSpace & ~((1 << (5 * (depth - 1))) - 1) // number of elements by which we'll shift right (only move at top level)
        val shiftBlocks = freeSpace >>> (5 * (depth - 1))       // number of top-level blocks

        if (shift != 0) {
          // case A: we can shift right on the top level
          if (depth > 1) {
            val newBlockIndex = blockIndex + shift
            val newFocus = focus + shift

            val s = new Vector(startIndex - 1 + shift,endIndex + shift,newBlockIndex)
            s.initFrom(this)
            s.dirty = dirty
            s.shiftTopLevel(0,shiftBlocks) // shift right by n blocks
            s.gotoFreshPosWritable(newFocus,newBlockIndex,newFocus ^ newBlockIndex) // maybe create pos; prepare for writing
            s.display0(lo) = value.asInstanceOf[AnyRef]
            s
          } else {
            val newBlockIndex = blockIndex + 32
            val newFocus = focus

            val s = new Vector(startIndex - 1 + shift,shiftBlocks) // shift right by n elements
            s.gotoPosWritable(newFocus,newFocus ^ newBlockIndex) // prepare for writing
            s.display0(shift - 1) = value.asInstanceOf[AnyRef]
            s
          }
        } else if (blockIndex < 0) {
          // case B: we need to move the whole structure
          val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth))
          val newBlockIndex = blockIndex + move
          val newFocus = focus + move

          val s = new Vector(startIndex - 1 + move,endIndex + move,newBlockIndex)
          s.initFrom(this)
          s.dirty = dirty
          s.gotoFreshPosWritable(newFocus,newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch
          s.display0(lo) = value.asInstanceOf[AnyRef]
          s
        } else {
          val newBlockIndex = blockIndex
          val newFocus = focus

          val s = new Vector(startIndex - 1,newFocus ^ newBlockIndex)
          s.display0(lo) = value.asInstanceOf[AnyRef]
          s
        }
      }
    } else {
      // empty vector,just insert single element at the back
      val elems = new Array[AnyRef](32)
      elems(31) = value.asInstanceOf[AnyRef]
      val s = new Vector(31,32,0)
      s.depth = 1
      s.display0 = elems
      s
    }
  }

（编辑：李大同）

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