欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

使用typescript類型來實現(xiàn)快排詳情

 更新時間：2022年08月14日 09:41:44   作者：東東么么噠  
這篇文章主要介紹了使用typescript類型來實現(xiàn)快排詳情，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下

前言

本文執(zhí)行環(huán)境typescript，版本4.7.4

不使用typescript的計算能力，通過類型來實現(xiàn)快排

元組快排

能否將元組 [3, 1, 2, 4] 通過泛型轉(zhuǎn)換成 [1, 2, 3, 4]

如何實現(xiàn)快排？

  • 遍歷元組
  • 元組每個值的大小比較
  • 每次比較中挑選出符合條件的值，也就是實現(xiàn) Filter

實現(xiàn)邏輯

實現(xiàn)數(shù)字的大小比較

在typescript類型中沒有比較符，那如何判斷 5 和 6 誰更大？

typescript類型不知道，所以需要找到在typescript中已經(jīng)存在的遞增數(shù)列，通過這個數(shù)列來實現(xiàn)

怎么理解呢？

類似有 張三 和 李四 兩個人，要比較他們誰的位置靠前，需要有一個他們排隊的數(shù)列，然后依次查看，先看到 張三，那么 張三 的位置明顯靠前

typescript中有這樣的遞增數(shù)列嗎？

有的：元組下標，只需要遞歸元組，就可以實現(xiàn)依次點名

實現(xiàn) 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, [...T, 0]>;

實現(xiàn) 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<A, B, [...T, 0]>;

當然也可以依賴 SmallerThan 泛型來實現(xiàn)

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

實現(xiàn)Filter

  • 根據(jù)元組長度遞歸
  • 當滿足條件（比如：大于等于 一個值），將值存儲到新元組中，否則不操作
  • 依賴上面實現(xiàn)的大小值比較 分別實現(xiàn) 對應的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<T[R['length']], A> 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<T[R['length']], A> extends true ? [...Z, T[R['length']]] : Z,
        [...R, 0]
    >;

優(yōu)化Filter

Filter寫的很重復了，將泛型作為參數(shù)傳進去

重構(gòu)數(shù)字的大小值比較

如何把泛型作為參數(shù)傳入，然后在參數(shù)中限定...好問題

// 目標是實現(xiàn)這種
type Test<A extends number, T extends ?> = T<A>;

貌似不太行，那變個思路：

實現(xiàn)一個對象，每個鍵值對實現(xiàn)一個泛型，最后只需要傳入這個對象的key來獲取泛型，在參數(shù)的限定可以變成對key的限定，通過keyof 對象即可實現(xiàn)

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

復用邏輯，將對應的泛型改成鍵值對

type Compare<A extends number, B extends number, T extends number[] = []> = {
    ['SmallerThan']:
        T['length'] extends A ? true :
            T['length'] extends B ? false :
                Compare<A, B, [...T, 0]>['SmallerThan'];

    ['LargerThan']:
        T['length'] extends A ? false :
            T['length'] extends B ? true :
            Compare<A, B, [...T, 0]>['LargerThan'];
}

重構(gòu)Filter

復用邏輯，將對應的泛型改成鍵值對，key需要手動傳入

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

實現(xiàn)快排

  • 遞歸元組
  • 元組長度小于等于1的時候返回自身
  • 默認取第一項作為對比值
  • 遞歸的參數(shù)通過filter和第一項比較
type UNSHIFT<T extends number[]> = T extends [number, ...infer U] ? U: [];

// 快排
type QuickSort<T extends any[]> = T['length'] extends 0 | 1 ?
    T : [
        ...QuickSort<Filter<UNSHIFT<T>, T[0], 'SmallerThan'>>,
        T[0],
        ...QuickSort<Filter<UNSHIFT<T>, T[0], 'LargerThan'>>
    ];

測試快排

type ARR1 = [5, 2, 4, 1, 0, 6];
type test1 = QuickSort<ARR1>;
// [0, 1, 2, 4, 5, 6]

type ARR2 = [3, 2, 7, 1, 0, 6, 9, 5, 8, 4];
type test2 = QuickSort<ARR2>;
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

type ARR3 = [1, 1, 0, 1, 1, 0, 0];
type test3 = QuickSort<ARR3>;
// [0, 0, 0, 1, 1, 1, 1]

看起來一切正常，可以發(fā)現(xiàn)遺漏了負數(shù)

測試負數(shù)的時候問題出現(xiàn)了

