frank

frank 查看完整档案

填写现居城市浙江大学城市学院  |  计算机科学与技术 编辑  |  填写所在公司/组织填写个人主网站
编辑

前端工程师

个人动态

frank 发布了文章 · 2020-08-26

基于 React 实现的仿 MOO 音乐风格的音乐网站,支持 PWA

github 地址

项目网址-pika-music

pika-music api 服务器参考 Binaryify 的 NeteaseCloudMusicApi

项目技术特点

  1. PWA 支持。支持PWA的浏览器可以安装到桌面
  2. 实现 React-SSR 框架
  3. 实现结合 SSR 的 Dynamic Import
  4. 实现 webpack 打包支持module/nomudule 模式
  5. 实现全站图片懒加载

其他特点:

  1. http2
  2. 安卓端支持锁屏音乐控制
  3. banner轮播组件
  4. 视频和音频播放组件

网站截图

image
image
image
image

技术特点介绍

React-SSR 框架介绍

主要思想参考的是 NextJS。首屏服务端渲染时,调用组件的 getInitialProps(store)方法,注入 redux store,getInitialProps 获取该页面的数据后,把数据储存到 redux store 中。在客户端 hydrate 时,从 redux store 中获取数据,然后把数据注入swr的 initialData 中,后续页面的数据获取和更新就使用了 swr 的能力。非 SSR 的页面会直接使用 swr。

下面以首页(Discover)为例:
项目中有 ConnectCompReducer 这个父类:

class ConnectCompReducer {
  constructor() {
    this.fetcher = axiosInstance
    this.moment = moment
  }

  getInitialData = async () => {
    throw new Error("child must implememnt this method!")
  }
}

每个实现 SSR 的页面都需要继承这个类,比如主页面:

class ConnectDiscoverReducer extends ConnectCompReducer {
  // Discover 页面会实现的getInitialProps方法就是调用getInitialData,注入redux store
  getInitialData = async store => {}
}

export default new ConnectDiscoverReducer()

Discover 的 JSX:

import discoverPage from "./connectDiscoverReducer"

const Discover = memo(() => {
  // banner 数据
  const initialBannerList = useSelector(state => state.discover.bannerList)

  // 把banner数据注入swr的initialData中
  const { data: bannerList } = useSWR(
    "/api/banner?type=2",
    discoverPage.requestBannerList,
    {
      initialData: initialBannerList,
    },
  )

  return (
    ...
    <BannersSection>
      <BannerListContainer bannerList={bannerList ?? []} />
    </BannersSection>
    ...
  )
})

Discover.getInitialProps = async (store, ctx) => {
  // store -> redux store,  ctx -> koa 的ctx
  await discoverPage.getInitialData(store, ctx)
}

服务端数据的获取:

// matchedRoutes: 匹配到的路由页面,需要结合dynamic import,下一小节会介绍
const setInitialDataToStore = async (matchedRoutes, ctx) => {
  // 获取redux store
  const store = getReduxStore({
    config: {
      ua: ctx.state.ua,
    },
  })

  // 600ms后超时,中断获取数据
  await Promise.race([
    Promise.allSettled(
      matchedRoutes.map(item => {
        return Promise.resolve(
          // 调用页面的getInitialProps方法
          item.route?.component?.getInitialProps?.(store, ctx) ?? null,
        )
      }),
    ),
    new Promise(resolve => setTimeout(() => resolve(), 600)),
  ]).catch(error => {
    console.error("renderHTML 41,", error)
  })

  return store
}

自行实现结合 SSR 的 Dynamic Import

页面 dynamic import 的封装, 重要的处理是加载错误后的 retry 和 避免页面 loading 闪现:

class Loadable extends React.Component {
  constructor(props) {
    super(props)
    this.state = {
      Comp: null,
      error: null,
      isTimeout: false,
    }
  }

  // eslint-disable-next-line react/sort-comp
  raceLoading = () => {
    const { pastDelay } = this.props
    return new Promise((_, reject) => {
      setTimeout(() => reject(new Error("timeout")), pastDelay || 200)
    })
  }

  load = async () => {
    const { loader } = this.props
    try {
      this.setState({
        error: null,
      })
      // raceLoading 避免页面loading 闪现
      const loadedComp = await Promise.race([this.raceLoading(), loader()])
      this.setState({
        isTimeout: false,
        Comp:
          loadedComp && loadedComp.__esModule ? loadedComp.default : loadedComp,
      })
    } catch (e) {
      if (e.message === "timeout") {
        this.setState({
          isTimeout: true,
        })
        this.load()
      } else {
        this.setState({
          error: e,
        })
      }
    }
  }

  componentDidMount() {
    this.load()
  }

  render() {
    const { error, isTimeout, Comp } = this.state
    const { loading } = this.props
    // 加载错误,retry
    if (error) return loading({ error, retry: this.load })
    if (isTimeout) return loading({ pastDelay: true })

    if (Comp) return <Comp {...this.props} />
    return null
  }
}

