歷史時間軸：排程重構優化 & Trade-off

首先思考一題：

在 Opus 4.7、GPT-5.5 能輕易吐出技術教學的現在，為何還寫技術文章？

以前幫了我們莫大的忙，但現在，這些文章的存在意義呢？

---

這題交給時間慢慢回答。

本篇呢，主要是在講需求演進導致架構迭代的過程中，該怎麼 Trade-off，以及對無時無刻都在接近的臨界點做預判。AI Assistant 能寫出最佳化的 function，但在產品體驗、效能瓶頸、開發成本的三角關係中，若沒有人下明確的指示，AI 不會主動清技術債、不會提重構優化，於是可能就這樣撞到極限，系統漸漸不穩，常常 broken。

本篇記錄了本站 STORY 頁面的 Timeline 架構迭代：從 Client-side 運算，到 Server-side pre-computation 的重構過程。

為什麼現在重構？預判臨界點

STORY 頁面的核心需求是繪製多個主題（先稱之為Cluster，如日本史、世界史）的時間軸，且相同主題的事件必須相鄰。

初期資料量少 （事件 < 100）時資料結構如下：

type TimelineData = {
  japan: Event[];
  world_history: Event[];
  books: Event[];
};

配合 D3.js 繪製 timeline，這在當初最小可行 MVP 是合理的技術選擇，開發速度快，邏輯集中在前端，且視覺直覺。沒有 Over-engineering。

但隨著資料量增加，有計畫導入 DB。舊架構的 Bottleneck 開始浮現，好比以下 UI 上的侷限與效能瓶頸。

瓶頸 1：UI 配置與 UX 的衝突

在前端動態計算 timeline 的軌道 (Track) 寬度時，會遇到以下兩難：

1. 靜態分配寬度：寫死每個 Cluster 的空間。代價是若某段期間該 Cluster 沒事件，版面會出現無謂的留白。
2. 動態分配寬度：每年份動態計算需要的空間。這會衍生另一個問題：當某 Cluster 在特定年份新增事件，其他 Cluster 的軌道是否要推移？
   • 不推移：新事件塞不下，版面破圖。
   • 推移：原有的線條會在某個年份突然轉彎。這不僅會造成 Layout Shift，導致畫面跳動，也大幅增加 D3 處理 svg path 的計算成本。

瓶頸 2：前端運算的效能限制

原先的實作是「在 render 階段即時計算 Track」。必須等所有事件的 Track 計算完畢，才能把 DOM 畫出來。

這帶來兩個致命傷：

1. 拖垮 FCP (First Contentful Paint)：運算時間隨資料量線性甚至指數增長，直接阻塞渲染。
2. 無法實作 Lazy Loading：因為軌道的佈局依賴全局資料。不知道全貌，就無法計算局部的線條位置。（詳見： [待寫] D3 Timeline - Lazy loading ）

如何解決？

用幾句話就可以描述，重構的核心思路是：將本來在前端 render 時做的大量計算 ，shift-left 到 backend，一部分甚至在寫入 DB 時就做完 pre-computation。

這樣做會有何成效，下面接著說明。

架構優化：從 O(S²) 到 O(S)

先來拆解 Before & After 時間複雜度。

變數定義：

C：表示 Cluster。在 Before以一個 Cluster 為單位分析，After因打平結構，不分 Cluster 直接表示總數。

• E：單一 Cluster 的事件數量
• S：跨年事件 (Spanning events) 數量，S <= E
• T：Track 表示 timeline 中某一事件要顯示在第幾軌道。
  同時存在的 Track 數量，最差情況 T = S
• V：當前 Viewport 內可見的事件數量，V <= S

做了哪些事	複雜度	備註
過濾跨年事件 spanningEvents	O(E)	掃描所有事件
排序 spanningEvents	O(S log S)
分配 Tracks	O(S * T)	每個事件線性掃描現有 Tracks，尋找空位
D3 繪製 Timeline	O(S)
渲染文字標籤（Title Tags）	O(V)	每次 Scroll 的成本

