advertentie

Dit forum is niet langer actief. Voor vragen kun je voortaan terecht in de Vraag & Antwoord-rubriek van PCMweb.nl

 

Ga terug   PCM Forum > Scripting > Software programmatuur

Antwoord
 
Discussietools Weergave
Oud 22 February 2009, 14:48   #11
blua tigro
Just Joined!
 
Geregistreerd: 16 February 2009
Locatie: nh
Berichten: 20
Cool snelhied 3

dat van N * log( N )
wist ik niet
je kun nooit alles weten
weer wat geleerd

maar dat is dan wel t MINIMUM aantal
de randomgenerator zal soms n bestaand getal kiezen
de kans dat dat NIET gebeurt :

//LIJST < WAARDEN
const int LIJST = 320 ;
const int WAARDEN = 1000 ;
int main( )
{
double d = 1.0 ;
int i ;
for ( i = 1 ; i < LIJST ; i++ )
{
d *= ( WAARDEN - i ) / WAARDEN * 1.0 ;
}
//print d ;
//wacht toets ;
return 0 ;
}

t zal je verbazen hoe klein die kans is
probeer ook eens andere getallen
t wordt helemaal erg als LIJST in de buurt komt van WAARDEN
------------------------------------------------------------------------
data is nog geen infomatie
informatie is nog geen kennis
kennis is nog geen inzicht
inzicht is nog geen wijsheid
blua tigro is offline   Met citaat antwoorden
Oud 22 February 2009, 22:29   #12
gvanvoor
PCM Lord
 
gvanvoor's schermafbeelding
 
Geregistreerd: 26 January 2006
Locatie: De gezelligste stad ter wereld: Gent
Berichten: 928
Standaard

Citaat:
Oorspronkelijk geplaatst door blua tigro Bekijk bericht
dat van N * log( N )

