ZhgChg.Li

AI 協作設計 Rangeable RFC|資料結構演算法與多語言實作詳解

針對 Medium Markup 與 AVPlayer Cache 區間問題,揭露 AI 如何從抽象問題、演算法選型到 Ruby、Swift 等多語言實作 Rangeable RFC,帶來最高效區間合併與查詢解決方案,令 Markdown 渲染效能提升超過 2 倍。

AI 協作設計 Rangeable RFC|資料結構演算法與多語言實作詳解

AI 不只會做應用:用 AI 協作完成一份資料結構 RFC 與多語言實作

以 Rangeable RFC 為例,從問題抽象、演算法選型、語意定義到 Ruby / Swift 參考實作,記錄 AI 如何參與更深入的技術研究與設計。

背景

前幾週為了 Re-Design 我的 個人網站 ,直上了 Claude Code Max 後來又用 AI x Google Apps Script 做了一個個人桌上 Dashboard Deck 把舊的 iPhone 變廢為寶;這週開始把目標轉向之前做的開源專案,用 AI 重構原本手搓的程式碼,優化效率、補充文件、補足測試。

TL;DR

先用 AI 重構了幾個開源專案的應用層面,因而得到啟發也讓他做做深入的 Foundation 資料結構設計。

A fully customized, 100% free, open-source LinkTree alternative — deployed straight to GitHub Pages.

第一個優化的是之前做的 類 — Linktree 免費開源自架版,用 AI 重整了一下架構、多設計幾個主題、多做幾個內建 Plugin、新增 Design AI Skill 讓使用者方便客製化、補充本地測試環境。

ZMediumToMarkdown

Download Medium posts as clean Markdown, preserving structure, images, links, code blocks, and common embeds for plain Markdown or Jekyll workflows.

幫你把文章的所有內容包含圖片、內嵌程式碼、Youtube 連結…全部下載轉換成 Markdown、圖片也會一起下載放到 ./assets

第二個是我一直在使用、維護了四年多的專案 — 「下載並轉換 Medium 文章成 Markdown 格式」的工具,因為後期我幾乎只把 Medium 當成文章編輯器後台,主力是透過這工具把原文下載轉換後傳到我的 自架網站

這個專案是我的網站跟 Medium 之間的重要橋樑,不能斷;當初第一版開發的時候花了我大量的時間跟精力,這幾年也都在修修補補一些小問題,但是很久沒有整個重新檢視設計與優化了。

一樣是先從 AI 優化應用開始,除了請他重構+補測試原本手搓的渲染邏輯外;還有補強 Medium Cloudflare Anti-bot 流程,讓使用者可以在遇到 Medium 阻擋爬蟲時能優雅地從 Chrome 登入後自動獲取 Cookies 然後自動執行。

mcp-medium-reader

最後還請 AI 建了 Medium.com 文章 Reader MCP 服務。

主要是基礎的轉換服務 ZMediumToMarkdown 都做好了,MCP 只是一層 Wrapper 呼叫它來做就能達成。

解決的問題是 AI 如 ChatGPT, Codex, Claude, Claude Code 貼給他 Medium 文章時很容易被 Medium 的 Cloudflare Anti-bot 阻擋爬取內容,以至於 AI 無法直接讀取文章,就算能也是讀取 HTML,不是 AI 友善的 Markdown。

mcp-medium-reader 能讓你的 AI 穿透封鎖並且讀取 Markdown 版本的 Medium 文章,節省 Token 的同時又能提升 AI 理解性。

帶標籤區間集合問題

當年在做 ZMediumToMarkdown 的時候有遇到 這個 Foundation 資料結構設計(算法)問題 ,那時候沒有多餘的精力也沒有能力解決,但現在有 AI 了,想想可以嘗試用 AI 解決這個問題。

案例一 — Medium 渲染問題

Medium.com 的 GraphQL API 回傳的文章內容資料如下格式:

