[c] Prio Buffer

[Verwijderd]

Ik ben bezig met een school project en zit met het volgende probleem.

Ik moet een op prioriteit gesorteerde buffer zien te maken. Dus er komt iets binnen met hogere prioriteit dan de laatste helft van de buffer dan moet het daar tussen worden geplaatst.

Nu zat ik zelf te denken om een circular array te maken(omdat er constant dingen bij komen en af gaan (i/o op een 8051 kitje)) en als er dan iets nieuws binnen komt de array te doorlopen alles met lagere prioriteit ff naar een temp array te schrijven, de nieuwe input in de array en dan de oudere er weer achter...

Is dit de handigste methode of kan ik het beter anders aan pakken, zo ja: hoe?

B.v.d

[.oisyn]

[google=priority queue]
Het wordt meestal geimplementeerd als een boomstructuur, waarbij het element met de hoogste prioriteit altijd in de root staat. Als je die uitleest en verwijderd uit de boom, dan moet er natuurlijk een nieuwe root-node komen. Je kijkt dan naar het linker en het rechterdeel, en degene met de hoogste prioriteit schuif je door naar de root. Dat veroorzaakt natuurlijk weer een gat op de plaats waar die node stond, dus moet je weer verschuiven op dezelfde manier. En dat doe je totdat je aan het eind van de boom komt.

Toevoegen aan de boom gaat in de omgekeerde richting. Je voegt het element toe aan een van de bladeren, en als de prioriteit van het nieuwe element hoger is dan dat van de node waaraan je 'm hebt toegevoegd, dan wissel je ze om. Dan vergelijk je weer met de ouder van die node, etc., net zolang totdat de prioriteit van het nieuwe element lager is dan z'n ouder.

Deze binaire boomstructuur kan overigens gewoon in een array worden gestopt. De root staat op index 1, daarna volgen alle kinderen van de root, daarna alle kinderen van die kinderen, etc. Met andere woorden, eerst alle nodes op hoogte 0, daarna alle nodes op hoogte 1, enzovoort. Als n de index van je huidige node is, dan is n/2 de index van de ouder, en n*2 en n*2+1 de indices van de 2 kinderen

[ Voor 20% gewijzigd door .oisyn op 13-05-2004 14:27 ]

[Verwijderd]

Je bedoeld dus een fibonnaci structuur?

[.oisyn]

Niet bepaald. Op index 1 staat de root, op indices 2&3 de 2 kinderen van de root, op indices 4 t/m 7 staan de 4 kinderen van die kinderen, en op indices 8 t/m 15 staan de 8 kinderen van die kinderen, etc.

Het aantal nodes op hoogte n is 2ⁿ. Heeft dus niets met fibonacci te maken.

[ Voor 18% gewijzigd door .oisyn op 13-05-2004 14:39 ]

[Verwijderd]

Ik kan me er niet een goed beeld bij vormen sorrie...

Ik vind via google ook niet echt wat ik zoek. Veel java en c++ met ingebakken functies, die ik hier ook wel in boeken heb staan... Ik blijf wel ff doorzoeken

[4VAlien]

Misschien kan je met buckets werken, dus verschillende arrays waarin waarden met verschillende prioriteit staan, dit werkt natuurlijk alleen als je een beperkt aantal priorteiten hebt.

edit: let ook op starvation, dus dat sommige data nooit verwerkt wordt als er data met hogere prioriteit blijft binnenkomen. Dit kan een probleem worden.

[ Voor 35% gewijzigd door 4VAlien op 13-05-2004 14:48 ]

[Verwijderd]

4VAlien schreef op 13 mei 2004 @ 14:47:
Misschien kan je met buckets werken, dus verschillende arrays waarin waarden met verschillende prioriteit staan, dit werkt natuurlijk alleen als je een beperkt aantal priorteiten hebt.

Dit is niet eens zon slecht iedeen en relatief makkelijk toe te passen in onze source. Het aantal prioriteiten valt wel mee, dus dat zit wel goed.
Thanx m8

[Verwijderd]

4VAlien schreef op 13 mei 2004 @ 14:47:


edit: let ook op starvation, dus dat sommige data nooit verwerkt wordt als er data met hogere prioriteit blijft binnenkomen. Dit kan een probleem worden.

we maken een lift besturing en ik vermoed niet dat we daar starvation bij gaan krijgen...

[Verwijderd]

.

[ Voor 99% gewijzigd door Verwijderd op 31-10-2023 22:27 ]

[Soultaker]

hasse_m: heb je de thread wel gelezen? Dat was dus al het oorspronkelijke plan van de topicstarter.

Verwijderd schreef op 13 mei 2004 @ 14:36:
Je bedoeld dus een fibonnaci structuur?

.oisyn beschreef een gewone heap tree, maar een Fibonacci heap is inderdaad ook geschikt. (Bedenk dat Fibonacci gewoon de naam van een persoon is en eerder met Fibonacci getallen wordt geassocieerd dan met een datastructuur.) In principe is een Fibonacci heap efficiënter dan een 'gewone' heap tree maar in dit geval is het misschien ook overkill: een gewone heap is met O(log N) insertion en removal waarschijnlijk al efficiënt zat (en een grote verbetering ten opzichte van de O(N) insertion in je cyclische lijst).

Als je echter al weet hoe een Fibonacci heap werkt is dat ook gewoon een geschikte oplossing, al is een gewone heap makkelijker te programmeren. (Het is in verband met Google/searches trouwens wel handig als je Fibonacci goed spelt ).

Een goed beginpunt voor dit soort problemen is The Algorithm Design Manual, in dit geval de sectie over Priority Queues. Geen volledige uitleg, maar wel een overzicht van de mogelijkheden en zoektermen om met Google verder te zoeken.

[ Voor 17% gewijzigd door Soultaker op 13-05-2004 15:42 ]

[.oisyn]

Verwijderd schreef op 13 mei 2004 @ 14:57:
Maak een linked list! Kun je eenvoudig elementen ergens tussenvoegen!

Het invoegen is alleen een O(n) operatie, terwijl dat bij de priority queue (de de-factor standaard die wordt gebruikt voor dit soort dingen, en met een reden) slechts O(log n) is

Verwijderd schreef op 13 mei 2004 @ 14:44:
Ik kan me er niet een goed beeld bij vormen sorrie...

Je weet hoe een boomstructuur in elkaar zit neem ik aan?

code:

             [1]
              |
       +------+------+
       |             |
      [2]           [3]
       |             |
   +---+---+     +---+---+
   |       |     |       |
  [4]     [5]   [6]     [7]

En dat stop je gewoon op die manier in de array. De root komt op 1, de 2 kinderen op 2 en 3, enzovoort. In principe hoef je alleen maar te onthouden:
• De parent van n is n/2
• Het linker kind van n is n*2
• Het rechter kind van n is n*2+1

De hoogste prioriteit van je hele queue staat altijd in de root. Als je die eruit weghaalt, dan staat daar dus een lege plaats. Om te bepalen wat daar staat, kijk je naar [2] en [3], en degene met de hoogste prioriteit verplaats je naar de plaats van [1]. Stel je hebt [2] verplaatst, dan staat daar een lege plek, en moet je weer kijken naar [4] en [5]. Dit gaat door net zolang tot je bij de bladeren bent.

Als er 23 items in de queue staan, dan is positie 1 t/m 23 dan ook gevuld met die elementen. Een nieuw item toevoegen doe je gewoon door 'm op positie 24 te zetten. Vervolgens kijk je naar de parent van [24], [12] dus, en als de prioriteit van [12] lager is dan die van [24] dan wissel je ze om. Vervolgens kijk je naar de parent van [12], [6] dus, en wissel je ze weer om als de prioriteit van [12] hoger is dan die van [6]. Daarna kijk je naar positie [3], en vervolgens naar positie [1]. Als je nieuwe element uiteindelijk op [1] terecht komt betekent dat dus dat ie een prioriteit heeft die hoger is dan de rest van de elementen.


