線性內插法優化
研究動機&目的
根據文獻與右圖，interpolationSearch在已排序、均勻分布的資料集的搜尋時間最短，但常態、指數等非均勻分布的資料集表現不如binarySearch，或是AS、IBS等搜尋策略。文獻提出IOBS策略，最小化interpolationSearch帶來的成本，在非均勻資料集比AS、IBS快。(2024，Jun-Lin Lin)
然而，我們設計badtry ratio機制，追蹤搜尋演算法的搜尋範圍，發現interpolationSearch與binarySearch的badtry Ratio都接近0.5，顯示兩者的有效縮小範圍機率並無顯著差異，如下圖顯示。
為了確認內插法的運算優勢，本文旨在調整interpolationSearch，加快interpolationSearch在均勻分布資料集的速度，以強化interpolationSearch在均勻分布資料集的搜尋優勢。策略上參考Peter Van Sandt等人的演算法，並嘗試優化。(2019,Peter Van Sandt)
_edited.jpg)
%20(2)_edited_edited.jpg)
研究方法&實驗設計
本文將沿用Peter Van Sandt等人的策略，並調整演算法切換，如下
-
重複使用斜率:
-
內差法的除法以浮點數計算，比整數運算成本高。為了降低時間成本。Peter Van Sandt等人提出重複使用斜率一次即更新，本文近一步討論只重複利用首個斜率和重複兩次斜率。
-
-
演算法切換：
-
重複使用斜率可能導致計算位置超出資料集範圍，不符合內插法定義。
-
由研究動機可知，當接近目標位置時，切換為循序搜尋法以減少內插運算成本。
-
改寫的演算法僅改動內部判斷式及少量區域變數，盡量不增加時間複雜度下，統一使用無條件捨去進行內插計算。
實驗設計如下:
-
操縱變因:斜率重複使用次數，觀察重複次數與輸出結果的關聯。
-
實驗條件:每次執行程式皆重新生成資料集。在均勻分布、由大到小、大小一百萬筆的搜尋資料集中，抽出未排序、大小一萬筆的目標資料集做搜尋。
-
測試方法:生成30次資料集，紀錄每次生成，各搜尋演算法的執行時間，單位為奈秒。
-
數據分析:將輸出結果平均，觀察花費時間，與己有文獻做對比。考量重複使用次數對搜尋時間的影響，及切換條件的效益。
研究結果與討論
結果
經過30組資料集執行時間統計後，結果顯示本文調整未達預期，具體結果如右:
只重複利用首個斜率與重複兩次的內插法，執行時間比interpolatonSearch久，也不如文獻中表現最差的binarySearch。(2024，Jun-Lin Lin)
討論
-
策略檢討: 重複使用斜率的並非唯一且主要的影響因素。雖然時間複雜度難以顯示差異，但是由策略而新增的判斷式、區域變數之成本，反而抵銷策略優勢導致了整體執行時間的增加。
-
測試設計不夠嚴謹: 資料集大小不足，數據未嚴格處理，未量化影響，進而顯示不出差異
-
只專注在演算法層面過於單一。若搭配資料結構和儲存策略會有更多變化
-
現如今許多電腦加強浮點運算的設計，整數與浮點數的運算成本差異縮小
研究結論
本文探討了減少interpolatonSearch中浮點數運算次數的優化策略，嘗試優化interpolatonSearch，但改動時因引進額外的判斷式與變數，調整後甚至不如表現最差的binarySearch。顯示在均勻分布資料集下，對interpolatonSearch而言，減少浮點數運算的效益不如成本，儘管在數學公式上具有簡化潛力。未來的程式優化，應採取演算法搭配資料結構等整體性的策略，而非改進局部計算。未來研究演算法優化，可擴大規模與多樣化資料集避免局部改進。探索其他變因如資料結構、硬體，並統計量化策略組合的影響。