{
  "text": "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.",
  "markups": [
    {
      "type": "A",
      "start": 169,
      "end": 207,
      "href": "https://zhgchg.li/posts/f6713ba3fee3/",
      "anchorType": "LINK",
      "userId": null,
      "linkMetadata": null,
      "__typename": "Markup"
    },
    {
      "type": "STRONG",
      "start": 0,
      "end": 29,
      "href": null,
      "anchorType": null,
      "userId": null,
      "linkMetadata": null,
      "__typename": "Markup"
    },
    {
      "type": "EM",
      "start": 15,
      "end": 55,
      "href": null,
      "anchorType": null,
      "userId": null,
      "linkMetadata": null,
      "__typename": "Markup"
    },
    {
      "type": "STRONG",
      "start": 69,
      "end": 88,
      "href": null,
      "anchorType": null,
      "userId": null,
      "linkMetadata": null,
      "__typename": "Markup"
    }
  ]
}

翻譯成白話文:

[0,14]    STRONG       = Lorem ipsum dol
[15,29]   STRONG + EM  = or sit amet, co
[30,55]   EM           = nsectetur adipiscing elit,
[56,68]   normal       =  sed do eiusm
[69,88]   STRONG       = od tempor incididunt
[89,168]  normal       =  ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercit
[169,207] A            = ation ullamco laboris nisi ut aliquip e

預期渲染結果:

注意:Medium 原始資料的 end 語意需依實際 API 定義轉換;本文後續以 Rangeable RFC 的 closed interval 語意說明。

問題

  • 區間疊加 同一區間可以是多個狀態疊加,例如 [15,29] 是 STRONG + EM
  • 區間交錯 極端狀況下使用者可能設定交錯的樣式,[0,29] 是 STRONG / [15,55] 是 EM

  • 區間連續合併 資料可能給 [0,12] 是 STRONG / [12,29] 是 STRONG 需要合併成 [0,29] 是 STRONG

區間疊加、區間連續合併還算好處理,最麻煩的是區間交錯閉合處理,不能直接照 index 渲染,會變成 **AA_AA**BBB_ ,需要自己處理開閉變成 **AA_AA_**_BBB_ 才會是正確的 Markdown。

iOS 開發者如果有用過 NSAttributedString attributes 也是一樣的問題,只是 Apple Foundation 幫我們做好區間合併跟疊加處理了。

當時也是搞了很久想了老半天,書到用時方恨少,平時刷題太少遇到實際要用的時候沒武器可用;那時候是用最暴力的 walkthrough 解決,結果正確只是效能跟程式碼很可怕。

關聯的 LeetCode 題型

  • Merge Intervals
56. Merge Intervals
57. Insert Interval

用途: 合併 STRONG [0,12], STRONG [13,29] -> STRONG [0,29]。

  • Sweep Line
253. Meeting Rooms II
731. My Calendar II
732. My Calendar III
1094. Car Pooling
1851. Minimum Interval to Include Each Query

用途:

STRONG [0,29]
EM     [15,55]
A      [169,207]

to

0    open STRONG
15   open EM
30   close STRONG
56   close EM
169  open A
208  close A
  • Difference Array,但不是純數字差分
370. Range Addition
1109. Corporate Flight Bookings
1094. Car Pooling

用途: 維護 active markup set

  • Interval Split / Segment Construction

用途:

STRONG [0,29]
EM     [15,55]

to

[0,14]   STRONG
[15,29]  STRONG + EM
[30,55]  EM

其他用到的題型、資料結構:

  • Event Sorting
  • Interval Partition / Segment Split
  • Stack / Parentheses Matching
  • Binary Search
  • Ordered Set / LinkedHashSet
  • Canonicalization

案例二 — AVPlayer Cache 區段問題

上面 Medium 遇到的區間問題其實我之前也遇過類似的,在開發「 AVPlayer 本地邊播邊 Cache 時 」也有遇到。

因為串流資料是不連續的,一份 Size: 1000 的 Data,AVPlayer 可能會要求 [0,100] [300–500] [150, 200]… 之間的不連續或是交錯資料。

以上圖為例,假設 目前已有資料區段: [250,566] [850,959] ,理想上:

  • AVPlayer 詢問 [0,300] 時: [0,249] 從遠端拿、[250,300] 從本地拿
  • AVPlayer 詢問 [350, 920] 時: [350,566] 從本地拿、[567,849] 從遠端拿、[850,920] 從本地拿