标记动态加载的组件,用于服务端识别:

const asyncLoader = ({ loader, loading, pastDelay }) => {
  const importable = props => (
    <Loadable
      loader={loader}
      loading={loading}
      pastDelay={pastDelay}
      {...props}
    />
  )

  // 标记
  importable.isAsyncComp = true

  return importable
}

封装好页面的动态加载后需要考虑两点:

  1. ssr 的时候需要主动去执行动态路由的组件,不然服务端不会渲染组件本身的内容
  2. 在浏览器端不先去加载动态 split 出的组件的话,会导致组件的 loading 状态闪现。所以,要先加载好动态路由组件,再去渲染页面。

具体代码如下:

服务端加载标记 isAsyncComp 的动态组件:

const ssrRoutesCapture = async (routes, requestPath) => {
  const ssrRoutes = await Promise.allSettled(
    [...routes].map(async route => {
      if (route.routes) {
        return {
          ...route,
          routes: await Promise.allSettled(
            [...route.routes].map(async compRoute => {
              const { component } = compRoute

              if (component.isAsyncComp) {
                try {
                  const RealComp = await component().props.loader()

                  const ReactComp =
                    RealComp && RealComp.__esModule
                      ? RealComp.default
                      : RealComp

                  return {
                    ...compRoute,
                    component: ReactComp,
                  }
                } catch (e) {
                  console.error(e)
                }
              }
              return compRoute
            }),
          ).then(res => res.map(r => r.value)),
        }
      }
      return {
        ...route,
      }
    }),
  ).then(res => res.map(r => r.value))

  return ssrRoutes
}

浏览器端加载动态组件:

const clientPreloadReady = async routes => {
  try {
    // 匹配当前页面的组件
    const matchedRoutes = matchRoutes(routes, window.location.pathname)

    if (matchedRoutes && matchedRoutes.length) {
      await Promise.allSettled(
        matchedRoutes.map(async route => {
          if (
            route?.route?.component?.isAsyncComp &&
            !route?.route?.component.csr
          ) {
            try {
              await route.route.component().props.loader()
            } catch (e) {
              await Promise.reject(e)
            }
          }
        }),
      )
    }
  } catch (e) {
    console.error(e)
  }
}

最后,在浏览器端 ReactDOM.hydrate 的时候先加载动态分割出的组件:

clientPreloadReady(routes).then(() => {
  render(<App store={store} />, document.getElementById("root"))
})

module/nomudule 模式

主要实现思路:webpack 先根据 webpack.client.js 的配置打包出支持 es module 的代码,其中产出 index.html。然后 webpack 根据 webpack.client.lengacy.js 的配置,用上一步的 index.html 为 template,打包出不支持 es module 的代码,插入 script nomodule 和 script type="module" 的脚本。主要依赖的是 html webpack plugin 的相关 hooks。webpack.client.js 和 webpack.client.lengacy.js 主要的不同是 babel 的配置和 html webpack plugin 的 template

babel presets 配置:

exports.babelPresets = env => {
  const common = [
    "@babel/preset-env",
    {
      // targets: { esmodules: true },
      useBuiltIns: "usage",
      modules: false,
      debug: false,
      bugfixes: true,
      corejs: { version: 3, proposals: true },
    },
  ]
  if (env === "node") {
    common[1].targets = {
      node: "13",
    }
  } else if (env === "legacy") {
    common[1].targets = {
      ios: "9",
      safari: "9",
    }
    common[1].bugfixes = false
  } else {
    common[1].targets = {
      esmodules: true,
    }
  }
  return common
}

实现在 html 内插入 script nomodule 和 script type="module"的 webpack 插件代码链接:https://github.com/mbaxszy7/p...

全站图片懒加载

图片懒加载的实现使用的是 IntersectionObserver 和浏览器原生支持的image lazy loading

const pikaLazy = options => {
  // 如果浏览器原生支持图片懒加载,就设置懒加载当前图片
  if ("loading" in HTMLImageElement.prototype) {
    return {
      lazyObserver: imgRef => {
        load(imgRef)
      },
    }
  }

  // 当前图片出现在当前视口,就加载图片
  const observer = new IntersectionObserver(
    (entries, originalObserver) => {
      entries.forEach(entry => {
        if (entry.intersectionRatio > 0 || entry.isIntersecting) {
          originalObserver.unobserve(entry.target)
          if (!isLoaded(entry.target)) {
            load(entry.target)
          }
        }
      })
    },
    {
      ...options,
      rootMargin: "0px",
      threshold: 0,
    },
  )

  return {
    // 设置观察图片
    lazyObserver: () => {
      const eles = document.querySelectorAll(".pika-lazy")
      for (const ele of Array.from(eles)) {
        if (observer) {
          observer.observe(ele)
          continue
        }
        if (isLoaded(ele)) continue

        load(ele)
      }
    },
  }
}

PWA

PWA 的缓存控制和更新的能力运用的是 workbox。但是加了缓存删除的逻辑:

