Komplexität von switch

[ness]

Ich denke mal das ist ne Anfängerfrage, aber ist die komplexität von switch linear zur Menge der Abfragen?
OK, sagt ihr jetzt vielleicht, die Frage kann ich mir selbst beantworten, indem ich es Probiere. Nun, eigentlich bin ich bein Probieren darauf gestoßen: ich hab probiert ob es schneller ist einen übergebenen Wert mit switch einer Ausgabe zuzuordnen oder on dies über ein statisch konstantes array von Funktionszeigern schneller geht...
Nun kommt aber bei beidem immer genau 62 ticks raus, kann das sein?
Kommen mir da die optimierungen des kompilers in die quere? Könnte mal bitte jemnd außerdem zwei Funktionen schreiben, die definitiv unterschiedliche Zeit benötigen? (Es könnte ja sein das ich irgendwo anders nen Fehler habe...)

[jt.]

Der Compiler generiert daraus eine Sprungtabelle

[ness]

Hm, also jetzt weiß ich mir auch nicht zu helfen. Guckt sich mal bitte jemand den code an (das ist nicht alles, nur das wichtigste...):

template
<
	class Function,
	class Argument_generator
>
class performance_tester
{
public:
	class node
	{
	private:
		Function f;
		clock_t begin;
		clock_t end;
		bool already_tested;
		node();
		unsigned times_best;
	public:
		node(Function f_)
			:f(f_),begin(0),end(0),already_tested(false),times_best(0){};
		clock_t test(Argument_generator& a)
		{
			begin=clock();
			f(a());
			end=clock();
			already_tested=true;
			return end-begin;
		};
		clock_t get_test_result()const
		{
			assert(already_tested);
			return end-begin;
		};
		Function get_fun()const{return f;};
		unsigned get_times_best()const{return times_best;};

		bool operator<(const node& n)
		{
			assert(already_tested&&n.already_tested);
			return (end-begin)<(n.end-n.begin);
		};

		template<class T,class U>
		friend class performance_tester;
		friend struct best_sorter;
	};
private:
	struct best_sorter
	{
		bool operator()(const node& lhs,const node& rhs)
		{
			assert(lhs.already_tested&&rhs.already_tested);
			return lhs.times_best>rhs.times_best;
		};
	};
	std::list<node> funs;
public:
	const node& test_all(Argument_generator& a)
	{
		for(std::list<node>::iterator i=funs.begin();i!=funs.end();++i)
		{
			i->test(a);
		};
		funs.sort();
		return funs.front();
	};
	const node& test_all_x_times(unsigned t,Argument_generator& a)
	{
		for(unsigned i=0;i<t;++i)
		{
			test_all(a);
			++(funs.front().times_best);
		};
		funs.sort(best_sorter());
		return funs.front();
	};
	const node& get_best()const{return funs.front();};
	const std::list<node> get_test_objects()const{return funs;};
};

Getstet hab ich das so:

enum status{random,incrementing};

struct arg_generator
{
private:
	arg_generator();
	const status st;
	unsigned i;
public:
	explicit arg_generator(const status s)
		:st(s),i(0){};
	unsigned operator()()
	{
		switch(st)
		{
			case random:
				return rand()%15+1;
			case incrementing:
				return i==15?i=1:++i;
			default:
				cout<<"ERROR";
		};
	};
};

void eins() {cout<<"eins"<<endl;};
void zwei() {cout<<"zwei"<<endl;};
void drei() {cout<<"drei"<<endl;};
void vier() {cout<<"vier"<<endl;};
void fuenf() {cout<<"fuenf"<<endl;};
void sechs() {cout<<"sechs"<<endl;};
void sieben() {cout<<"sieben"<<endl;};
void acht() {cout<<"acht"<<endl;};
void neun() {cout<<"neun"<<endl;};
void zehn() {cout<<"zehn"<<endl;};
void elf() {cout<<"elf"<<endl;};
void zwoelf() {cout<<"zwoelf"<<endl;};
void dreizehn() {cout<<"dreizehn"<<endl;};
void vierzehn() {cout<<"vierzehn"<<endl;};
void fuenfzehn() {cout<<"fuenfzehn"<<endl;};

void using_switch(unsigned arg)
{
	switch(arg)
	{
		case 1:
			eins();
			break;
		case 2:
			zwei();
			break;
		case 3:
			drei();
			break;
		case 4:
			vier();
			break;
        case 5:
			fuenf();
			break;
		case 6:
			sechs();
			break;
		case 7:
			sieben();
			break;
		case 8:
			acht();
			break;
		case 9:
			neun();
			break;
		case 10:
			zehn();
			break;
		case 11:
			elf();
			break;
		case 12:
			zwoelf();
			break;
		case 13:
			dreizehn();
			break;
		case 14:
			vierzehn();
			break;
		case 15:
			fuenfzehn();
			break;
		default:
			cout<<"ERROR!"<<endl;
	};
};

