GripNews18h ago
🌕 A* 演算法導論
➤ 探索圖搜尋與路徑規劃的基礎
✤ https://www.redblobgames.com/pathfinding/a-star/introduction.html
本文深入介紹了 A* 演算法及其相關的圖搜尋演算法，包括廣度優先搜尋（Breadth First Search）和戴克斯特拉演算法（Dijkstra’s Algorithm）。文章闡述了 A* 演算法的核心概念，即如何利用圖形數據結構尋找最短路徑，並探討了圖的表示方法、演算法的優化以及在遊戲地圖和環境中的應用。此外，文章還介紹瞭如何通過早期退出、權重成本等方式提升演算法效率。
+ 這篇文章解釋得非常清楚，即使我對演算法不太熟悉也能理解 A* 演算法的基本原理。
+ 我在開發遊戲時一直苦惱於路徑尋找的問題，這篇文章提供了一些非常有用的想法和實用技巧。
#演算法 #圖論 #路徑尋找
Red Blob Games: Introduction to A*

Interactive tutorial for A*, Dijkstra's Algorithm, and other pathfinding algorithms

GripNews4d ago
🌕 子字串搜尋的SIMD友善演算法
➤ 如何利用SIMD指令集提升字串搜尋效率
✤ http://0x80.pl/notesen/2016-11-28-simd-strfind.html
本文探討了在現代CPU架構下，針對字串搜尋問題的效能優化。傳統字串搜尋演算法（如Knuth-Morris-Pratt、Boyer Moore、Karp-Rabin）假設單個字元比較是廉價操作，但現代CPU的SIMD指令集允許同時比較多個字元，使得傳統假設不再成立。文章介紹了兩種利用SIMD指令集優化字串搜尋的方法，並提供了從SWAR到AVX512F等不同實現的效能測試結果，證明瞭SIMD在提升搜尋效率上的潛力。
+ 這篇文章深入淺出地解釋了SIMD運算在字串搜尋中的應用，對於想提升程式效能的開發者來說很有幫助。
+ 實際的效能測試數據讓人信服，SIMD確實能在某些情況下大幅提升搜尋速度。
#演算法 #SIMD #程式效能
SIMD-friendly algorithms for substring searching

GripNews4d ago
🌗 如何調查阿姆斯特丹建立「公平」欺詐偵測模型的嘗試
➤ AI 倫理的棘手現實：阿姆斯特丹的公平模型探索
✤ https://www.lighthousereports.com/methodology/amsterdam-fairness/
Lighthouse Reports 針對阿姆斯特丹市嘗試建立公平的社會福利欺詐偵測模型進行了深入調查。儘管該市致力於透明化和公平性，但研究發現，即使避免使用明顯的歧視性變數，模型仍可能因訓練數據的偏見和指標選擇的差異而產生不公平的結果。此調查突顯了在實際應用中建立真正公平的 AI 工具所面臨的挑戰，並呼應了歐盟等地區對 AI 監管日益增加的趨勢。
+ 「這篇文章讓我意識到，即使是為了公平而設計的 AI，也可能因為數據本身的問題而產生偏見。這真的是一個需要持續關注和改進的領域。」
+ 「阿姆斯特丹的做法值得肯定，他們願意公開模型和數據供人檢視，但這項調查也證明瞭 AI 的公平性不是一句口號，需要嚴謹的測試和監控。」
#人工智慧 #倫理 #演算法 #歧視 #社會福利
How we investigated Amsterdam’s attempt to build a ‘fair’ fraud detection model

Amsterdam spent years trying to build an unbiased welfare fraud algorithm. Here’s what we found when we analyzed it.