當時一樣遇到區間計算問題 — Covered / Uncovered Interval Query ,不過比 Medium 問題簡單因為這邊是 Binary Data 0 跟 1 的區別而已,只需要計算結果。

當時也是暫時沒解,因為光開發 AVPlayer 邊播放邊緩存的功能就花大半時間了;加上當時場景是音訊,檔案本身就不大; 直接先走區間沒資料就全拿覆蓋的方式 — 細節請參考原文章「 AVPlayer 本地 Cache 實作攻略|使用 AVAssetResourceLoaderDelegate 節省 iOS 音樂串流流量

整體協作流程

用 AI 實現 Foundation 資料結構設計

工具

  • Claude Code Max
  • Effort: Max
  • Model: Opus 4.7

流程

  • 先請 AI Plan Mode 起草研究 RFC 撰寫方案
  • 請 AI 開始研究並且有兩個 Agent 身份:一位是研究生專門負責研究與撰寫 RFC、另一位是教授只負責專注在 Review 算法效率與合理性。(Review 直到 Approve)
  • 研究生可以先以 Medium 案例為實驗、用 Ruby 開發看看
  • 最終產出 RFC.md 文件
  • 交由其他 Agent 實現到各種語言 (我 ZMediumToMarkdown 是 Ruby / AVPlayer 是 iOS Swift 問題)

1. AI 研擬資料結構 RFC — Rangeable RFC

Prompt (Plan Mode):

/plan

請使用英文,參考英文論文研究,研擬一份 RFC 實作文件,之後會交付讓其他語言可以遵循這份文件實現,研擬期間可以使用 Ruby 作為實驗語言。
你需要研究所有資料結構與演算法,找出一套時間與空間效率最平衡的算法達成需求。
工具名稱:Rangeable
功能:計算泛型物件組合的連續與不連續集合。
範例:
var strings:Rangeable<String> = []
strings.insert(Strong(), start: 2, end: 5) // 2-5 Strong
strings.insert(Strong(), start: 3, end: 7) // 3-7 Strong
strings.insert(Strong(), start: 9, end: 11) // 9-11 Strong
strings.insert(Italic(), start: 3, end: 8 ) // 3-8 Italic

// Usage:
Strong().getRange(from: strings) -> [{2,7},{9-11}]
Italic().getRange(from strings) -> [{3,8}]
//
strings[4].objs -> [Strong(), Italic()]
strings[8].objs -> [Italic()]
strings[10].objs -> [Strong()]
//
請注意 Strong, Italic 本身也是泛型,這裡只是舉例
//

