Skip to content

[Python] 陣列二分演算法(Array bisection algorithm)bisect 筆記

Last Updated on 2022-11-26 by Clay

bisect 是一個 Python 的內建模組,其主要功能是維持一個排序後的 List 順序,讓該 List 在進行插入(insert)操作後無需重新排序整個 List

很多人在寫題目、製作某項功能時可能都會有這樣的經驗:

當我們想要維持某個陣列中數值的順序,但是系統又有著需要不斷添加新的數值進入該陣列的需求,所以我們就很直覺地、無視效能地一次次重新排序陣列。

當然,這樣的操作在較長陣列中的效能是毀滅性的。而 bisect 就是基於這樣一個 bisection 的演算法去實作的。


bisect 使用方法

bisect.bisect_left(axlo=0hi=len(a)*key=None)

參數意義如下:

  • a 是一組排序後的陣列
  • x 是我們欲插入之值
  • lo 是陣列判斷的起始點,預設為 0
  • hi 是陣列判斷的結束點,預設為陣列長度
  • key 在 Python3.10 以後新增,你可以將希望判斷的比較方式寫成 key function 來使用。如果為 None,則預設是以陣列中的值大小進行比較

來看段範例程式碼:

# coding: utf-8
import bisect


def main() -> None:
    arr = [1, 2, 5, 5, 6, 8]
    insert_val = 3
    print(bisect.bisect_left(arr, insert_val))


if __name__ == "__main__":
    main()


Output:

2


我們會發現,在陣列 [1, 2, 5, 5, 6, 8] 中,如果要插入 3 這個數值,我們確實要插入在索引 2 的位置才不會讓排序亂掉。

除此之外,還有另外一個函式 bisect_right()。它又跟 bisect_left() 有什麼差異呢?


bisect.bisect_right(axlo=0hi=len(a)*key=None)

就參數上來看,這兩個函式簡直一模一樣。唯一的區別是一個是優先返回最左邊的可能插入點、另一個則是優先返回最右邊的可能插入點。

以程式來看就很明顯:

# coding: utf-8
import bisect


def main() -> None:
    arr = [1, 2, 5, 5, 6, 8]
    insert_val = 5
    print(f"bisect_left(): {bisect.bisect_left(arr, insert_val)}")
    print(f"bisect_right(): {bisect.bisect_right(arr, insert_val)}")


if __name__ == "__main__":
    main()


Output:

bisect_left(): 2
bisect_right(): 4


現在就可以很明顯看出差異。因為 5 這個數值無論放在陣列中連續個 5 中任何一個位置都行,但是一個會優先返回左邊的索引、一個則是返回最右邊的索引。


bisect.insort_left(axlo=0hi=len(a)*key=None)

這個函式就不再是搜索而已,而是直接幫你把數值插入(insert)陣列中、並且不會打亂順序。(當然,也有 insort_right()insort() 這兩個函式)

# coding: utf-8
import bisect


def main() -> None:
    # Init
    arr = [1, 2, 5, 6, 8]
    
    # Insert
    bisect.insort_left(arr, 9)
    bisect.insort_left(arr, 4)
    bisect.insort_left(arr, 7)
    bisect.insort_left(arr, 3)

    # Show
    print(f"arr: {arr}")


if __name__ == "__main__":
    main()


Output:

arr: [1, 2, 3, 4, 5, 6, 7, 8, 9]


你會發現插入新的數值並不會打亂已經排序後的陣列。


References


Read More

Tags:

Leave a Reply取消回覆

Exit mobile version