Voorbeedje dan maar:
Stel je hebt nog een lege boom, en je gaat elementen toevoegen met de volgende prioriteiten: 16, 3, 5, 12, 45, 34. Een hogere waarde betekent een hogere prioriteit.

Je begint met een lege boom, dan voeg je 16 in. De boom is leeg, dus 16 komt in de root:

code:

boom:        [1:16]

array: [16,-]

Dan doe je 3. Op index [2] staat een lege plaats, dus daar voeg je 'm toe:

code:

boom:      [1:16]
              |
       +------+------+
       |             |
     [2:3]         [3:-]

array: [16,3,-]

Vervolgens kijk je naar de parent van [2], [1] dus, maar aangezien 16 hoger is dan 3 hoef je niet om te wisselen

Hetzelfde doe je met de 5, die start op plaats [3], en hoeft ook niet omgewisseld te worden met [1], dus je hebt nu:

code:

boom:        [16]
              |
       +------+------+
       |             |
      [3]           [5]

array: [16,3,5,-]

Nu moet je 12 in gaan voeren. Plaats [4] is de eerste vrije plaats, dus je krijgt

code:

boom:      [1:16]
              |
       +------+------+
       |             |
     [2:3]         [3:5]
       |
   +---+---+
   |       |
[4:12]   [5:-]

array: [16,3,5,12,-]

Maar, 12 is groter dan 3 (je vergelijkt [4] met [2]), dus die wissel je om:

code:

boom:      [1:16]
              |
       +------+------+
       |             |
     [2:12]         [3:5]
       |
   +---+---+
   |       |
[4:3]   [5:-]

array: [16,12,5,3,-]

Nu ga je 45 invoegen, en plaats [5] is de eerste vrije plaats. Plaats [5] vergelijk je met plaats [2], en 45 is hoger dan 12, dus die wissel je om:

code:

boom:      [1:16]
              |
       +------+------+
       |             |
     [2:45]         [3:5]
       |
   +---+---+
   |       |
[4:3]  [5:12]

array: [16,45,5,3,12,-]

Dan ga je [2] met [1] vergelijken, en omdat 45 hoger is dan 16 wissel je die ook om:

code:

boom:      [1:45]
              |
       +------+------+
       |             |
     [2:16]         [3:5]
       |
   +---+---+
   |       |
[4:3]  [5:12]

array: [45,16,5,3,12,-]

Daarna moet je 34 invoegen, die komt op plaats [6], maar aangezien op plaats [3] een 5 staat, moet je die omwisselen. Vervolgens hoef je 'm niet met [1] om te wisselen, om dat de 45 die daar staat hoger is dan 34. Het resultaat is dus:

code:

boom:      [1:45]
              |
       +------+------+
       |             |
     [2:16]         [3:34]
       |             |
   +---+---+     +---+---+
   |       |     |       |
 [4:3]  [5:12] [6:5]   [7:-]

array: [45,16,34,3,12,5,-]

Een element uit de boom halen is simpel: je pakt de root, oftewel het element op [1] met prioriteit 45. Dit is het element met het hoogste prioriteit. Nu je die afgehandeld hebt haal je 'm natuurlijk uit de boom, maar dat zorgt voor een gat bovenaan.

code:

boom:      [1:?]
              |
       +------+------+
       |             |
     [2:16]         [3:34]
       |             |
   +---+---+     +---+---+
   |       |     |       |
 [4:3]  [5:12] [6:5]   [7:-]

De 2 kinderen van [1] zijn 1*2 en 1*2+1, dus [2] en [3]. 34 is natuurlijk hoger dan 16, dus de 34 verplaats je naar boven.

code:

boom:      [1:34]
              |
       +------+------+
       |             |
     [2:16]         [3:?]
       |             |
   +---+---+     +---+---+
   |       |     |       |
 [4:3]  [5:12] [6:5]   [7:-]

Nu moet je [6] en [7] met elkaar vergelijken. Aangezien positie 7 nog niet gevuld is, kun je gewoon [6] naar [3] verplaatsen, en is [6] een nieuwe vrije positie

Ik hoop dat het zo een beetje duidelijk is

[Verwijderd]

.

[ Voor 99% gewijzigd door Verwijderd op 31-10-2023 22:27 ]

[Soultaker]

In termen van algoritmische complexiteit is zijn oplossing even goed als de jouwe; insertion blijft een O(N) operatie. Je ruilt dus de ene matige oplossing in voor de andere. Verder is het een schoolproject dus ik neem aan dat het wel de bedoeling is dat de TS er wat van leert en uiteindelijk met een (ook theorethisch) solide oplossing komt. Hij kan dan beter een heap tree implementeren, want behalve dat dat erg goed werkt is het ook een erg nuttige datastructuur om te leren kennen.

(Overigens zou ik de Fibonacci heap in deze situatie afraden; de implementatie is veel ingewikkelder en in deze situatie valt er niet van de prettige eigenschappen ten op zichte van een gewone heap tree te profiteren.)

[Verwijderd]

Bedankt voor jullie replies, ik heb nu een redelijk goed overzicht van de mogelijkheden gekregen. Nu nog uit zien te werken en toe passen. Ik ben geen programmeer held, maar nu heb ik dusdanig veel tips dat ik met een beetje hulp van internet (programmeer voorbeelden) er wel uit moet komen.

Ik was een beetje op het verkeerde been gebracht doordat het in c moet en ik dus methodes die we hadden geleerd niet kon gebruiken (we hebben een boek: data structures and program design in c++) en daar staan de meeste van jullie methodes wel in uitgelegt, maar in c++ uitgwerkt (meestal met dingen die in c niet werken).

[Elijan9]

4VAlien schreef op 13 mei 2004 @ 14:47:
Misschien kan je met buckets werken, dus verschillende arrays waarin waarden met verschillende prioriteit staan, dit werkt natuurlijk alleen als je een beperkt aantal priorteiten hebt.

Aangezien je met een 8051 MCU te maken hebt met waarschijnlijk niet meer dan 64k geheugen (of flink minder) waar alles in moet gebeuren, lijkt mij dat ^^ ook het beste, scheelt een hoop zoektijd en memory management (traaag voor een kleine MCU)...

Dan zou je inderdaad circulaire buffers kunnen gebruiken - per prioriteit - met een initiële grootte. Pas als de buffer vol zit, zou ik dan een grotere buffer alloceren en de queue daar naartoe kopieren, scheelt een hoop alloc/free. Maar voor een liftbesturing heeft voor de meeste prioriteiten de queue waarschijnlijk een berekenbare maximum, afhankelijk van de besturingselementen en het aantal verdiepingen.

Heb je wel veel geheugen/klokpulsen/geld beschikbaar en of veel taken en prioriteiten af te handelen, ga dan inderdaad (pas) voor de beter zoekalgorithmes.

[.oisyn]

Elijan9 schreef op 13 mei 2004 @ 17:52:
ga dan inderdaad (pas) voor de beter zoekalgorithmes.

Een priority queue als binary heap is ook gewoon O(n) in geheugen hoor, en het kost zelfs in totaal minder geheugen omdat je maar 1 array hebt ipv meerdere (dus minder pointers en minder management)

[ Voor 6% gewijzigd door .oisyn op 13-05-2004 18:04 ]

[Soultaker]

Elijan9: ik snap niets van jouw redenatie. Als je een trage processor hebt, dan moet je juist een efficienter algoritme gebruiken: O(log N) in plaats van O(N) dus. Het enige argument waar ik me iets bij voor kan stellen is de grote code size die een ingewikkelder algoritme met zich mee brengt, maar at runtime is een O(N) algoritme juist op een trage chip kwalijk.

Verder is een binary heap veel efficienter in geheugengebruik zoals.oisyn ook al aangeeft. In theorie gebruiken zowel een binary heap als een linked list O(N) geheugen, maar in de praktijk sla je in een binary heap op in een array, en dan alloceer je uitsluitend ruimte voor de elementen terwijl je in de linked list per element een link extra moet alloceren. Als je een linked list bouwt met simpele elementen (getallen, bijvoorbeeld) dan kan je dus zomaar twee keer zoveel geheugen alloceren als wanneer je een gewone array had gealloceerd.

