Coder Social home page Coder Social logo

ng-study's People

Watchers

avatar

ng-study's Issues

todo 结构型指令中diff的一些总结

  1. react的diff
    todo

  2. ng2中ngFor的diff, 下面是指令部分的源代码片段:

    changes.forEachOperation(
        (item: IterableChangeRecord<any>, adjustedPreviousIndex: number, currentIndex: number) => {
          if (item.previousIndex == null) {
            const view = this._viewContainer.createEmbeddedView(
                this._template, new NgForOfContext<T>(null !, this.ngForOf, -1, -1), currentIndex);
            const tuple = new RecordViewTuple<T>(item, view);
            insertTuples.push(tuple);
          } else if (currentIndex == null) {
            this._viewContainer.remove(adjustedPreviousIndex);
          } else {
            const view = this._viewContainer.get(adjustedPreviousIndex) !;
            this._viewContainer.move(view, currentIndex);
            const tuple = new RecordViewTuple(item, <EmbeddedViewRef<NgForOfContext<T>>>view);
            insertTuples.push(tuple);
          }
        });

在这个变动更新的实现中, 这里执行分成2个部分, diff和patch.

  1. diff部分通过previousIndex, currentIndex标记了在数组中的一项, 在以前和现在在数组中的位置, 从而实现了项的增, 删, 位移. 这个实现可以通过hash轻松的完成. 数组长度为N, 算法复杂度为O(NlogN),
    这个策略无法保证后续进行patch�时编辑操作数最小.
  2. patch部分, 因为考虑到线性数据结构, 数组与链表的单次插入或者删除操作的复杂度是O(N),
    故如果没有优化在最坏的情况下, 整个patch操作的时间复杂度为O(N^2).
    这里我们如果能直接操作viewContainer内部的子view数组(或者链表)和对应的子view, 是可以把patch部分复杂度降低到O(N)的. 但是这样也就没办法利用viewContainer提供的基础增,删接口, 同时严重的破坏了封装. 总的来说这不是一个好注意.
    考虑另外的方案, 当viewContainer内部children实现方式为链表时, 应该可以通过缓存idx和对应的项, 将算法复杂度降低到O(N).

这个方案的好处是实现和理解相对简单, 并且不论数据变动程度如何, 运行速度都相当稳定, 而且diff部分算法复杂度也是非常优秀的O(NlogN).

ps: patch时候有个比较麻烦的地方, adjustedPreviousIndex的求取, 这里需要知道在某一步操作时,
对应的adjustedPreviousIndex和previousIndex之间的偏移, 当操作只有add和remove时恒造成偏移+1, -1,
但是move操作导致的偏移却是动态的.
以下是: angular/packages/core/src/change_detection/differs/default_iterable_differ.ts的部分代码

const adjPreviousIndex = getPreviousIndex(record, addRemoveOffset, moveOffsets);
/* 这里省略了很多代码, 只显示了关键的几行 */
function getPreviousIndex(
    item: any, addRemoveOffset: number, moveOffsets: number[] | null): number {
  const previousIndex = item.previousIndex;
  if (previousIndex === null) return previousIndex;
  let moveOffset = 0;
  if (moveOffsets && previousIndex < moveOffsets.length) {
    moveOffset = moveOffsets[previousIndex];
  }
  return previousIndex + addRemoveOffset + moveOffset;
}

diff笔记

编辑距离问题

两个字符串距离的度量

编辑距离是一种度量两个字符串的不相似度的一种手段。�通过测量最小的编辑操作, 使得源字符串变为目标串。

  1. 找到字符串A和B中最长的公共子序列,
  2. 找到一个最短的编辑脚本, 使得字符串A转换为B
    这个2个问题可以看做是同一个问题的不同表述。

最简化的情况

为了简化问题我们从最简单的情况开始讨论, �对于源字符串s, 定义三种最基本的编辑操作:

  1. add 在指定位置添加一个字符
  2. del 在指定位置删除一个字符
  3. match 匹配2个特定位置的字符
    由这3种最基础的操作, 构成一个操作序列, 当s经过这组操作序列的修改后, 将会变为一个新的字符串。
    那么最短编辑距离问题就可以表述为: 求一个最短的编辑脚本序列, 使得s串变为t串。

编辑矩阵

TODO 你看见了一个矩阵

�源串: ABCABBA
目标串: CBABAC

