您现在的位置是：网站首页> 编程资料编程资料

使用typescript类型来实现快排详情_javascript技巧_

2023-05-24 465人已围观

简介 使用typescript类型来实现快排详情_javascript技巧_

前言

本文执行环境typescript，版本4.7.4

不使用typescript的计算能力，通过类型来实现快排

元组快排

能否将元组 [3, 1, 2, 4] 通过泛型转换成 [1, 2, 3, 4]

如何实现快排？

  • 遍历元组
  • 元组每个值的大小比较
  • 每次比较中挑选出符合条件的值，也就是实现 Filter

实现逻辑

实现数字的大小比较

在typescript类型中没有比较符，那如何判断 5 和 6 谁更大？

typescript类型不知道，所以需要找到在typescript中已经存在的递增数列，通过这个数列来实现

怎么理解呢？

类似有 张三 和 李四 两个人，要比较他们谁的位置靠前，需要有一个他们排队的数列，然后依次查看，先看到 张三，那么 张三 的位置明显靠前

typescript中有这样的递增数列吗？

有的：元组下标，只需要递归元组，就可以实现依次点名

实现 A 是否 小于或等于 B

  • 无限递归，直到匹配到 A 或者 B
type SmallerThan< A extends number, B extends number, T extends number[] = [] > = T['length'] extends A ? true : T['length'] extends B ? false : SmallerThan;

实现 A 是否 大于或等于 B

逻辑同理：

无限递归，直到匹配到 A 或者 B

type LargerThan< A extends number, B extends number, T extends number[] = [] > = T['length'] extends A ? false : T['length'] extends B ? true : LargerThan;

当然也可以依赖 SmallerThan 泛型来实现

type LargerThan< A extends number, B extends number, T extends number[] = [] > = SmallerThan extends true ? false : true;

实现Filter

  • 根据元组长度递归
  • 当满足条件（比如：大于等于 一个值），将值存储到新元组中，否则不操作
  • 依赖上面实现的大小值比较 分别实现 对应的Filter
type FilterLargerThan< T extends number[], A extends number, Z extends number[] = [], R extends number[] = [] > = T['length'] extends R['length'] ? Z : FilterLargerThan< T, A, LargerThan extends true ? [...Z, T[R['length']]] : Z, [...R, 0] >; type FilterSmallerThan< T extends number[], A extends number, Z extends number[] = [], R extends number[] = [] > = T['length'] extends R['length'] ? Z : FilterSmallerThan< T, A, SmallerThan extends true ? [...Z, T[R['length']]] : Z, [...R, 0] >;

优化Filter

Filter写的很重复了，将泛型作为参数传进去

重构数字的大小值比较

如何把泛型作为参数传入，然后在参数中限定...好问题

// 目标是实现这种 type Test = T;

貌似不太行，那变个思路：

实现一个对象，每个键值对实现一个泛型，最后只需要传入这个对象的key来获取泛型，在参数的限定可以变成对key的限定，通过keyof 对象即可实现

type F = A; type Demo = { a: F; } type Test> = Demo[T]; type t1 = Test<1, 'a'>;

复用逻辑，将对应的泛型改成键值对

type Compare = { ['SmallerThan']: T['length'] extends A ? true : T['length'] extends B ? false : Compare['SmallerThan']; ['LargerThan']: T['length'] extends A ? false : T['length'] extends B ? true : Compare['LargerThan']; }

重构Filter

复用逻辑，将对应的泛型改成键值对，key需要手动传入

type Filter< T extends number[], A extends number, key extends keyof Compare, Z extends number[] = [], R extends number[] = [], > = T['length'] extends R['length'] ? Z : Filter< T, A, key, Compare[key] extends true ? [...Z, T[R['length']]] : Z, [...R, 0] >;

实现快排

  • 递归元组
  • 元组长度小于等于1的时候返回自身
  • 默认取第一项作为对比值
  • 递归的参数通过filter和第一项比较
type UNSHIFT = T extends [number, ...infer U] ? U: []; // 快排 type QuickSort = T['length'] extends 0 | 1 ? T : [ ...QuickSort, T[0], 'SmallerThan'>>, T[0], ...QuickSort, T[0], 'LargerThan'>> ];

测试快排