[Elijan9]

.oisyn schreef op 13 mei 2004 @ 18:03:
[...]


Een priority queue als binary heap is ook gewoon O(n) in geheugen hoor, en het kost zelfs in totaal minder geheugen omdat je maar 1 array hebt ipv meerdere (dus minder pointers en minder management)

Zoals jij het beschreef moet je toch vaak alloceren/free-en en of moven als je een nieuw element erbij krijgt of een element weer verwijderd kan worden (taak is uitgevoerd), blijkbaar begrijp ik het verkeerd...
Een cyclische buffer eind- of beginpointer ophogen kost vrijwel niks en vanaf de hoogste prioriteitbuffer alle buffers nalopen kost toch ook bijna geen tijd?

[ Voor 14% gewijzigd door Elijan9 op 13-05-2004 19:07 ]

[.oisyn]

Je hoeft niets te alloceren of te free'en (het is gewoon 1 array), en worst case hoef je maar ²log n verschuivingen te doen, met n het aantal elementen al in de boom

[Soultaker]

Voor elk element moet je ruimte alloceren; dat geldt zowel bij een linked list als bij een heap tree. Je kunt het aantal allocaties op laag nivo echter wel beperken door meerdere elementen tegelijk te alloceren; liefst exponentieel groter wordende aantallen, zodat het aantal allocaties logaritmisch is ten op zichte van het aantal elementen. Dit geldt nog steeds voor zowel de linked list als de heap tree.

Het werkelijke verschil in de kosten zit 'm in het invoegen en verwijderen van elementen. Als je een linked list gebruikt heb je in principe de keuze uit de lijst gesorteerd houden of gesorteerd elementen uit de lijst halen. In het eerste geval is insertion een O(N) operatie en extraction een O(1) operatie; in het tweede geval is het precies andersom. Door de bank genomen kom je altijd op O(N) uit, aangezien er uiteindelijk evenveel items in de queue gaan als er uit komen.

Insertion en extraction op een heap tree is een O(log N) operatie. (Insertion in een Fibonacci heap is zelfs O(1), maar dat terzijde). Gemiddeld kom je dus op een complexiteit van O(log N) per element uit. Dat is een aanzienlijk lagere complexiteit. Het volgen van de pointers in een linked list is op zichzelf weliswaar wat goedkoper dan het verwisselen van elementen in een heap tree, maar op de lange termijn verliest de linked list het omdat 1000 elementen langslopen toch echt trager is dan 10 elementen verwisselen (²log(1000) is immers ongeveer 10).

[Verwijderd]

ik ben het wel met Elijan9 eens... De code lijkt in c misschien niet zo veel, maar volgens mij worden die algoritmes wel heel veel machine instructies...

Ik ga voor dit iedee denk ik (lijkt me ook makkelijkste te programmeren)

[.oisyn]

Nou de code voor een priority queue is echt maar een paar regels hoor, en het vertaalt zich niet naar veel machine instructies, Elijan9 heeft in deze ook gewoon ongelijk. Ik krijg meer het idee dat je het niet wilt implementeren omdat je het niet helemaal begrijpt, maar goed, dat is jouw keuze natuurlijk

Maar wel een beetje flauw dat je dan hier om advies komt vragen en dat vervolgens dan gewoon in de wind slaat (ik zal de volgende iig wel uitkijken voor ik een 4 pagina tellende uitleg tik)

[ Voor 9% gewijzigd door .oisyn op 13-05-2004 20:12 ]

[Soultaker]

De helft van de code zit 'm bovendien in bounds checking en reallocaties. Als je de grootte van de heap van te voren vastlegt (op een mooie 2-macht natuurlijk) dan is zowel de push als de pop operatie een regel of 5, 6 aan code. Niet echt schokkend dus, zelfs als je het gaat compileren.

Je oorspronkelijke vraag was of er een handigere methode was dan wat je nu van plan was. Die vraag is beantwoord. Wat je er mee doet, moet je verder zelf maar weten.

[Verwijderd]

Soultaker schreef op 13 mei 2004 @ 20:42:
De helft van de code zit 'm bovendien in bounds checking en reallocaties. Als je de grootte van de heap van te voren vastlegt (op een mooie 2-macht natuurlijk) dan is zowel de push als de pop operatie een regel of 5, 6 aan code. Niet echt schokkend dus, zelfs als je het gaat compileren.

Je oorspronkelijke vraag was of er een handigere methode was dan wat je nu van plan was. Die vraag is beantwoord. Wat je er mee doet, moet je verder zelf maar weten.

Aah de push en pop methodes die niet in c zitten (komen uit c++).

Ik snap de meeste methodes wel ik heb er hier een boek vol mee... Maar ik ben geen programmeur held (ik ben er echt slecht in) en al helemaal niet als het op dit soort dingen aan komt en dus ga ik voor de handige manier waar ik me wel aardig een (programma) beeld van kan vormen...

[Verwijderd]

.oisyn schreef op 13 mei 2004 @ 20:10:
Nou de code voor een priority queue is echt maar een paar regels hoor, en het vertaalt zich niet naar veel machine instructies, Elijan9 heeft in deze ook gewoon ongelijk. Ik krijg meer het idee dat je het niet wilt implementeren omdat je het niet helemaal begrijpt, maar goed, dat is jouw keuze natuurlijk

Maar wel een beetje flauw dat je dan hier om advies komt vragen en dat vervolgens dan gewoon in de wind slaat (ik zal de volgende iig wel uitkijken voor ik een 4 pagina tellende uitleg tik)

nah, vond het wel erg interessant verhaaltje... mss zelfs een keertje bruikbaar voor mij

[Elijan9]

.oisyn schreef op 13 mei 2004 @ 20:10:
Nou de code voor een priority queue is echt maar een paar regels hoor, en het vertaalt zich niet naar veel machine instructies, Elijan9 heeft in deze ook gewoon ongelijk. Ik krijg meer het idee dat je het niet wilt implementeren omdat je het niet helemaal begrijpt, maar goed, dat is jouw keuze natuurlijk

Ik begrijp het eerlijk gezegd dan ook niet zo, ik las toch echt dat je als er iets toegevoegd wordt op positie 24, dat daar dus een allloc (linked list) dan wel realloc (dynamische array) op gedaan moest worden... En als positie 1 klaar is, dan... moet element 1 weer verwijderd worden en moet alles verschoven worden...
Of stel je dit in combinatie met een cyclische buffer voor, dat had ik niet begrepen uit jouw uitleg, de TS mogelijk ook niet, vandaar het misverstand? Kijk dan gaan we praten... Maar data-moves blijven behoorlijk duur op de 8051...

[.oisyn]

Ik zei:

Als er 23 items in de queue staan, dan is positie 1 t/m 23 dan ook gevuld met die elementen. Een nieuw item toevoegen doe je gewoon door 'm op positie 24 te zetten. Vervolgens kijk je naar de parent van [24], [12] dus, en als de prioriteit van [12] lager is dan die van [24] dan wissel je ze om. Vervolgens kijk je naar de parent van [12], [6] dus, en wissel je ze weer om als de prioriteit van [12] hoger is dan die van [6]. Daarna kijk je naar positie [3], en vervolgens naar positie [1]. Als je nieuwe element uiteindelijk op [1] terecht komt betekent dat dus dat ie een prioriteit heeft die hoger is dan de rest van de elementen.

Ik zeg daar niets over allocs. De boom wordt gerepresenteerd door een array. Ik ging er vanuit dat de array langer was dan de 23 elementen die er al in stonden, zodat je niets hoeft te realloceren. Je kunt de array een vaste lengte geven; gezien de toepassing van Blair swift is dat wel te doen. Ander moet je idd realloceren als de array te vol zit, maar zo vaak is dat niet (je gaat natuurlijk niet steeds maar 1 element erbij alloceren, dan ben je dom bezig). Als je array echt goed moet kunnen groeien dan zou je natuurlijk ook een lijst van arrays kunnen gebruiken, waarbij elke array een voorgedefinieerde lengte heeft. Het opvragen van een element kost dan nog steeds O(1), omdat je precies weet in welke array het staat als ze allemaal een vaste lengte hebben. En als je je al je arrays gevuld hebt kun je gemakkelijk een nieuwe aanmaken, zonder dat je de rest hoeft te kopiëren.