import { cacheNames } from "workbox-core"

const currentCacheNames = {
  "whole-site": "whole-site",
  "net-easy-p": "net-easy-p",
  "api-banner": "api-banner",
  "api-personalized-newsong": "api-personalized-newsong",
  "api-playlist": "api-play-list",
  "api-songs": "api-songs",
  "api-albums": "api-albums",
  "api-mvs": "api-mvs",
  "api-music-check": "api-music-check",
  [cacheNames.precache]: cacheNames.precache,
  [cacheNames.runtime]: cacheNames.runtime,
}

self.addEventListener("activate", event => {
  event.waitUntil(
    caches.keys().then(cacheGroup => {
      return Promise.all(
        cacheGroup
          .filter(cacheName => {
            return !Object.values(currentCacheNames).includes(`${cacheName}`)
          })
          .map(cacheName => {
            // 删除与当前缓存不匹配的缓存
            return caches.delete(cacheName)
          }),
      )
    }),
  )
})

项目的 PWA 缓存控制策略主要选择的是 StaleWhileRevalidate,先展示缓存(如果有的话),然后 pwa 会更新缓存。由于项目用了 swr,该库会轮询页面的数据或者在页面从隐藏到显示时也会请求更新数据,从而达到了使用 pwa 更新的缓存的目的。

浏览器兼容

IOS >=10,
Andriod >=6

最后,如果对你的 react 学习有帮助的话,麻烦 star 一下呗~github 地址 🎉🎉

查看原文

赞 0 收藏 0 评论 0

frank 关注了收藏夹 · 2018-02-25

2017 优秀文章 - Javascript

SegmentFault 2017 Top Rank 系列之 Javascript 篇

关注 790

frank 赞了文章 · 2018-02-15

构建二叉树进行数值数组的去重及优化

构建二叉树进行数值数组的去重及优化

常见两层循环实现数组去重

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
let newArr = []
for (let i = 0; i < arr.length; i++) {
    let unique = true
    for (let j = 0; j < newArr.length; j++) {
        if (newArr[j] === arr[i]) {
            unique = false
            break
        }
    }
    if (unique) {
        newArr.push(arr[i])
    }
}
console.log(newArr)

构建二叉树实现去重(仅适用于数值类型的数组)

将先前遍历过的元素,构建成二叉树,树中每个结点都满足:左子结点的值 < 当前结点的值 < 右子结点的值

这样优化了判断元素是否之前出现过的过程

若元素比当前结点大,只需要判断元素是否在结点的右子树中出现过即可

若元素比当前结点小,只需要判断元素是否在结点的左子树中出现过即可

let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路一,记录最大最小值

记录已经插入元素的最大最小值,若比最大元素大,或最小元素小,则直接插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
        this.max = null
        this.min = null
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            this.max = value
            this.min = value
            return this.arr
        }
        if (value > this.max) {
            this.arr.push(value)
            this.max = value
            this.findMax().right = node
            return this.arr
        }
        if (value < this.min) {
            this.arr.push(value)
            this.min = value
            this.findMin().left = node
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }

    findMax() {
        let current = this.root
        while (current.right) {
            current = current.right
        }
        return current
    }

    findMin() {
        let current = this.root
        while (current.left) {
            current = current.left
        }
        return current
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路二,构建红黑树

构建红黑树,平衡树的高度

有关红黑树的部分,请见红黑树的插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
console.log(Array.from(new Set(arr)))

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
        this.parent = null
        this.color = 'red'
    }
}

class RedBlackTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            node.color = 'black'
            this.root = node
            this.arr.push(value)
            return this
        }
        let cur = this.root
        let inserted = false
        while (true) {
            if (value > cur.value) {
                if (cur.right) {
                    cur = cur.right
                } else {
                    cur.right = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value < cur.value) {
                if (cur.left) {
                    cur = cur.left
                } else {
                    cur.left = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value === cur.value) {
                break
            }
        }
        // 调整树的结构
        if(inserted){
            this.fixTree(node)
        }
        return this
    }

    fixTree(node) {
        if (!node.parent) {
            node.color = 'black'
            this.root = node
            return
        }
        if (node.parent.color === 'black') {
            return
        }
        let son = node
        let father = node.parent
        let grandFather = father.parent
        let directionFtoG = father === grandFather.left ? 'left' : 'right'
        let uncle = grandFather[directionFtoG === 'left' ? 'right' : 'left']
        let directionStoF = son === father.left ? 'left' : 'right'
        if (!uncle || uncle.color === 'black') {
            if (directionFtoG === directionStoF) {
                if (grandFather.parent) {
                    grandFather.parent[grandFather.parent.left === grandFather ? 'left' : 'right'] = father
                    father.parent = grandFather.parent
                } else {
                    this.root = father
                    father.parent = null
                }
                father.color = 'black'
                grandFather.color = 'red'

                father[father.left === son ? 'right' : 'left'] && (father[father.left === son ? 'right' : 'left'].parent = grandFather)
                grandFather[grandFather.left === father ? 'left' : 'right'] = father[father.left === son ? 'right' : 'left']

                father[father.left === son ? 'right' : 'left'] = grandFather
                grandFather.parent = father
                return
            } else {
                grandFather[directionFtoG] = son
                son.parent = grandFather

                son[directionFtoG] && (son[directionFtoG].parent = father)
                father[directionStoF] = son[directionFtoG]

                father.parent = son
                son[directionFtoG] = father
                this.fixTree(father)
            }
        } else {
            father.color = 'black'
            uncle.color = 'black'
            grandFather.color = 'red'
            this.fixTree(grandFather)
        }
    }
}