Before：Client-side computation

時間複雜度： O(Σ(S_c log S_c + S_c * T_c))

S_c = 該 Cluster 的 SpanningEvents。

上面寫的這個 Σ 加總，降一維來說就是每個 Cluster = O(S log S + S * T)。

這個版本的主要瓶頸是 render 階段即時計算 track layout。因為每個跨年事件都會掃描現有 tracks，複雜度是 O(S * T)，最壞會退化成 O(S²)。

After：Server-side pre-computation

重構重點是，將大量計算 shift-left 到 Server-side。

也就是在 DB 寫入 Event 時，一併把算好的 Track 寫進去，之後預計改成批次處理。前端簡化單純做 render，拿到資料直接畫。

打平結構後，前端渲染的複雜度降為 O(S)，S 表所有 Spanning Event。

把重度運算移出前端後，也一併解決了因一次性載入而做不到前述的瓶頸2 Lazy Loading 的問題。

另外，Scroll 的複雜度仍維持 O(V)，這屬於 DOM 操作的極限。有關繪製 Title tag 未來打算再寫一篇來紀錄： [待寫] 在 D3 內繪製定位標籤：SVG <text> vs HTML <foreignObject> 。

Track 分配演算法：兼顧空間與 UX

目的是解決上述的 瓶頸1。

在 timeline 時間軸，事件的 Track 軌道分配算法佔了很重要的位置，關乎到 Events 是否清晰能見，Events 不段增加時，空間是否有能夠容納，以及同一 Cluster 的事件是否能夠被安排在相鄰的軌道上，讓使用者在閱讀特定主題時，視線不用左右大幅跳動就能追蹤歷史事件。

在充滿變化的各種長度、頻度的 Events 中，要如何建構一套平衡兼顧「同 Cluster 鄰近」「空間預留／利用率」的 Track 分配演算法呢？

將邏輯移至後端預先處理後，我重新設計了 Track 分配演算法。這不僅是資料結構的轉換，更是為了提升 UX 而做的決定。

1. Stable Sort

第一步先決定事件的處理優先級，此階段時間複雜度為 O(S log S)：

spanningEvents.sort((a, b) => (
  a.yearFrom - b.yearFrom ||         // 1. 開始年份早的優先
  a.yearTo - b.yearTo ||             // 2. 結束年份早的優先
  a.clusterOrder - b.clusterOrder || // 3. 確保 Cluster 順序
  a.sortOrder - b.sortOrder          // 4. 自訂權重
));

2. Greedy Algorithm

使用 tracks: Array<{ endYear: number; clusterKey: ClusterKey}> 記錄使用中的軌道，並依序套用以下規則尋找可用 Track，此階段複雜度為 O(S * T)：

1. 優先尋找同 Cluster 且「已結束超過 10 年」的 Track。
   • UX 考量：為什麼要等 10 年，為了避免畫面上的文字標籤重疊。寧可犧牲一點垂直空間，也要確保文字的易讀性。
2. 尋找首個已結束的 Track。
   • UX 考量：依序由左至右填滿空缺，避免時間軸上出現長時間的 Track 空白。這能最大化空間利用率，讓版面緊湊不鬆散。
3. 若無空位，則在最右側開啟新 Track。

小結

被 shift-left 到 backend 的 pre-computation 整趟複雜度為 O(S log S + S * T)。雖然運算量不小，但因為是在寫入 DB 時就批次處理完畢，不是每次 Client-side rerender 都重繪。

這套算法確保了同一個 Cluster 的事件會盡可能被安排在相鄰的軌道上。這讓使用者在閱讀特定主題時，視線不用左右大幅跳動就能追蹤歷史事件，在「空間利用率」與「閱讀直覺性」之間取得了理想的平衡。