C#组合处理时间太慢且内存不足异常 [英] c# combination process time too slow and out of memory exception
本文介绍了C#组合处理时间太慢且内存不足异常的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有这种n元素
public class Ricerca:IComparable
{
public int id;
public double Altezza;
public double lunghezza;
}
我需要计算这些元素的所有可能组合，我的问题是，当我有很多元素时，我使用的方法太慢，有时会出现内存不足的异常.
I need to calculate all the possible combination of this elements, my problem is that the method I am using is too slow when I have a lot of elements and sometimes I get the out of memory exception.
有什么建议吗?
感谢您的帮助
这是我计算在C#论坛中未找到的方法的组合的方法
this is how I calculate the combination I found this method in a c# forum I didn't do it
public void allMyCombination(List<Ricerca>Elements,int i,ref List<List<Ricerca>> combinazioni)
{
Combinations<Ricerca> combinations = new Combinations<Ricerca>(Elements, i);
foreach (Ricerca[] combination in combinations)
{
List<Ricerca> rsr = new List<Ricerca>() { };
foreach (Ricerca rsh in combination)
{
rsr.Add(rsh);
}
// rsr.AddRange(combination);
combinazioni.Add(rsr);
}
}
这些是使用的类:
class Combinations<T> : IEnumerable<T>
{
#region Combinations Members
private ElementSet<T> _Elements;
private int _Choose;
/// <param name="elements">the collection of elements</param>
/// <param name="choose">the length of a combination</param>
public Combinations(IEnumerable<T> elements, int choose)
: this(new ElementSet<T>(elements, null), choose)
{
}
/// <param name="elements">the collection of elements</param>
/// <param name="choose">the length of a combination</param>
/// <param name="comparer">the comparer used to order the elements</param>
public Combinations(IEnumerable<T> elements, IComparer<T> comparer, int choose)
: this(new ElementSet<T>(elements, comparer), choose)
{
}
/// <param name="elements">the collection of elements</param>
/// <param name="choose">the length of a combination</param>
public Combinations(ElementSet<T> elements, int choose)
{
if (elements == null)
{
throw new ArgumentNullException("elements");
}
if (choose < 0 || choose > elements.Count)
{
throw new ArgumentOutOfRangeException("choose");
}
_Elements = elements;
_Choose = choose;
}
#endregion
#region IEnumerable<T[]> Members
/// <seealso cref="IEnumerable{T}.GetEnumerator"/>
public IEnumerator<T[]> GetEnumerator()
{
if (_Choose == 0)
{
return new ChooseZeroEnumerator();
}
else
{
return new Enumerator(this);
}
}
#endregion
#region IEnumerable Members
IEnumerator IEnumerable.GetEnumerator()
{
return new Enumerator(this);
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
throw new NotImplementedException();
}
#endregion
#region Enumerator Class
private class Enumerator : IEnumerator<T[]>
{
#region Enumerator Members
private Combinations<T> _Combinations;
private int[] _Indices, _IndicesAt;
private bool _PastEnd;
internal Enumerator(Combinations<T> combinations)
{
_Combinations = combinations;
_Indices = new int[_Combinations._Choose];
_IndicesAt = new int[_Combinations._Elements.Elements.Count];
Reset();
}
private void MoveFirst()
{
int currentIndex = 0;
int usedCurrent = 0;
for (int i = 0; i < _Indices.Length; i++)
{
Debug.Assert(currentIndex < _Combinations._Elements.Elements.Count);
_Indices[i] = currentIndex;
_IndicesAt[currentIndex]++;
usedCurrent++;
if (usedCurrent == _Combinations._Elements.Elements.Values[currentIndex])
{
currentIndex++;
usedCurrent = 0;
}
}
}
private void MoveIndex(int index, int offset)
{
if (_Indices[index] >= 0 && _Indices[index] < _IndicesAt.Length)
{
_IndicesAt[_Indices[index]]--;
}
_Indices[index] += offset;
if (_Indices[index] >= 0 && _Indices[index] < _IndicesAt.Length)
{
_IndicesAt[_Indices[index]]++;
}
}
private bool IsFull(int position)
{
// True if (position) has as many indices as it can hold.
return _IndicesAt[position] == _Combinations._Elements.Elements.Values[position];
}
private bool CanFitRemainingIndices(int index)
{
int space = _Combinations._Elements.ElementsAtOrAfter[_Indices[index]];
return space >= _Indices.Length - index;
}
private bool AdvanceIndex(int index, int doNotReach)
{
// First move the index one position to the right.
MoveIndex(index, 1);
// If we've found an existing position with no other index, and there's room at-and-to-the-right-of us for all the indices greater than us, we're good.
if (_Indices[index] < doNotReach)
{
if (_IndicesAt[_Indices[index]] == 1)
{
if (CanFitRemainingIndices(index))
{
return true;
}
}
}
// We've either fallen off the right hand edge, or hit a position with another index. If we're index 0, we're past the end of the enumeration. If not, we need to advance the next lower index, then push ourself left as far as possible until we hit another occupied position.
if (index == 0)
{
_PastEnd = true;
return false;
}
if (!AdvanceIndex(index - 1, _Indices[index]))
{
return false;
}
if (IsFull(_Indices[index] - 1))
{
_PastEnd = true;
return false;
}
// Move left until the next leftmost element is full, or the current element has an index.
do
{
MoveIndex(index, -1);
} while (_IndicesAt[_Indices[index]] == 1 && !IsFull(_Indices[index] - 1));
return true;
}
#endregion
#region IEnumerator<T[]> Members
public T[] Current
{
get
{
if (_Indices[0] == -1 || _PastEnd)
{
// Before first or after last.
throw new InvalidOperationException();
}
else
{
T[] current = new T[_Indices.Length];
for (int i = 0; i < _Indices.Length; i++)
{
current[i] = _Combinations._Elements.Elements.Keys[_Indices[i]];
}
return current;
}
}
}
#endregion
#region IDisposable Members
public void Dispose()
{
// Do nothing.
}
#endregion
#region IEnumerator Members
object IEnumerator.Current
{
get
{
return Current;
}
}
public bool MoveNext()
{
if (_PastEnd)
{
return false;
}
if (_Indices[0] == -1)
{
MoveFirst();
return true;
}
else
{
bool ret = AdvanceIndex(_Indices.Length - 1, _IndicesAt.Length);
return ret;
}
}
public void Reset()
{
for (int i = 0; i < _Indices.Length; i++)
{
_Indices[i] = -1;
}
Array.Clear(_IndicesAt, 0, _IndicesAt.Length);
_PastEnd = false;
}
#endregion
}
#endregion
#region ChooseZeroEnumerator Class
private class ChooseZeroEnumerator : IEnumerator<T[]>
{
#region ChooseZeroEnumerator Members
private enum State
{
BeforeBeginning,
OnElement,
PastEnd,
}
private State _State;
internal ChooseZeroEnumerator()
{
Reset();
}
#endregion
#region IEnumerator<T[]> Members
public T[] Current
{
get
{
if (_State == State.OnElement)
{
return new T[0];
}
else
{
throw new InvalidOperationException();
}
}
}
#endregion
#region IDisposable Members
public void Dispose()
{
// Do nothing.
}
#endregion
#region IEnumerator Members
object IEnumerator.Current
{
get
{
return Current;
}
}
public bool MoveNext()
{
switch (_State)
{
case State.BeforeBeginning:
_State = State.OnElement;
return true;
case State.OnElement:
case State.PastEnd:
_State = State.PastEnd;
return false;
default:
throw new InvalidOperationException();
}
}
public void Reset()
{
_State = State.BeforeBeginning;
}
#endregion
}
#endregion
}
class ElementSet<T>
{
private SortedList<T, int> _Elements;
private int _Count;
private int[] _ElementsAtOrAfter;
/// <summary>
/// Constructs a new <c>ElementSet</c> from a collection of elements, using the default comparer for the element type.
/// </summary>
/// <param name="elements">the elements</param>
public ElementSet(IEnumerable<T> elements)
: this(elements, null)
{
}
/// <summary>
/// Constructs a new <c>ElementSet</c> from a collection of an elements, using a custom comparer.
/// </summary>
/// <param name="elements">the elements</param>
/// <param name="comparer">the comparer</param>
public ElementSet(IEnumerable<T> elements, IComparer<T> comparer)
{
if (elements == null)
{
throw new ArgumentNullException("elements");
}
SortedDictionary<T, int> sorted = new SortedDictionary<T, int>(comparer);
foreach (T element in elements)
{
int count;
if (sorted.TryGetValue(element, out count))
{
sorted[element] = count + 1;
}
else
{
sorted[element] = 1;
}
_Count++;
}
_Elements = new SortedList<T, int>(sorted, comparer);
_Elements.Capacity = _Elements.Count;
// Produce the Number of Elements At or After array.
// This is a cumulative sum of the reverse of the values array.
if (_Elements.Count > 0)
{
_ElementsAtOrAfter = new int[_Elements.Count];
_ElementsAtOrAfter[_Elements.Count - 1] = _Elements.Values[_Elements.Count - 1];
for (int i = _Elements.Count - 2; i >= 0; i--)
{
_ElementsAtOrAfter[i] = _ElementsAtOrAfter[i + 1] + _Elements.Values[i];
}
}
}
internal SortedList<T, int> Elements
{
get
{
return _Elements;
}
}
internal int Count
{
get
{
return _Count;
}
}
internal int[] ElementsAtOrAfter
{
get
{
return _ElementsAtOrAfter;
}
}
}
推荐答案
找到的不错的类！做了一些测试.我在您的元素类中添加了一个比较器.不知道您的比较器是什么样..但是也许可以通过优化它来提高速度.为了进行测试，我将其保持在最低限度.参见下面的代码.
Nice class you found ! Did some testing with it. I added a comparer to your element class. Don't know what your comparer looks like.. but maybe speed can be improved by optimizing it. For my tests, I kept it minimal. See code below.
public class Ricerca : IComparable
{
public double altezza;
public double lunghezza;
// added some index to sort by
public int i = 0;
public Ricerca(int ci) { altezza = 53; lunghezza = -4.5; i = ci; }
// comparator to sort with
public int CompareTo(object e)
{ return (((Ricerca)e).i > i) ? 1 : (((Ricerca)e).i == i) ? 0 : -1; }
}
两个观察
-
上述关于成千上万个排列的评论仅在所有元素都不同时才计算在内.当列表中有许多相等的值时，结果计数要小得多，并且运算要快得多.因此，如果该通用类对您有用，则不仅取决于列表计数，还取决于您正在分析的数据.
above remarks about zillions of permutations only count when all elements are different. When there are many equal values in the list, the result count is much smaller and operation is much faster. So if this generic class is usable for you, depends not only on list counts, also on the data you are analysing..
这是托管代码，因此内存使用量取决于GC.当所有索引都是唯一的时，我得到10015005集(29 9)，24秒运行时间和大约900MB的消耗.当第二个索引相等时，我得到0.7秒的运行时间和48MB的消耗.当您不将组合列表转换为另一个列表，而是在组合本身上使用foreach()时，可以消除此负担.我的测试显示了恒定的内存使用量，因为我不存储列表，因此无论参数如何，使用下面的循环我都会得到大约18MB的恒定内存消耗.对于Elements.Count = 29，设置大小9需要12秒.
this is managed code, so memory usage depends on GC. When all indexes are unique, I get 10015005 sets for (29 9), 24 sec runtime and about 900MB consumption. When every second index is equal, I get 0.7 sec runtime and 48MB consumption. You can eliminate this load, when you don't translate the Combinations list to another list, but use the foreach() on combinations itself. My test shows constant memory use, because I dont store the list, I get constant memory consumption of about 18MB with below loop irrespective of parameters. for Elements.Count=29, set size 9 it needs 12 sec.
private void doSomething(List<Ricerca> AChosen)
{
// perform some task on chosen set
}
void Test(List<Ricerca> Elements, int rSetSize)
{
Combinations<Ricerca> combinations = new Combinations<Ricerca>(Elements, rSetSize);
int nReported = 0;
foreach (Ricerca[] combination in combinations)
{
List<Ricerca> chosenPlaces = new List<Ricerca>();
for (int j = 0; j < combination.Length; j++)
chosenPlaces.Add(combination[j]);
doSomething(chosenPlaces); // instance, save only when needed
nReported++;
}
}
这篇关于C#组合处理时间太慢且内存不足异常的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
