schnell intervall finden

pospiech

ich möchte double Wert einem Intervall zupordnen. Derzeit mache ich das primitiv mit

double digitizedValue(double value)
	{
		if (value == m_InputLevel[0]) // 1. Level == 0
			return m_OutputLevel[0];

		for (int level = 0; level < m_LevelNumber - 1; level++)
		{
			double comparevalue1 = m_InputLevel[level];
			double comparevalue2 = m_InputLevel[level + 1];
			if ((value > comparevalue1) && (value <= comparevalue2))
				return m_OutputLevel[level];
		}
		// if nothing can be applied (should never happen)
		return m_InputLevel[0];
	}

Es wird dabei geschaut zwischen welchem Bereich (leve)

m_InputLevel[level] < value <= m_InputLevel[level + 1]

der Wert value liegt.

Das ganze ist nur unheimlich langsamm. Für 1000x1000 Werte dauert das ganze 1-2 Sekunden.

Die Werte liegen in InputLevel der Größe nach sortiert vor.

Mir würde noch einfallen die Suche erst mit einem Gröberen Intervall 10 Punkte aus 256 und dann mit den übrigen 10 genauen Punkten durchzuführen.
Ich könnte aber auch das Intervall immer durch 2 teilen, schauen in welchem Bereich der Wert liegt und dann von diesem wieder druch 2 teilen, bis ich das Intervall habe.

Welche optimiertere Strategien gibt es noch? Welche machen Sinn?

Matthias

camper

double digitizedValue(double value)
{
    return m_OutputLevel[ std::distance( &m_InputLevel[ 0 ], std::lower_bound( &m_InputLevel[ 0 ], &m_InputLevel[ m_LevelNumber - 1 ], value ) ];
}

Unter der Annahme, dass es sich um Arrays handelt, sonst die Zeiger durch entsprechende Iteratoren ersetzen.

pospiech

camper schrieb:

double digitizedValue(double value)
{
    return m_OutputLevel[ std::distance( &m_InputLevel[ 0 ], std::lower_bound( &m_InputLevel[ 0 ], &m_InputLevel[ m_LevelNumber - 1 ], value ) ];
}
Unter der Annahme, dass es sich um Arrays handelt, sonst die Zeiger durch entsprechende Iteratoren ersetzen.

Es sind vector arrays. Wie müsste das ganz den mit Iteratoren aussehen (habe damit noch nicht gearbeitet).

Gibt es weitere Informationen wie diese Funktion arbeitet und was sie genau macht?

camper

pospiech schrieb:

camper schrieb:
double digitizedValue(double value)
{
    return m_OutputLevel[ std::distance( &m_InputLevel[ 0 ], std::lower_bound( &m_InputLevel[ 0 ], &m_InputLevel[ m_LevelNumber - 1 ], value ) ];
}
Unter der Annahme, dass es sich um Arrays handelt, sonst die Zeiger durch entsprechende Iteratoren ersetzen.
Es sind vector arrays. Wie müsste das ganz den mit Iteratoren aussehen (habe damit noch nicht gearbeitet).

Gibt es weitere Informationen wie diese Funktion arbeitet und was sie genau macht?

lower_bound findet in einer sortierten Sequenz das erste Element, an dem unser Vergleichswert eingefügt werden könnte, ohne die Sortierung der Sequenz zu beeinflussen (upper_bound findet das letzte Element - das entspräche der Bedingung (value >= comparevalue1) && (value < comparevalue2)).
Beispiel:

Sequenz:       0  5  6  9 10
Suche nach 3:     lu
Suche nach 6:        l  u

Hier markiert l das Element, auf dass der von lower_bound zurückgegebene Iterator zeigen würde, u das Element, dass zu upper_bound gehört. Dabei haben wir im Hinterkopf, dass der bei insert übergebene Iterator nach dem Einfügen jeweils auf das Element nach dem eingefügtene Element zeigt.
lower_bound und upper_bound gehören zu den Algorithmen der Standardbibliothek, die mit sortierten Sequenzen arbeiten - diese haben logarithmische Laufzeit, wenn random-access-Iteratoren verwendet werden.

double digitizedValue(double value)
{
    return m_OutputLevel[ std::distance( m_InputLevel.begin(), std::lower_bound( m_InputLevel.begin(), m_InputLevel.end() - 1, value ) ];
}