代碼的效率和準確性

Question

我試圖來解決代碼戰爭的問題和提供的單元測試做絕對沒有任何意義......

的問題如下，聽起來絕對夠簡單，有一些在5個工作分鐘

Consider a sequence u where u is defined as follows: 

The number u(0) = 1 is the first one in u. 
For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too. 
There are no other numbers in u. 
Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...] 

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on... 

Task: 

Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u. 

Example: 

dbl_linear(10) should return 22 

起初，我用了一個SortedSet的使用爲我沒有真正關心效率的LINQ查詢，我很快就發現，該操作將不得不計算出其中n可以相等〜10萬在12秒至。

所以這個憎惡出生了，然後一次又一次地被屠殺，因爲for循環會因某種原因產生問題。然後它被「升級」爲一個while循環，它給出了更多通過的單元測試（4 - > 8）。

public class DoubleLinear { 
    public static int DblLinear(int n) { 
     ListSet<int> table = new ListSet<int> {1}; 
     for (int i = 0; i < n; i++) { 
      table.Put(Y(table[i])); 
      table.Put(Z(table[i])); 
     } 
     table.Sort(); 
     return table[n]; 
    } 

    private static int Y(int y) { 
     return 2 * y + 1; 
    } 

    private static int Z(int z) { 
     return 3 * z + 1; 
    } 

} 

public class ListSet<T> : List<T> { 
    public void Put(T item) { 
     if (!this.Contains(item)) 
      this.Add(item); 
    } 

} 

有了這個代碼仍然失敗在超過n = 75000的計算，但通過多達8個試驗。

我檢查過，如果其他人已通過這個，他們有。但是，我無法檢查他們寫了什麼來從中學習。

任何人都可以提供洞察哪裏可能是錯誤的？我敢肯定，答案顯而易見，我很愚蠢。

也是用這種方式自定義列表一個壞主意？有沒有更好的辦法？

Answer 1

ListSet排序很慢，並且在構建集合時不斷獲得內存重新分配。我會先從全尺寸表中分配表格，儘管老實說，我還會告訴你，使用一個你需要的尺寸的準系統是最好的表現。

如果您知道您需要n = 75,000+，請分配一個大小的ListSet（或ARRAY！）。如果單元測試開始將您帶入平流層，那麼我們可以討論一種二元分割技術，但這有點牽扯並且在邏輯上更難構建。

我沒有看到任何邏輯錯誤的代碼。它所產生的數字在我所站的地方是正確的。

編輯：既然你知道3N + 1> 2N + 1，你永遠只能有維持6個值：

Target index in u 
Current index in u 
Current x for y 
Current x for z 
Current val for y 
Current val for z 
public static int DblLinear(int target) { 
    uint index = 1; 
    uint ind_y = 1; 
    uint ind_z = 1; 
    uint val_y = 3; 
    uint val_z = 4; 

    if(target < 1) 
     return 1; 

    while(index < target) { 
     if(val_y < val_z) { 
      ind_y++; 
      val_y = 2*ind_y + 1; 
     } else { 
      ind_z++; 
      val_z = 3*ind_z + 1; 
     } 
     index++; 
    } 

    return (val_y < val_z) ? val_y : val_z; 

} 

您可以修改val_y如果是一個while循環（更有效的關鍵路徑）如果您要麼將分支擴展到2個條件，要麼在您吹過目標索引時執行backstep循環。

沒有內存分配一定會加快你的計算速度，即使是在這樣一個容易預測的情況下，甚至人們都想（不正確地）在分支預測中痛苦不堪。

此外，你是否在你的Visual Studio項目中優化了？如果您提交的是二進制文件而不是代碼文件，那麼這也可以減少很多時間。