flexible-data-reordering

如何實現靈活的資料排序

最近遇到任意排序資料的需求，研究了一輪後找到了一個有趣的解決方案。

方案是一個名為 Fractional indexing 的演算法，能夠實現靈活的資料排序。

其特點為能夠在現有清單中任意位置插入新資料且不改變其他資料順序的情況下進行排序。

換個比喻，就像是可以在不變更其他人號碼牌的情況下，讓你手上的號碼牌變成任意位置，可以隨意插隊的感覺。◝( •ω• )◟

讓我們一步步探討看看。

如何排序？

如何自由調整資料排序呢？ლ(╹ε╹ლ)

有人可能會想說：「阿不就調整矩陣順序就好了？( ˘･з･)」

不過那是在同一個矩陣中才有辦法，如果是從 DB 取出來呢？

DB 內的資料通常都只能依靠某個欄位進行排序取值，不能像矩陣換個位置就行。

舉個類比情境，就像是 object 的 key-value 資料那樣，例如：

const data = {
  1: {
    name: 'cod',
    age: 10,
  },
  2: {
    name: 'cat',
    age: 1,
  },
  3: {
    name: 'dog',
    age: 4,
  },
}

需要將此 data 內容轉換成矩陣，若依據 age 排升序則為：

const list = [
  {
    name: 'cat',
    age: 1,
  },
  {
    name: 'dog',
    age: 4,
  },
  {
    name: 'cod',
    age: 10,
  },
]

object 不會保證資料順序，所以直接轉換成 array 不能保證順序正確，一定要先 sort() 才行。

剛剛依 age 欄位排序，現在需求改成可以隨意調整資料順序，該怎麼做呢？

大家可能應該都想到方法了，新增一個 order 欄位不就好了嗎？

const data = {
  1: {
    name: 'cod',
    age: 10,
    order: 1,
  },
  2: {
    name: 'cat',
    age: 1,
    order: 2,
  },
  3: {
    name: 'dog',
    age: 4,
    order: 3,
  },
}

若要移動位置，只需要調整 order 欄位的值即可。

例如：要將 dog 移到 cat 前面，只需要將 dog 的 order 改成 1.5 即可。

這就是 Fractional indexing 的核心概念！( •̀ ω •́ )✧

不過此演算法的數值範圍使用 0 到 1 之間的浮點數。

TIP

至於為甚麼是 0 到 1 之間，這個倒是沒有特別找到具體的原因，若有大大知道為甚麼還請不吝告訴我。(*´∀`)~♥

此演算法來自鼎鼎大名的 Figma，其 CTO 分享的這篇文章。

文章內有很生動的互動效果，能夠讓人更直覺地理解 Fractional indexing 運作方式。

浮點數精度

不過這裡還有個小問題，就是浮點數的精度有限，若交換太多次可能會導致因精度不足，讓排序異常。

以 JS 的數字（IEEE 754 的 64 位元雙精度浮點數）為例，小數點後大約可以正確表示到 15~17 位數字，若超過這個範圍，會出現數值遺失問題。

有沒有可以存好存滿的方法呢？

那就用字串吧！同時使用 Base62 編碼，讓字串短一點。(・∀・)９

TIP

JS 有時候也會使用字串表示數值，避免潛在的精度損失問題。

Decimal.js

甚麼是 Base62 編碼？這是一種將資料轉換成只包含 62 個可列印字元的編碼方式

62 個字元包括：

數字：0 到 9（共 10 個）
大寫英文字母：A 到 Z（共 26 個）
小寫英文字母：a 到 z（共 26 個）

總共：10 + 26 + 26 = 62 個字元

舉個例子：( ´ ▽ ` )ﾉ🌰

假設要將十進位的數字 125 轉成 Base62 編碼

125 ÷ 62 = 2 餘 1 → 第一個字元是 1
2 ÷ 62 = 0 餘 2 → 第二個字元是 2

最終得到 125 的 Base62 編碼為 21

所以 Fractional Indexing 範例程式碼才會都是奇怪的英文數字組合：

import { generateKeyBetween } from 'fractional-indexing'

const first = generateKeyBetween(null, null) // "a0"

// Insert after 1st
const second = generateKeyBetween(first, null) // "a1"

// Insert after 2nd
const third = generateKeyBetween(second, null) // "a2"

// Insert before 1st
const zeroth = generateKeyBetween(null, first) // "Zz"

// Insert in between 2nd and 3rd (midpoint)
const secondAndHalf = generateKeyBetween(second, third) // "a1V"

所以我說那個程式碼呢？

讓我們用工程師的語言來對話吧！來人啊，上程式碼！(≖‿ゝ≖)✧

這裡實作使用 fractional-indexing-jittered 這個套件。

讓我們新增一個 createDataManager function 建立一個管理資料排序的物件。

首先新增一些預期可能用到的基礎方法。

content\blog-ocean-world\flexible-data-reordering\index.ts

export function createDataManager<Data>() {
  const dataMap: Map<string, {
    data: Data;
    order: string;
  }> = new Map()

  return {
    add(data: Data) {
      return ''
    },

    moveBefore(
      id: string,
      targetId: string,
    ) { },

    moveAfter(
      id: string,
      targetId: string,
    ) { },

    delete(id: string) { },

    getAll() {
      return []
    },
  }
}

接著讓我們新增測試檔案與測試案例。

content\blog-ocean-world\flexible-data-reordering\index.test.ts

import { describe, expect, it } from 'vitest'
import { createDataManager } from './'