因為最開始的大小值對比，是從0開始無限遞歸的

結(jié)束條件是命中其中一個數(shù)，然而負數(shù)是永遠不會命中，這就是致命bug！

優(yōu)化：負數(shù)

負數(shù)的判斷

負數(shù)的特點：多了一個符號，也就是 '-'，轉(zhuǎn)換成字符串后拿第一個字符判斷

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

type i1 = isFuShu<6>;  // false
type i2 = isFuShu<-6>;  // true

字符串轉(zhuǎn)數(shù)字

但是這樣拿到的是字符串，還要把字符串轉(zhuǎn)成數(shù)字

和大小比較的邏輯一樣

  • 無限遞歸，每次循環(huán)創(chuàng)建新元組
  • 元組長度（模板字符串） 等于 參數(shù)后結(jié)束遞歸，并返回元組長度
type ToNumber<S extends string, R extends number[] = []> =
    S extends `${R['length']}` ?
        R['length'] : ToNumber<S, [...R, 0]>;

獲取負數(shù)的值

判斷是負數(shù)后要拿到負數(shù)的值

  • 和負數(shù)符號判斷類似，獲取除開符號之后的字符串，轉(zhuǎn)數(shù)字
type GetFushu<T extends number> = `${T}` extends `${string}${infer U}` ?
    ToNumber<U> : 0;

完善獲取絕對值

type GetAbs<T extends number> = isFuShu<T> extends true ? GetFushu<T> : T;

重構(gòu)數(shù)字的大小比較

負數(shù)的對比和正數(shù)相反，且正數(shù)一定比負數(shù)大

  • 非負數(shù)數(shù)直接比較
  • 負數(shù)取反比較
  • 非負數(shù)一定大于負數(shù)
type CompareV2<A extends number, B extends number, T extends number[] = []> = {
    ['SmallerThan']:
        T['length'] extends A ? true :
            T['length'] extends B ? false :
                CompareV2<GetAbs<A>, GetAbs<B>, [...T, 0]>['SmallerThan'];

    ['SmallerThanV2']:
        isFuShu<A> extends true ?
            (isFuShu<B> extends true ?
                CompareV2<A, B>['LargerThan'] :
                true) :
            (isFuShu<B> extends true ?
                false :
                CompareV2<A, B>['SmallerThan']);

    ['LargerThan']:
        T['length'] extends A ? false :
            T['length'] extends B ? true :
                CompareV2<GetAbs<A>, GetAbs<B>, [...T, 0]>['LargerThan'];
    
    ['LargerThanV2']:
        isFuShu<A> extends true ?
            (isFuShu<B> extends true ?
                CompareV2<A, B>['SmallerThan'] :
                false) :
            (isFuShu<B> extends true ?
                true :
                CompareV2<A, B>['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

重構(gòu)快排

  • 更換重構(gòu)的泛型
type FilterV2<
    T extends number[],
    A extends number,
    key extends keyof CompareV2<number, number>,
    Z extends number[] = [],
    R extends number[] = [],
> = T['length'] extends R['length'] ?
    Z : FilterV2<
        T,
        A,
        key,
        CompareV2<T[R['length']], A>[key] extends true ? [...Z, T[R['length']]] : Z,
        [...R, 0]
    >;

// 快排
type QuickSortV2<T extends any[]> = T['length'] extends 0 | 1 ?
    T : [
        ...QuickSortV2<FilterV2<UNSHIFT<T>, T[0], 'SmallerThanV2'>>,
        T[0],
        ...QuickSortV2<FilterV2<UNSHIFT<T>, T[0], 'LargerThanV2'>>
    ];

測試快排V2

type ARR4 = [-5, -2, -4, -1, 0, -6];
type test4 = QuickSortV2<ARR4>;
// [-6, -5, -4, -2, -1, 0]

type ARR5 = [-5, -2, 4, -1, 0, -6, 2, -3, 7];
type test5 = QuickSortV2<ARR5>;
// [-6, -5, -3, -2, -1, 0, 2, 4, 7]

type ARR6 = [3, -2, 7, -1, 0, -6, 9, -5, 8, -4];
type test6 = QuickSortV2<ARR6>;
// [-6, -5, -4, -2, -1, 0, 3, 7, 8, 9]

到此這篇關于使用typescript類型來實現(xiàn)快排詳情的文章就介紹到這了,更多相關typescript實現(xiàn)快排內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論