物件導向程式設計的核心理念是將資料和操作資料的方法封裝成物件，以模擬現實世界的實體。然而，並非所有問題都適合使用 OOP，尤其是一些小型專案或資料結構簡單的應用。封裝是 OOP 最有價值的特性，它能隱藏內部實作細節，簡化程式碼的維護和修改。繼承雖然可以實作程式碼重用，但實際上，透過函式庫或模組也能達到同樣的效果，甚至更有效率。多型性允許使用相同的介面操作不同型別的物件，提高了程式碼的靈活性。然而，過度使用繼承和多型性反而可能增加程式碼的複雜度，降低可讀性。因此，在實際應用中，需要根據具體問題選擇合適的程式設計方法，而非盲目追求 OOP。
對物件導向程式設計（OOP）的警惕
許多人對 OOP 持懷疑態度。Thomas Kurtz 認為 OOP 的最大優點是封裝，而非其他特性。研究表明，OOP 和程式式方法在生產力上沒有顯著差異。
OOP 的優缺點
封裝：將函式和資料繫結成新的資料型別，是 OOP 最有用的特性。
內容解密：
- 抽象化：介面和實作的分離使得編碼更容易。
- 類別介面：用於操作資料的方法集合。
繼承：透過繼承實作程式碼重用，但實際上，程式碼重用也可以透過其他方式實作，如匯入函式庫。
總之，在程式設計教育中引入 eval 能夠幫助學生理解其強大功能和潛在風險。同時，對於大型專案，應遵循合理的方法論。而對於 OOP，需要客觀評估其優缺點，並非所有情況下都是最佳選擇。
物件導向程式設計的反思
物件導向程式設計（Object-Oriented Programming, OOP）承諾可以讓程式設計師以物件而非個別元件的方式來思考和寫程式碼。這種思維方式類別似於以和絃而非個別音符來思考音樂。然而，實際上，許多有價值的問題並未從抽象資料型別中獲得太多好處。相反，許多人遇到的是為了教學而設計的人工問題，例如汽車和摩托車繼承自車輛。
封裝的設計哲學
封裝是一種設計，而有效的設計往往來自於捨棄多個無效的設計。專家建議，首先嘗試撰寫自然的函式，使其與現實相符。類別（抽象）的重點在於使思考和程式設計更加直觀。因此，與其試圖設計一個接近最佳的類別，不如設計一個易於擴充套件的類別。
def doIt(*args):
if len(args) == 1:
print(args[0])
return
if type(args[1]) == list:
print('list')
else:
print(args[1])
def main():
doIt(1) # 輸出: 1
doIt(1,'A') # 輸出: A
doIt(1,[1,2,]) # 輸出: list
內容解密：
doIt函式使用*args接受可變數量的引數。- 當只有一個引數時，直接列印該引數。
- 當有兩個引數時，檢查第二個引數是否為列表。如果是，則列印
'list'；否則，列印第二個引數。
物件之間的溝通
物件之間的溝通方式很少被討論。根據一些OOP專家的說法，有效的訊息傳遞至關重要。在撰寫神經網路程式時，最初嘗試使用Node類別，但後來發現這樣反而使事情變得複雜。因此，將程式重寫為一個神經網路類別，只建立一個物件，這樣簡化了程式碼。
多型性與運算元過載
多型性支援運算元過載，使得程式碼更加直觀。例如，在處理向量時，可以過載所有運算元，從而寫出更簡潔的表示式，如F = 3*(B+C)/4 - A/2。
工業界的觀點
工業界認為，在龐大的程式中，類別使程式碼更易於以物件的方式撰寫。然而，在大多數學校問題中，這種優勢並不明顯。
簡單幾何圖形的繪製限制
一個有趣的問題是，是否存在無法按比例繪製的簡單幾何圖形。答案在於叉積圖無法按比例繪製，因為叉積的單位與原始向量的單位不同。
最終反思
本章節探討了物件導向程式設計的優缺點，並透過例項展示瞭如何有效地使用封裝、多型性和運算元過載。同時，也指出了在某些情況下，過度使用OOP可能會導致程式碼複雜化。透過對這些概念的深入理解，可以更好地設計和實作高效、易於維護的程式碼。
演算法最佳化：從效率低下的分割問題談起
在優秀的數學普及書籍《The Golden Ticket》（P, NP，和對不可能的探索）中，作者提出了一個挑戰：將38個數字分成兩個不同的集合，每個集合包含19個數字，並且每個集合的數字總和均為1,000,000。給定的數字列表如下：
Lst = [14175, 15055, 16616, 17495, 18072, 19390, 19731,
22161, 23320, 23717, 26343, 28725, 29127, 32257,
40020, 41867, 43155, 46298, 56734, 57176, 58306,
61848, 65825, 66042, 68634, 69189, 72936, 74287,
74537, 81942, 82027, 82623, 82802, 82988, 90467,
97042, 97507, 99564]
分割問題的複雜度分析
作者評論道：「這並不簡單，是吧？將這些數字分成兩組的方法超過170億種。」這個問題本質上是一個NP難題，涉及將一個集合分割成兩個具有特定屬性的子集。在本例中，這兩個子集需要具有相同的總和。
程式碼實作：暴力法（低效率）
import itertools
def find_partition(numbers):
target_sum = sum(numbers) / 2
for combination in itertools.combinations(numbers, len(numbers) // 2):
if sum(combination) == target_sum:
return combination
return None
Lst = [14175, 15055, 16616, 17495, 18072, 19390, 19731,
22161, 23320, 23717, 26343, 28725, 29127, 32257,
40020, 41867, 43155, 46298, 56734, 57176, 58306,
61848, 65825, 66042, 68634, 69189, 72936, 74287,
74537, 81942, 82027, 82623, 82802, 82988, 90467,
97042, 97507, 99564]
result = find_partition(Lst)
if result:
print("找到符合條件的子集：", result)
else:
print("未找到符合條件的子集")
#### 程式碼解析：
import itertools：匯入itertools模組，用於生成數字列表的所有可能組合。find_partition函式接收一個數字列表作為輸入，並計算目標總和（即列表總和的一半）。- 使用
itertools.combinations生成列表中所有可能的19個數字的組合，並檢查每個組合的總和是否等於目標總和。 - 如果找到符合條件的組合，則傳回該組合；否則傳回
None。 - 對給定的列表
Lst呼叫find_partition函式，並列印結果。
更高效的演算法：動態規劃
作者提出的解決方案是使用「動態規劃」。這種方法非常難以應用，以至於已經有整本文籍專門用來幫助程式設計師建立這方面的技能。動態規劃是一種透過將問題分解為更小的子問題、儲存子問題的解以避免重複計算，從而提高效率的演算法設計方法。
程式碼實作：動態規劃（高效）
def subset_sum(numbers, target_sum):
n = len(numbers)
half_n = n // 2
dp = [[False for _ in range(target_sum + 1)] for _ in range(half_n + 1)]
dp[0][0] = True
for i in range(n):
for j in range(half_n, -1, -1):
for k in range(target_sum, numbers[i] - 1, -1):
if j > 0:
dp[j][k] = dp[j][k] or dp[j-1][k-numbers[i]]
closest_sum = None
for k in range(target_sum, -1, -1):
if dp[half_n][k]:
closest_sum = k
break
# 重建子集
subset = []
remaining_sum = closest_sum
for i in range(n-1, -1, -1):
if half_n > 0 and remaining_sum >= numbers[i] and dp[half_n-1][remaining_sum-numbers[i]]:
subset.append(numbers[i])
remaining_sum -= numbers[i]
half_n -= 1
return subset
target_sum = sum(Lst) // 2
result = subset_sum(Lst, target_sum)
print("動態規劃找到的子集：", result)
#### 程式碼解析：
subset_sum函式使用動態規劃解決子集總和問題。- 初始化一個三維DP表，但這裡為了簡化直接使用了三層迴圈來更新DP狀態。
dp[j][k]表示是否能從前i個數字中選出j個數字使得它們的總和為k。- 最後透過回溯DP表來重建符合條件的子集。
無效演算法的意外高效應用
在程式設計的世界中，我們經常追求高效、最佳化的演算法，但這並不代表所有看似低效的演算法都毫無用處。事實上，有些看似無效的演算法在特定情況下反而能發揮出意想不到的效果。本文將探討「失敗快速猜測法」（fail-fast guessing）以及氣泡排序（bubble sort）這兩個例子，展示無效演算法如何在特定情境下變得高效。
失敗快速猜測法
在某些問題中，系統性地檢查每種可能性可能需要耗費大量時間。失敗快速猜測法提供了一種替代方案，透過隨機猜測來尋找解決方案。以一個從 38 個數字中找出 19 個數字總和為 1000000 的問題為例，傳統方法需要檢查所有可能的組合，但使用失敗快速猜測法，只需隨機選取 19 個不同的索引，直到找到符合條件的組合。
import random
Lst = [...] # 原始數字列表
count = 0
flag = True
while flag:
count += 1
s = set()
while len(s) < 19:
s.add(random.randint(0, 37)) # 隨機選取索引
if sum(Lst[n] for n in s) == 1000000:
s = sorted(s)
print('答案 =', end=' ')
for n in s:
print(Lst[n], end=', ')
print('\n總和 =', sum(Lst[n] for n in s))
print('嘗試次數 =', count)
flag = False
內容解密：
- 隨機選取索引：使用
random.randint(0, 37)隨機生成索引，並加入集合s中。由於集合不允許重複元素，這確保了每次選取的索引都是不同的。 - 檢查總和：計算
s中索引對應的數字總和，若總和為 1000000，則輸出結果並停止。 - 計數器：
count變數記錄了嘗試的次數，最終輸出顯示找到解所需的猜測次數。
這個方法在實際測試中僅用了不到十秒（約 220,000 次猜測）就找到了解，顯示了在某些問題上，失敗快速猜測法可以非常高效。
氣泡排序及其變體
氣泡排序是一種簡單的排序演算法，但它通常被認為是低效的。然而，在某些特定情況下，它卻能展現出意外的優勢。
標準氣泡排序
def bubble(x):
leng = len(x)
for i in range(leng-1):
for j in range(leng-i-1):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
return x
內容解密：
- 雙重迴圈：外迴圈控制排序的遍數，內迴圈進行實際的元素比較和交換。
- 元素交換：若前一個元素大於後一個，則交換兩者的位置。
- 最佳化：每次外迴圈執行後，最大的元素會「冒泡」到列表末尾，因此內迴圈的範圍逐次縮減。
儘管氣泡排序在大多數情況下表現不佳，但針對小資料集（如四個元素），經過最佳化後的版本可以非常高效。進一步地，將氣泡排序與其他技巧結合，可以衍生出更高效的演算法，如梳排序（comb sort）。
梳排序
梳排序是氣泡排序的一種改進，透過引入間隔（gap）的概念來提高效率。
def comb_sort(x):
leng = len(x)
gap = leng
flag = True
while gap != 1 or flag:
gap = max(1, int(gap / 1.3))
flag = False
for i in range(leng - gap):
if x[i] > x[i + gap]:
x[i], x[i + gap] = x[i + gap], x[i]
flag = True
return x
內容解密：
- 間隔縮減：初始間隔設為列表長度，每次迭代縮減為原來的 1/1.3，直到間隔為 1。
- 比較與交換：在每次迭代中，比較間隔為
gap的元素對，若前者大於後者，則交換。 - 標誌位：
flag用於標記是否發生了交換，若某次迭代沒有交換，則排序完成。
梳排序在實際應用中表現良好，尤其是在需要原地排序且記憶體有限的情況下，它比快速排序更容易實作且記憶體佔用更少。
解決實際問題：從排序演算法到程式設計思維
在程式設計的世界中，排序演算法是基礎且重要的課題。從簡單的氣泡排序到複雜的快速排序，每種演算法都有其特點和適用場景。本篇文章將探討兩種特殊的排序演算法：梳排序（Comb Sort）和計數排序（Count Sort），並分析它們在不同情況下的效率和適用性。
梳排序（Comb Sort）實作與分析
梳排序是一種改進的氣泡排序演算法，其主要特點是消除了「烏龜效應」（即小的元素在陣列末端會慢慢移動到前端）。以下是一個 Python 的實作範例：
def combSort(array):
aLength = len(array)
recentSwap = False
gap = aLength
while recentSwap or gap > 1:
gap = max(1, int(gap/1.3))
recentSwap = False
for i in range(aLength-gap):
j = i+gap
if array[i] > array[j]:
array[i], array[j] = array[j], array[i]
recentSwap = True
return array
內容解密：
- 初始間隙（Gap）設定：首先將間隙設為陣列長度，然後在每次迭代中以 1.3 的縮減因子減少間隙，直到間隙為 1。
- 比較與交換：在每次迭代中，遍歷陣列並比較間隙兩端的元素，如果前者大於後者，則交換它們。
- 最佳化條件：如果在某次迭代中沒有發生任何交換，則表示陣列已經排序完成，可以提前結束。
為了驗證梳排序的正確性，我們可以編寫一個測試函式來生成隨機陣列並進行排序測試：
def sortTest(trialRuns, sortFunct):
def arraySorted(x):
for i in range(len(x)-1):
if x[i] > x[i+1]:
print('NOT SORTED! at positions', i, 'and', i+1)
return False
return True
for n in range(trialRuns):
listSize = randint(0,50)
array = [randint(-20, 20) for _ in range(listSize)]
sortFunct(array)
if not arraySorted(array):
exit()
print('\nTested', sortFunct.__name__)
print('Passed test of', trialRuns, 'random trialRuns.')
print('-'*46)
from random import randint
def main():
sortTest(trialRuns=10000, sortFunct=combSort)
if __name__ == "__main__":
main()
內容解密：
- 測試函式設計：
sortTest函式接受測試次數和排序函式作為引數，生成隨機陣列並進行排序，驗證排序結果的正確性。 - 隨機陣列生成：每次測試生成一個隨機大小的陣列，包含隨機整數。
- 結果驗證：使用
arraySorted函式檢查排序後的陣列是否正確有序。
計數排序（Count Sort）實作與分析
計數排序是一種線性時間複雜度的排序演算法，適用於一定範圍內的整數排序。其基本思想是統計每個元素出現的次數，然後按照次序輸出。
def countSort(array, max_val):
counters = [0] * (max_val + 1)
for number in array:
counters[number] += 1
sorted_array = []
for number, count in enumerate(counters):
sorted_array.extend([number]*count)
return sorted_array
內容解密：
- 計數陣列初始化：建立一個計數陣列，其大小等於待排序陣列中的最大值加一。
- 元素計數：遍歷待排序陣列，對每個元素在計數陣列中對應的位置加一。
- 排序輸出：遍歷計數陣列，根據每個計數值的大小輸出對應的元素。
不同排序演算法的比較與選擇
不同的排序演算法在不同場景下有不同的效率和適用性。例如，當資料量較小時，簡單的氣泡排序可能就足夠了；而對於大資料集，快速排序或歸併排序等更高效的演算法則更為合適。計數排序則在特定範圍內的整數排序中表現出色。