Dotaz: Efektivni volani funkci C++

[Martin]

Ahoj, muj dotaz se tyka jazyka C++. Jde o to, ze bych na zaklade nacteni vstupu (nejlepe string) potreboval zavolat konkretni fci. (prikladne zadam "haf", vola fci stekej() atd.) Tech funkci je ale velke mnozstvi a ja nevim, jak nejlepe interpretovat strukturu. Nabizi se if if if, pripadne swich (ale ten funguje jen pro ord hodnoty), nebo take nejky typ stromu. Slozitost si take umim spocitat, jde mi spis o to, jestli na to neni nejaky "trik". Googlit jsem zkousel - evidentne spatne, nebo malo. :D dekuju..

---

---

Odpovědi

[Radek Miček]

Co třeba (perfektní) hašování?

[Radek Miček]

Pro perfektní hašování lze použít gperf.

[holobradek]

Ahoj, pokud maji vsechny ty funkce ktere chces volat stejny prototyp, doporucuji pouzit neco jako:

typedef int (*funkce_t)(); struct {

char *jmeno;

funkce_t funkce;

} seznam[] = {

{

"haf", stekej,

},

};

a nasledne prochazet tohle a volat podle toho... je to teda spis C nez C++, ale hadam ze se to az tak lisit nebude (C++ se mozna nebude libit to deklarovani a definovani struktury i promenne v jednom)

[rADOn]

Hash tabule, klic bude pointer na funkci. Neco v tomhle stylu:

std::map<std::string, void*>

[Radek Miček]

std::map nebývá hašovací tabulka. std::unordered_map bývá.

[Jardík]

void*

No klidně bych tam spíš rval std::function<void()>, může to pak být i volání nějaký metody nějakýho objektu, lambda, ...

[Jardík]

#include <iostream>
#include <map>
#include <unordered_map>
#include <functional>
#include <string>

void stekej()
{
	std::cout << "haf" << std::endl;
}

void mnoukej()
{
	std::cout << "mňau" << std::endl;
}

class Jardik
{
public:
	void jardikuj(std::string const& oCem)
	{
		std::cout << "Jardíkuju o " << oCem << std::endl;
	}
};

using Mapa = std::unordered_map<std::string, std::function<void()>>;
//using Mapa = std::map<std::string, std::function<void()>>;

int main(int argc, char **argv)
{
	Jardik jardik;
	
	Mapa mapa{
		{"haf", stekej},
		{"mňau", mnoukej},
		{"jardikujo64bitech", std::bind(&Jardik::jardikuj, &jardik, "64bitech")},
		{"jardikujowindows", std::bind(&Jardik::jardikuj, &jardik, "woknech")}
	};
	
	std::string codelat;
	
	for (;;)
	{
		std::cin >> codelat;
		if (!std::cin)
			break;
		
		Mapa::const_iterator it = mapa.find(codelat);
		if (it != mapa.end()) {
			it->second();
		}
		else {
			std::cout << "Neumim" << std::endl;
		}
	}
	
	return 0;
}

[Šangala]

Možná by se slušelo doplnit, že tak jak je to napsané, je to C++0x (C++11).

[Jardík]

Tak používání C++11 2 roky po schválení standardu by snad nemuselo nikoho překvapovat. V clang je podpora kompletní, v GCC skoro taky. Pokud ale hold má někdo nainstalován 10 let zastaralý kompilátor, tak hold smůla.

[Šangala]

No nevím jak s tímto přístupem uspěješ/uspíváš…, já bych za takovou závislost na prkotiny nebo pokud to má být „pro široké použití“ rovnou řekl „tak ahoj“

[Jardík]

Zrovna věci z C++11, které jsem ve zdrojáku užil, jsou podporovnány v GCC od 4.7, možná dokonce už od 4.6. Aktuální je 4.8 a v normálních distibucích je běžně dostupná (např. Arch Linux), popř. v distribucích obsahujících zastaralý software už při vydání (debian, ubuntu) se jistě dá jednoduše doinstalovat vedle jejich zastaralé verze. Navíc je asi lepší držet se standardu (i když novějšího), než kvůli kravině mít závislost třeba na věcech typu boost. Pokud je navíc zadáno "udělej to v C++" a není to dále nějak upřesněno, omezeno, zvolím si nejjednodušší cestu, místo složitého programování kravin, co už někdo napsal za mě.

