Mam dwudzielny wykres i szukam najbardziej efektywnego, iteracyjnego sposobu dzielenia go na połączone komponenty. Moja wersja rekursywna zaczęła przepełniać stos na dużych zbiorach danych. Jestem gotowy do portu z dowolnego języka/pseudocode, ale dla kompletności będę kodowanie w C#.Algorytm iteracyjnych komponentów połączonych
Mój istniejący kod specjalizuje się w moich typach danych. Jedna partycja to białka, druga to widma. Mapa i zestaw są workflowami C++ stdlib.
void recursivelyAssignProteinToCluster (long proteinId,
long clusterId,
Set<long> spectrumSet,
Map<long, Set<long>> spectrumSetByProteinId,
Map<long, Set<long>> proteinSetBySpectrumId,
Map<long, long> clusterByProteinId)
{
// try to assign the protein to the current cluster
var insertResult = clusterByProteinId.Insert(proteinId, clusterId);
if (!insertResult.WasInserted)
return;
// recursively add all "cousin" proteins to the current cluster
foreach (long spectrumId in spectrumSet)
foreach (var cousinProteinId in proteinSetBySpectrumId[spectrumId])
{
if (proteinId != cousinProteinId)
{
Set<long> cousinSpectrumSet = spectrumSetByProteinId[cousinProteinId];
recursivelyAssignProteinToCluster(cousinProteinId,
clusterId,
cousinSpectrumSet,
spectrumSetByProteinId,
proteinSetBySpectrumId,
clusterByProteinId);
}
}
}
Map<long, long> calculateProteinClusters (NHibernate.ISession session)
{
var spectrumSetByProteinId = new Map<long, Set<long>>();
var proteinSetBySpectrumId = new Map<long, Set<long>>();
var query = session.CreateQuery("SELECT pi.Protein.id, psm.Spectrum.id " + GetFilteredQueryString(FromProtein, ProteinToPeptideSpectrumMatch));
foreach (var queryRow in query.List<object[]>())
{
long proteinId = (long) queryRow[0];
long spectrumId = (long) queryRow[1];
spectrumSetByProteinId[proteinId].Add(spectrumId);
proteinSetBySpectrumId[spectrumId].Add(proteinId);
}
var clusterByProteinId = new Map<long, long>();
int clusterId = 0;
foreach (var pair in spectrumSetByProteinId)
{
long proteinId = pair.Key;
// for each protein without a cluster assignment, make a new cluster
if (!clusterByProteinId.Contains(proteinId))
{
++clusterId;
recursivelyAssignProteinToCluster(proteinId,
clusterId,
pair.Value,
spectrumSetByProteinId,
proteinSetBySpectrumId,
clusterByProteinId);
}
}
return clusterByProteinId;
}
Zgodnie z sugestią ShinTakezou, zreagowałem, aby umieścić stos na stercie i działa świetnie. Użyłem podejścia DepthFirstSearch z przykładu digEmAll.
var clusterByProteinId = new Map<long, long>();
int clusterId = 0;
var clusterStack = new Stack<KeyValuePair<long, Set<long>>>();
foreach (var pair in spectrumSetByProteinId)
{
long proteinId = pair.Key;
if (clusterByProteinId.Contains(proteinId))
continue;
// for each protein without a cluster assignment, make a new cluster
++clusterId;
clusterStack.Push(new KeyValuePair<long, Set<long>>(proteinId, spectrumSetByProteinId[proteinId]));
while (clusterStack.Count > 0)
{
var kvp = clusterStack.Pop();
// try to assign the protein to the current cluster
var insertResult = clusterByProteinId.Insert(kvp.Key, clusterId);
if (!insertResult.WasInserted)
continue;
// add all "cousin" proteins to the current cluster
foreach (long spectrumId in kvp.Value)
foreach (var cousinProteinId in proteinSetBySpectrumId[spectrumId])
if (!clusterByProteinId.Contains(cousinProteinId))
clusterStack.Push(new KeyValuePair<long, Set<long>>(cousinProteinId, spectrumSetByProteinId[cousinProteinId]));
}
}
Po przesłaniu metody rekurencyjnej i ktoś tutaj przetłumaczy ją na metodę iteracyjną. – Brannon
kiedy rekursja zjada zbyt dużo stosu, jako pierwsza próba zachowania tego samego algorytmu, możesz spróbować zmienić rekursję na dane zużywające pętlę (przez "pop") ze stosu * * (wywołanie tej samej funkcji staje się popchnięciem tego stos wymaganych argumentów dla funkcji). Oczywiście z "stosem" rozumiem listę implementowaną przez użytkownika, a to wymaga trochę pracy, ale w ten sposób jesteś ograniczony przez stertę, a nie przez stos. (może to działa z łatwością tylko dla rekurencji ogona? Muszę o tym pomyśleć ...) – ShinTakezou
Przez "komponenty" masz na myśli podgramy? – Beta