编程与类型系统10
发表于：2024-07-05 | 分类： 学习

泛型算法和迭代器

迭代器实现的map()、 filter()、 reduce()

  • map()

    1
    2
    3
    4
    5
    6
    7
    8
    function* map<T, U>(
      value: Iterable<T>,
      func: (value: T) => U
    ): IterableIterator<U> {
      for (const key of value) {
        yield func(key);
      }
    }

    map()接受一个 T 值序列和一个函数(value: T) => U，将该函数应用到序列中的全部元素，然后返回一个 U 值序列。其他名称包括fmap()和select()。

  • filter()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    function* filter<T>(
      value: Iterable<T>,
      func: (value: T) => boolean
    ): IterableIterator<T> {
      for (const key of value) {
        if (func(key)) {
          yield key;
        }
      }
    }

    filter()接受一个 T 值序列和一个谓词(value: T) => boolean，并返回一个 T 值序列，其中包含谓词返回true的所有数据项。其他名称包括where()。

  • reduce()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function* reduce<T>(
      value: Iterable<T>,
      init: T,
      func: (valueX: T, valueY: T) => T
    ): IterableIterator<T> {
      let result: T = init;
      for (const key of value) {
        result = func(result, key);
      }
      return result;
    }

    reduce()接受一个 T 值序列、一个 T 类型的初始值，以及将两个 T 值合并为一个值的操作(x: T, y: T) => T。当使用该操作把序列中的全部元素合并起来后，它返回一个 T 值。其他名称包括fold()、collect()、accumulate()和aggregate()

约束类型参数

类型参数的约束：约束告诉编译器某个类型实参必须具有的能力。如果没有任何约束，那么类型实参可以是任何类型。一旦要求泛型类型上必须有特定成员，就使用约束将允许类型的集合限制为具有必要成员的那些类型。

大 O 表示法

大 O 表示法提供了当函数的实参趋近于特定值 n 时，执行该函数需要的时间和空间的上界。我们不会深入讨论这个主题，而是会列举一些常见的上界，并解释它们的含义。

  • 常量时间，或 O(1)，意味着函数的执行时间不依赖于它需要处理的数据项个数。函数 first()取出一个序列中的第一个元素，无论该序列中包含 2 个还是 200 万个数据项，它的运行时间是相同的。对数时间，或 O(logn)，意味着函数的输入在每一步减半，所以即使对于很大的 n 值，它的效率也很高。例如，在排序后的序列中进行二分搜索。

  • 线性时间，或 O(n)，意味着函数的运行时间与其输入成比例。遍历一个序列需要的时间是 O(n)，例如，判断序列的所有元素是否都满足某个谓词。

  • 二次方时间，或 O(n2)，其效率比线性时间低得多，因为运行时间的增长比输入规模的增长快得多。序列上的两个嵌套循环的运行时间为 O(n2)。

  • 线性代数时间，或 O(nlogn)，不如线性时间高效，但是比二次方时间高效。最高效的比较排序算法是 O(nlogn)；我们不能只使用一个循环排序一个序列，但能够做到比使用两个嵌套循环更快。

正如时间复杂度为输入规模增长时函数运行时间的增长设置了上界，空间复杂度为输入规模增长时函数需要的额外内存量设置了上界。

  • 常量空间，或 O(1)，意味着在输入的规模增长时，函数不需要更多空间。例如，max()函数需要额外的内存来存储正在计算中的最大值和迭代器，但无论序列有多大，函数需要的内存量是固定的。

  • 线性空间，或 O(n)，意味着函数需要的内存量与其输入的规模成比例。一开始的 inOrder()二叉树遍历就是这样一个函数，它将所有结点的值复制到一个数组中，以提供树的迭代器

