提高代碼效率 - ChatGPT應用實例

為Python代碼的效率提升提供想法。

提示

系統 
你将會得到一段Python代碼，你的任務是提供提升效率的想法。 
用戶 
from typing import List 
                        
def has_sum_k(nums: List[int], k: int) -> bool: 
   """ 
   如果在nums中有兩個不同的元素使得它們的和等于k，則返回True，否則返回False。 
   """ 
   n = len(nums) 
   for i in range(n): 
       for j in range(i+1, n): 
           if nums[i] + nums[j] == k: 
               return True 
   return False

樣例回複

當前實現的時間複雜度是O(n^2)，因為有兩層for循環。我們可以通過使用一個集合來存儲我們已經看到的數字，将它改進為O(n)。

這是改進後的代碼：

```python 
from typing import List

def has_sum_k(nums: List[int], k: int) -> bool: 
   """ 
   如果在nums中有兩個不同的元素使得它們的和等于k，則返回True，否則返回False。 
   """ 
   seen = set() 
   for num in nums: 
       if k - num in seen: 
           return True 
       seen.add(num) 
   return False 
```

在這段代碼中，我們隻遍曆一次數字列表。對于每個數字，我們檢查它的補數（k - num）是否在我們已經看到的數字的集合中。如果在，我們返回True，因為我們找到了兩個和為k的數字。如果不在，我們把當前的數字加入到集合中，然後繼續下一個數字。如果我們遍曆完列表都沒有找到兩個和為k的數字，我們就返回False。

這種方法将時間複雜度從O(n^2)降低到了O(n)，對于大列表來說，這是一個顯著的改進。空間複雜度也是O(n)，因為在最壞的情況下，我們可能需要把所有的數字都存到集合中。然而，這是為了提高時間複雜度而做的合理的權衡。

API請求

{ 
 "model": "gpt-4", 
 "messages": [ 
   { 
     "role": "system", 
     "content": "You will be provided with a piece of Python code, and your task is to provide ideas for efficiency improvements." 
   }, 
   { 
     "role": "user", 
     "content": "from typing import List\n            \n            \ndef has_sum_k(nums: List[int], k: int) -> bool:\n    \"\"\"\n    Returns True if there are two distinct elements in nums such that their sum \n    is equal to k, and otherwise returns False.\n    \"\"\"\n    n = len(nums)\n    for i in range(n):\n        for j in range(i+1, n):\n            if nums[i] + nums[j] == k:\n                return True\n    return False" 
   } 
 ], 
 "temperature": 0, 
 "max_tokens": 1024 
}

來源：Improve code efficiency

• 發表新回應