Dat verschuiven kost kost maar ²log n, met n het aantal elementen in de boom. Bij 1000 elementen zijn dat dus slechts 10 verschuivingen, zoals Soultaker al aangaf. Als die verschuivingen echt enorm duur zijn kun je er ook nog voor kiezen om een ternaire of quaternaire boom te gebruiken. Bij een quaternaire boom heb je nog maar ⁴log 1000 = 5 verschuivingen nodig, maar wel wat meer compares. En dit heeft niet de vervelende eigenschap dat je maar een klein aantal prioriteiten kunt hebben.

[ Voor 3% gewijzigd door .oisyn op 13-05-2004 23:21 ]

[Verwijderd]

.

[ Voor 100% gewijzigd door Verwijderd op 31-10-2023 22:27 ]

[Elijan9]

.oisyn schreef op 13 mei 2004 @ 23:17:
Ik zeg daar niets over allocs.

Dat was ook mijn punt toch Het idee is perfect, net zoals ik ook het liefst de meest mooie oplossingen zou willen kiezen en de mooiste portable code zou willen schrijven voor een 8051.. Ik ben gewoon heel benieuwd naar de uitvoering, dus wat er gebeurt als taken klaar zijn en/of als er nieuwe bijkomen. Ik vind je voorstel geweldig, maar ik denk niet dat dit een geschikte oplossing is in deze zeer specifieke situatie met de weinige middelen ter beschikking.

De boom wordt gerepresenteerd door een array. Ik ging er vanuit dat de array langer was dan de 23 elementen die er al in stonden, zodat je niets hoeft te realloceren. Je kunt de array een vaste lengte geven; gezien de toepassing van Blair swift is dat wel te doen. Ander moet je idd realloceren als de array te vol zit, maar zo vaak is dat niet (je gaat natuurlijk niet steeds maar 1 element erbij alloceren, dan ben je dom bezig). Als je array echt goed moet kunnen groeien dan zou je natuurlijk ook een lijst van arrays kunnen gebruiken, waarbij elke array een voorgedefinieerde lengte heeft. Het opvragen van een element kost dan nog steeds O(1), omdat je precies weet in welke array het staat als ze allemaal een vaste lengte hebben. En als je je al je arrays gevuld hebt kun je gemakkelijk een nieuwe aanmaken, zonder dat je de rest hoeft te kopiëren.

Dat verschuiven kost kost maar ²log n, met n het aantal elementen in de boom. Bij 1000 elementen zijn dat dus slechts 10 verschuivingen, zoals Soultaker al aangaf. Als die verschuivingen echt enorm duur zijn kun je er ook nog voor kiezen om een ternaire of quaternaire boom te gebruiken. Bij een quaternaire boom heb je nog maar ⁴log 1000 = 5 verschuivingen nodig, maar wel wat meer compares. En dit heeft niet de vervelende eigenschap dat je maar een klein aantal prioriteiten kunt hebben.

Ik voel me dus heel dom, maar ik snap dus nog steeds niet wat jij doet als taak 1 uitgevoerd is. Je noemt groeien, maar hoe zit het met slinken, lees ik daar nu overheen... Gebruik je de buffer circulair, en hoog je de beginpointer op? Je noemt weer dat je een array zou gebruiken - dat nam ik ook al aan, maar gebruik je deze wel of niet circulair, dat vroeg ik me af! Dat maakt dan zeker wel efficient gebruik van de geheugeruimte, alleen ben ik dus bang dat het toevoegen van nieuwe taken wel meer kost dan je er voor terugkrijgt. Vooral omdat juist dat waarschijnlijk interrupt-based is. Ook moet je de prioriteit opslaan bij elk element.
Nogmaals,ik bekritiseer niet de techniek, zeker niet -daar men ik lovend over- ik zet alleen kantekeningen bij de uitvoering voor de 8051. Waar ik mee op de proppen kwam, daar hoef je geen data te verschuiven, alleen pointers te verzetten, misschien kun je toch eens wat C of 8051 asm code laten zien en kunnen anderen oordelen, ik ben blijkbaar niet geloofwaardig genoeg voor je.

Maar misschien zitten we op verschillende golflengten, maar 1000 taken in de queue is voor een 8051 (verschrikkelijk) veel. Ik schat zelf de situatie zo in: ca 4 prioriteisniveaus, hooguit 128 wachtende taken, maar dat is mijn invulling... Maar dat is het kader, waarin ik een optimale oplossing probeer te vinden voor dit probleem.

Mocht je bekend zijn met de 8051, hier wat ideeën:
Begin en eind pointers kun je in het snelle interne idata geheugen stoppen, dan heb je snelle compares om te kijken of een buffer voor een prioriteit leeg is of niet. Vervolgens hoef je maar 1x data uit het xdata geheugen te halen. Daar kun je je buffers namelijk prima neerleggen, omdat je daar alleen maar 1x naar hoeft weg te schrijven voor een nieuw element en 1x vandaan hoeft te lezen voor het ophalen van een element, meer niet, alle berekeningen worden op idata variabelen uitgevoerd..

[Infinitive]

Eigenschap van een heap is (daar praten jullie tenslotte over) dat je tot het één na diepste niveau een propere binaire boom hebt (elke interne node twee kinderen) en op het diepste niveau de nodes van links naar rechts.

Als je die boom implementeerd met een array, zul je dus altijd bij het toevoegen van nieuwe elementen dit aan de achterkant doen. En als je een element eruit haalt, dan doe je een correctiestap waarbij je er dus uiteindelijk ook voor gezorgt hebt dat je aan de achterkant in feite een element weghaalt.

Wanneer je dus een lijst van arrays bijhoud, betekent dit dat je bij het groeien op een gegeven moment een array aan die lijst toevoegt als er niet voldoende ruimte is. En op een gegeven moment gooi je een element weg en zul je merken dat zo'n array niet meer gebruikt wordt en kan je 'm weg gooien.

[Verwijderd]

.

[ Voor 101% gewijzigd door Verwijderd op 31-10-2023 22:28 ]

[Verwijderd]

Elijan9 schreef op 14 mei 2004 @ 10:22:
Ik voel me dus heel dom, maar ik snap dus nog steeds niet wat jij doet als taak 1 uitgevoerd is. Je noemt groeien, maar hoe zit het met slinken, lees ik daar nu overheen... Gebruik je de buffer circulair, en hoog je de beginpointer op? Je noemt weer dat je een array zou gebruiken - dat nam ik ook al aan, maar gebruik je deze wel of niet circulair, dat vroeg ik me af!

Je gebruikt die array als een heap. Dat wil dus zeggen dat je de array niet gebruikt als een (circulaire) buffer en niet als een lijst, maar als een heap. Als je niet weet wat een heap is zou ik daarover zelfstandig wat informatie zoeken want er is al diverse malen uitgelegd wat een heap is maar je begrijpt het blijkbaar niet.

Het voordeel van een heap is dat invoegen en verwijderen sneller gaat dan met een buffer/list. Je zorgen maken dat een heap inefficienter is dan een circulaire buffer toont alleen maar aan dat je het niet begrijpt.

Nogmaals,ik bekritiseer niet de techniek, zeker niet -daar men ik lovend over- ik zet alleen kantekeningen bij de uitvoering voor de 8051. Waar ik mee op de proppen kwam, daar hoef je geen data te verschuiven, alleen pointers te verzetten, misschien kun je toch eens wat C of 8051 asm code laten zien en kunnen anderen oordelen, ik ben blijkbaar niet geloofwaardig genoeg voor je.

Het is meestal voordeliger een paar elementen te verschuiven in plaats van een hele array te doorlopen om de juiste invoegplaats te zoeken.

Samenvattend: een heap gebruikt evenveel opslagcapaciteit als een buffer terwijl invoegen en verwijderen sneller is.