maar dat is dan wel t MINIMUM aantal
Dat is het gemiddeld aantal in dit specifieke geval (als je ooit een cursus datastructuren en algoritmen volgt zul je de details te weten komen).
De kans dat in de laatste stap een getal wordt gekozen dat al in de lijst voorkomt is 0,319. Die waarde is een maximum (de kans is kleiner voor alle voorgaande stappen) en mocht je die in rekening willen brengen kom je uit op O(n * (1 + 0,319) * log(n)) = O(1,319 * n * log(n)) = 1,319 * O(n * log(n)) wat overeenkomt met O(n * log(n)) omdat multiplicatieve constanten van geen belang zijn (we willen weten hoe de snelheid van het algoritme zich verhoudt bij een probleem van grootte n t.o.v. een probleem van grootte n' en dan valt die constante toch weg).
__________________
If you want to work on your computer: buy a PC. If you want to do work on your computer: buy a Mac.
gvanvoor is offline   Met citaat antwoorden
Oud 25 February 2009, 11:05   #13
blua tigro
Just Joined!
 
Geregistreerd: 16 February 2009
Locatie: nh
Berichten: 20
Cool

ik had al wel veel ervaring
met arrays in basic
minstens sins 1993
vandaar
c++
doe ik pas sins nov 08
-------------------------------------------------------------------------
sun tzu : de beste manier om n slag te winnen is zonder te vechten
blua tigro is offline   Met citaat antwoorden
Oud 26 February 2009, 00:12   #14
gvanvoor
PCM Lord
 
gvanvoor's schermafbeelding
 
Geregistreerd: 26 January 2006
Locatie: De gezelligste stad ter wereld: Gent
Berichten: 928
Standaard

Een goede bron van informatie wat betreft de standard template library van C++ vind je op http://www.sgi.com/tech/stl/
Er staat daar ook informatie m.b.t. de tijdscomplexiteit van bepaalde operaties.
__________________
If you want to work on your computer: buy a PC. If you want to do work on your computer: buy a Mac.
gvanvoor is offline   Met citaat antwoorden
Oud 26 February 2009, 11:30   #15
blua tigro
Just Joined!
 
Geregistreerd: 16 February 2009
Locatie: nh
Berichten: 20
Cool set

ik heb op de site gekeken
het ziet r daar heer anders uit
daar is set nieteens n object
zn set lijkt mij wel handig voor t sorteren
van n wilekurig objectarray
maar kan dat ook op doubles ipv ints ?
dat heb ik namelijk nodig voor t sorteren
van polygonen in n vr syteem
N log( N ) < ( N - 1 ) * ( N - 1 ) / 2
dan kan t dus sneller of met meer polygonen
-------------------------------------------------------------------------
non in solo pane vivid homo
blua tigro is offline   Met citaat antwoorden
Oud 26 February 2009, 22:54   #16
gvanvoor
PCM Lord
 
gvanvoor's schermafbeelding
 
Geregistreerd: 26 January 2006
Locatie: De gezelligste stad ter wereld: Gent
Berichten: 928
Standaard

Het zijn wel degelijk objecten: het zijn template klassen. Als je een array van willekeurige objecten wil sorteren kan je ook een std::vector gebruiken in combinatie met std::sort. De code ziet er dan ongeveer zo uit:
Code:
#include <vector>
#include <algorithm>

std::vector< double > theDoubleVector;

// voeg de elementen toe m.b.v. push_back (eenGetal moet in dit geval een double zijn)
theDoubleVector.push_back(eenGetal);

// sorteer
std::sort(theDoubleVector.begin(), theDoubleVector.end());
Welke van de 2 (vector + sort vs set) het effici?ntst is hangt een beetje af van wat je nog van plan bent met de gegevens...

Als je op voorhand weet hoe groot je vector zal zijn kan je ook op voorhand de benodigde ruimte reserveren: dan vermijd je dat de vector bij het toevoegen van elementen telkens nieuw geheugen moet alloceren.

Bij objecten die op zich geen comparator hebben zal je wel de sort aanroep met 3 argumenten moeten gebruiken.
__________________
If you want to work on your computer: buy a PC. If you want to do work on your computer: buy a Mac.

Laatst gewijzigd door gvanvoor : 26 February 2009 om 23:02 Reden: foutje rechtgezet...
gvanvoor is offline   Met citaat antwoorden
Oud 27 February 2009, 13:35   #17
blua tigro
Just Joined!
 
Geregistreerd: 16 February 2009
Locatie: nh
Berichten: 20
Cool set + vector

to nu toe deed ik t zo
int rij[ POLY_MAX } ;
for ( i = 0 ; i < POLY_MAX ; i++ ) rij[ i ] = i ;
for ( h = 1 ; h < PLOY_MAX ; h++ )
{
for ( l = 0 ; l < PLOY_MAX - 1 ; l++ )
{
if ( ploygon{ rij[ l ] ].led().z > ploigon[ rij[ h ] ].led().z )
{ //n int swappen gaat sneller dan n polygon dacht ik
swap( rij[ i ] , rij[ h ] ) ;
}
}
)
for ( i = 0 ; i < POLY_MAX ; i++ )
{
polygon{ rij{ i ] ].draw() ;
}
hoe nu dit met n vector of set ?
-------------------------------------------------------------------------
we are all different therefore we are all equal
blua tigro is offline   Met citaat antwoorden
Oud 27 February 2009, 22:31   #18
gvanvoor
PCM Lord
 
gvanvoor's schermafbeelding
 
Geregistreerd: 26 January 2006
Locatie: De gezelligste stad ter wereld: Gent
Berichten: 928
Standaard

Ik was vergeten vermelden dat pointers voldoen aan de "criteria" om als iterator gebruikt te worden, dus je kan gewoon je begin en eind-pointer doorgeven aan std::sort die dan je array zal sorteren in O(n * log(n)).

Code:
#include <algorithm>

int rij[ POLY_MAX ] ;
for ( i = 0 ; i < POLY_MAX ; i++ )
    rij[ i ] = i ;

std::sort(rij, rij + POLY_MAX);

for ( i = 0 ; i < POLY_MAX ; i++ )
{
    polygon[ rij[ i ] ].draw() ;
}
__________________
If you want to work on your computer: buy a PC. If you want to do work on your computer: buy a Mac.
gvanvoor is offline   Met citaat antwoorden
Oud 5 March 2009, 18:48   #19
blua tigro
Just Joined!
 
Geregistreerd: 16 February 2009
Locatie: nh
Berichten: 20
Cool polygonen sorteren

dat gaat niet werken
als je
for ( i = 0 ; i < PLOYMAX ; i++ ) rij[ i ] = i ;
doet dan is rij al gesorteerd
polygon blijft dan in oorsprongkelijke volgorde
even wat info :
class CV3d { double x , y , z ; } ;
//met wat operanden
class CPoly { CV3d pnt[ 6 ] ; } ;
//met metode draw( )
//pnt[ 0 ] = zwaartepunt
//pnt[ 1...4 ] = hoekpunt
//pnt[ 5 ] = loodlijn

ik sorteer nu zo
CPoly poly[ POLYMAX ] ;
//lus h //lus l
if ( poly[ rij[ l ] ].pnt[ 0 ].z > poly[ rij[ h ] ].pnt[ 0 ].z )
swap rij[ l ] , rij[ h ] ;
//next i , h
//lus i
poly[ rij[ i ] ].draw( ) ;
//next i
dit werk prima maar gaat wel in 0( ( N - 1 ) ^ 2 / 2 )

maar hoe HETZELFDE effect met
std::sort ???
-----------------------------------------------------------------------
we are al different therefore we are al equal

Laatst gewijzigd door blua tigro : 5 March 2009 om 20:08 Reden: foutje
blua tigro is offline   Met citaat antwoorden
Oud 6 March 2009, 01:00   #20
gvanvoor
PCM Lord
 
gvanvoor's schermafbeelding
 
Geregistreerd: 26 January 2006
Locatie: De gezelligste stad ter wereld: Gent
Berichten: 928
Standaard

Je hebt een strikt-kleiner-dan operator nodig voor de klasse die de objecten die je wil sorteren beschrijft.
Veronderstel dat je een array van objecten van de klasse "Element" moet sorteren:

Code:
class Element
{
    ...
};

Element teSorteren[arrayGrootte];
De eenvoudigste (en makkelijkst te begrijpen) oplossing is een kleiner-dan-functie aan de Element klasse toe te voegen:
Code:
class Element
{
    ...

    public:
        static bool KleinerDan(Element const & inLinks, Element const & inRechts);
};
en dan schrijf je waar je moet sorteren
Code:
std::sort(teSorteren, teSorteren + arrayGrootte, Element::KleinerDan);
In je implementatie van de operator moet je er dan voor zorgen dat die enkel true teruggeeft als inLinks < inRechts. (Dus false als ze gelijk zijn; dit is zeer belangrijk want anders zal het resultaat niet kloppen of het programma crashen).

Een andere manier is de functie operator overladen maar dat is minder proper...

Ik heb de code niet getest dus mogelijk staan er een paar foutjes in, maar in grote lijnen klopt het zeker.
__________________
If you want to work on your computer: buy a PC. If you want to do work on your computer: buy a Mac.
gvanvoor is offline   Met citaat antwoorden
Antwoord


Discussietools
Weergave

Regels voor berichten
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Aan
Smileys zijn Aan
[IMG]-code is Aan
HTML-code is Uit

Forumnavigatie


Alle tijden zijn GMT +1. Het is nu 13:48.



Powered by vBulletin Version 3.8.6
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Nederlandse vBulletin-vertaling door Alacer beschikbaar gesteld door Applinet.