let redBlackTree = new RedBlackTree()
for (let i = 0; i < arr.length; i++) {
    redBlackTree.insert(arr[i])
}
console.log(redBlackTree.arr)

其他去重方法

通过 Set 对象去重

[...new Set(arr)]

通过 sort() + reduce() 方法去重

排序后比较相邻元素是否相同,若不同则添加至返回的数组中

值得注意的是,排序的时候,默认 compare(2, '2') 返回 0;而 reduce() 时,进行全等比较

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.sort((a, b) => {
    let res = a - b
    if (res !== 0) {
        return res
    } else {
        if (a === b) {
            return 0
        } else {
            if (typeof a === 'number') {
                return -1
            } else {
                return 1
            }
        }
    }
}).reduce((pre, cur) => {
    if (pre !== cur) {
        newArr.push(cur)
        return cur
    }
    return pre
}, null)

通过 includes() + map() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

通过 includes() + reduce() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = arr.reduce((pre, cur) => {
    !pre.includes(cur) && pre.push(cur)
    return pre
}, [])

通过对象的键值对 + JSON 对象方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let obj = {}
arr.map(a => {
    if(!obj[JSON.stringify(a)]){
        obj[JSON.stringify(a)] = 1
    }
})

console.log(Object.keys(obj).map(a => JSON.parse(a)))
查看原文

赞 6 收藏 40 评论 0

frank 赞了文章 · 2018-02-15

构建二叉树进行数值数组的去重及优化

构建二叉树进行数值数组的去重及优化

常见两层循环实现数组去重

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
let newArr = []
for (let i = 0; i < arr.length; i++) {
    let unique = true
    for (let j = 0; j < newArr.length; j++) {
        if (newArr[j] === arr[i]) {
            unique = false
            break
        }
    }
    if (unique) {
        newArr.push(arr[i])
    }
}
console.log(newArr)

构建二叉树实现去重(仅适用于数值类型的数组)

将先前遍历过的元素,构建成二叉树,树中每个结点都满足:左子结点的值 < 当前结点的值 < 右子结点的值

这样优化了判断元素是否之前出现过的过程

若元素比当前结点大,只需要判断元素是否在结点的右子树中出现过即可

若元素比当前结点小,只需要判断元素是否在结点的左子树中出现过即可

let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路一,记录最大最小值

记录已经插入元素的最大最小值,若比最大元素大,或最小元素小,则直接插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
        this.max = null
        this.min = null
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            this.max = value
            this.min = value
            return this.arr
        }
        if (value > this.max) {
            this.arr.push(value)
            this.max = value
            this.findMax().right = node
            return this.arr
        }
        if (value < this.min) {
            this.arr.push(value)
            this.min = value
            this.findMin().left = node
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }

    findMax() {
        let current = this.root
        while (current.right) {
            current = current.right
        }
        return current
    }

    findMin() {
        let current = this.root
        while (current.left) {
            current = current.left
        }
        return current
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路二,构建红黑树

构建红黑树,平衡树的高度

有关红黑树的部分,请见红黑树的插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
console.log(Array.from(new Set(arr)))

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
        this.parent = null
        this.color = 'red'
    }
}

class RedBlackTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            node.color = 'black'
            this.root = node
            this.arr.push(value)
            return this
        }
        let cur = this.root
        let inserted = false
        while (true) {
            if (value > cur.value) {
                if (cur.right) {
                    cur = cur.right
                } else {
                    cur.right = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value < cur.value) {
                if (cur.left) {
                    cur = cur.left
                } else {
                    cur.left = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value === cur.value) {
                break
            }
        }
        // 调整树的结构
        if(inserted){
            this.fixTree(node)
        }
        return this
    }

    fixTree(node) {
        if (!node.parent) {
            node.color = 'black'
            this.root = node
            return
        }
        if (node.parent.color === 'black') {
            return
        }
        let son = node
        let father = node.parent
        let grandFather = father.parent
        let directionFtoG = father === grandFather.left ? 'left' : 'right'
        let uncle = grandFather[directionFtoG === 'left' ? 'right' : 'left']
        let directionStoF = son === father.left ? 'left' : 'right'
        if (!uncle || uncle.color === 'black') {
            if (directionFtoG === directionStoF) {
                if (grandFather.parent) {
                    grandFather.parent[grandFather.parent.left === grandFather ? 'left' : 'right'] = father
                    father.parent = grandFather.parent
                } else {
                    this.root = father
                    father.parent = null
                }
                father.color = 'black'
                grandFather.color = 'red'

                father[father.left === son ? 'right' : 'left'] && (father[father.left === son ? 'right' : 'left'].parent = grandFather)
                grandFather[grandFather.left === father ? 'left' : 'right'] = father[father.left === son ? 'right' : 'left']

                father[father.left === son ? 'right' : 'left'] = grandFather
                grandFather.parent = father
                return
            } else {
                grandFather[directionFtoG] = son
                son.parent = grandFather

                son[directionFtoG] && (son[directionFtoG].parent = father)
                father[directionStoF] = son[directionFtoG]

                father.parent = son
                son[directionFtoG] = father
                this.fixTree(father)
            }
        } else {
            father.color = 'black'
            uncle.color = 'black'
            grandFather.color = 'red'
            this.fixTree(grandFather)
        }
    }
}