高效迭代器算法

  • 输入迭代器：输入迭代器是能够遍历序列一次并提供其值的迭代器。它不能第二次重放值，因为值可能已经不再可用。输入迭代器并非必须遍历持久性数据结构，它也可以从生成器或其他某种数据源提供值。
  • 输出迭代器：输出迭代器是能够遍历一个序列并向其写入值的迭代器，它并不需要能够读出值。输出迭代器并非必须遍历持久性数据结构，也可以把值写入其他输出。
  • 前向迭代器：前向迭代器是可以向前推进、可以读取当前位置的值以及更新该值的迭代器。前向迭代器也可以被克隆，使得推进该迭代器不会影响该迭代器的克隆。这一点很重要，因为它允许多次遍历一个序列。这一点不同于输入和输出迭代器。
  • 双向迭代器：双向迭代器具有前向迭代器的所有能力，但除此之外，还可以递减。换句话说，双向迭代器既可以前向，又可以后向遍历序列。
  • 随机访问迭代器：随机访问迭代器能够以常量时间向前或向后跳过任意多个元素。双向迭代器每次递增或递减一步，而随机访问迭代器则可以移动任意数量的元素。

新的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
interface IReadable<T> {
  get(): T;
}
interface IIncrementable<T> {
  increment(): void;
}
interface IInputIterator<T> extends IReadable<T>, IIncrementable<T> {
  equals(other: IInputIterator<T>): boolean;
}

class LinkedNodes<T> {
  value: T;
  next: LinkedNodes<T> | undefined;
  constructor(value: T) {
    this.value = value;
  }
}

class LinkedIterator<T> implements IForwardIterator<T> {
  private node: LinkedNodes<T> | undefined;
  constructor(node: LinkedNodes<T> | undefined) {
    this.node = node;
  }
  increment(): void {
    if (!this.node) throw new Error("node is undefined");
    this.node = this.node.next;
  }
  get(): T {
    if (!this.node) throw new Error("node is undefined");
    return this.node.value;
  }
  set(val: T): void {
    if (!this.node) throw new Error("node is undefined");
    this.node.value = val;
  }

  equals(other: IForwardIterator<T>): boolean {
    return this.node == (<LinkedIterator<T>>other).node;
  }
  clone(): IForwardIterator<T> {
    return new LinkedIterator(this.node);
  }
}
interface IWritable<T> {
  set(val: T): void;
}
interface IOutputIterator<T> extends IWritable<T>, IIncrementable<T> {
  equals(other: IOutputIterator<T>): boolean;
}
class ConsoleOutputIterator<T> implements IOutputIterator<T> {
  set(val: T): void {
    console.log(val);
  }
  increment(): void {}
  equals(other: IOutputIterator<T>): boolean {
    return false;
  }
}
interface IForwardIterator<T>
  extends IReadable<T>,
    IWritable<T>,
    IIncrementable<T> {
  equals(other: IForwardIterator<T>): boolean;
  clone(): IForwardIterator<T>;
}

  • 新的 map()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function map<T, U>(
      begin: IInputIterator<T>,
      end: IInputIterator<T>,
      out: IOutputIterator<U>,
      func: (value: T) => U
    ): void {
      while (!begin.equals(end)) {
        out.set(func(begin.get()));
        begin.increment();
        out.increment();
      }
    }

  • 单向查找迭代器 find()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function find<T>(
      begin: IForwardIterator<T>,
      end: IForwardIterator<T>,
      pred: (value: T) => boolean
    ): IForwardIterator<T> {
      while (!begin.equals(end)) {
        if (pred(begin.get())) {
          return begin;
        }
        begin.increment();
      }
      return end;
    }

  • 双向查找迭代器 reverse()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function reverse<T>(
      begin: IBidirectionalIterator<T>,
      end: IBidirectionalIterator<T>
    ): void {
      while (!begin.equals(end)) {
        end.decrement();
        if (begin.equals(end)) return;

        const temp: T = begin.get();
        begin.set(end.get());
        end.set(temp);
        begin.increment();
      }
    }

  • 随即访问迭代器 elementAt()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    function elementAt<T>(
      begin: IRandomAccessIterator<T>,
      end: IRandomAccessIterator<T>,
      n: number
    ): IRandomAccessIterator<T> {
      begin.move(n);
      if (begin.distance(end) <= 0) return end;
      return begin;
    }
Ts学习
上一篇:
编程与类型系统11
下一篇:
编程与类型系统09

    • Copyright © 2019 - 2020 setking | Powered by Hexo | Theme Bamboo