System.OutOfMemoryException 生成排列时
System.OutOfMemoryException when generating permutations
我在尝试生成 6 个字母排列时得到 System.OutOfMemoryException。 5 个字母的排列仍然有效。
这是我用来生成所有排列的代码：
private static List<string> getPermutations(int n,string source)
{
IEnumerable<string> q = source.Select(x => x.ToString());
for (int i = 0; i < n - 1; i++)
{
q = q.SelectMany(x => source, (x, y) => x + y);
}
return q.ToList(); // THIS IS WHERE THE ERROR HAPPENS
}
之后我使用这段代码根据正则表达式过滤它们：
private static List<string> filterListByRegex(List<string> list, string regex)
{
List<string> newList = list.ToList();
for (int i = newList.Count - 1; i >= 0; i--)
{
Match match = Regex.Match(""+newList[i], regex, RegexOptions.IgnoreCase);
if (!match.Success)
{
newList.RemoveAt(i);
}
}
return newList;
}
因为我真的不需要所有这些排列，有没有一种方法可以在生成排列时进行正则表达式过滤，或者我应该使用更有效的代码来生成排列？
这是一张图片，可以更好地展示我想要实现的目标：
我告诉代码要使用的是垂直字母字符串。
您运行一次性存储所有这些排列，内存不足。
假设长度为 5 个字符，则有 7,893,600 种不同的排列。
假设长度为 6 个字符，则有 165,765,600 种不同的排列。
考虑到字符串中的每个字符相当于 2 个字节的内存，您将需要 1,989,187,200 个字节（大约 2 GB）来存储所有排列。这不是很理想。
那么我们该如何解决这个问题？
我从未用 c# 编写过代码，但这里有一个实用的设计决策：在自行创建排列时执行单独的处理。这样，您只需要存储所需的排列。这是一些伪代码：
List<string> storedPermutations;
string s = createPermutation();
bool shouldAdd = shouldAddPermutation(s);
if (bool)
{
storedPermutations.add(s);
}
这可以说不是最好的（也可能不是伪代码），但这里的逻辑是决定是否在创建排列时将排列添加到列表中，而不是将所有内容都添加到列表中，并且然后尝试处理整个列表。如果你仍然 运行 内存不足，那么还有很多排列。
这里最好的做法是使用惰性初始化来避免内存中同时存在所有排列。
private static IEnumerable<string> getPermutations(int n,string source)
{
IEnumerable<string> q = source.Select(x => x.ToString());
for (int i = 0; i < n - 1; i++)
{
q = q.SelectMany(x => source, (x, y) => x + y);
}
return q;
}
private static List<string> filterListByRegex(IEnumerable<string> list, string regex)
{
List<string> newList = new List();
foreach(var item in list)
{
Match match = Regex.Match(item, regex, RegexOptions.IgnoreCase);
if (match.Success)
{
newList.Add(item);
}
}
return newList;
}
这可能不是最有效的方法，但至少可以解决内存问题。
这是一个简单的解决方案，计算和内存效率都很高。
- 不是生成整个排列列表然后查找匹配项，而是使用迭代器让我们在生成潜在的排列匹配项时对其进行处理。
- 通过一点回溯，只会生成有机会匹配您的正则表达式的排列。
您所需要的只是一个额外的正则表达式，它接受部分候选项。如果添加字符，它应该接受 可能 成为匹配项的字符串。 （在 Java 中有类似 hitEnd() 的东西会很好，它正是这样做的。这将消除对正则表达式的需要。不幸的是，我认为 .Net 中没有等价物）
在我的示例中，我想找到与正则表达式“32145.67”匹配的字符串“123456789”的排列。我使用（次优）正则表达式“^3$|^32$|^321”来丢弃不以 321 开头的排列。（当然，这里可以生成“456789”的排列并在前面添加结果为“123”，但这只是为了说明这个概念。）
此解决方案的效率主要取决于您可以在排列生成的早期丢弃多少无效匹配。
排列生成如何工作的简短说明。让我们尝试生成字符串 "abc" 的所有排列。很容易看出：
permutations("abc") = {"a" + permutations("bc"),
"b" + permutations("ac"),
"c" + permutations("ab")}
换句话说，我们获取输入字符串的每个字符，将其附加到累加器并计算输入字符串的所有排列，并删除该字符。一旦我们到达叶子 - 输入字符串的排列 - ，累加器将具有输入字符串的大小。
这可以用递归伪代码简洁地写成：
permutation(input, acc)
if input empty
return acc
foreach(character in input)
left <- remove char from input
permutation(left, acc+char)
现在这不是生成排列的最有效方法。 （参见 Heap 的算法）但至少它允许我们不探索整个树结构并仅通过查看它们的前缀来丢弃排列。
由于"yield return"在递归函数中效果不佳，我只是以迭代的方式重写了解决方案（注：space复杂度比上述递归DFS差）。
public IEnumerable<string> getPermutation(string input, string regexp)
{
Stack<string> left = new Stack<string>();
Stack<string> acc = new Stack<string>();
left.Push(input);
acc.Push("");
// generate all permutations that match regexp
while (left.Count > 0)
{
string c = left.Pop();
string r = acc.Pop();
if(r.Length==input.Length)
{
yield return r;
}
else
{
for(int i=0;i<c.Length;i++)
{
string p = r + c[i];
if (Regex.IsMatch(p,regexp)) // continue if we have a potential match
{
left.Push(c.Substring(0, i) + c.Substring(i + 1));
acc.Push(p);
}
}
}
}
}
foreach(var a in getPermutation("123456789", "^3$|^32$|^321"))
{
if(Regex.IsMatch(a, "32145.67"))
{
// found match
}
}
首先，我想说明一下，我们这里讨论的不是真正的排列，而是所谓的n-tuples或permutations with repetition-Wikipedia。
其次，关于 System.OutOfMemoryException when generating permutations，我认为我们都同意结果不应存储在列表中，而应作为可枚举的形式提供，这将允许应用过滤并仅使用（最终存储）列表中的结果兴趣。
在这方面，@juharr 提供的 LINQ 解决方案表现非常好。所以我的目标是尽量减少中间内存分配，包括字符串连接，并最终得到一个更通用、更快的解决方案。
为了做到这一点，我需要做出一些艰难的设计决定。我正在谈论的通用函数的签名将如下所示
public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)
问题是生成的数组应该是什么。如果我们遵循建议，它们应该是一个单独的数组实例。但是，请记住我想尽量减少分配，我决定打破该规则并生成一个相同的数组实例，将不修改它并在必要时克隆它的责任转移给调用者。例如，这允许调用者执行无成本过滤。或者像这样在上面实现OP函数
public static IEnumerable<string> RepeatingPermutations(this string set, int N)
{
return set.ToCharArray().RepeatingPermutations(N).Select(p => new string(p));
}
关于算法的几句话。我不想像其他一些回答者那样递归地看待问题，而是想有效地实现类似这样的东西
from e1 in set
from e2 in set
...
from eN in set
select new [] { e1, e2, .., eN }
有趣的是，我最近回答了一个相关的组合，发现算法几乎相同。
综上所述，函数如下：
public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)
{
var result = new T[N];
var indices = new int[N];
for (int pos = 0, index = 0; ;)
{
for (; pos < N; pos++, index = 0)
{
indices[pos] = index;
result[pos] = set[index];
}
yield return result;
do
{
if (pos == 0) yield break;
index = indices[--pos] + 1;
}
while (index >= set.Length);
}
}
我通过使用 N=2,3,..6 简单地调用不同的函数并简单地迭代和计数来进行一些测试。这是我机器上的结果：
A : N=2 Count= 676 Time=00:00:00.0000467 Memory= 29K
B1: N=2 Count= 676 Time=00:00:00.0000263 Memory= 16K
B2: N=2 Count= 676 Time=00:00:00.0000189 Memory= 8K
A : N=3 Count= 17,576 Time=00:00:00.0010107 Memory= 657K
B1: N=3 Count= 17,576 Time=00:00:00.0003673 Memory= 344K
B2: N=3 Count= 17,576 Time=00:00:00.0001415 Memory= 8K
A : N=4 Count= 456,976 Time=00:00:00.0184445 Memory= 2,472K
B1: N=4 Count= 456,976 Time=00:00:00.0096189 Memory= 2,520K
B2: N=4 Count= 456,976 Time=00:00:00.0033624 Memory= 8K
A : N=5 Count= 11,881,376 Time=00:00:00.4281349 Memory= 397K
B1: N=5 Count= 11,881,376 Time=00:00:00.2482835 Memory= 4,042K
B2: N=5 Count= 11,881,376 Time=00:00:00.0887759 Memory= 8K
A : N=6 Count= 308,915,776 Time=00:00:11.2697326 Memory= 1,688K
B1: N=6 Count= 308,915,776 Time=00:00:06.5638404 Memory= 1,024K
B2: N=6 Count= 308,915,776 Time=00:00:02.2674431 Memory= 8K
哪里
A - 来自@juharr 的 LINQ 函数
B1 - 我的函数与 string
B2 - 我的函数与 char[]
正如我们所见，在内存方面，这两个字符串函数具有可比性。在性能方面，LINQ 函数只慢了约 2 倍，这是相当不错的结果。
正如在这种情况下预期的那样，非分配函数明显优于它们。
更新： 根据评论中的要求，这里是上述函数的示例用法（注意它们是扩展方法，必须放在静态 class）：
var charSet = Enumerable.Range('A', 'Z' - 'A' + 1).Select(c => (char)c).ToArray();
var charPermutations = charSet.RepeatingPermutations(3);
var stringSet = new string(charset);
var stringPermutations = stringSet.RepeatingPermutations(3);
但是，请记住我所做的设计选择，因此如果您在调试器中展开 charPermutations，您将看到一个相同的值（最后一个排列）。消耗上面调用 char[] 的整个结果应该是这样的
var charPermutationList = charSet.RepeatingPermutations(3)
.Select(p => (char[])p.Clone()).ToList();
实际上，对所提供的两种方法的一个很好的补充是以下扩展方法：
public static IEnumerable<T[]> Clone<T>(this IEnumerable<T[]> source)
{
return source.Select(item => (T[])item.Clone());
}
所以消费调用会很简单
var charPermutationList = charSet.RepeatingPermutations(3).Clone().ToList();
我在尝试生成 6 个字母排列时得到 System.OutOfMemoryException。 5 个字母的排列仍然有效。
这是我用来生成所有排列的代码：
private static List<string> getPermutations(int n,string source)
{
IEnumerable<string> q = source.Select(x => x.ToString());
for (int i = 0; i < n - 1; i++)
{
q = q.SelectMany(x => source, (x, y) => x + y);
}
return q.ToList(); // THIS IS WHERE THE ERROR HAPPENS
}
之后我使用这段代码根据正则表达式过滤它们：
private static List<string> filterListByRegex(List<string> list, string regex)
{
List<string> newList = list.ToList();
for (int i = newList.Count - 1; i >= 0; i--)
{
Match match = Regex.Match(""+newList[i], regex, RegexOptions.IgnoreCase);
if (!match.Success)
{
newList.RemoveAt(i);
}
}
return newList;
}
因为我真的不需要所有这些排列，有没有一种方法可以在生成排列时进行正则表达式过滤，或者我应该使用更有效的代码来生成排列？
这是一张图片，可以更好地展示我想要实现的目标：
我告诉代码要使用的是垂直字母字符串。
您运行一次性存储所有这些排列，内存不足。
假设长度为 5 个字符，则有 7,893,600 种不同的排列。
假设长度为 6 个字符，则有 165,765,600 种不同的排列。
考虑到字符串中的每个字符相当于 2 个字节的内存，您将需要 1,989,187,200 个字节（大约 2 GB）来存储所有排列。这不是很理想。
那么我们该如何解决这个问题？
我从未用 c# 编写过代码，但这里有一个实用的设计决策：在自行创建排列时执行单独的处理。这样，您只需要存储所需的排列。这是一些伪代码：
List<string> storedPermutations;
string s = createPermutation();
bool shouldAdd = shouldAddPermutation(s);
if (bool)
{
storedPermutations.add(s);
}
这可以说不是最好的（也可能不是伪代码），但这里的逻辑是决定是否在创建排列时将排列添加到列表中，而不是将所有内容都添加到列表中，并且然后尝试处理整个列表。如果你仍然 运行 内存不足，那么还有很多排列。
这里最好的做法是使用惰性初始化来避免内存中同时存在所有排列。
private static IEnumerable<string> getPermutations(int n,string source)
{
IEnumerable<string> q = source.Select(x => x.ToString());
for (int i = 0; i < n - 1; i++)
{
q = q.SelectMany(x => source, (x, y) => x + y);
}
return q;
}
private static List<string> filterListByRegex(IEnumerable<string> list, string regex)
{
List<string> newList = new List();
foreach(var item in list)
{
Match match = Regex.Match(item, regex, RegexOptions.IgnoreCase);
if (match.Success)
{
newList.Add(item);
}
}
return newList;
}
这可能不是最有效的方法，但至少可以解决内存问题。
这是一个简单的解决方案，计算和内存效率都很高。
- 不是生成整个排列列表然后查找匹配项，而是使用迭代器让我们在生成潜在的排列匹配项时对其进行处理。
- 通过一点回溯，只会生成有机会匹配您的正则表达式的排列。
您所需要的只是一个额外的正则表达式，它接受部分候选项。如果添加字符，它应该接受 可能 成为匹配项的字符串。 （在 Java 中有类似 hitEnd() 的东西会很好，它正是这样做的。这将消除对正则表达式的需要。不幸的是，我认为 .Net 中没有等价物）
在我的示例中，我想找到与正则表达式“32145.67”匹配的字符串“123456789”的排列。我使用（次优）正则表达式“^3$|^32$|^321”来丢弃不以 321 开头的排列。（当然，这里可以生成“456789”的排列并在前面添加结果为“123”，但这只是为了说明这个概念。）
此解决方案的效率主要取决于您可以在排列生成的早期丢弃多少无效匹配。
排列生成如何工作的简短说明。让我们尝试生成字符串 "abc" 的所有排列。很容易看出：
permutations("abc") = {"a" + permutations("bc"),
"b" + permutations("ac"),
"c" + permutations("ab")}
换句话说，我们获取输入字符串的每个字符，将其附加到累加器并计算输入字符串的所有排列，并删除该字符。一旦我们到达叶子 - 输入字符串的排列 - ，累加器将具有输入字符串的大小。
这可以用递归伪代码简洁地写成：
permutation(input, acc)
if input empty
return acc
foreach(character in input)
left <- remove char from input
permutation(left, acc+char)
现在这不是生成排列的最有效方法。 （参见 Heap 的算法）但至少它允许我们不探索整个树结构并仅通过查看它们的前缀来丢弃排列。
由于"yield return"在递归函数中效果不佳，我只是以迭代的方式重写了解决方案（注：space复杂度比上述递归DFS差）。
public IEnumerable<string> getPermutation(string input, string regexp)
{
Stack<string> left = new Stack<string>();
Stack<string> acc = new Stack<string>();
left.Push(input);
acc.Push("");
// generate all permutations that match regexp
while (left.Count > 0)
{
string c = left.Pop();
string r = acc.Pop();
if(r.Length==input.Length)
{
yield return r;
}
else
{
for(int i=0;i<c.Length;i++)
{
string p = r + c[i];
if (Regex.IsMatch(p,regexp)) // continue if we have a potential match
{
left.Push(c.Substring(0, i) + c.Substring(i + 1));
acc.Push(p);
}
}
}
}
}
foreach(var a in getPermutation("123456789", "^3$|^32$|^321"))
{
if(Regex.IsMatch(a, "32145.67"))
{
// found match
}
}
首先，我想说明一下，我们这里讨论的不是真正的排列，而是所谓的n-tuples或permutations with repetition-Wikipedia。
其次，关于 System.OutOfMemoryException when generating permutations，我认为我们都同意结果不应存储在列表中，而应作为可枚举的形式提供，这将允许应用过滤并仅使用（最终存储）列表中的结果兴趣。
在这方面，@juharr 提供的 LINQ 解决方案表现非常好。所以我的目标是尽量减少中间内存分配，包括字符串连接，并最终得到一个更通用、更快的解决方案。
为了做到这一点，我需要做出一些艰难的设计决定。我正在谈论的通用函数的签名将如下所示
public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)
问题是生成的数组应该是什么。如果我们遵循建议，它们应该是一个单独的数组实例。但是，请记住我想尽量减少分配，我决定打破该规则并生成一个相同的数组实例，将不修改它并在必要时克隆它的责任转移给调用者。例如，这允许调用者执行无成本过滤。或者像这样在上面实现OP函数
public static IEnumerable<string> RepeatingPermutations(this string set, int N)
{
return set.ToCharArray().RepeatingPermutations(N).Select(p => new string(p));
}
关于算法的几句话。我不想像其他一些回答者那样递归地看待问题，而是想有效地实现类似这样的东西
from e1 in set
from e2 in set
...
from eN in set
select new [] { e1, e2, .., eN }
有趣的是，我最近回答了一个相关的组合
综上所述，函数如下：
public static IEnumerable<T[]> RepeatingPermutations<T>(this T[] set, int N)
{
var result = new T[N];
var indices = new int[N];
for (int pos = 0, index = 0; ;)
{
for (; pos < N; pos++, index = 0)
{
indices[pos] = index;
result[pos] = set[index];
}
yield return result;
do
{
if (pos == 0) yield break;
index = indices[--pos] + 1;
}
while (index >= set.Length);
}
}
我通过使用 N=2,3,..6 简单地调用不同的函数并简单地迭代和计数来进行一些测试。这是我机器上的结果：
A : N=2 Count= 676 Time=00:00:00.0000467 Memory= 29K
B1: N=2 Count= 676 Time=00:00:00.0000263 Memory= 16K
B2: N=2 Count= 676 Time=00:00:00.0000189 Memory= 8K
A : N=3 Count= 17,576 Time=00:00:00.0010107 Memory= 657K
B1: N=3 Count= 17,576 Time=00:00:00.0003673 Memory= 344K
B2: N=3 Count= 17,576 Time=00:00:00.0001415 Memory= 8K
A : N=4 Count= 456,976 Time=00:00:00.0184445 Memory= 2,472K
B1: N=4 Count= 456,976 Time=00:00:00.0096189 Memory= 2,520K
B2: N=4 Count= 456,976 Time=00:00:00.0033624 Memory= 8K
A : N=5 Count= 11,881,376 Time=00:00:00.4281349 Memory= 397K
B1: N=5 Count= 11,881,376 Time=00:00:00.2482835 Memory= 4,042K
B2: N=5 Count= 11,881,376 Time=00:00:00.0887759 Memory= 8K
A : N=6 Count= 308,915,776 Time=00:00:11.2697326 Memory= 1,688K
B1: N=6 Count= 308,915,776 Time=00:00:06.5638404 Memory= 1,024K
B2: N=6 Count= 308,915,776 Time=00:00:02.2674431 Memory= 8K
哪里
A - 来自@juharr 的 LINQ 函数
B1 - 我的函数与 string
B2 - 我的函数与 char[]
正如我们所见，在内存方面，这两个字符串函数具有可比性。在性能方面，LINQ 函数只慢了约 2 倍，这是相当不错的结果。
正如在这种情况下预期的那样，非分配函数明显优于它们。
更新： 根据评论中的要求，这里是上述函数的示例用法（注意它们是扩展方法，必须放在静态 class）：
var charSet = Enumerable.Range('A', 'Z' - 'A' + 1).Select(c => (char)c).ToArray();
var charPermutations = charSet.RepeatingPermutations(3);
var stringSet = new string(charset);
var stringPermutations = stringSet.RepeatingPermutations(3);
但是，请记住我所做的设计选择，因此如果您在调试器中展开 charPermutations，您将看到一个相同的值（最后一个排列）。消耗上面调用 char[] 的整个结果应该是这样的
var charPermutationList = charSet.RepeatingPermutations(3)
.Select(p => (char[])p.Clone()).ToList();
实际上，对所提供的两种方法的一个很好的补充是以下扩展方法：
public static IEnumerable<T[]> Clone<T>(this IEnumerable<T[]> source)
{
return source.Select(item => (T[])item.Clone());
}
所以消费调用会很简单
var charPermutationList = charSet.RepeatingPermutations(3).Clone().ToList();