實際研擬 RFC 時請用 sub-agent 一個是研究生負責研究人實現方式與撰寫 RFC、另一個是教授以學術或更深入的演算法為主回頭 Review 研究生 Agent 的產出;如果被教授 Agent 駁回就重新研究撰寫 RFC。
可以先建立 ./RubyRangeable Ruby 的實現 和 ./SwiftRangeable Swift 的實現
你可以盡情消耗 Token 與花費資源做研究。
//
提供一個實際應用場景:../ZMediumToMarkdown 中的 MarkupStyleRender.rb
目前會解析 Medium GraphQL 回傳的 Paragraphs
{"id": "f30dc1c4fe6c_19", "name": "b2ba", "type": "BQ", "href": null, "layout": null, "metadata": null, "text": "A notification webhook is an endpoint you create on your server.\n通知型 Webhook 是你在自己伺服器上建立的一個端點(endpoint)。", "hasDropCap": null, "dropCapImage": null, "markups": [{"type": "EM", "start": 0, "end": 104, "href": null, "anchorType": null, "userId": null, "linkMetadata": null, "__typename": "Markup"}], "__typename": "Paragraph", "codeBlockMetadata": null, "iframe": null, "mixtapeMetadata": null},
{"id": "f30dc1c4fe6c_20", "name": "f2e8", "type": "BQ", "href": null, "layout": null, "metadata": null, "text": "This webhook endpoint receives HTTP POST requests from App Store Connect.\n這個 Webhook 端點會接收來自 App Store Connect 的 HTTP POST 請求。", "hasDropCap": null, "dropCapImage": null, "markups": [{"type": "EM", "start": 0, "end": 126, "href": null, "anchorType": null, "userId": null, "linkMetadata": null, "__typename": "Markup"}], "__typename": "Paragraph", "codeBlockMetadata": null, "iframe": null, "mixtapeMetadata": null},
{"id": "f30dc1c4fe6c_21", "name": "1725", "type": "BQ", "href": null, "layout": null, "metadata": null, "text": "The POST requests describe important events about your app.\n這些 POST 請求會描述與你的 App 相關的重要事件。", "hasDropCap": null, "dropCapImage": null, "markups": [{"type": "EM", "start": 0, "end": 89, "href": null, "anchorType": null, "userId": null, "linkMetadata": null, "__typename": "Markup"}], "__typename": "Paragraph", "codeBlockMetadata": null, "iframe": null, "mixtapeMetadata": null},
{"id": "f30dc1c4fe6c_22", "name": "3e9d", "type": "BQ", "href": null, "layout": null, "metadata": null, "text": "Use the webhooks notifications endpoint to configure the notifications for events happening to your apps.\n你可以使用 Webhook 通知端點,來設定當你的 App 發生各種事件時所要接收的通知。", "hasDropCap": null, "dropCapImage": null, "markups": [{"type": "EM", "start": 0, "end": 151, "href": null, "anchorType": null, "userId": null, "linkMetadata": null, "__typename": "Markup"}], "__typename": "Paragraph", "codeBlockMetadata": null, "iframe": null, "mixtapeMetadata": null},
然後依照 start, end 渲染出 Markdown,可是目前沒有算法所以是用巡迴填補的方法。

2. 方案確定後研究生 Agent 開始研究 -> 產出第一版 RFC

3. 教授 Agent 開始 Review -> REJECTED

主因是教授認為 RFC 還有 6 個 MUST-FIX ,也就是不修不能通過的規格/演算法正確性問題。

4. 研究生 Agent 回頭研究修改 -> 產出第二版 RFC

5. 教授 Agent 重新 Review -> APPROVED

6. Done

  • 花費時間:約 1 hr 30 mins
  • 花費 Token:178K (約佔 Claude Code Max 5 hr 可用額度的 30%)

Rangeable RFC

TL;DR

Rangeable<Element> 是一個用來管理「元素在哪些整數閉區間內生效」的通用資料結構。它可以把同一元素重疊或相鄰的區間自動合併,並支援查詢某個 index 上有哪些元素 active,以及輸出某段範圍內的 open / close transition events。它原本是為了解決 Medium Markdown markup render 問題,例如判斷某個字元同時套用了 STRONGEMLINK 哪些樣式;但同樣 也能套用在 Calendar、遊戲狀態、Genome annotation、AVPlayer byte-range cache 等場景 。核心價值是把「區間合併、active set 查詢、邊界事件產生」抽象成一個 deterministic、跨語言一致、適合 Ruby / Swift 實作的規格。

以下 RFC 細節除非很有興趣不然可以直接略過。這邊也是直接用 AI 翻譯總結的。

Rangeable<Element> 是一個「 把元素對應到多段整數閉區間,並能快速查詢某個位置有哪些元素生效 」的通用資料結構。

它解的不是單純的 Range 問題,而是給我很多個 (元素, start, end) ,我要能:

  1. 查某個元素有哪些合併後的區間
  2. 查某個 index 上有哪些元素 active
  3. 查某段範圍內有哪些 open / close 邊界事件

RFC 明確定義 Rangeable 是一個 language-neutral、generic、integer-coordinate、closed-interval set container,元素必須可 Hash,比對以 value equality 為準。它支援 getRanger[i].objstransitions 三種查詢。

主要動機

這份 RFC 起源於 ZMediumToMarkdown 的 Medium markup render 問題。

Medium paragraph 內會有像這樣的 markups:

STRONG: [2, 5]
STRONG: [3, 7]
EM:     [4, 10]