Maar misschien zitten we op verschillende golflengten, maar 1000 taken in de queue is voor een 8051 (verschrikkelijk) veel. Ik schat zelf de situatie zo in: ca 4 prioriteisniveaus, hooguit 128 wachtende taken, maar dat is mijn invulling... Maar dat is het kader, waarin ik een optimale oplossing probeer te vinden voor dit probleem.

Juist, als je de queue organiseert als buffer moet je 128 vergelijkingen doen, organiseer je hem als een heap dan kost het 7 (want 2⁷ = 128) vergelijkingen.

[Soultaker]

Het aantal vergelijkingen is veel lager; je kunt met een binary search (complexiteit O(²log N)) ook met 7 vergelijkingen de invoegplek vinden. Het probleem is echter dat invoegen in een gesorteerde array zo traag is omdat je gemiddeld de halve array een plek moet doorschuiven.

Elementen uit een circulaire buffer halen is gelukkig wel een O(1) operatie, dus als het van kritiek belang is dat razendsnel elementen uit de buffer gehaald moeten worden (ten koste van het veel tragere toevoegen) dan is dat nog wel een geschikte keuze.

Verwijderd schreef op 14 mei 2004 @ 13:18:
Maar nogmaals, als dit de enige plek is waar je de heap gebruikt dan is dat verschrikkelijk inefficient in termen van geheugen gebruik. Het is dan gewoon efficienter om een platte array te gebruiken.

Je hebt daar op zichzelf wel gelijk in, maar dat is niet anders bij het gebruik van een circulaire buffer. Zowel de circulaire gesorteerde buffer van de TS als de heap van .oisyn kunnen in een array gerepresenteerd worden; dat kan een dynamisch gealloceerde array zijn, een statische array met vaste grootte, of een combinatie daarvan zoals Infinitive al voorstelde. De keuze voor de manier waarop die array gealloceerd bepaalt echter niet hoe die array ingericht wordt.

[ Voor 42% gewijzigd door Soultaker op 14-05-2004 14:27 ]

[Elijan9]

Verwijderd schreef op 14 mei 2004 @ 14:12:
Je gebruikt die array als een heap. Dat wil dus zeggen dat je de array niet gebruikt als een (circulaire) buffer en niet als een lijst, maar als een heap. Als je niet weet wat een heap is zou ik daarover zelfstandig wat informatie zoeken want er is al diverse malen uitgelegd wat een heap is maar je begrijpt het blijkbaar niet.

Het voordeel van een heap is dat invoegen en verwijderen sneller gaat dan met een buffer/list. Je zorgen maken dat een heap inefficienter is dan een circulaire buffer toont alleen maar aan dat je het niet begrijpt.

Lekker scheldforum, mijn laatste post nadert snel zo, nog een paar regels te gaan

Ik denk dat je niet zo bekend bent met de 8051, ik zou daar eerst informatie over inwinnen en een beetje spelen met de heap, dan weet je dat een heap ook nadelen kan hebben t.o.v. een statische buffer

Heap ken ik, maar met het memory-management van de 8051 heb ik ook veel ervaring Je geen zorgen maken dat een heap inefficienter is, toont alleen maar aan dat je niet veel begrijpt van de status van 8-bit uC memorymanagement..

Het is meestal voordeliger een paar elementen te verschuiven in plaats van een hele array te doorlopen om de juiste invoegplaats te zoeken.

OMG OMG. Verschuiven is duurder dan niet schuiven, is dat zo moeilijk te geloven? Een circulaire buffer (queue) per prioriteit wil zeggen dat je niet een array hoeft te doorzoeken verder, en dat je ook niet de prioriteit meer hoeft op te slaan.. Waarom heb ik het gevoel dat de meesten maar een kwart lezen, en vier keer oordelen..

Trouwens, ook O(n) en O(logn) kun je niet zondermeer vergelijken als appels! Een beter benadering is dan

Tavg(O1) = Tc_O1
Tavg(On) = Tc_On + Ti_On * n
Tavg(Ologn) = Tc_Ologn + Ti_Ologn * log(n)

En de Tc en de Ti verschillen totaal per methode. Bij grote hoeveelheden is het meteen duidelijk welke insert/zoek/delete totaaloplossing het snelste is. Bij een interruptbased insertion geldt dat het zwaartepunt bij de insert ligt, die moet snel afgehandeld worden.

[.oisyn]

Elijan9 schreef op 14 mei 2004 @ 10:22:
misschien kun je toch eens wat C of 8051 asm code laten zien en kunnen anderen oordelen, ik ben blijkbaar niet geloofwaardig genoeg voor je.

C++:

class PriorityQueue
{
    IntArray heap;
    int heapEnd;

public:
    PriorityQueue ()
    {
        heap.setSize (4);
        heapEnd = 1;
    }

    int pop ()
    {
        if (heapEnd == 1)
            return -1;

        int ret = heap[1];

        int i;
        for (i = 2; i < heapEnd; i *= 2)
        {
            if (heap[i] < heap[i+1])
                heap[i / 2] = heap[i];
            else
                heap[i / 2] = heap[++i];
        }

        if (i < --heapEnd)
            insert (i, heap[heapEnd]);

        if (heapEnd () * 2 < heap.size ())
            heap.decreaseSize ();

        return ret;
    }

    void push (int n)
    {
        if (heapEnd == heap.size ())
            heap.increaseSize ();
        insert (heapEnd++, i);
    }

private:
    void insert (int i, int n)
    {
        while (i >= 1)
        {
            int p = i / 2;
            if (heap[p] >= n)
                break;

            heap[i] = heap[p];
            i = p;
        }

        heap[i] = n;
    }
};

Hoe je die IntArray implementeert mag je natuurlijk helemaal zelf weten, zolang je maar O(1) access hebt

[.oisyn]

Elijan9 schreef op 14 mei 2004 @ 15:20:
[...]

Lekker scheldforum, mijn laatste post nadert snel zo, nog een paar regels te gaan

Ik zie niemand hier schelden Of kun je gewoon niet zo tegen wat fellere discussies?

Anyway, zoals ik eerder al zei, je kunt het aantal verschuivingen verkleinen door meer kinderen per node te nemen (wat natuurlijk wel zorgt voor meer compares per node). Ik beweer niet dat de priority queue sneller zal performen dan een lijst van buckets per prioriteit, maar die laatste is natuurlijk wel heel erg gelimiteerd. Als je met 32 verschillende prioriteiten zit heb je al snel een grote geheugen-footprint. Het aantal prioriteiten voor de priority queue is in principe eindeloos.

En een word of advice: trek het je niet zo aan

[Soultaker]

Als je een klein aantal prioriteiten hebt kun je ook weer overwegen om een linked list per prioriteit te bouwen. Het voordeel daarvan is dat je per data-element alleen een link hoeft op te slaan en geen prioriteit, terwijl het in de heap precies andersom is (wel een prioriteit maar geen link).

Met een beetje gepruts is het ook wel mogelijk om een enkele linked list te bouwen waarin alle elementen achter elkaar zitten (gesorteerd op prioriteit) en waarmee je met behulp van een lookup table (met evenveel entries als prioriteiten) elementen in constante tijd aan kunt toevoegen. Dan hoef je dus niet eens meer alle buffers langs te lopen om een element uit de queue te halen.

[Elijan9]

Een 8 bit processor ondersteunt dan wel geen C++, maar de essentie is duidelijk, maar juist de IntArray implementatie is cruciaal, maar zeker nog wel snel te krijgen...

Foutjes daargelaten, zat ik meer te denken in de richting:

C:

static __xdata job_t    prio0_buffer[PRIO0_SIZE];
static __xdata job_t    prio1_buffer[PRIO1_SIZE];
static __xdata job_t    prio2_buffer[PRIO2_SIZE];
static __xdata job_t    prio3_buffer[PRIO3_SIZE];

typedef struct {
    job_t* begin;
    job_t* end;
    job_t *const buffer;
} priobuf_t;

