Springen naar inhoud

[c++] unsigned int


  • Log in om te kunnen reageren

#1

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 21 maart 2009 - 19:05

Voor school moeten een radix sort implementeren voor unsigned ints. Het komt er op neer bij radix sort dat je de getallen gaat opdelen in groepen volgens een bepaalde radix (bij radix 10 zou je dus groepen maken van getallen die beginnen met 0, 1, 2, ... 9). Daarna zou je elk van deze groepen opnieuw bekijken en daar opnieuw die regel op toepassen om zo de volgende groep te maken, ... (tot daar mijn korte uitleg over radix sort).

Nu bestaat een unsigned int in c++ uit 4 bytes. Ik gebruik nu elke byte om op te delen in groepen. Voor de meeste beduidende byte krijgen we dus radix = 256. We gaan de elementen dus opdelen in groepen van 256. Wanneer ik dit nu doe voor een tabel van 10 elementen is de kans groot dat alle elementen in een aparte groep belanden (wat ook zo is), als we nu de groepen in juiste volgorde sorteren kunnen we enkel uit de hoogste byte al de juiste volgorde halen. (Zo kan je de getallen 3454,4333,1222 ook sorteren door alleen naar de eerste getallen te kijken vermits de 3 getallen in een andere groep zouden belanden).

Goed, alle getallen zitten in een aparte groep, de groepen worden correct gesorteerd, maar tot mijn verbazing zijn de getallen zelf niet gesorteerd!

Klein voorbeeldje:
byte  getal
89	1625
40	21544
200	32200
177	11953
202	7626
113	26993
88	8280
0	16384
34	7714
223	28127
Na sorteren:
0	16384
34	7714
40	21544
88	8280
89	1625
113	26993
177	11953
200	32200
202	7626
223	28127

Iemand die een verklaring kan geven waarom ik die groepen krijg voor die getallen?

Veranderd door Cycloon, 21 maart 2009 - 19:06


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 21 maart 2009 - 23:29

Ik denk dat ik zelf al een stukje verder ben. Blijkbaar geeft rand() allemaal waarden terug die gaan tot max 2^15 (een signed int van 16 bits). Hoe krijg ik random unsigned int's van 32 bit?

#3

Schwartz

    Schwartz


  • >250 berichten
  • 691 berichten
  • Verbannen

Geplaatst op 22 maart 2009 - 00:30

Simpel:
eerst vul je de eerste twee bytes in met je random en dan de volgende twee bytes met een nieuwe random.

wel ervan uitgaan dat 4 bytes uit 32 bits bestaat:
0..65535 en dan nog eens 0..65535

Veranderd door Schwartz, 22 maart 2009 - 00:32

Een computertaal is voor mensen, niet voor de computer.

#4

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 22 maart 2009 - 10:55

Goed, alle getallen zitten in een aparte groep, de groepen worden correct gesorteerd, maar tot mijn verbazing zijn de getallen zelf niet gesorteerd!

Waarom verwacht je dat de 'least significant byte' iets zegt over de uiteindelijke positie van het totale getal?

Stel dat je 124 en 39 gaat sorteren (radix = 10). Je begint dan met 4 en 9 te sorteren. Deze staan al in de juiste volgorde dus je doet niks. Dit betekent logischer wijs dat de getallen nog steeds in de verkeerde volgorde staan. Bij de volgende stap vergelijk je 2 en 3. Wederom doe je niks. Daarna vergelijk je 1 en 0. Nu draai je 124 en 39 om om op de juiste volgorde te komen.

#5

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 22 maart 2009 - 11:57

Waarom verwacht je dat de 'least significant byte' iets zegt over de uiteindelijke positie van het totale getal?


Dat doe ik ook niet, ik sprak wel degelijk over de meeste significante byte.

Je moet het dan zien als je 124 en 039 gaat sorteren, eerst vergelijk je 0 en 1, 039 zal dus voor 124 komen. Vermits beiden in een andere deelgroep zitten kan je stoppen met vergelijken van de volgende getallen.

Maar het probleem waarom mijn code niet werkt is omdat ik vermoed dat c++ daar zelf int's heeft ingestoken die ik uit de rand() heb gehaald, ipv unsigned int's die ik wil. Hierdoor zijn de 2 meest significante bytes niet ingevuld geweest vermoed ik waardoor die geen betekenis hebben in dit geval.

Simpel:
eerst vul je de eerste twee bytes in met je random en dan de volgende twee bytes met een nieuwe random.

wel ervan uitgaan dat 4 bytes uit 32 bits bestaat:
0..65535 en dan nog eens 0..65535


En hoe vul ik 1 unsigned integer met 2 16 int getallen?

#6

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 22 maart 2009 - 13:41

Ok het probleem is opgelost. Blijkbaar worden de bytes opgeslagen van minst significant naar meest significant, waardoor ik eerst moet groeperen op de laatste byte en niet op de eerste. Waarom ze dit op deze manier opslaan is mij een raadsel, maar het probleem is dus wel opgelost ;)

#7

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 22 maart 2009 - 14:03

Waarom ze dit op deze manier opslaan is mij een raadsel, maar het probleem is dus wel opgelost ;)

Endianness.

Ik overigens benieuwd hoe jij de 4 bytes uit je int haalt.

#8

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 22 maart 2009 - 18:07

Ik ben overigens benieuwd hoe jij de 4 bytes uit je int haalt.


unsigned int i = 2345;
unsigned char* p = ((unsigned char*)(&i);

p is nu een pointer naar de eerste byte, de 2de byte is dan natuurlijk p+1 enzovoort. Indien je het ding wil afdrukken in een cout o.i.d. moet je het wel terugcasten naar een int.

#9

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 22 maart 2009 - 19:26

Dat is mijn inziens niet echt netjes (en bovendien introduceer je op deze manier machineafhankelijkheid).

Je had mijn inziens beter iets in de volgende trant kunnen doen:
unsigned int i = 1234;
unsigned char lsb = i & 0xFF;
unsigned char s2b = (i >> 8) & 0xFF;
unsigned char s3b = (i >> 16) & 0xFF;
unsigned char msb = (i >> 24) & 0xFF;

#10

Cycloon

    Cycloon


  • >1k berichten
  • 4810 berichten
  • VIP

Geplaatst op 22 maart 2009 - 22:01

Die code was gegeven door een docent. Sowieso ben je toch afhankelijk van je systeem als ik die endianness goed versta.

Het is ook de bedoeling om die radix sort meer algemeen te maken zodat het ook strings e.d. kan gaan sorteren en dan is het makkelijker om met een pointer systeem te gaan werken om zo algemeen mogelijk te blijven.

Veranderd door Cycloon, 22 maart 2009 - 22:03


#11

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 22 maart 2009 - 22:13

Sowieso ben je toch afhankelijk van je systeem als ik die endianness goed versta.

Nee, dat is niet zo. Als je namelijk met bijvoorbeeld (i & 0xFF) de onderste 8 bits van je integer bekijkt, krijg je altijd het least significant byte. Dit is onafhankelijk van endianness.

Het is ook de bedoeling om die radix sort meer algemeen te maken zodat het ook strings e.d. kan gaan sorteren en dan is het makkelijker om met een pointer systeem te gaan werken om zo algemeen mogelijk te blijven.

Daar ben ik het wel mee eens, maar ik denk dat je dit alleen kunt doen als je ook methodes levert waarmee je dan garandeert dat de strings/integers/whatever op die manier worden uitgelezen zodat ze juist gesorteerd gaan worden.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures