嘗試在特定範圍內查找不存在的值時，查詢是否比for循環更快？

-2

我有一個方法應該考慮一個類的實例的集合，並找到第一個正數不存在作爲這些情況下的屬性。嘗試在特定範圍內查找不存在的值時，查詢是否比for循環更快？

這是我的情況：我有一個名爲GestorePersonale（員工經理級別）的類，它管理Dipendente（員工類）的List實例。每個Dipendente都有一個ID，在List中存在的所有其他Dipendente實例中必須唯一。

當創建一個新Dipendente我必須找到一個唯一的ID分配給它。
對於這個任務，我先找出在所有情況下的列表中通過所有從0到該ID號的最高ID（Matricola），然後循環，試圖找到一個缺口ID使用新Dipendente 。如果一切都失敗了，我只會分配一個對應於max + 1的ID。

這裏是方法MatricolaMax()它負責所有那些在List（我張貼此代碼只是爲了清楚起見，實例之間返回最高的ID，它是不是問題的重點部分，儘管性能改進任何建議將高度讚賞這裏也一樣）：

private uint MatricolaMax() 
{ 
    // Looking for the highest ID 
    return dipendenti.OrderByDescending(dipendente => dipendente.Matricola).First().Matricola; 
}

，這裏是這個問題的標題是指方法：

private uint MatricolaLibera() 
{ 
    var max = MatricolaMax(); 
    for (uint i = 0; i < max; i++) 
    { 
     var conto = dipendenti.Where(dipendente => dipendente.Matricola == i).Count(); 

     if (conto == 0) 
      return i; 
    } 
    return max + 1; 
}

正如你可以在上面的代碼中看到，要找到一個缺口ID我使用一個Where查詢，以檢查與Matricola（ID），對應於i一個Dipendente實例是否存在。

如果我要做到這一點使用一個for循環，而不是查詢，這將是我寫的代碼：

private uint MatricolaLibera() 
{ 
    var max = MatricolaMax(); 
    bool found; 
    for (uint i = 0; i < max; i++) 
    { 
     found = false; 
     for(int j = 0; j < dipendenti.Count; j++) 
      if (dipendenti[j].Matricola == i) 
      { 
       found = true; 
       break; 
      } 

     if (!found) 
      return i; 
    } 
    return max + 1; 
}

基本上將內環路for和布爾檢查，看是否有免費ID被發現。

我對你的問題如下：

其中介紹（查詢與內部的for循環）兩種方法的效果最好？是否存在更好的解決方案？

來源

2012-02-08 Gabriele Cirulli

+12

你爲什麼問我們？你已經寫了兩種方式。 **運行代碼，看看哪一個更快**，然後你就會知道答案！如果你有兩匹馬，並且你想知道哪一匹馬跑得更快，你會問在互聯網上從未見過馬匹的陌生人，或者你會跑馬嗎？ – 2012-02-08 22:58:49

答案可能取決於收藏大小。我認爲如果你能衡量他們的工作方式會好得多。我會投票，第二秒會更快，因爲它不會創建新的對象。但是，我真的不認爲這種差異將是不明顯的。 – 2012-02-08 22:58:57

@EricLippert hahaha，這裏是缺乏適當的睡眠可以帶來：P。等一下，我會去試試這個併發布結果。 – 2012-02-08 23:09:05

埃裏克利珀擁有最好的回答您的主要問題，但你的「有沒有更好的辦法的問題」，這裏是一個答案。

您可以使用一個整數持有發現的最高的選項，以及一個bool數組來保存使用的值。假設你有一個好的上界，你可以用一個數組來完成這個工作，如果你不需要，你需要根據需要處理增長的數組。然後，您可以簡單地列舉您的列表，標記使用的值並在需要時更新最大值。如果您不知道上限或者它可以任意高，則使用不同的算法。

但是在這一點上，你正在尋找一些非常不平凡的代碼（可以可怕，如果執行上限是不知道），因此，如果您現有的解決方案的工作，使用它們。

來源

2012-02-08 23:21:09 Guvante

當然，正如Eric所說，你應該運行代碼來回答你的問題，哪個更好。（但應在類似於你會真正使用，不只是小尺寸看尺寸運行）

有些事情，我會建議：

你MatricolaMax方法列表進行排序，找到最高值。排序至少爲O（n * logn），而列舉列表並比較這些值將是O（n）。

這兩個MatricolaLibra函數都經歷了整個集合的每個可能的價值。這是O（n * m）。我建議一次列出所有的關鍵字，然後枚舉字典以找到第一個不存在的關鍵字。這應該快得多。

來源

2012-02-08 23:31:02

嘗試在特定範圍內查找不存在的值時，查詢是否比for循環更快？

回答

相關問題