对于字符串的编辑与修改可以用一个编辑矩阵来直观的表示, , 而在矩阵上的每一次移动, 对应于一次修改操作, 现在我们看一下每一种移动对应的物理意义, 一个编辑序列可以等价为编辑矩阵上的一条路径:
�在编辑矩阵中的每一步移动, 都可以看做一次不同的编辑操作:

  1. 向右移动, 可以看做对于s串的一个插入操作,
  2. 向下移动, 可以看做对于s串的一个删除操作,
  3. 右下对角线移动, 当s[i] === t[j]时, 我们可以直接完成一次匹配
    现在问题就可以等价为, 找到一条移动轨迹, 使得修改值最小。

那么我们这个时候考虑一个位置[i, j], �这个位置可能通过3个不同的位置转移过来,

  1. [i - 1, j]的位置通过一次右移(在位置i处插入字符)到达
  2. [i, j - 1]的位置通过一次下移(删除�i处的字符)到达
  3. [i - 1, j - 1]时, 由于s[i] === s[j]通过一次匹配操作完成
    �我们这时只需要代价最小的情况, 即matrix[i, j ] = Math.min(matrix[i - 1])

一些简单的上下界分析

最长子序列问题

可以表述为,

Levenshtein distance

Levenshtein distance在操作中加入了替换, 当s[i] !=== s[j] 的时候, 我们可以通过一次修改来走斜线。

Myers Algorithm

这次我们换一个思路, 由上文可知，
这一次我们按照拓扑序进行递推,

一些优化

  1. 预处理优化

  2. 选择合适算法的策略

  3. post-processing cleanup

angular中viewContainer内部insert, remove的执行

总结:

  1. 抽象类ViewContainerRef作为views的容器, 定义了view的创建, 插入, 移动, 删除操作接口, 其具体实现为ViewContainerRef_类.
  2. ViewContainerRef_ 通过数组 _embeddedViews 保存所含view, 当我们调用insert的时候, 实际最终完成的是一次数组的添加操作.
  3. 由上可知, 调用一次insert操作, 复杂度为O(N)的数组插入操作.

相关源码片段及出处

  1. 抽象类ViewContainerRef定义了创建, 插入, 删除的操作接口, 用于增删内含view:
    https://github.com/angular/angular/blob/master/packages/core/src/linker/view_container_ref.ts
export abstract class ViewContainerRef {
  abstract get element(): ElementRef;
  abstract get injector(): Injector;
  abstract get parentInjector(): Injector;
  abstract clear(): void;
  abstract get(index: number): ViewRef|null;
  abstract get length(): number;
  abstract createEmbeddedView<C>(templateRef: TemplateRef<C>, context?: C, index?: number):
      EmbeddedViewRef<C>;
  abstract createComponent<C>(
      componentFactory: ComponentFactory<C>, index?: number, injector?: Injector,
      projectableNodes?: any[][], ngModule?: NgModuleRef<any>): ComponentRef<C>;

  abstract insert(viewRef: ViewRef, index?: number): ViewRef;
  abstract move(viewRef: ViewRef, currentIndex: number): ViewRef;
  abstract indexOf(viewRef: ViewRef): number;
  abstract remove(index?: number): void;
  abstract detach(index?: number): ViewRef|null;
}
  1. ViewContainerRef一个具体的实现在:
    https://github.com/angular/angular/blob/master/packages/core/src/view/refs.ts#L130
/* 现在我们以insert接口为例 */
insert(viewRef: ViewRef, index?: number): ViewRef {
    if (viewRef.destroyed) {
      throw new Error('Cannot insert a destroyed View in a ViewContainer!');
    }
    const viewRef_ = <ViewRef_>viewRef;
    const viewData = viewRef_._view;
    attachEmbeddedView(this._view, this._data, index, viewData);
    viewRef_.attachToViewContainerRef(this);
    return viewRef;
  }
  1. insert对view的操作, 通过调用attachEmbeddedView函数完成:
    https://github.com/angular/angular/blob/master/packages/core/src/view/view_attach.ts#L12
export function attachEmbeddedView(
    parentView: ViewData, elementData: ElementData, viewIndex: number | undefined | null,
    view: ViewData) {
  let embeddedViews = elementData.viewContainer !._embeddedViews;
  if (viewIndex === null || viewIndex === undefined) {
    viewIndex = embeddedViews.length;
  }
  view.viewContainerParent = parentView;
  addToArray(embeddedViews, viewIndex !, view);
  attachProjectedView(elementData, view);

  Services.dirtyParentQueries(view);

  const prevView = viewIndex ! > 0 ? embeddedViews[viewIndex ! - 1] : null;
  renderAttachEmbeddedView(elementData, prevView, view);
}

function addToArray(arr: any[], index: number, value: any) {
  // perf: array.push is faster than array.splice!
  if (index >= arr.length) {
    arr.push(value);
  } else {
    arr.splice(index, 0, value);
  }
}

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.