目前 render 時需要逐字掃描,判斷每個字元上有哪些 tag active,例如 bold、italic、link、code 等。RFC 裡提到原本做法會把 markups 轉成 TagChar ,依照 startIndex 排序,然後每個字元線性掃過所有 tags,最壞會到 O(L · m)Rangeable 想把這件事抽象化成通用容器,讓 renderer 只要 insert markups,再用 r[i].objstransitions 查詢即可。

RFC 也把這個問題擴展到其他場景,例如:

RFC 明確指出共通問題是:給定很多 (eᵢ, lᵢ, hᵢ) ,查某個位置 i 時,要回傳所有滿足 l ≤ i ≤ h 的元素。

核心概念翻譯

1. Rangeable<Element>

可以想成:

Element -> [ClosedRange<Int>]

但它不是普通 Dictionary,因為它會:

  1. 自動合併同一元素的重疊區間
  2. 自動合併相鄰區間
  3. 保留元素第一次插入順序
  4. 支援快速查詢某個 index 上 active 的 elements
  5. 支援輸出 open / close transition events

例如:

insert(STRONG, 2, 5)
insert(STRONG, 3, 7)

最後會變成:

STRONG -> [(2, 7)]

因為 [2,5][3,7] 重疊。

API 重點

RFC 定義的主要 API 如下。

insert(e, start, end)

insert(e: Element, start: Int, end: Int)

效果是:

R(e) = canonicalize(R(e)  [start, end])

也就是把新區間加入元素 e 的既有區間集合,然後做 canonicalize:合併所有重疊或相鄰的區間並排序。 start > end 必須丟出 InvalidIntervalError ;重複 insert 相同內容是 idempotent,不應改變結果,也不應增加 version。

r[i].objs / activeAt(index:)

r[i] -> Slot
r.activeAt(index: i) -> Slot

回傳某個 index 上 active 的 elements。

例如:

insert(Strong, 2, 5)
insert(Italic, 3, 7)

查詢:

r[3].objs

結果是:

[Strong, Italic]

查詢複雜度目標是:

O(log M + r)

其中 M 是所有元素合併後的 interval 數量總和, r 是該位置實際回傳的元素數。

getRange(of:)

getRange(of e) -> [(Int, Int)]

回傳某個元素目前合併後的 canonical ranges。

例如:

insert(Strong, 2, 4)
insert(Strong, 5, 7)

因為 [2,4][5,7] 在整數座標上相鄰,所以結果是:

[(2, 7)]

RFC 明確要求回傳的 intervals 必須排序、互不重疊、也不相鄰。

transitions(over:)

transitions(over: ClosedRange<Int>) -> [TransitionEvent]

回傳一段範圍內的 open / close 邊界事件。

例如:

insert(Strong, 2, 5)
insert(Italic, 3, 7)

則 transitions 會是:

[
  (2, open,  Strong),
  (3, open,  Italic),
  (6, close, Strong),
  (8, close, Italic)
]

注意 close event 的位置是 hi + 1 ,因為外部語意是閉區間 [lo, hi] ,但 sweep-line 內部用「第一個不再 active 的位置」當 close coordinate。RFC 明確說明 transitions(over: lo..hi) 會包含 hi + 1 的 close event,方便處理右邊界。

區間語意

1. end 是 inclusive

這份 RFC 非常明確: insert(e, start: a, end: b) 表示閉區間 [a, b]b 本身也包含在 active range 裡。

也就是:

insert(Strong, 2, 5)

代表:

2, 3, 4, 5  active

不是 [2, 5)

RFC 選擇 inclusive 的原因包括:

  1. 符合 Medium markup / ZMediumToMarkdown 的歷史資料模型
  2. 比較符合「這個字元是否 active」的人類直覺
  3. 整數相鄰合併可以寫成 hi + 1 == lo
  4. 單點區間 [k, k] 可以自然表示一個有效位置

2. 相鄰區間要合併

在整數座標上:

[2, 4] + [5, 7] => [2, 7]

因為 4 和 5 之間沒有任何整數位置可以表示「不 active」。RFC 要求同一個元素的整數相鄰區間必須合併。

但:

[2, 4] + [6, 7] => [(2, 4), (6, 7)]

因為中間有 5 這個 gap。

3. start == end 是合法 singleton interval

insert(e, 5, 5)