Lighthouse Reports
GripNewsJun 10
🌕 計算複雜性：新哥德爾獎得主風味十足且更清爽
➤ 偽隨機數與拉姆齊理論的交匯
✤ https://blog.computationalcomplexity.org/2025/06/the-new-godel-prize-winner-tastes-great.html
埃山·查託帕迪亞（Eshan Chattopadhyay）和戴維·祖克曼（David Zuckerman）因其關於顯式雙源提取器和彈性函數的論文榮獲2025年哥德爾獎。該研究成果在偽隨機性和拉姆齊理論中均有應用，尤其在構建性拉姆齊理論方面提供了顯著的改進，將建構性界限提升至指數級別。儘管作者對於其在拉姆齊理論中的應用存在爭論，但其核心價值在於從兩個獨立的低最小熵來源中提取接近完美的隨機位。
+ 聽起來這篇論文在理論計算機科學領域有著重要的影響，特別是在隨機性相關的研究中。
+ 哥德爾獎得主的研究成果，肯定非常深奧，但能應用到實際問題中，實在令人敬佩。
#計算機科學 #數學 #哥德爾獎 #演算法
The New Godel Prize Winner Tastes Great and is Less Filling

David Zuckerman The 2025 Gödel Prize has been awarded to Eshan Chattopadhyay and David Zuckerman for their paper Explicit two-source extrac...

GripNewsJun 8
🌗 計算複雜性：你所需的記憶體遠少於時間
➤ 時間與空間的劃時代差異
✤ https://blog.computationalcomplexity.org/2025/02/you-need-much-less-memory-than-time.html
最新研究表明，所有演算法都可以使用比原始演算法所需時間少得多的記憶體來模擬。Ryan Williams 的研究成果顯示，DTIME(t(n)) 包含於 DSPACE(√(t(n)log t(n)))，這相較於先前的模擬結果有顯著提升。此突破建立在James Cook和Ian Mertz的空間效率樹狀評估演算法之上，並對計算複雜性理論產生深遠影響，也可能影響 P 與 PSPACE 的分離問題。
+ 這個研究結果真是令人驚訝！一直以為時間和空間是密不可分的，現在看來事情並非如此。
+ 雖然我不是這個領域的專家，但這個發現似乎可能對未來電腦的設計和演算法的優化產生重大影響。
#計算複雜性 #演算法 #理論電腦科學
You Need Much Less Memory than Time

Just as I was complaining that we haven't seen many surprising breakthroughs in complexity recently, we get an earthquake of a result to st...

GripNewsJun 8
🌕 艾特金森抖動演算法
➤ 經典圖像濾鏡的現代實現
✤ https://gazs.github.io/canvas-atkinson-dither/
這是一個艾特金森抖動演算法的網頁應用程式，模擬了早期 Macintosh 1-bit 濾鏡的效果。它將每個像素與 50% 灰階比較，轉換為黑或白，並將差異分散到相鄰像素，以達到更平滑的視覺效果。使用者可以上傳圖片並選擇不同的尺寸進行轉換，最終圖像可以右鍵儲存。
+ 這演算法效果不錯，讓黑白圖看起來更細緻，不像直接二值化那麼粗糙！
+ 介面簡單易用，上傳圖片速度也很快，很方便！
#圖像處理 #演算法 #網頁應用程式
Atkinson Dithering

GripNewsJun 3
🌗 網格邊緣構建：藝術、科技與其他雜談
➤ 理解多邊形網格拓撲結構的關鍵
✤ https://maxliani.wordpress.com/2025/03/01/mesh-edge-construction/
本文探討了計算多邊形網格邊緣的三種等效演算法，旨在提高效率。作者首先闡述了網格拓撲的常見表示方式，區分了不同類型的邊緣概念，並以具體範例說明瞭面-頂點網格（Face-Vertex Mesh）的結構。文章重點解釋了「半邊」（Half-Edge）的概念，以及如何透過排序頂點索引來識別網格中的唯一邊緣，為後續的演算法設計奠定基礎。作者強調了理解網格拓撲結構對於3D圖形處理的重要性，並引導讀者思考邊緣的連接關係與應用場景。
+ 這篇文章深入淺出地解釋了網格邊緣的處理方式，對於從事3D圖形開發的人員來說非常有幫助。
+ 作者的講解非常清晰，範例也很實用，讓我對網格拓撲的理解更上一層樓。
#3D圖形 #演算法 #網格處理
Mesh Edge Construction

