0

以下是我用来计算列表中元素的幂集的两段代码

代码 1) 

 public static List<List<int>> getCpower(List<int> list)
    {
        var result = new List<List<int>>();
        for (int i = 0; i < (1 << list.Count); i++)
        { 
            var sublist = new List<int>();
            for (int j = 0; j < list.Count; j++)
            {   if ((i & (1 << j)) != 0)
                {   sublist.Add(list[j]); 
                }
            }
            result.Add(sublist); 
        }

        return result;
    }

代码 2)

public static List<List<int>> getCpower(List<int> list)
    {
        var result = new List<List<int>>();var sublist = new List<int>();
        for (int i = 0; i < (1 << list.Count); i++)
        { 
            sublist.Clear();sublist.TrimExcess();
            for (int j = 0; j < list.Count; j++)
            {   if ((i & (1 << j)) != 0)
                {   sublist.Add(list[j]); 
                }
            }
            result.Add(sublist); 
        }

        return result;
    }

第一个代码使用了一个新语句，如果我尝试找出计数为 30 的列表的幂集，则会出现 OutOfMemoryException。所以为了节省内存，我使用 Clear() 和 TrimExcess() 来获取列表，就好像它是使用新语句初始化的一样在代码2中。但是这两个代码返回不同的结果。我不明白为什么会这样。请帮忙。

下面的两块是不是做同样的事情

   for(....)   
      {
       var sublist = new List<int>();
       for(......)
           {
            //some code
           }
      }

和

 var sublist = new List<int>();
 for(.....)
    {
      sublist.Clear();sublist.TrimExcess();
      for(.... )
      {
      //some code 
      }
    }
4

3 回答 3

5

在您的第二个代码中，您只有一个嵌套列表 - 您正在添加多个引用同一个子列表的引用，这是没有意义的。

您是否考虑过您的第一个代码空间不足的原因可能是因为您从根本上试图一次在内存中保存太多数据？

您可以考虑返回IEnumerable<List<int>>这样的：

public static IEnumerable<List<int>> getCpower(List<int> list)
{
    for (int i = 0; i < (1 << list.Count); i++)
    { 
        var sublist = new List<int>();
        for (int j = 0; j < list.Count; j++)
        {   if ((i & (1 << j)) != 0)
            {   
                sublist.Add(list[j]); 
            }
        }
        yield return sublist;
    }
}

这现在将被延迟评估 - 因此您可以迭代顶级序列，但除非调用者保留列表，否则您一次只能在内存中拥有一个列表。

于 2012-06-16T18:01:39.283 回答
0

在第二段代码中，您正在清除结果列表。这会改变算法的结果。您正在丢弃您的结果，因为您正在为所有迭代重用相同的列表实例。

于 2012-06-16T18:00:55.593 回答
0

在第二个代码示例中，您只有一个sublist实例。每次循环时，相同的实例都会被清除并再次添加到列表中。这里有一个例子可以帮助你理解：

var sublist = new List<int> { 1, 2, 3 };
var result = new List<List<int>> { sublist };
//result[0] is now {1, 2, 3}
sublist.Clear();
//result[0] is now {}
result.Add(sublist);
//result[0], result[1], and sublist are the same instance
于 2012-06-16T18:01:17.343 回答