static __idata priobuf_t prio_buffer[] = {
    [0] = {
        .begin = prio0_buffer,
        .end = prio0_buffer,
        .buffer = prio0_buffer,
    },
    [1] = {
        .begin = prio1_buffer,
        .end = prio1_buffer,
        .buffer = prio1_buffer,
    },
    [2] = {
        .begin = prio2_buffer,
        .end = prio2_buffer,
        .buffer = prio2_buffer,
    },
    [3] = {
        .begin = prio3_buffer,
        .end = prio3_buffer,
        .buffer = prio3_buffer,
    },
};

void process_and_execute()
{
    job_t job_id;

    /* look for priority 3 task */
    if (prio_buffer[3].begin != prio_buffer[3].end)
    {
        /* priority 3 task in queue, select for execution */
        job_id = *prio_buffer[3].begin++;
        
        /* if we crossed the end of our buffer,
           circulate to the beginning of the buffer instead */
        if (prio_buffer[3].begin > &prio_buffer[3].buffer[PRIO3_SIZE-1])
            prio_buffer[3].begin = &prio_buffer[3].buffer[0];
    }
    /* look for priority 2 task */
    else if (prio_buffer[2].begin != prio_buffer[2].end)
    {
        /* priority 2 task in queue, select for execution */
        job_id = *prio_buffer[2].begin++;
        
        /* if we crossed the end of our buffer,
           circulate to the beginning of the buffer instead */
        if (prio_buffer[2].begin > &prio_buffer[2].buffer[PRIO2_SIZE-1])
            prio_buffer[2].begin = &prio_buffer[2].buffer[0];

    }
    /* look for priority 1 task */
    else if (prio_buffer[1].begin != prio_buffer[1].end)
    {
        /* priority 1 task in queue, select for execution */
        job_id = *prio_buffer[1].begin++;
        
        /* if we crossed the end of our buffer,
           circulate to the beginning of the buffer instead */
        if (prio_buffer[1].begin > &prio_buffer[1].buffer[PRIO1_SIZE-1])
            prio_buffer[1].begin = &prio_buffer[1].buffer[0];

    }
    /* look for priority 0 task */
    else if (prio_buffer[0].begin != prio_buffer[0].end)
    {
        /* priority 0 task in queue, select for execution */
        job_id = *prio_buffer[0].begin++;
        
        /* if we crossed the end of our buffer,
           circulate to the beginning of the buffer instead */
        if (prio_buffer[0].begin > &prio_buffer[0].buffer[PRIO0_SIZE-1])
            prio_buffer[0].begin = &prio_buffer[0].buffer[0];

    }
    else
        return;

    execute_job(job_id);
}

void add_job_with_prio(job_t job_id, uint8_t priority)
{
    switch (priority)
    {
    case 0:
        /* push job on the queue */
        *prio_buffer[0].end++ = job_id;

        /* Did we cross the circulair boundary? */
        if (prio_buffer[0].end > &prio_buffer[0].buffer[PRIO0_SIZE-1])
            prio_buffer[0].end = &prio_buffer[0].buffer[0];

        /* buffer full? */
        if (prio_buffer[0].end == prio_buffer[0].begin)
        {
            /* Move first task to next priority */
            add_job_with_prio(*prio_buffer[0].begin,1);
            prio_buffer[0].begin++;
        }

        break;
    case 1:
        /* push job on the queue */
        *prio_buffer[1].end++ = job_id;

        /* Did we cross the circulair boundary? */
        if (prio_buffer[1].end > &prio_buffer[1].buffer[PRIO1_SIZE-1])
            prio_buffer[1].end = &prio_buffer[1].buffer[0];

        /* buffer full? */
        if (prio_buffer[1].end == prio_buffer[1].begin)
        {
            /* Move first task to next priority */
            add_job_with_prio(*prio_buffer[1].begin,2);
            prio_buffer[1].begin++;
        }

        break;
    case 2:
        /* push job on the queue */
        *prio_buffer[2].end++ = job_id;

        /* Did we cross the circulair boundary? */
        if (prio_buffer[2].end > &prio_buffer[2].buffer[PRIO2_SIZE-1])
            prio_buffer[2].end = &prio_buffer[2].buffer[0];

        /* buffer full? */
        if (prio_buffer[2].end == prio_buffer[2].begin)
        {
            /* Move first task to next priority */
            add_job_with_prio(*prio_buffer[2].begin,3);
            prio_buffer[2].begin++;
        }

        break;
    case 3:
        /* push job on the queue */
        *prio_buffer[3].end++ = job_id;

        /* Did we cross the circulair boundary? */
        if (prio_buffer[3].end > &prio_buffer[3].buffer[PRIO3_SIZE-1])
            prio_buffer[3].end = &prio_buffer[3].buffer[0];

        /* buffer full? */
        if (prio_buffer[3].end == prio_buffer[3].begin)
        {
            /* Move first task to next priority */
            add_job_with_prio(*prio_buffer[3].begin,4);

            prio_buffer[3].begin++;
        }

        break;
    default:    /* prio > 3 => execute immediately, only use for emergency matters please! */
        execute_job(job_id);
    }
}

[ Voor 20% gewijzigd door Elijan9 op 15-05-2004 19:55 . Reden: 1 xdata qualifier vergeten, off by one error ]

[Soultaker]

Hoe groot zijn je jobs? Is de overhead van de links klein genoeg om een linked list implementatie te overwegen?

Het grote voordeel van een linked list is dat je een maximum aantal items op de gehele queue alloceert, in plaats van een maximum aantal items per prioriteit.

Verder, is het een vereiste dat een later binnengekomen job ook later wordt verwerkt dan een eerder binnengekomen job met dezelfde prioriteit, of is het alleen van belang dat jobs van lagere prioriteit eerder worden verwerkt dan jobs van hogere prioriteit?

[ Voor 33% gewijzigd door Soultaker op 14-05-2004 16:21 ]

[.oisyn]

Elijan9 schreef op 14 mei 2004 @ 16:12:
Een 8 bit processor ondersteunt dan wel geen C++

elke processor (die C ondersteunt in ieder geval) ondersteunt C++

[ Voor 9% gewijzigd door .oisyn op 14-05-2004 16:25 ]

[Elijan9]

.oisyn schreef op 14 mei 2004 @ 16:23:
[...]


elke processor (die C ondersteunt in ieder geval) ondersteunt C++

Mmm, dat ben ik niet helemaal met je eens, als je maar 64k code kunt gebruiken en je hebt geen hardwarematige exceptie-support, wordt het een onmogelijke opgave om (gecertificeerd) ANSI C++ te ondersteunen... Maar ik was wat voorbarig, er zal vast wel een 8-bitter zijn met excepties en een groot geheugen bereik, al heb ik zelf dan de neiging om zo'n uC voor DSP uit te maken En als zo'n processor niet door de fabrikant al als DSP wordt bestempeld, is dat geen slimme marketing zet..

[Verwijderd]

Elijan9 schreef op 14 mei 2004 @ 15:20:
Lekker scheldforum, mijn laatste post nadert snel zo, nog een paar regels te gaan

Ik scheld niet, ik zeg alleen dat jullie "heap" verkeerd begrijpen. Een heap is niet alleen een geheugengebied waar je (in C) malloc() en free() op kunt loslaten, een heap is ook een partieel geordende datastructuur. Die datastructuur kun je gewoon in een statisch array implementeren; wat dus alle voordelen van die partieele ordening geeft, gecombineerd met alle voordelen van een statisch array.

Heap ken ik, maar met het memory-management van de 8051 heb ik ook veel ervaring Je geen zorgen maken dat een heap inefficienter is, toont alleen maar aan dat je niet veel begrijpt van de status van 8-bit uC memorymanagement..

Nee, je kent "heap" als een partieel geordende datastructuur dus blijkbaar niet, je praat hier n.l. over de alloc/free heap; wij niet.

[ Voor 5% gewijzigd door Verwijderd op 14-05-2004 16:42 ]

[.oisyn]

Elijan9 schreef op 14 mei 2004 @ 16:37:
[...]