I present algorithms to compute unique edges in a polygonal mesh.

Art, Tech and other Nonsense
GripNewsMay 31
🌗 雞化逆百達夫的復仇 – Pluralistic: Cory Doctorow 的每日連結
➤ 科技、演算法與勞工權力的博弈
✤ https://pluralistic.net/2022/04/17/revenge-of-the-chickenized-reverse-centaurs/
本文探討了科技公司如何透過演算法和「雞化」手段（類似於現代養雞業的剝削模式）來控制勞工，並分析了勞工如何利用科技反制這種剝削。文章指出，演算法不僅用於提升效率，更被企業用來隱瞞真實工資、施加不合理的壓力，並將勞工變成被控制的「逆百達夫」（AI主導，人被動執行）。然而，勞工正在利用新的科技工具，如Para等應用程式，來揭露隱藏的資訊、協同行動，並試圖扭轉這種不平衡的權力關係，重新掌握談判的主動權。
+ 讀完這篇文章，我開始擔心自己是不是也正在被演算法操縱，而且根本不知道！
+ 看到勞工利用科技來反抗，真的很有希望，希望未來能有更多這樣的案例。
#勞工權益 #科技 #演算法 #企業控制
Revenge of the Chickenized Reverse-Centaurs – Pluralistic: Daily links from Cory Doctorow

GripNewsMay 29
🌗 使用純資料型態實現複數和快速傅立葉轉換 (不使用浮點數)
➤ 探索以資料型態為基礎的數值計算和演算法優化
✤ https://gist.github.com/VictorTaelin/5776ede998d0039ad1cc9b12fd96811c
這篇文章探討了使用純代數資料型態 (ADTs) 而非浮點數來實現複數和快速傅立葉轉換 (FFT) 的可能性。作者指出，在某些情境下，浮點數的應用會阻礙效能優化，尤其是在需要函數融合 (function fusion) 的環境中。文章分析了傳統 FFT 演算法中存在的效率瓶頸，並暗示了透過使用 ADTs 和更精確的程式結構來改善 FFT 效能的可能性，目標是設計出在實際應用中超越現有方法的演算法。
+ 這篇文章很有意思，它讓我重新思考了在程式設計中是否總是需要浮點數。
+ 雖然我不太懂 FFT，但文章解釋得很清楚，讓我理解到優化程式碼結構的重要性。
#程式設計 #演算法 #函數式程式設計 #效能優化
Implementing complex numbers and FFT with just datatypes (no floats)

Implementing complex numbers and FFT with just datatypes (no floats) - implementing_fft.md

Gist
GripNewsMay 28
🌕 重訪改變賽馬賭注的演算法
➤ 數學模型與賽馬博弈：比爾·賓特的成功之路
✤ https://actamachina.com/posts/annotated-benter-paper
本文探討了比爾·賓特（Bill Benter）的經典賽馬賭注策略，並運用現代程式碼進行強化，同時將其與過去三十年不斷演變的數據進行對比。文章深入研究了賓特於1994年發表的學術論文，分析其模型建構、校準以及使用PyTorch重新擬合調整因子等細節。透過對香港賽馬會歷史賠率數據的分析，本文旨在揭示數學在非傳統領域中的應用潛力。
+ 令人驚嘆！原來賽馬賭注也能運用如此複雜的數學模型，這顛覆了我對賭博的印象。
+ 這篇文章深入淺出地解釋了演算法的原理，讓人即使不懂程式碼也能理解其背後的邏輯，很有啟發性。
#賽馬 #演算法 #數據分析 #賭注策略
Revisiting the Algorithm that Changed Horse Race Betting

Explore Bill Benter’s iconic horse betting strategy, enhanced with modern code and contrasted against three decades of evolving data.

Acta Machina