let redBlackTree = new RedBlackTree()
for (let i = 0; i < arr.length; i++) {
    redBlackTree.insert(arr[i])
}
console.log(redBlackTree.arr)

其他去重方法

通过 Set 对象去重

[...new Set(arr)]

通过 sort() + reduce() 方法去重

排序后比较相邻元素是否相同,若不同则添加至返回的数组中

值得注意的是,排序的时候,默认 compare(2, '2') 返回 0;而 reduce() 时,进行全等比较

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.sort((a, b) => {
    let res = a - b
    if (res !== 0) {
        return res
    } else {
        if (a === b) {
            return 0
        } else {
            if (typeof a === 'number') {
                return -1
            } else {
                return 1
            }
        }
    }
}).reduce((pre, cur) => {
    if (pre !== cur) {
        newArr.push(cur)
        return cur
    }
    return pre
}, null)

通过 includes() + map() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

通过 includes() + reduce() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = arr.reduce((pre, cur) => {
    !pre.includes(cur) && pre.push(cur)
    return pre
}, [])

通过对象的键值对 + JSON 对象方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let obj = {}
arr.map(a => {
    if(!obj[JSON.stringify(a)]){
        obj[JSON.stringify(a)] = 1
    }
})

console.log(Object.keys(obj).map(a => JSON.parse(a)))
查看原文

赞 6 收藏 40 评论 0

frank 赞了文章 · 2018-02-15

构建二叉树进行数值数组的去重及优化

构建二叉树进行数值数组的去重及优化

常见两层循环实现数组去重

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
let newArr = []
for (let i = 0; i < arr.length; i++) {
    let unique = true
    for (let j = 0; j < newArr.length; j++) {
        if (newArr[j] === arr[i]) {
            unique = false
            break
        }
    }
    if (unique) {
        newArr.push(arr[i])
    }
}
console.log(newArr)

构建二叉树实现去重(仅适用于数值类型的数组)

将先前遍历过的元素,构建成二叉树,树中每个结点都满足:左子结点的值 < 当前结点的值 < 右子结点的值

这样优化了判断元素是否之前出现过的过程

若元素比当前结点大,只需要判断元素是否在结点的右子树中出现过即可

若元素比当前结点小,只需要判断元素是否在结点的左子树中出现过即可

let arr = [0, 1, 2, 2, 5, 7, 11, 7, 6, 4,5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路一,记录最大最小值

记录已经插入元素的最大最小值,若比最大元素大,或最小元素小,则直接插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinaryTree {
    constructor() {
        this.root = null
        this.arr = []
        this.max = null
        this.min = null
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            this.root = node
            this.arr.push(value)
            this.max = value
            this.min = value
            return this.arr
        }
        if (value > this.max) {
            this.arr.push(value)
            this.max = value
            this.findMax().right = node
            return this.arr
        }
        if (value < this.min) {
            this.arr.push(value)
            this.min = value
            this.findMin().left = node
            return this.arr
        }
        let current = this.root
        while (true) {
            if (value > current.value) {
                if (current.right) {
                    current = current.right
                } else {
                    current.right = node
                    this.arr.push(value)
                    break
                }
            }
            if (value < current.value) {
                if (current.left) {
                    current = current.left
                } else {
                    current.left = node
                    this.arr.push(value)
                    break
                }
            }
            if (value === current.value) {
                break
            }
        }
        return this.arr
    }

    findMax() {
        let current = this.root
        while (current.right) {
            current = current.right
        }
        return current
    }

    findMin() {
        let current = this.root
        while (current.left) {
            current = current.left
        }
        return current
    }
}

let binaryTree = new BinaryTree()
for (let i = 0; i < arr.length; i++) {
    binaryTree.insert(arr[i])
}
console.log(binaryTree.arr)

优化思路二,构建红黑树

构建红黑树,平衡树的高度

有关红黑树的部分,请见红黑树的插入