代表只有 index 5 active。RFC 要求這是合法且非空的區間。

4. start > end 必須丟錯

insert(e, 10, 5)

不能自動反轉成 [5,10] ,也不能 silent normalize。RFC 要求必須丟出 InvalidIntervalError ,而且 container 狀態不能改變。

Element equality 語意

Rangeable 判斷兩個 element 是否同一個元素,是看語言原生的 value equality。

Ruby:

eql? + hash

Swift:

Hashable / Equatable

所以:

Link("a")  Link("a") 會被視為同一個元素,區間會合併
Link("a")  Link("b") 是不同元素,不會合併
Strong()  Strong() 如果 equality 相等,也會合併

RFC 要求 equality 必須滿足 reflexive、symmetric、transitive、hash consistency,而且元素插入後不應再被外部 mutation 破壞 hash/equality。

排序規則

這是 RFC 很重要的部分。

Active set 排序

r[i].objs 的順序不是依 hash、不是依字母、也不是依 range 長度,而是:

元素第一次被 insert 的順序

例如:

insert(Strong, 1, 10)
insert(Italic, 1, 10)
insert(Code, 1, 10)

則:

r[5].objs == [Strong, Italic, Code]

RFC 指出這樣做是為了 deterministic、跨語言一致,而且符合 Markdown nesting:越早出現的 style 通常是外層。

Merge 不會改變 insertion order

例如:

insert(Strong, 1, 5)   // Strong ord = 1
insert(Italic, 3, 7)   // Italic ord = 2
insert(Strong, 4, 8)   // Strong range 合併成 [1,8],但 ord 還是 1

查詢:

r[6].objs

結果是:

[Strong, Italic]

雖然 Strong 是第三步才延伸到 index 6,但它的 first-insert order 仍然比 Italic 早。RFC 用這個 case 釘死「元素第一次出現的順序」才是排序基準。

Transitions 排序

同一個 coordinate 上:

  1. .open.close
  2. 多個 .open :依 insertion order 升序
  3. 多個 .close :依 insertion order 降序,也就是 LIFO

這樣可以符合 Markdown stack discipline:

** open
_ open
_ close
** close

RFC 明確定義這套 tie-breaking,以避免 Ruby / Swift hash order 不一致造成跨語言輸出不同。

內部資料結構

RFC 選擇的核心設計是:

Map<Element, SortedList<Interval>>
+ insertion_order
+ lazy boundary-event index
+ version counter

1. Per-element sorted disjoint list

每個元素有自己的 interval list:

intervals: Map<Element, SortedList<Interval>>

而且必須維持 canonical form:

  1. lo 遞增排序
  2. 彼此不重疊
  3. 彼此不相鄰
  4. 每個 interval 都滿足 lo <= hi

RFC 稱這是 I1 invariant。

2. Lazy boundary-event index

Rangeable 不會每次 insert 都重建查詢 index,而是等第一次 query 時才 build。

version: Int
event_index: EventIndex?

event_index 包含:

events: SortedArray<Event>
segments: SortedArray<Segment>
version: Int

這個設計是為了符合「build-once-then-query-densely」的 workload:大量 insert 完後,再密集查詢每個位置。RFC 明確說明 lazy index 適合這種模式,因為 build phase 不需要一直 rebuild index,query phase 只付一次 O(M log M) 成本。

演算法重點

insert 的核心流程

RFC 的 pseudocode 大致是:

function insert(r, e, start, end):
  if start > end:
    raise InvalidIntervalError

  e_frozen = freeze_for_insert(e)

  if e not in intervals:
    intervals[e] = []
    insertion_order.append(e)
    ord[e] = insertion_order.length

  list = intervals[e]
  lo = start
  hi = end

  找到第一個可能與 [lo, hi] 重疊或相鄰的 interval

  while interval 跟 [lo, hi] 重疊或相鄰:
    lo = min(lo, interval.lo)
    hi = max(hi, interval.hi)
    移除舊 interval

  插入合併後的新 [lo, hi]

  如果真的有改變:
    version += 1
    event_index = nil

特別要注意 RFC 提醒不能用 lo - 1 來判斷,因為 lo == Int.min 時會 underflow;應該用 hi + 1 >= lo 或等價的 successor model。