type ARR1 = [5, 2, 4, 1, 0, 6]; type test1 = QuickSort; // [0, 1, 2, 4, 5, 6] type ARR2 = [3, 2, 7, 1, 0, 6, 9, 5, 8, 4]; type test2 = QuickSort; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] type ARR3 = [1, 1, 0, 1, 1, 0, 0]; type test3 = QuickSort; // [0, 0, 0, 1, 1, 1, 1]

看起来一切正常，可以发现遗漏了负数

测试负数的时候问题出现了

因为最开始的大小值对比，是从0开始无限递归的

结束条件是命中其中一个数，然而负数是永远不会命中，这就是致命bug！

优化：负数

负数的判断

负数的特点：多了一个符号，也就是 '-'，转换成字符串后拿第一个字符判断

type isFuShu = `${T}` extends `${infer P}${string}` ? P extends '-' : true : false; type i1 = isFuShu<6>; // false type i2 = isFuShu<-6>; // true

字符串转数字

但是这样拿到的是字符串，还要把字符串转成数字

和大小比较的逻辑一样

  • 无限递归，每次循环创建新元组
  • 元组长度（模板字符串） 等于 参数后结束递归，并返回元组长度
type ToNumber = S extends `${R['length']}` ? R['length'] : ToNumber;

获取负数的值

判断是负数后要拿到负数的值

  • 和负数符号判断类似，获取除开符号之后的字符串，转数字
type GetFushu = `${T}` extends `${string}${infer U}` ? ToNumber : 0;

完善获取绝对值

type GetAbs = isFuShu extends true ? GetFushu : T;

重构数字的大小比较

负数的对比和正数相反，且正数一定比负数大

  • 非负数数直接比较
  • 负数取反比较
  • 非负数一定大于负数
type CompareV2 = { ['SmallerThan']: T['length'] extends A ? true : T['length'] extends B ? false : CompareV2, GetAbs, [...T, 0]>['SmallerThan']; ['SmallerThanV2']: isFuShu extends true ? (isFuShu extends true ? CompareV2['LargerThan'] : true) : (isFuShu extends true ? false : CompareV2['SmallerThan']); ['LargerThan']: T['length'] extends A ? false : T['length'] extends B ? true : CompareV2, GetAbs, [...T, 0]>['LargerThan']; ['LargerThanV2']: isFuShu extends true ? (isFuShu extends true ? CompareV2['SmallerThan'] : false) : (isFuShu extends true ? true : CompareV2['LargerThan']); }

测试用例：

type h1 = CompareV2<-8, -6>['SmallerThanV2']; // true type h2 = CompareV2<8, -6>['SmallerThanV2']; // false type h3 = CompareV2<6, 8>['SmallerThanV2']; // true type h4 = CompareV2<-8, 6>['SmallerThanV2']; // true type i1 = CompareV2<-8, -6>['LargerThanV2']; // false type i2 = CompareV2<8, -6>['LargerThanV2']; // true type i3 = CompareV2<6, 8>['LargerThanV2']; // false type i4 = CompareV2<-8, 6>['LargerThanV2']; // false

重构快排

  • 更换重构的泛型
type FilterV2< T extends number[], A extends number, key extends keyof CompareV2, Z extends number[] = [], R extends number[] = [], > = T['length'] extends R['length'] ? Z : FilterV2< T, A, key, CompareV2[key] extends true ? [...Z, T[R['length']]] : Z, [...R, 0] >; // 快排 type QuickSortV2 = T['length'] extends 0 | 1 ? T : [ ...QuickSortV2, T[0], 'SmallerThanV2'>>, T[0], ...QuickSortV2, T[0], 'LargerThanV2'>> ];

测试快排V2

type ARR4 = [-5, -2, -4, -1, 0, -6]; type test4 = QuickSortV2; // [-6, -5, -4, -2, -1, 0] type ARR5 = [-5, -2, 4, -1, 0, -6, 2, -3, 7]; type test5 = QuickSortV2; // [-6, -5, -3, -2, -1, 0, 2, 4, 7] type ARR6 = [3, -2, 7, -1, 0, -6, 9, -5, 8, -4]; type test6 = QuickSortV2; // [-6, -5, -4, -2, -1, 0, 3, 7, 8, 9]

到此这篇关于使用typescript类型来实现快排详情的文章就介绍到这了,更多相关typescript实现快排内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

您可能感兴趣的文章:

相关内容

点击排行

本栏推荐

猜你喜欢