Mmm, dat ben ik niet helemaal met je eens, als je maar 64k code kunt gebruiken en je hebt geen hardwarematige exceptie-support, wordt het een onmogelijke opgave om (gecertificeerd) ANSI C++ te ondersteunen...

Even afgezien van de standaard library van ISO C++ (die je net zo goed niet hebt op die platformen voor C) kun je prima de volledige taalset van C++ gebruiken. Die 64k is slechts een limitatie van je hoeveelheid code, niet van de taal. En waar heb je hardware exceptions voor nodig?

[Elijan9]

.oisyn schreef op 14 mei 2004 @ 16:48:
Even afgezien van de standaard library van ISO C++ (die je net zo goed niet hebt op die platformen voor C) kun je prima de volledige taalset van C++ gebruiken. Die 64k is slechts een limitatie van je hoeveelheid code, niet van de taal. En waar heb je hardware exceptions voor nodig?

Voor certificatie Programmeertools voor 8-bitters zijn o.h.a. wel volledig C99 gecertificeerd..

@mietje
Ik zie een heap toch meer als een queue, de tegenpool van de stack, zo heb ik het altijd geleerd al zolang als ik in C programmeer voor uC. Vooral omdat je die heap vaak tegenkomt, is het gewoon niet handig meerdere dingen dezelfde naam te geven (voor mij).

Maar ik dacht dat een heap iets is wat onder water geimplementeerd kan worden op allerlei manieren, manieren die hier genoemd zijn of desnoods als twee stacks . Volgens mij is dat een dialect verschil tussen C en C++ programmeurs. Wat jij aanduidde als heap, zou ik dus gewoon "partieel geordende datastructuur" noemen, ik ken het maar ik legde niet direct de connectie met heap.

[.oisyn]

Elijan9 schreef op 14 mei 2004 @ 17:19:
[...]

Voor certificatie Programmeertools voor 8-bitters zijn o.h.a. wel volledig C99 gecertificeerd..

En er zijn zat compilers die C++ code naar ISO C kunnen compileren, waardoor die C++ code dus net zo goed draait op die 8-bitters

[Verwijderd]

Elijan9 schreef op 14 mei 2004 @ 17:19:
Maar ik dacht dat een heap iets is wat onder water geimplementeerd kan worden op allerlei manieren, manieren die hier genoemd zijn of desnoods als twee stacks . Volgens mij is dat een dialect verschil tussen C en C++ programmeurs. Wat jij aanduidde als heap, zou ik dus gewoon "partieel geordende datastructuur" noemen, ik ken het maar ik legde niet direct de connectie met heap.

Partieel geordend wil zeggen dat de datastructuur uit geordende deelverzamelingen bestaat; dat kan op velerlei manieren. De heap waar wij op doelen is daar een van; en is overigens bekend buiten C en C++, het bekende heapsort werkt door het ongeordende array te veranderen in een heap en vervolgens herhaaldelijk het grootste element van die heap te poppen en achteraan de heap terug te plaatsen. Dit lijkt een even naieve oplossing als bubblesort, maar omdat poppen van een heap slechts O(₂log n) kost, kost heapsort (altijd, niet gemiddeld) O(n ₂log n) tegen bubblesort O(n²).

[ Voor 5% gewijzigd door Verwijderd op 14-05-2004 18:22 . Reden: heapsort verduidelijkt (voor er commentaar komt) ]

[Infinitive]

Partieel geordend wil zeggen dat de datastructuur uit geordende deelverzamelingen bestaat; dat kan op velerlei manieren. De heap waar wij op doelen is daar een van;

Ter aanvullig: als je de heap ziet als een boom (geïmplementeerd al dan niet met een array), dan is elk pad in die boom zo'n geordende deelverzameling (met lengte ten hooste log2(n)).

[Elijan9]

.oisyn schreef op 14 mei 2004 @ 15:29:

C++:

class PriorityQueue
{
    ...
};

Hoe je die IntArray implementeert mag je natuurlijk helemaal zelf weten, zolang je maar O(1) access hebt

Zoals je code eigenlijk al laat zien, is (vooral) de pop implementatie hier behoorlijk duur voor de 8051, aangezien er veel moves plaats vinden van en naar de IntArray "heap", die hoe dan ook in het xdata memory gebied terecht moet komen. Misschien is het het beste om het zo te zien: de 8051 heeft een paar registers en beetje interne data, maar vooral xdata, en ik zal dit maar vergelijken met het ongebufferd lezen en schrijven naar een harddisk...
Je heap zal niet passen in het snelle geheugen, en elke lees en schrijfoperatie haalt je performance naar beneden.. Misschien dat de sceptici dan snappen waarom de TS en ik niet in deze omkaderde situatie (vergeet dat niet, ik werk ook met uC waar ik het juist wel zo zou doen!) niet direcht warm lopen voor een binaire boomstructuur..

Soultaker schreef op 14 mei 2004 @ 16:20:
Hoe groot zijn je jobs? Is de overhead van de links klein genoeg om een linked list implementatie te overwegen?

Het grote voordeel van een linked list is dat je een maximum aantal items op de gehele queue alloceert, in plaats van een maximum aantal items per prioriteit.

Verder, is het een vereiste dat een later binnengekomen job ook later wordt verwerkt dan een eerder binnengekomen job met dezelfde prioriteit, of is het alleen van belang dat jobs van lagere prioriteit eerder worden verwerkt dan jobs van hogere prioriteit?

Ik kan niet namens de TS spreken, maar ik heb zelf in mijn voorbeeld 5 prioriteiten verwerkt en kan me niet voorstellen dat dat niet genoeg is.

Als de job-id's gewoon 8 bit zijn, dan zou een linked list met alleen een next pointer als extra argument al 3 xdata byte moves kosten i.p.v. 1, die twee extra reads moeten hun waarde dan nog wel bewijzen..

