[C#] Geschwindigkeits Problem beim Erzeugen von Kombinationen

[Trux]

Ich habe ein array m_Signs dadrin sind bis zu 255 byte die als mögliche zeichen gegeben sind.

Nun möchte ich immer die linke position erhöhen, wenn diese am ende ist wieder auf den ersten eintrag setzen und den linken nachbar um einen erhöhen.

Funktioniert auch alles wie es soll, jedoch ist die Geschwindigkeit nicht optimal.

Sieht hier jemand optimierungs ansätze?

public string GetNextPacket(string strPacket)

{

	if(strPacket.Length-1 >= 0)

	return CountUp(strPacket,strPacket.Length-1);

	else

	return ((char)((byte)m_Signs[0])).ToString();

}


private string CountUp(string strPacket, int nPosi)

{

	StringBuilder sb = new StringBuilder(strPacket);

	if(nPosi < sb.Length)

	{

		int nIndex = m_Signs.IndexOf((byte)strPacket[nPosi]);

		if(nIndex >= 0)

		{

			if(nIndex + 1 < m_Signs.Count)

			{

				sb[nPosi] = (char)(byte)m_Signs[nIndex+1];

			}

			else

			{

				sb[nPosi] = (char)(byte)m_Signs[0];

				if(0 <= nPosi-1)

				{

					return CountUp(sb.ToString(),nPosi-1);

				}

				else

				{

					sb.Insert(0,(char)(byte)m_Signs[0]);

				}

			}

		}

		else

		{

			sb[nPosi] = (char)(byte)m_Signs[0];

		}

	}

	else

	{

		strPacket = strPacket + (Char)m_Signs[0];

	}


	return sb.ToString();

}

[Bubble]

Ich habe ein array m_Signs dadrin sind bis zu 255 byte die als mögliche zeichen gegeben sind.

Nun möchte ich immer die linke position erhöhen, wenn diese am ende ist wieder auf den ersten eintrag setzen und den linken nachbar um einen erhöhen.

Zu unklar ausgedrückt.

[Trux]

Hoffe das wird hiermit klarer.

//Alle Signs ins Array

foreach(Sign sign in signs)

{

	for(int i=sign.Start; i <= sign.End; i++)

	{

		if(!m_Signs.Contains((byte)i))

			m_Signs.Add((byte)i);

	}

}


//Sortieren

for(int i=0; i < m_Signs.Count; i++)

{

	for(int k=i; k <m_Signs.Count; k++)

	{

		if((byte)m_Signs[k] < (byte)m_Signs[i])

		{

			byte byTemp = (byte)m_Signs[i];

			m_Signs[i] = m_Signs[k];

			m_Signs[k] = byTemp;

		}

		else

		{

		}

	}

}

Angenommen in m_Signs ist 97 ('a') - 122 ('z')

ich erhöhe das Packet "az" um einen Schritt erhalte ich "ba"

beim nächsten aufruf dann "bb" usw

[Klotzkopp]

Ich denke, das Hauptproblem ist die Suche in m_Signs. Du benutzt IndexOf, das benutzt eine lineare Suche. Da m_Sign sortiert ist, könntest du statt dessen eine binäre Suche benutzen, die ist um einiges schneller.

Eine andere Möglichkeit wäre, m_Signs als Array von bool-Werten aufzusetzen, und diejenigen Positionen mit True zu kennzeichnen, die als Zeichen auftauchen können. Das hätte den Vorteil, dass du gar nicht mehr in m_Signs nach einem Zeichen suchen müsstest, sondern direkt über den Index gehen könntest.

Warum benutzt du einen StringBuilder, statt den String selbst zu ändern? Das könnte einiges an unnötigen Kopieraktionen ersparen.

[Trux]

Vielen Dank, das hat eine menge an speed gebracht

Wenn du das so meintest:

ArrayList tmpArray = new ArrayList();

m_nPacketSize = nPacketSize;

//Alle Signs ins Array

foreach(Sign sign in signs)

{

	for(int i=sign.Start; i <= sign.End; i++)

	{

		if(!tmpArray.Contains((byte)i))

			tmpArray.Add((byte)i);

	}

}


//Sortieren

for(int i=0; i < tmpArray.Count; i++)

{

	for(int k=i; k <tmpArray.Count; k++)

	{

		if((byte)tmpArray[k] < (byte)tmpArray[i])

		{

			byte byTemp = (byte)tmpArray[i];

			tmpArray[i] = tmpArray[k];

			tmpArray[k] = byTemp;

		}

		else

		{

		}

	}

}


m_nLowest = (byte)tmpArray[0];


for(int i=0; i <= 255; i++)

{

	if(tmpArray.Contains((byte)i))

		m_Signs.Add(true);

	else

		m_Signs.Add(false);

}


private string CountUp(string strPacket, int nPosi)

{

	int ndx = (int)(byte)strPacket[nPosi];

	do

	{

		ndx++;

	}while(ndx <= 255 && !(bool)m_Signs[ndx]);


	if(ndx > 255)

	{

		if(nPosi -1 >= 0)

		{

			strPacket =  strPacket.Remove(nPosi,1);

			strPacket = strPacket.Insert(nPosi,((char)((byte)m_nLowest)).ToString());

			strPacket = CountUp(strPacket,nPosi-1);

		}

		else

		{


			strPacket =  strPacket.Remove(nPosi,1);

			strPacket = strPacket.Insert(nPosi,((char)((byte)m_nLowest)).ToString());

			strPacket = ((char)((byte)m_nLowest)).ToString() + strPacket;

		}

	}

	else

	{

		strPacket =  strPacket.Remove(nPosi,1);

		strPacket = strPacket.Insert(nPosi,((char)ndx).ToString());

	}

	return strPacket;

}

[Bubble]

Warum benutzt du einen StringBuilder, statt den String selbst zu ändern? Das könnte einiges an unnötigen Kopieraktionen ersparen.

String-Objekte sind in .NET unveränderlich. Man muss, um einen veränderten "string" zu erhalten, einen neues "string"-Objekt erzeugen, vermutlich greift er deswegen auf den StringBuilder zurück.

Eventuell wäre es hier sinnvoller ein char-Array (oder byte-Array, je nachdem was eigentlich gewollt ist) zu benutzen und dessen Inhalt zu verändern.

[Trux]

dank euerer hilfe konnte ich die zeit für die berechnung bestimmt mehr als verdoppeln.

Habt vielen dank.

[athlet1]

Man muss, um einen veränderten "string" zu erhalten, einen neues "string"-Objekt erzeugen...

Dies ist nicht richtig. Wenn man einen string manipuliert wird intern ein neues string objekt erzeugt und dem ursprünglichem string zugewiesen. man muss folglich sebst kein neues anlegen.

Eventuell wäre es hier sinnvoller ein char-Array (oder byte-Array, je nachdem was eigentlich gewollt ist) zu benutzen und dessen Inhalt zu verändern.

Ein char Array ist hier unnötig, da der StringBuilder intern mit einem Char Array arbeitet.

Grüße

[Bubble]

Dies ist nicht richtig. Wenn man einen string manipuliert wird intern ein neues string objekt erzeugt und dem ursprünglichem string zugewiesen. man muss folglich sebst kein neues anlegen.

Genau das habe ich gesagt (und es ist richtig): Veränderung (Manipulation) eines String-Objektes ist unmöglich, nach dem Erzeugen kann man nur lesend auf den Inhalt zugreifen. Methoden wie "Insert" machen auch nichts anderes, als einen neuen String zu erzeugen. Das alte Objekt bleibt dabei unverändert.

Ein char Array ist hier unnötig

Das hängt ganz vom Problem ab.

[Trux]

zur info ich habe das ganze mit einem byte array gelöst, was ich denke auch am schlausten ist...