Keskustelu: Ohjelmointikysymykset: Pointteri pari ja C++ map

Tervehdys kaikki,

Huomasin ohjelmaan vääntäessä, että C++ map find-metodi on todella hidas?

Luodaan kuvitteelinen tilanne, jossa lisään Pointer1 tyyppisen osoittimen käsittelijälle, joka luo sille parin Pointer2. Add -funktion ideana on myös olla luomatta paria, jos Pointer1 on jo paritus mapissa.

Huomasin Add -funktio optimoidessani, että vaikka lisäsin tarkistuksen on Add -funktio hyvin hidas. Eli käytännössä mapin find -metodi kutsu on myös raska? Olisiko tämä parempi toteuttaa jollain muulla kun map:lla( jokin nopeampi tapa )?

// Minulla on map, joka parittaa 2 pointteria
map _mMap<Pointer1 *, Pointer2 *>;

Pointer2 *getPointer2ByPointer1( Pointer1 *p1Pointer1_ )
{
	if( _mMap.find( p1Pointer1_) != _mMap.end() )
	{
		return _mMap.at( p1Pointer1_);
	}

	return NULL;
}

Pointer2 *add( Pointer1 *p1Pointer1_ )
{
	Pointer2 *_p2Pointer2 = NULL;

	_p2Pointer2 = this->getPointer2ByPointer1( p1Pointer1_ );

	if( _p2Pointer2 == NULL )
	{
		_p2Pointer2 = new Pointer2 ( p1Pointer1_ );

		_mMap.insert( make_pair( p1Pointer1_ , _p2Pointer2  ) );
	}

	return _p2Pointer2;
}

Tietorakenne std::map säilyttää avaimia jonkinlaisessa järjestyksessä ja toimii logaritmisessa ajassa. Lisää nopeutta voit hakea C++11-standardin tietorakenteesta std::unordered_map, joka käyttää hajautustaulua ja toimii usein lähes vakioajassa (mutta teoreettisessa huonossa tilanteessa paljon hitaammin).

Toisaalta miksei Pointer1-luokkasi sisällä suoraan tarvittavaa osoitinta? Silloin et tarvitsisi ollenkaan erillistä tietorakennetta.

Kiitos vastauksestasi.

Mietin tuossa myös, että jos tietorakenteen toteuttaisikin std::vectorilla ja haussa iteroisi vain taulua pari parilta läpi. Kuitenkin tämä toimii vain tiettyyn rajaan asti ( Kunnes iteroitavien parien määrä kasvaa suureksi ).

Metabolix kirjoitti:

Toisaalta miksei Pointer1-luokkasi sisällä suoraan tarvittavaa osoitinta? Silloin et tarvitsisi ollenkaan erillistä tietorakennetta.

Koska Pointer2 luodaan rajapinnan sisällä, enkä halua sekoittaa sitä "toiselle" puolelle, jotta modulaarisuus ei kärsi.

kayttaja-3842 kirjoitti:

Mietin tuossa myös, että jos tietorakenteen toteuttaisikin std::vectorilla

Kannattaisi nyt varmaan hankkia jotkin perustiedot tietorakenteista ja niiden aikavaatimuksista. Suoran tietorakenteen iterointi on ylivoimaisesti hitain vaihtoehto: jos elementtejä on N, haku kestää keskimäärin N/2 askelta, eli miljoonan elementin tapauksessa aikaa kuluu keskimäärin jo todella paljon. Tasapainotettu binääripuu (kuten map yleensä) on klassinen melko hyvä ratkaisu, koska jos elementtejä on N, haku vie enintään log2(N) askelta eli bittien määrän verran eli yleensä enintään parikymmentä. Hajautustaulu (kuten unordered_map) saattaa parhaimmillaan toimia vakioajassa ja yleensäkin melko nopeasti.

Voi ajatella myös toisella tavalla: jos parin etsiminen lineaarisesta (vector-tyyppisestä) rakenteesta olisi järkevää, varmaan myös map-luokka toimisi sisäisesti niin.

Metabolix kirjoitti:

Kannattaisi nyt varmaan hankkia jotkin perustiedot tietorakenteista ja niiden aikavaatimuksista.

Hyvin olit ignorennut tuon minun oman kommenttini tuosta lainauksesta. Kuten itsekkin tuossa totesin.

kayttaja-3842 kirjoitti:

Kuitenkin tämä toimii vain tiettyyn rajaan asti ( Kunnes iteroitavien parien määrä kasvaa suureksi ).

Lisäksi, eikös tämä ole foorumi sitä varten, että kysytään apua?

Mielestäni kohtuu asiaton kommentti?! :)

kayttaja-3842 kirjoitti:

Hyvin olit ignorennut tuon minun oman kommenttini tuosta lainauksesta.

Näin kyllä kommenttisi. Se on minusta aika laiha puolustus, jos kerran tarkoitukseen suunniteltu tietorakenne on liian hidas ja vaihtoehdoksi tulee mieleen maailman alkeellisin ratkaisu eli lineaarinen haku silmukalla – ratkaisu, jota hitaampaa on vaikea tehdä edes tahallaan.