let arr = [11, 12, 13, 9, 8, 7, 0, 1, 2, 2, 5, 7, 11, 11, 7, 6, 4, 5, 2, 2]
console.log(Array.from(new Set(arr)))

class Node {
    constructor(value) {
        this.value = value
        this.left = null
        this.right = null
        this.parent = null
        this.color = 'red'
    }
}

class RedBlackTree {
    constructor() {
        this.root = null
        this.arr = []
    }

    insert(value) {
        let node = new Node(value)
        if (!this.root) {
            node.color = 'black'
            this.root = node
            this.arr.push(value)
            return this
        }
        let cur = this.root
        let inserted = false
        while (true) {
            if (value > cur.value) {
                if (cur.right) {
                    cur = cur.right
                } else {
                    cur.right = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value < cur.value) {
                if (cur.left) {
                    cur = cur.left
                } else {
                    cur.left = node
                    this.arr.push(value)
                    node.parent = cur
                    inserted = true
                    break
                }
            }

            if (value === cur.value) {
                break
            }
        }
        // 调整树的结构
        if(inserted){
            this.fixTree(node)
        }
        return this
    }

    fixTree(node) {
        if (!node.parent) {
            node.color = 'black'
            this.root = node
            return
        }
        if (node.parent.color === 'black') {
            return
        }
        let son = node
        let father = node.parent
        let grandFather = father.parent
        let directionFtoG = father === grandFather.left ? 'left' : 'right'
        let uncle = grandFather[directionFtoG === 'left' ? 'right' : 'left']
        let directionStoF = son === father.left ? 'left' : 'right'
        if (!uncle || uncle.color === 'black') {
            if (directionFtoG === directionStoF) {
                if (grandFather.parent) {
                    grandFather.parent[grandFather.parent.left === grandFather ? 'left' : 'right'] = father
                    father.parent = grandFather.parent
                } else {
                    this.root = father
                    father.parent = null
                }
                father.color = 'black'
                grandFather.color = 'red'

                father[father.left === son ? 'right' : 'left'] && (father[father.left === son ? 'right' : 'left'].parent = grandFather)
                grandFather[grandFather.left === father ? 'left' : 'right'] = father[father.left === son ? 'right' : 'left']

                father[father.left === son ? 'right' : 'left'] = grandFather
                grandFather.parent = father
                return
            } else {
                grandFather[directionFtoG] = son
                son.parent = grandFather

                son[directionFtoG] && (son[directionFtoG].parent = father)
                father[directionStoF] = son[directionFtoG]

                father.parent = son
                son[directionFtoG] = father
                this.fixTree(father)
            }
        } else {
            father.color = 'black'
            uncle.color = 'black'
            grandFather.color = 'red'
            this.fixTree(grandFather)
        }
    }
}

let redBlackTree = new RedBlackTree()
for (let i = 0; i < arr.length; i++) {
    redBlackTree.insert(arr[i])
}
console.log(redBlackTree.arr)

其他去重方法

通过 Set 对象去重

[...new Set(arr)]

通过 sort() + reduce() 方法去重

排序后比较相邻元素是否相同,若不同则添加至返回的数组中

值得注意的是,排序的时候,默认 compare(2, '2') 返回 0;而 reduce() 时,进行全等比较

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.sort((a, b) => {
    let res = a - b
    if (res !== 0) {
        return res
    } else {
        if (a === b) {
            return 0
        } else {
            if (typeof a === 'number') {
                return -1
            } else {
                return 1
            }
        }
    }
}).reduce((pre, cur) => {
    if (pre !== cur) {
        newArr.push(cur)
        return cur
    }
    return pre
}, null)

通过 includes() + map() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = []
arr.map(a => !newArr.includes(a) && newArr.push(a))

通过 includes() + reduce() 方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let newArr = arr.reduce((pre, cur) => {
    !pre.includes(cur) && pre.push(cur)
    return pre
}, [])

通过对象的键值对 + JSON 对象方法去重

let arr = [0, 1, 2, '2', 2, 5, 7, 11, 7, 5, 2, '2', 2]
let obj = {}
arr.map(a => {
    if(!obj[JSON.stringify(a)]){
        obj[JSON.stringify(a)] = 1
    }
})

console.log(Object.keys(obj).map(a => JSON.parse(a)))
查看原文

赞 6 收藏 40 评论 0

frank 赞了文章 · 2018-02-15

MVVM 框架解析之双向绑定

MVVM 框架

近年来前端一个明显的开发趋势就是架构从传统的 MVC 模式向 MVVM 模式迁移。在传统的 MVC 下,当前前端和后端发生数据交互后会刷新整个页面,从而导致比较差的用户体验。因此我们通过 Ajax 的方式和网关 REST API 作通讯,异步的刷新页面的某个区块,来优化和提升体验。

MVVM 框架基本概念

在 MVVM 框架中,View(视图) 和 Model(数据) 是不可以直接通讯的,在它们之间存在着 ViewModel 这个中间介充当着观察者的角色。当用户操作 View(视图),ViewModel 感知到变化,然后通知 Model 发生相应改变;反之当 Model(数据) 发生改变,ViewModel 也能感知到变化,使 View 作出相应更新。这个一来一回的过程就是我们所熟知的双向绑定。

MVVM 框架的应用场景

MVVM 框架的好处显而易见:当前端对数据进行操作的时候,可以通过 Ajax 请求对数据持久化,只需改变 dom 里需要改变的那部分数据内容,而不必刷新整个页面。特别是在移动端,刷新页面的代价太昂贵。虽然有些资源会被缓存,但是页面的 dom、css、js 都会被浏览器重新解析一遍,因此移动端页面通常会被做成 SPA 单页应用。由此在这基础上诞生了很多 MVVM 框架,比如 React.js、Vue.js、Angular.js 等等。

MVVM 框架的简单实现

模拟 Vue 的双向绑定流,实现了一个简单的 MVVM 框架,从上图中可以看出虚线方形中就是之前提到的 ViewModel 中间介层,它充当着观察者的角色。另外可以发现双向绑定流中的 View 到 Model 其实是通过 input 的事件监听函数实现的,如果换成 React(单向绑定流) 的话,它在这一步交给状态管理工具(比如 Redux)来实现。另外双向绑定流中的 Model 到 View 其实各个 MVVM 框架实现的都是大同小异的,都用到的核心方法是 Object.defineProperty(),通过这个方法可以进行数据劫持,当数据发生变化时可以捕捉到相应变化,从而进行后续的处理。

Mvvm(入口文件) 的实现

一般会这样调用 Mvvm 框架

const vm = new Mvvm({
            el: '#app',
            data: {
              title: 'mvvm title',
              name: 'mvvm name'
            },
          })

但是这样子的话,如果要得到 title 属性就要形如 vm.data.title 这样取得,为了让 vm.title 就能获得 title 属性,从而在 Mvvm 的 prototype 上加上一个代理方法,代码如下:

function Mvvm (options) {
  this.data = options.data

  const self = this
  Object.keys(this.data).forEach(key =>
    self.proxyKeys(key)
  )
}

Mvvm.prototype = {
  proxyKeys: function(key) {
    const self = this
    Object.defineProperty(this, key, {
      get: function () { // 这里的 get 和 set 实现了 vm.data.title 和 vm.title 的值同步
        return self.data[key]
      },
      set: function (newValue) {
        self.data[key] = newValue
      }
    })
  }
}

实现了代理方法后,就步入主流程的实现

function Mvvm (options) {
  this.data = options.data
  // ...
  observe(this.data)
  new Compile(options.el, this)
}

observer(观察者) 的实现

observer 的职责是监听 Model(JS 对象) 的变化,最核心的部分就是用到了 Object.defineProperty() 的 get 和 set 方法,当要获取 Model(JS 对象) 的值时,会自动调用 get 方法;当改动了 Model(JS 对象) 的值时,会自动调用 set 方法;从而实现了对数据的劫持,代码如下所示。

let data = {
  number: 0
}

observe(data)

data.number = 1 // 值发生变化

function observe(data) {
  if (!data || typeof(data) !== 'object') {
    return
  }
  const self = this
  Object.keys(data).forEach(key =>
    self.defineReactive(data, key, data[key])
  )
}

function defineReactive(data, key, value) {
  observe(value) // 遍历嵌套对象
  Object.defineProperty(data, key, {
    get: function() {
      return value
    },
    set: function(newValue) {
      if (value !== newValue) {
        console.log('值发生变化', 'newValue:' + newValue + ' ' + 'oldValue:' + value)
        value = newValue
      }
    }
  })
}

运行代码,可以看到控制台输出 值发生变化 newValue:1 oldValue:0,至此就完成了 observer 的逻辑。

Dep(订阅者数组) 和 watcher(订阅者) 的关系

观测到变化后,我们总要通知给特定的人群,让他们做出相应的处理吧。为了更方便地理解,我们可以把订阅当成是订阅了一个微信公众号,当微信公众号的内容有更新时,那么它会把内容推送(update) 到订阅了它的人。

那么订阅了同个微信公众号的人有成千上万个,那么首先想到的就是要 new Array() 去存放这些人(html 节点)吧。于是就有了如下代码:

// observer.js
function Dep() {
  this.subs = [] // 存放订阅者
}

Dep.prototype = {
  addSub: function(sub) { // 添加订阅者
    this.subs.push(sub)
  },
  notify: function() { // 通知订阅者更新
    this.subs.forEach(function(sub) {
      sub.update()
    })
  }
}

function observe(data) {...}

function defineReactive(data, key, value) {
  var dep = new Dep()
  observe(value) // 遍历嵌套对象
  Object.defineProperty(data, key, {
    get: function() {
      if (Dep.target) { // 往订阅器添加订阅者
        dep.addSub(Dep.target)
      }
      return value
    },
    set: function(newValue) {
      if (value !== newValue) {
        console.log('值发生变化', 'newValue:' + newValue + ' ' + 'oldValue:' + value)
        value = newValue
        dep.notify()
      }
    }
  })
}

初看代码也比较顺畅了,但可能会卡在 Dep.targetsub.update,由此自然而然地将目光移向 watcher,

// watcher.js
function Watcher(vm, exp, cb) {
  this.vm = vm
  this.exp = exp
  this.cb = cb
  this.value = this.get()
}

Watcher.prototype = {
  update: function() {
    this.run()
  },

  run: function() {
    // ...
    if (value !== oldVal) {
      this.cb.call(this.vm, value) // 触发 compile 中的回调
    }
  },

  get: function() {
    Dep.target = this // 缓存自己
    const value = this.vm.data[this.exp] // 强制执行监听器里的 get 函数
    Dep.target = null // 释放自己
    return value
  }
}

从代码中可以看到当构造 Watcher 实例时,会调用 get() 方法,接着重点关注 const value = this.vm.data[this.exp] 这句,前面说了当要获取 Model(JS 对象) 的值时,会自动调用 Object.defineProperty 的 get 方法,也就是当执行完这句的时候,Dep.target 的值传进了 observer.js 中的 Object.defineProperty 的 get 方法中。同时也一目了然地在 Watcher.prototype 中发现了 update 方法,其作用即触发 compile 中绑定的回调来更新界面。至此解释了 Observer 中 Dep.target 和 sub.update 的由来。

来归纳下 Watcher 的作用,其充当了 observer 和 compile 的桥梁。

1 在自身实例化的过程中,往订阅器(dep) 中添加自己

2 当 model 发生变动,dep.notify() 通知时,其能调用自身的 update 函数,并触发 compile 绑定的回调函数实现视图更新

最后再来看下生成 Watcher 实例的 compile.js 文件。

compile(编译) 的实现

首先遍历解析的过程有多次操作 dom 节点,为提高性能和效率,会先将跟节点 el 转换成 fragment(文档碎片) 进行解析编译,解析完成,再将 fragment 添加回原来的真实 dom 节点中。代码如下:

function Compile(el, vm) {
  this.vm = vm
  this.el = document.querySelector(el)
  this.fragment = null
  this.init()
}

Compile.prototype = {
  init: function() {
    if (this.el) {
      this.fragment = this.nodeToFragment(this.el) // 将节点转为 fragment 文档碎片
      this.compileElement(this.fragment) // 对 fragment 进行编译解析
      this.el.appendChild(this.fragment)
    }
  },
  nodeToFragment: function(el) {
    const fragment = document.createDocumentFragment()
    let child = el.firstChild // △ 第一个 firstChild 是 text
    while(child) {
      fragment.appendChild(child)
      child = el.firstChild
    }
    return fragment
  },
  compileElement: function(el) {...},
}

这个简单的 mvvm 框架在对 fragment 编译解析的过程中对 {{}} 文本元素v-on:click 事件指令v-model 指令三种类型进行了相应的处理。

Compile.prototype = {
  init: function() {
    if (this.el) {
      this.fragment = this.nodeToFragment(this.el) // 将节点转为 fragment 文档碎片
      this.compileElement(this.fragment) // 对 fragment 进行编译解析
      this.el.appendChild(this.fragment)
    }
  },
  nodeToFragment: function(el) {...},
  compileElement: function(el) {...},
  compileText: function (node, exp) { // 对文本类型进行处理,将 {{abc}} 替换掉
    const self = this
    const initText = this.vm[exp]
    this.updateText(node, initText) // 初始化
    new Watcher(this.vm, exp, function(value) { // 实例化订阅者
      self.updateText(node, value)
    })
  },

  compileEvent: function (node, vm, exp, dir) { // 对事件指令进行处理
    const eventType = dir.split(':')[1]
    const cb = vm.methods && vm.methods[exp]

    if (eventType && cb) {
      node.addEventListener(eventType, cb.bind(vm), false)
    }
  },

  compileModel: function (node, vm, exp) { // 对 v-model 进行处理
    let val = vm[exp]
    const self = this
    this.modelUpdater(node, val)
    node.addEventListener('input', function (e) {
      const newValue = e.target.value
      self.vm[exp] = newValue // 实现 view 到 model 的绑定
    })
  },
}

在上述代码的 compileTest 函数中看到了期盼已久的 Watcher 实例化,对 Watcher 作用模糊的朋友可以往上回顾下 Watcher 的作用。另外在 compileModel 函数中看到了本文最开始提到的双向绑定流中的 View 到 Model 是借助 input 监听事件变化实现的。

项目地址

本文记录了些阅读 mvvm 框架源码关于双向绑定的心得,并动手实践了一个简版的 mvvm 框架,不足之处在所难免,欢迎指正。

项目演示

项目地址

查看原文

赞 3 收藏 2 评论 0

认证与成就

  • 获得 0 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2018-02-15
个人主页被 169 人浏览