interface Data {
  name: string;
  value: number;
}

describe('createDataManager', () => {
  it('新增資料並取得所有資料', () => {
    const manager = createDataManager<Data>()
    manager.add({ name: 'a', value: 1 })
    manager.add({ name: 'b', value: 2 })

    const allData = manager.getAll()

    expect(allData).toHaveLength(2)
    expect(allData[0]?.name).toBe('a')
    expect(allData[1]?.name).toBe('b')
  })

  it('根據 id 刪除資料', () => {
    const manager = createDataManager<Data>()
    const aId = manager.add({ name: 'a', value: 1 })
    manager.add({ name: 'b', value: 2 })

    manager.delete(aId)

    const allData = manager.getAll()
    expect(allData).toHaveLength(1)
    expect(allData[0]?.name).toBe('b')
  })

  it('可以移動資料到指定資料之後', () => {
    const manager = createDataManager<Data>()
    const aId = manager.add({ name: 'a', value: 1 })
    const bId = manager.add({ name: 'b', value: 2 })
    const cId = manager.add({ name: 'c', value: 3 })

    manager.moveAfter(aId, cId)

    const allData = manager.getAll()
    expect(
      allData.map((d) => d.name),
    ).toEqual(['b', 'c', 'a'])
  })

  it('可以移動資料到指定資料之前', () => {
    const manager = createDataManager<Data>()
    const aId = manager.add({ name: 'a', value: 1 })
    const bId = manager.add({ name: 'b', value: 2 })
    const cId = manager.add({ name: 'c', value: 3 })

    manager.moveBefore(bId, aId)

    const allData = manager.getAll()
    expect(
      allData.map((d) => d.name),
    ).toEqual(['b', 'a', 'c'])
  })
})

執行測試，結果全部失敗，不意外，因為還沒有實作任何邏輯，如果全過我會比較驚訝。(´・ω・`)

現在讓我們完成實作吧！ヾ(◍'౪`◍)ﾉﾞ

content\blog-ocean-world\flexible-data-reordering\index.ts

import { generateKeyBetween } from 'fractional-indexing-jittered'

export function createDataManager<Data>() {
  const dataMap: Map<string, {
    data: Data;
    order: string;
  }> = new Map()

  function getDataEntriesList() {
    return Array
      .from(dataMap)
      .sort((a, b) => a[1].order < b[1].order ? -1 : 1)
  }

  return {
    add(data: Data) {
      const id = crypto.randomUUID()
      const lastData = getDataEntriesList().at(-1)

      const order = generateKeyBetween(
        lastData?.[1].order ?? null,
        null,
      )
      dataMap.set(id, { data, order })
      return id
    },
    moveBefore(
      id: string,
      targetId: string,
    ) {
      const currentData = dataMap.get(id)
      if (!currentData)
        return
      const targetData = dataMap.get(targetId)
      if (!targetData)
        return

      const dataList = getDataEntriesList()
      const targetIndex = dataList.findIndex((item) => item[0] === targetId)
      const prevTarget = dataList[targetIndex - 1]

      const newOrder = generateKeyBetween(
        prevTarget?.[1].order ?? null,
        targetData.order,
      )
      currentData.order = newOrder
      dataMap.set(id, currentData)
    },
    moveAfter(
      id: string,
      targetId: string,
    ) {
      const currentData = dataMap.get(id)
      if (!currentData)
        return
      const targetData = dataMap.get(targetId)
      if (!targetData)
        return

      const dataList = getDataEntriesList()
      const targetIndex = dataList.findIndex((item) => item[0] === targetId)
      const nextTarget = dataList[targetIndex + 1]

      const newOrder = generateKeyBetween(
        targetData.order,
        nextTarget?.[1].order ?? null,
      )
      currentData.order = newOrder
      dataMap.set(id, currentData)
    },
    delete(id: string) {
      dataMap.delete(id)
    },

    getAll() {
      return getDataEntriesList()
        .map(([_, { data }]) => data)
    },
  }
}

沒意外的話，現在測試應該全部通過了。

在 getDataEntriesList 中 log 一下內容，觀察看看 order 欄位的值。

txt

{ data: { name: 'b', value: 2 }, order: 'a1' }

{ data: { name: 'b', value: 2 }, order: 'a1' }

{ data: { name: 'b', value: 2 }, order: 'a1' }
{ data: { name: 'c', value: 3 }, order: 'a2' }
{ data: { name: 'a', value: 1 }, order: 'a3' }

{ data: { name: 'b', value: 2 }, order: 'Zz' }
{ data: { name: 'a', value: 1 }, order: 'a0' }
{ data: { name: 'c', value: 3 }, order: 'a2' }

可以發現內容與官方範例程式碼一致，相當有趣。(´,,•ω•,,)

TIP

這裡的測試案例只有簡單驗證，沒有考慮到其他案例與邊界情況，大家有興趣可以自己擴充測試。( ‧ω‧)ノ╰(‧ω‧ )

完整程式碼可以在這裡找到。

總結 🐟

Fractional indexing 演算法能夠實現靈活的資料排序，讓資料可以任意插隊。
浮點數有精度問題，使用 Base62 編碼的字串表示數值，可以避免精度損失。

如何實現靈活的資料排序 ​

如何排序？ ​

浮點數精度 ​

所以我說那個程式碼呢？ ​

總結 🐟 ​

如何實現靈活的資料排序

如何排序？

浮點數精度

所以我說那個程式碼呢？

總結 🐟