去除foreach - C#代码优化

Question

如何优化这段代码？

ParentDogList，ChildDogList是 IList，dogListBox 是列表框。

foreach (Dog ParentDog in ParentDoglist)
{
 foreach (Dog ChildDog in ChildDoglist)
 {
  if(ParentDog.StatusID==ChildDog.StatusID)
  dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key));
 }
}

编辑：ParentDogTypeList和DogTypeList已更名为ParentDoglist和ChildDoglist，两者之间没有关联。

if(ParentDog.Key==ChildDog.Key)

被更改为

if(ParentDog.StatusID==ChildDog.StatusID)

完整内容:

我需要填充下拉列表，其中包含父子关系。有些狗可能没有任何子代，这将被称为叶子狗。我还需要显示该特定类别中狗的数量。

下拉列表应如下所示：

Parent1
  Child11 (10)
  Child12 (12)
Parent2
  Child21 (23)
  Child22 (20)
Leaf1 (20)
Leaf2 (34)

因此，ParentDoglist会带来所有的Child和Leaf元素以及计数，而ChildDogList会有Parent和Leaf ID，因此我将能够将各自的Child填充到其Parent中并直接绑定Leaf。

Parent、Child和Leaf Dog将在一个表中维护，并通过statusid进行区分，计数将在另一个表中。

没有任何父级会有任何计数，只有子级和叶子级会有计数。

表模式如下图所示：

- Gopi

---

DogTypeList是所有狗品种的列表，而ParentDogTypeList则是狗品种的子集吗？ - gkrogers

这些列表是来自数据库吗？ - Sam Saffron

@Sam Saffron 是的，这两个列表都来自数据库。 - Gopi

@Preet Sangha 我有超过3个相同类型的内部foreach，所以我想减少foreach。 - Gopi

检查：如果一只狗有超过1个孩子，您希望它在Listbox中出现多次吗？您的代码似乎执行了外连接。 - H H

Answer 1

您可以对ParentDoglist和ChildDoglist进行排序，并执行线性的O(n)查找算法，而不是使用O(n^2)算法。

但您可以在O((ParentDoglist.Size() + ChildDoglist.Size()) * log2(ParentDoglist.Size() + ChildDoglist.Size()))的时间复杂度内对容器进行排序。

然后，如果您只运行此代码一次，则您的算法是最优的。但如果您需要多次搜索，则最佳解决方案是对容器进行排序，并以线性时间进行比较。但是，如果您的容器在启动搜索函数之间可能会发生更改，并且您正在使用“多次”解决方案，则必须使用RB-Tree容器来承载这些元素，因为使用普通列表后容器发生更改后，您无法在O(log(n))的时间内返回已排序状态。

- Svisstack

Answer 2

您最大的问题可能是dogListBox.Items.Add。逐个添加每个项相当昂贵。ListBox.Items.AddRange更有效率。

为了使内部循环更小，您可以在内部循环中创建一个键的查找表。

List<ListItem> listItems = new List<ListItem>();
ILookup<string, Dog> childDogsPerKey = ChildDoglist.ToLookup(dog => dog.Key);
foreach (Dog ParentDog in ParentDoglist)
{
    foreach (Dog ChildDog in childDogsPerKey[ParentDog.Key])
    {
        listItems.Add(new ListItem(ParentDog.Name, ParentDog.Key));
    }
}
dogListBox.Items.AddRange(listItems.ToArray());

这段代码假设多个子狗可以有相同的键。如果每个键只能有一个子狗，你可以使用.ToDictionary()代替。

- Albin Sunnanbo

---

同意 AddRange 可能会大有帮助。 - Sam Saffron

Answer 3

我认为最优雅和最优化的方法是使用Linq来实现。

box.Items.AddRange(
   ParentDoglist.Where(p=>ChildDoglist.Any(c=>c.StatusID== p.StatusID))
    .Select(r=>new ListItem(r.StatusID, r.Name)).ToArray());

就这样，只有一行代码。 如果您喜欢使用连接操作，您可以使用该查询语句。

box.Items.AddRange(
   ParentDoglist.Join(ChildDoglist, p => p.StatusID, c => c.StatusID, (p,c)=>p)
    .Select(r=>new ListItem(r.StatusID, r.Name)).ToArray());

- BitKFu

Answer 4

这不是 foreach 循环慢，而是添加和渲染新项慢。

使用 beginupdate/endupdate：

dogListBox.BeginUpdate();
foreach (Dog ParentDog in ParentDoglist) 
{ 
 foreach (Dog ChildDog in ChildDoglist) 
 { 
  if(ParentDog.Key==ChildDog.Key) 
  dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key)); 
 } 
} 
dogListBox.EndUpdate();

- jgauffin

Answer 5

由于这是来自数据库，数据库轮询很可能成为性能杀手。 此外，可以在SQL中进行比较ParentDog.Key==ChildDog.Key，因此您不必将所有数据拉到应用程序中，然后将其丢弃。

重新设计，以便您只需执行单个选择即可获取所有数据。

Albin提到了AddRange，但您甚至可以更进一步，使您的网格虚拟化，因此仅在用户查看该部分网格时才会拉取行显示给用户。

编辑

要生成列表，似乎您需要从DB返回类似以下内容：

Parent1, null, null
Parent1, Child1, 110
Parent1, Child12, 12
Parent2, null, null
Parent2, Child21, 23
Parent2, Child22 ,20
Leaf1, null, 20
Leaf2, null, 34

这似乎需要某种left join和count，还可能涉及union all。

- Sam Saffron

---

编辑了我的问题，以解释完整的场景。 - Gopi

是的，但是我怎么在不使用任何循环的情况下填充列表框？ - Gopi

@Sri，如果没有表架构和你使用的SQL版本（假设是SQL Server），我只能提供一个查询和一个循环，请理解。 - Sam Saffron

已更新为使用Mysql模式。 - Gopi

我使用了两个查询，一个用于获取叶子节点和子节点的计数，另一个用于获取类别，以帮助确定哪个子节点属于哪个父节点！ - Gopi

Answer 6

您可以用简单的Linq表达式替换嵌套的foreach循环。为此，您需要使用System.Linq;

foreach (Dog ParentDog in 
            (from dog in ParentDogList
             from ChildDog in dog.StatusId
             where dog.StatusId == ChildDog.StatusId)
             select dog) )
{
    dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key));
}

- Greg

Answer 7

foreach (var ParentDog in ParentDoglist.Where(p=>ChildDoglist.Any(c=>c.Key== p.Key)).ToList())
    dogListBox.Items.Add(new ListItem(ParentDog.Name, ParentDog.Key));

这就是你可以使用LinQ完成的方式

- BitKFu

---

那还是有一个隐式嵌套循环吧？ - kͩeͣmͮpͥ ͩ

这仍然是O(n^2) ;-(，只有在ChildDoglist容器中使用lazy foreach而没有任何优化。 - Svisstack