En een priority queue is volgens mij geen queue als de jobs van gelijke prioriteit niet op binnenkomende volgorde worden uitgevoerd... (misschien mijn mening, maar als ik als een reeks commando's stuur, moeten deze meestal ook op die volgorde uitgevoerd worden, en anders manipuleer ik met de prioriteiten...)

[ Voor 5% gewijzigd door Elijan9 op 14-05-2004 20:27 ]

[Verwijderd]

Elijan9 schreef op 14 mei 2004 @ 20:22:
Je heap zal niet passen in het snelle geheugen, en elke lees en schrijfoperatie haalt je performance naar beneden.. Misschien dat de sceptici dan snappen waarom de TS en ik niet in deze omkaderde situatie (vergeet dat niet, ik werk ook met uC waar ik het juist wel zo zou doen!) niet direcht warm lopen voor een binaire boomstructuur..

Waarom past een array die je als circular buffer gebruikt wel in het snelle geheugen maar een precies even grote array die je als heap gebruikt niet? Zoals al meermaals uitgelegd behandel je een array als een binaire boom en hoef je geen pointers of indexen van child-nodes op te slaan, omdat je de index van de child-nodes eenvoudig berekenen kunt: een node met index n heeft child-nodes met indexen 2n+1 en 2n+2.

Uiteraard zijn er ook snellere O(1) methodes om te schedulen dan met een heap (en die werken inderdaad meestal met een klein aantal priorities), maar zodra als je een lineaire list of array moet doorzoeken heb je verloren t.o.v de heap, tenzij een schrijf-operatie een orde van grootte duurder is dan een lees-operatie. (In ons voorbeeld moeten 6 schrijf-operaties meer kosten dan 121 lees-operaties, dus zeg minimaal 20x zo duur zijn om de heap te laten verliezen; hoe groter de de heap wordt, hoe gunstiger hij afsteekt tegen lineaire implementaties.)

[Elijan9]

Verwijderd schreef op 14 mei 2004 @ 21:44:
Waarom past een array die je als circular buffer gebruikt wel in het snelle geheugen maar een precies even grote array die je als heap gebruikt niet?

Als je iets beter dit topic had doorgelezen, dan had je geweten dat ik voorstelde de pointers in het snelle geheugen neer te leggen, ookal ligt de circulaire buffers daar niet. En dat een "push" dus maar 1 write naar xdata doet, en de "pop" maar 1 read vanuit xdata, de rest gebeurt met de pointers in direct adresseerbaar geheugen en met constanten..

[Verwijderd]

Elijan9 schreef op 15 mei 2004 @ 00:10:
Als je iets beter dit topic had doorgelezen, dan had je geweten dat ik voorstelde de pointers in het snelle geheugen neer te leggen, ookal ligt de circulaire buffers daar niet. En dat een "push" dus maar 1 write naar xdata doet, en de "pop" maar 1 read vanuit xdata, de rest gebeurt met de pointers in direct adresseerbaar geheugen en met constanten..

Dat moet ik dus in principe opmaken uit "__xdata" in dat stuk code, maar goed. Het probleem van jouw algoritme heeft .oisyn al beschreven, zo lang als je maar een klein aantal priorities hebt merk je het niet echt dat je telkens een lineaire lijst (van circular buffers) bent aan het doorlopen, maar met 32 of 64 priorities is het opeens niet meer zo fris; bij 256 priorities wint de heap gemakkelijk (en is daarbij ook nog eens geheugenefficienter).

offtopic:
Goed he, helemaal zonder hamertjes of muurtjes.

[Elijan9]

Elijan9 schreef op 14 mei 2004 @ 10:22:
...

Begin en eind pointers kun je in het snelle interne idata geheugen stoppen, dan heb je snelle compares om te kijken of een buffer voor een prioriteit leeg is of niet. Vervolgens hoef je maar 1x data uit het xdata geheugen te halen. Daar kun je je buffers namelijk prima neerleggen, omdat je daar alleen maar 1x naar hoeft weg te schrijven voor een nieuw element en 1x vandaan hoeft te lezen voor het ophalen van een element, meer niet, alle berekeningen worden op idata variabelen uitgevoerd..

Verwijderd schreef op 15 mei 2004 @ 07:46:
[...]


Dat moet ik dus in principe opmaken uit "__xdata" in dat stuk code, maar goed.

Nog even hierboven gekopieerd, daar stond dat dus al, was een reply op jou... En ik hoef geen lineaire lijst door te lopen. Voor een pop hoef ik alleen het eerstvolgende element van de queue met de hoogste prioriteit die niet leeg is weg te halen => Zoektijd O(1). Voor de push hoef ik alleen een switch te maken op prioriteit, waarna de het nieuwe element direct in de queue wordt gezet, ook O(1). Mijn code is afgezien van de __idata en __xdata memory qualifiers gewoon C, ik neem toch aan dat je er wel mee uit de voeten zou moeten kunnen..

Nogmaals, met dingen aankomen als 32, 64 of zelfs 256 prioriteiten heeft geen zin, ik heb al duidelijk gemaakt in welk kader je zou moeten denken voor een 8051 met al zijn beperkingen, en dat ook ik een andere aanpak zou gebruiken als het niet om een 8051 ging. En ik heb nog een klein (tricky) truckje uit de kast gehaald voor extra geheugen efficiëntie, heeft wel weer een klein (vaak niet schadelijk) bijeffect.

offtopic:
Misschien snap je dat niet, maar ik word een beetje gek van iets wat ruikt naar eigendunk en neerkijken. Waarschijnlijk is het enige grote verschil tussen onze werkterein en expertise dat ik met bytes rekening moet houden en jij nog niet eens met megabytes. Misschien is dat al genoeg reden voor jou, maar ik denk dat we niet veel verschillen kwa niveau. Ik programmeer voor DSPs en microcontrollers, schrijf de volledige besturinging van embedded devices met zo efficient mogelijke code vaak helemaal alleen, terwijl jij dagelijks -waarschijnlijk- met hele andere problematieken bezig bent. Mijn werk bestaat waarschijnlijk voor zo'n 80% uit het afstemmen op de gebruikte compiler en hardware, waarschijnlijk heb jij alles voor handen, mocht de hardware tekort schieten, dan worden de eisen veranderd. Mijn gepostte code is voor een 8051 microcontroller op zijn minst overzichtelijk en praktisch te noemen, je zou eens moeten controlleren hoe weinig operaties er gedaan worden terwijl het toch meer dan afdoende is voor de meest uiteenlopende toepassingen, zonder ook maar 1 regel assembly. Ik weet niet zo goed waarom ik me zo moet zitten verdedigen, probeer te begrijpen dat voor andere werkterreinen ook andere regels kunnen (gaan) gelden. Probeer dus liever niet over te komen als een club jehova's getuigen of een Idols jury, GoT had die reputatie een paar jaar terug ook al.

[ Voor 1% gewijzigd door Elijan9 op 15-05-2004 16:30 . Reden: typfout ]

[Verwijderd]

Elijan9 schreef op 15 mei 2004 @ 16:29:
En ik hoef geen lineaire lijst door te lopen. Voor een pop hoef ik alleen het eerstvolgende element van de queue met de hoogste prioriteit die niet leeg is weg te halen => Zoektijd O(1).

Je doorloopt dus een lijst van queues van de hoogste tot de laagste prioriteit...

Nogmaals, met dingen aankomen als 32, 64 of zelfs 256 prioriteiten heeft geen zin, ik heb al duidelijk gemaakt in welk kader je zou moeten denken voor een 8051 met al zijn beperkingen, en dat ook ik een andere aanpak zou gebruiken als het niet om een 8051 ging.

Ik mag dan wel geen 8051 geprogrammeerd hebben, ik heb in het verleden wel drivers voor IO-channels geprogrammeerd (in assembly) en heb dus een redelijk idee van de beperkingen die specifieke architecturen kunnen opleggen, maar ik begrijp niet waarom 4 priorities een heilige wet is als scheduling niet hardwarematig opgelost is. Het enige dat ik hierover nog wil zeggen is dat zelfs op beperkte architecturen een efficiënt algoritme brute kracht verslaat als de dataset maar groot genoeg is.

[Verwijderd]

Verwijderd schreef op 15 mei 2004 @ 17:15:Het enige dat ik hierover nog wil zeggen is dat zelfs op beperkte architecturen een efficiënt algoritme brute kracht verslaat als de dataset maar groot genoeg is.

Dit is natuurlijk precies waar het over gaat... een O(n lg n) algoritme zal vanaf een bepaalde van n altijd sneller zijn dan bijv. een O(n^2) algoritme. Als je echter zeker weet dat n nooit groter wordt dan een bepaalde (kleine) waarde, en je ook nog eens met een architectuur te maken hebt waar je niet zomaar de ene na de andere megabyte kan alloceren, kan de O(n^2) wel eens sneller zijn. Dit zie je bijvoorbeeld terug in veel quicksort implementaties, waar subarrays die onder een bepaalde lengte zitten met een insertion sort gesorteerd worden, terwijl insertion sort toch O(n^2) is.

[Elijan9]

Verwijderd schreef op 15 mei 2004 @ 17:15:
Je doorloopt dus een lijst van queues van de hoogste tot de laagste prioriteit...

Akkoord, maar dus een lijst met de grootte van het aantal prioriteiten, niet het aantal jobs. Het is natuurlijk nog beter om 1 extra byte te alloceren die de hoogste prioriteit aangeeft met een niet-lege queue, die is makkelijker te missen dan een hoop moves, en de pop-code wordt er in totaliteit kleiner van.

En mijn mening blijft liggen dat het er maar aan ligt hoe en op welke manier een architectuur beperkt is en of de dataset binnen die beperkingen nog wel groot genoeg kan worden om een theoretisch beter algoritme ook sneller te laten zijn..

4 prioriteiten is geen wet voor de 8051, (ik gebruik er 5), maar voor een priority queue voor de 8051 is het weinig realistisch om rekening te gaan houden met 32 of meer proriteiten, zo heel veel verschillende taken kan deze processor toch waarschijnlijk niet uitvoeren binnen een tijdsbestek. Verder is er nog de timer en uart-interrupt en nog een paar handige interrupts die ook erg prettig werken voor bepaalde taken (running led, keyscan).

[Verwijderd]

.

[ Voor 99% gewijzigd door Verwijderd op 31-10-2023 22:28 ]