void using_vec(unsigned arg)
{
	typedef void(*fun)();
	static const fun disp[]={eins,zwei,drei,vier,fuenf,sechs,sieben,acht,neun,zehn,elf,zwoelf,dreizehn,vierzehn,fuenfzehn};
	if(arg==0||arg>15)
		cout<<"ERROR!"<<endl;
	else
		disp[arg-1]();
};

int main()
{
	srand(time(NULL));
	performance_tester<void(*)(unsigned),arg_generator> m_tester;
	m_tester.add(using_vec);
	m_tester.add(using_switch);
	void(*best)(unsigned)=m_tester.test_all_x_times(30,arg_generator(random)).get_fun();
	//if(best==using_vec)
		cout<<endl<<"\nvector"<<"     "<<m_tester.get_best().get_test_result();
	//else if(best==using_switch)
		cout<<endl<<"\nswitch"<<"     "<<m_tester.get_test_objects().back().get_test_result();
	//else cout<<"ERROR!";
	cin.get();
	return 0;
}

Allerdings ist test_result immer 0, das begin und end immer 62 sind. (laut debugger)

[Jockelx]

jt. schrieb:

Der Compiler generiert daraus eine Sprungtabelle

Aber auch wenn's sich lohnt, also genügend 'nahe' Werte vorhanden sind.

Jockel

[ssm]

du hast einfach getestet, wie lange std::cout gearbeitet hat

http://lists.gnu.org/archive/html/texmacs-dev/2003-11/msg00034.html

[ness]

In beiden Fällen? Mit was für einer Funktion könnte man die Zeitmessung testen?

[ssm]

ness schrieb:

In beiden Fällen?

ja in beiden.

switch ist allerdings effectiver, als array of pointers.
As is generally the case and I'm sure you know, the C++ language does not
mandate any particular form of implementation of switches (nor does it
for any particular feature).

Switch implementation varies from one compiler to another. So any
statement about the internal implementation of switch may be valid for
one compiler and fails for another. However, it seems that good
optimizing compilers tend to use
(1) a table lookup when the switch-cases are large and dense;
(2) if-else branches when the switch-cases are small;
(3) a mixture of (1) and (2) for "interesting" cases.

As far as GCC/g++ is conerned, g++ shares the same middle-end and
back-end as the C front-rend (and Fortran and other supported
languages). Here is what the GCC source says (gcc/stmt.c):

Switch statements can be output in one of two forms. A branch table
is used if there are more than a few labels and the labels are dense
within the range between the smallest and largest case value. If a
branch table is used, no further manipulations are done with the case
node chain.

The alternative to the use of a branch table is to generate a series
of compare and jump insns. When that is done, we use the LEFT, RIGHT,
and PARENT fields to hold a binary tree. Initially the tree is
totally unbalanced, with everything on the right. We balance the tree
with nodes on the left having lower case values than the parent
and nodes on the right having higher values. We then output the tree
in order. */

This is to be taken with a grain of salt. This may change in the
future as the compiler is improving and more optimizations are being
implemented (e.g. tree-ssa branch). Other compiler may implement a
better strategy.

ness schrieb:

Mit was für einer Funktion könnte man die Zeitmessung testen?

z.B. QueryPerformanceCounter, QueryPerformanceFrequency für Windows

[Vertexwahn]

> Ich denke mal das ist ne Anfängerfrage, aber ist die komplexität von switch linear zur Menge der Abfragen?

Das hängt von der Wahl der Elementaren Schritte (siehe Zeitkomplexität) ab

Zeitkomplexitätsbetrachtungen machen erst Sinn, wenn man sich an irgendwelchen Elementaren Schritten festhält - wenn du diese Elementaren Schritte auf die Maschinensprache führen willst, dann must du erst einmal wissen was Maschinensprache ist, wissen wie dein Mikproprozesor funktioniert, wissen wie dein Compiler usw.

Was sind deine elementaren Schritte? ohne diese Angabe kann deine Frage gar nicht beantwortet werden...

Deine Vorgehensweiße macht keinen Sinn, wenn es dir nur um die Zeitkomplexität geht

> denke mal das ist ne Anfängerfrage, aber ist die komplexität von switch linear zur Menge der Abfragen?

der Standard legt doch keine konkrette Implementierung fest - daher kann diese Frage gar nicht beantwortet werden - ein dummer Compilerherställter könnte die switch Anweisung mit exponentieller Zeitkomplexität implementieren....

[ness]

Ich glaub ich bin blöd. Ich habe jetzt zum Test mal das gemacht:

clock_t b=clock();
int_nach_roem_string(arg_generator(random)());
cout<<clock()-b;

Ich erhalte wieder 0! Wieso das?
/edit: Ich seh grad, die Werte sind nur zustandegekommen, weil ich im debugger Zeit "vergeudet" habe.

cout<<clock();

Mitten in einem Programm liefert auch 0? Gints da vielleicht irgend einen schalter beim msvc?