複雜度

RFC 選擇的 reference structure 是:

per-element sorted disjoint list + lazy event index

複雜度大致如下:

其中:

m_e = 某個 element 自己的 merged interval 數量
k = 本次 insert 吸收/合併掉的舊 intervals 數量
M = 所有 elements 的 merged intervals 總數
r = 查詢位置實際 active 的 elements 數量

RFC 也指出,如果同一個位置真的有 m 個元素 active,那輸出本身就需要 Ω(m) ,所以 O(log M + m) 已經是 output-sensitive 的合理界線。

為什麼不用 Interval Tree / Segment Tree / Roaring Bitmap?

RFC 有一整節比較替代方案,最後選擇 (a) Per-element sorted disjoint list + lazy event index

重點如下:

RFC 總結選擇主結構的三個原因:

  1. per-element merge 語意自然, getRange 可以直接回傳 R(e)
  2. deterministic、跨語言可重現
  3. lazy index 很適合 build-once-then-query workload

v1 不包含的功能

RFC 明確列出 v1 不做:

remove(e, start, end)
remove(e)
clear
union / intersect / difference
persistent immutable snapshot
floating-point coordinates
multi-dimensional rectangle stabbing
r[lo...hi].objs 這種 range slot query

刪除、交集這塊也請 AI 著手在 RFC V2 實現。

請 AI 基於 Rangeable RFC 實現語言實作

流程

  1. 一樣是先走 /plan Plan Mode 請 AI 詳細閱讀 RFC 並規劃實作
  2. 一樣拆分 developer / reviewer 一個做一個審核,直到沒問題
  3. 撰寫 Readme 使用文件、Push 到 GitHub

最困難的 RFC 規格研究已經完成後面的實作只要 AI 遵照這個規格實現,幾乎都不會有問題。

目前已實現的語言如下

實際應用 AI 設計開發的 — Rangeable Foundation

東西都準備好之後,回到最一開始的開源專案 ZMediumToMarkdown 的算法問題本身,請 AI 套用這個 Lib 回到、移除原本複雜的 walkthrough 做法優化架構+ 補上驗證套用前後測試

ZMediumToMarkdown 3.6.0

Performance

  • Micro-benchmark: 5.5× faster on the markup render hot path.
  • End-to-end on a real Medium article: 2.23× faster (2073 µs → 930 µs per paragraph on average).

AVPlayer 本地 Cache 實作攻略

文章內容也多補充了套用 SwiftRangeable 的案例。

讚嘆 AI

原本都只拿 AI 做一些應用問題,例如 重新設計網站個人 Dashboard 亦或是工作上的產品問題修正;首次嘗試請他深入研究解決算法、底層資料設計的問題。

效果超乎我的想像,大略閱讀了他寫的 RFC,不管是格式還是內容都不比真實的人去研究寫出來的東西還差(至少一定比我寫的好),中間有觀察他在做什麼,他會用 Web Search 去搜尋公開的相關論文或是技術文獻然後整合評估實作合理性;拆分出 doer / reviewer 的效果也很顯著,doer 會太著重在實作而 reviewer 能以更廣更高的視角來縱觀看 doer 做的東西有沒有 side effect;最後 RFC 定下後再請 AI 基於這個文件實作,準確度幾乎是 100%。

AI 使用的反思

不過大家也不用怕被 AI 取代,主要還是解決問題的思維,這個 AI 就很弱了;例如如果直接叫他去優化 ZMediumToMarkdown 他可能只能專注在 Medium 的場景還有原本程式的寫法; 但是人知道可以抽成 Foundation,可以先研究 RFC,最後再實踐,這樣效果更好;當然我們也可以自己做,只是需要時間,AI 是幫我們加速這個過程,不是取代我們。

在 GitHub 上補充修正
編輯這篇文章
本文首次發表於 Medium
點此查看原文
分享這篇文章
複製連結 · 分享到社群
ZhgChgLi
作者

ZhgChgLi

An iOS, web, and automation developer from Taiwan 🇹🇼 who also loves sharing, traveling, and writing.

留言 · Comments