Toivottavasti sait kuitenkin vastauksia ajatuksiisi.

Metabolix kirjoitti:

Se on minusta aika laiha puolustus.

Ensinnäkään, mielestäni tämä ei ole mikään kilpailu missä vastapuolet kilpailevat?

Ideana oli vain kysyä asiaa ( johon tämä foorumi on kaiketi keskittynyt? ). Näin ollen minun ei tarvitse millään tavalla puolustella.

Fakta on vain se, että totesin tuossa, sen että olin miettinyt std::vectoria voisiko sitä mitenkään käyttää. Mutta totesin itsekkin, että olisi todella hidas tapa toteuttaa. Tämän takia alunperinkin toteutin ko. toiminnon std::map:lla.

Mitä virkaa ko. foorumilla on jos sielä sanotaan vain "Älä tuu tänne kyselee" tai "Pitäisi toi nyt tietää". Juuri sen takia kysyn, että joku joka tietää, voisi jelpata???

Metabolix kirjoitti:

Toivottavasti sait kuitenkin vastauksia ajatuksiisi.

Sain kyllä, kiitos siitä.

Itselläni on tapana tarkistaa, sisältääkö map avaimen, käyttäen count-funktiota. Se palauttaa suoraan luvun 1, jos avain löytyy, ja 0 muuten. Näin ei tarvitse luoda turhia iteraattoreita ja verrata niitä.

Noita funktioita voisi myös optimoida. Hakiessa kannattaa käyttää find-metodin palauttama iteraattori hyödyksi:

auto it = _mMap.find(p1Pointer1_);
if (it == _mMap.end())
    return NULL;
return it->second;

Näin puuta ei tarvitse kulkea läpi kahdesti. Lisäämiskoodiakin voisi lyhentää:

if (!_mMap.count(p1Pointer1_))
    return _mMap[p1Pointer1_] = new Pointer2(p1Pointer1_);
return _mMap[p1Pointer1_];

Tämä ei ehkä hirveästi nopeuta koodia, mutta ainakaan ei tarvitse kutsua yhtä montaa funktioita kuin aikaisemmin.

Hennkka kirjoitti:

Noita funktioita voisi myös optimoida.

Minustakin on selvempää käyttää findin palauttamaa iteraattoria: näkee suoraan, että palautetaan juuri se, mitä haettiinkin, ja on myös yksi muutettava kohta vähemmän, jos findin argumenttia täytyy joskus vaihtaa. Sen sijaan count ei välttämättä ole erityisen tehokas, koska sisäisesti se tekee varmasti aivan saman asian kuin find(x) != end().

Yksi optimointi lisäykseen olisi lähimmän avaimen haku funktiolla lower_bound, omatoiminen vertailu ja tarvittaessa insert käyttäen sijaintina tätä haettua iteraattoria.

Toisaalta nämä omat ”optimoinnit” eivät ehkä edes vaikuta, jos kääntäjä optimoi koodin järkevästi.

kayttaja-3842 kirjoitti:

Mitä virkaa ko. foorumilla on jos – –

Toisaalta mitä virkaa on kertoa, että ”sain idean, joka oli huono”? ;) Sitä paitsi en sanonut, että älä kysele tai että pitäisi tietää, vaan kehotin vastaisen varalle ottamaan selvää laajemminkin. Ainakin kannattaa käydä läpi C++:n tavanomaiset säiliöluokat ja opetella niiden edut ja haitat.

Metabolix kirjoitti:

Toisaalta mitä virkaa on kertoa, että ”sain idean, joka oli huono”? ;) Sitä paitsi en sanonut, että älä kysele tai että pitäisi tietää, vaan kehotin vastaisen varalle ottamaan selvää laajemminkin. Ainakin kannattaa käydä läpi C++:n tavanomaiset säiliöluokat ja opetella niiden edut ja haitat.

Oli miten oli. Kummallakin on oma näkymyksensä, eikä sitä mielestäni kannata enempää tässä viestiketjussa puida. Ketjun sisältö taitaa, jo nyt sisältää enemmän väittelyä kun itse asiaa. :)

Kiitos kummallekkin vinkeistä ja erityisesti Hennkka:n optimointi vinkistä. Loppu tulema oli se, että std::map:in käyttö tuossa kohtaa oli aika pitkälti oikea ratkaisu? Niinkuin arvelinkin.

kayttaja-3842 kirjoitti:

Loppu tulema oli se, että std::map:in käyttö tuossa kohtaa oli aika pitkälti oikea ratkaisu? Niinkuin arvelinkin.

No kuten sanoin, std::unordered_map on useissa tilanteissa selvästi nopeampi.

Aivan. :) Vaihdoinkin tuon std::map:in heti silloin käyttämään tuota std::unordered_map:ia. Ero ei kaiketi silmin nähden kauhean suuri ollut ( enkä sitä odottanutkaan ), mutta aina parempi jos hieman edes saa nopeammaksi.