Podle vás ale bude lepší C++11 nepoužít, C++TR1, C++03 radši taky ne (příliš nové verze!) a zůstaneme v roce 98 a budeme doufat, že to nějaký kompilátor podporuje. A pak zjistíte, že to bude rovnou lepší napsat v K&R C, protože je nejstarší a asi tedy i podporovaný super starými kompilátory. S takovýmhle přístupem ale zůstaneme v době kamenné.

[Šangala]

To, že to jde lehce doinstalovat je sice možné, ovšem ne vždy je to až tak lehce, a těžko bude někdo tahat spoustu věcí na spoustu mašin, které fungují normálně a ještě dlouho budou.
Debian: gcc 4.4.5, Ubuntu 12.04 LTS gcc 4.6.3., jestli nepletu CentOs: gcc 4.4.7.
Standardu je jistě se dobré držet, ale používat novinky, automaticky dané zdrojáky vylučuje ze spoustu nasazení.
A podle mě je dobré se držet co rozumě podporovaného standardu, klidně i v duchu C++11, ale tak aby to bylo možné zkompilovat na většině aktuálních distribucí tzn. necpat tam za každou cenu „všemožné“, pokud je to projektem dáno a je připravován pro budoucnost, tak klidně, ale v dnešní době pokud je to závislé na podpoře C++11 je dobré na to upozornit hned v první větě…

[potato]

Překlad: Exisují už verze GCC a clang, které to podporují; má je sice nainstalovány akorát Jardík, který si je kompiluje ještě před commitem, protože se kvůli získání aktuálních zdrojáků naboural vývojářům do počítačů, ale to nebrání správně to ideologicky podat.

[mimi.vx]

gcc 4.7 a 4.8 dle distrowatch ...

http://distrowatch.com/search.php?pkg=gcc&pkgver=4.8#pkgsearch

http://distrowatch.com/search.php?pkg=gcc&pkgver=4.7#pkgsearch

 

a c11 v clangu : http://clang.llvm.org/cxx_status.html

[potato]

To má být argument konkrétně pro co, nebo proti čemu? Letmým pohledem bych řekl, že gcc 4.8 není de facto nikde a gcc 4.7 je v části nejaktuálnějích verzí relevantních distribucí, a není nikde, kde by na tom záleželo (ozvěte se znovu, až bude ve všech podporovaných verzích RHEL).

[gamer]

No nechce se mi to zkoušet, ale myslím, že tohle by zkompilovalo i gcc 4.4 ve squeeze, nic extra sofistikované z C++11 tam není.

[Šangala]

Ne, a to kvůli použití using, pokud se opraví na typedef a přidá se flag -std=gnu++0x uklidňujícně označený jako „This support is currently experimental.“ tak už jo.
Ale ten kód je úmyslně C++11 i v detailech (např. >> za sebou bez mezery), pominulu-li std::bind.
PS: Nemám nic proti C++11 je to super, jen jsem napsal, že by bylo vhodné dodat že je to jen a pouze C++11.
A jinak si myslím (což je asi patrné s příspěvků), že je podle mě zbytečné používat tento level, na tak jednoduché zadání, a že takový kód je pak na spoustu věcí nepoužitelný.

[Josef Kufner]

Pokud by se nehodilo použití std::unordered_map, existuje na tohle například trie, což je asi nejefektivnější datová struktura pro tento účel. Složitost je lineární s délkou aktuálně hledaného řetězce a konstantní vzhledem k počtu prohledávaných řatěců. Ta std::unordered_map je na tom v průměru stejně, ale v nejhorším případě je lineární. Nicméně pochybuju, že by rozdíl byl takový, aby mělo smysl to implementovat namísto použití knihovny.

[Radek Miček]

což je asi nejefektivnější datová struktura pro tento účel

Pokud na vstupu budou vždy pouze slova z předem dané množiny, pak ta slova nepotřebuji ani ukládat.

Jednoduchý benchmark je v článku GPERF: A Perfect Hash Function Generator na straně 10.

[Josef Kufner]

Zajímavé čtení. Ale předpokládat jen validní vstup je velmi odvážné.

[xkucf03]

Nevalidní vstup znamená „nenalezeno“ a to nám stačí, ne?

[xkucf03]

(maximálně může nastat kolize, ale to asi při zadávání názvů funkcí není potřeba řešit – nikdo asi neudělá takový překlep, aby došlo ke kolizi)

[johniez]

V tom vygenerovanym examplu na straně 6 je i strcmp, takže kolize nalezeno nezpůsobí. Vzhledem k tomu, že se tam hash počítá ze 2 byte a délky, kolize by nastávala asi celkem často (dle vstupu).

[Michal Wirth]

doporucuji se trochu inspirovat na gamedev