Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie
Toon posts:

[C] Correcte implementatie van periodieke functies

Pagina: 1
Acties:

  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
In mijn C applicatie maak ik gebruik van een threadpool om met een beperkt aantal threads mijn functies af te handelen. Nu werken veel van die functies op basis van events. Echter zijn er ook functies die periodiek dienen plaats te vinden. De vraag is hoe je dit nu het beste implementeert. Er kunnen tientallen periodieke functies tegelijk aan het wachten zijn op uitvoering. Voorbeelden zijn:
- Elke drie seconden een cpu/ram gebruik opvraging.
- Elke zonsopgang / zonsondergang een event.
- Elke 24 uur een ntp-sync
- Elk uur een API aanvraag.
- Communiceren van de tijd via een klok functie.

Deze functies moeten ook afgehandeld worden door de threadpool. Nu heb ik dit op twee manieren proberen op te lossen van welke ik beide ontevreden was. In beide manieren stond dit stukje pseudocode centraal:
code:
1
2
3
4
5
func teller() {
    tik elke (milli)seconde (of wordt elke (milli)second aangeroepen)
    loop door periode threads
        als voldoende seconde gepasseerd, voer thread aan threadpool
}


De time-based threads registreren zich in dit voorbeeld in een pool welke elke (milli)seconde doorgelopen wordt om te zien om er al voldoende tijd is verstreken om de functie uit te voeren. Nu heb ik deze functie dus op twee manieren proberen te integreren:

1. Voer de teller elke (milli)seconde uit vanuit een timer. Probleem is dat dit niet veilig is qua deadlocks. De timer wacht namelijk niet totdat de functie klaar is voordat hij opnieuw wordt aangeroepen.
2. Start een aparte thread met een loop welke elke seconde alle functies nagaat. Probleem hier is dat de evaluatie tijd teveel lacency teweeg brengt waardoor ik uiteindelijk (milli)seconden mis in mijn klok.

Ik zoek dus naar een manier om deze functionaliteit goed in te bedden in mijn bestaande threadpool structuur, maar wel met een hoge betrouwbaarheid, accuraatheid en snelheid. Idealiter behaal ik een resolutie van 1 milliseconde.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • Sissors
  • Registratie: mei 2005
  • Nu online
Lijkt mij dat je wil dat alleen je timer functie wordt aangeroepen als hij daadwerkelijk iets moet doen, niet om te kijken of hij mogelijk iets zou moeten doen.

Gebaseerd op: https://github.com/mbedmi.../mbed/common/ticker_api.c

Je wilt een lijst met volgende tijden hebben dat iets moet gebeuren (kan zowel enkel lijst met tijden zijn, of gewoon loopen door de threads en aan elke vragen wanneer de volgende keer is dat hij wil plaatsvinden). Pak die tijd, trek huidige tijd ervanaf, en over zoveel (milli) seconde moet die functie worden uitgevoerd, dus je kan een timer achtig iets aanzetten die over zoveel tijd je een zeintje geeft. Afhankelijk van hoe je het precies implementeert moet je iig elke keer als je een nieuw iets eraan toevoegt opnieuw gekeken worden wanneer de eerstvolgende functie moet worden uitgevoerd. En mogelijk ook als je laatste functie is uitgevoerd kijken wanneer de volgende is. (In dat voorbeeld dat ik linkte gebruiken ze een gesorteerde linked list, waardoor je voor de volgende uit te voeren functie altijd de eerste uit je linked list kan gebruiken).

  • Soultaker
  • Registratie: september 2000
  • Laatst online: 30-09 21:44
Ik ben het met sissors eens: je moet je callbacks in een datastructuur opslaan die bijhoudt wanneer de eerstvolgende uitgevoerd moet worden. Dat kan met een sorted set of een priority queue of iets dergelijks.

Bedenk wel dat het mogelijk is dat een nieuwe callback toegevoegd wordt met een timeout vóór het eerste element in de queue. In dat geval moet je de scheduler kunnen onderbreken, zodat die niet blijft slapen.

Hoe het slapen/onderbreken precies werkt is systeem-afhankelijk.

PGP public key


  • farlane
  • Registratie: maart 2000
  • Laatst online: 11:47
Begrijp ik het goed: je scheduler functie duurt langer dan de tick van je scheduler?

Somniferous whisperings of scarlet fields. Sleep calling me and in my dreams i wander. My reality is abandoned (I traverse afar). Not a care if I never everwake.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
farlane schreef op woensdag 09 december 2015 @ 11:37:
Begrijp ik het goed: je scheduler functie duurt langer dan de tick van je scheduler?
In de huidige implementatie wel, vandaar dat ik ook tot de conclusie kwam dat het zo niet werkt :)

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • jeroen3
  • Registratie: mei 2010
  • Laatst online: 15:56
Laat elke taak een systeemtijd retourneren via een api wanneer de taak weer gewekt wil worden.
Systeemtijd kan een eigen tijdseenheid zijn (ms sinds start), of de unix timestamp (met milliseconden, in 64 bit).

In je scheduler hoef je alleen via een linked list de eerste te zoeken, met de hoogste prioriteit. De thread een signal te geven (reden van uitvoeren: trhead api, signal stop, user event).
Duurt dit zoeken langer dan 1ms, dan is je cpu is te traag, of je specificaties te strak.
Of je hebt teveel taken, in dan geval moet je misschien een tickless scheduler maken.

Menig (embedded real-time) operating system werkt zo. Kijk het anders af van ChibiOS.

  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Sissors schreef op woensdag 09 december 2015 @ 09:32:
Lijkt mij dat je wil dat alleen je timer functie wordt aangeroepen als hij daadwerkelijk iets moet doen, niet om te kijken of hij mogelijk iets zou moeten doen.
Zo simpel kan het zijn |:(

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • MSalters
  • Registratie: juni 2001
  • Laatst online: 11:45
jeroen3 schreef op woensdag 09 december 2015 @ 11:45:
In je scheduler hoef je alleen via een linked list de eerste te zoeken, met de hoogste prioriteit. De thread een signal te geven (reden van uitvoeren: trhead api, signal stop, user event).
Duurt dit zoeken langer dan 1ms, dan is je cpu is te traag, of je specificaties te strak ...
of je datastructuur verkeerd. Dit is een standaard situatie waarin je een priority queue gebruikt, geen linked list.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
MSalters schreef op donderdag 10 december 2015 @ 23:56:
[...]

of je datastructuur verkeerd. Dit is een standaard situatie waarin je een priority queue gebruikt, geen linked list.
Of een sorted linked list? Waarin dus de eerste elementen altijd het eerste uitgevoerd dienen te worden.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Een eerste opzet gemaakt, maar een milliseconde resolutie halen is toch lastiger dan gedacht.

(Getallen in nanoseconde zoals de invoer van itimerspec)
C:
1
2
3
4
5
6
7
8
9
10
11
timer_add_task(timer, "a", 2000, printtime);
timer_add_task(timer, "b", 1000, printtime);
timer_add_task(timer, "c", 3000, printtime);
timer_add_task(timer, "d", 1000, printtime);
timer_add_task(timer, "e", 3000, printtime);
timer_add_task(timer, "f", 4000, printtime);
timer_add_task(timer, "g", 5000, printtime);
timer_add_task(timer, "h", 6000, printtime);
timer_add_task(timer, "i", 7000, printtime);
timer_add_task(timer, "j", 8000, printtime);
timer_add_task(timer, "k", 9000, printtime);


De printtime functie bestaat uit niks meer dan het printen van de tijd.

De uitvoer van dit alles:
code:
1
2
3
4
5
6
7
8
9
10
11
d 2015:12:11 16:41:19.525209
b 2015:12:11 16:41:19.525214
a 2015:12:11 16:41:19.527219
e 2015:12:11 16:41:19.529204
c 2015:12:11 16:41:19.529208
f 2015:12:11 16:41:19.531217
g 2015:12:11 16:41:19.533224
h 2015:12:11 16:41:19.535215
i 2015:12:11 16:41:19.537216
j 2015:12:11 16:41:19.539207
k 2015:12:11 16:41:19.541221

Probleem is dus dat de resolutie blijft steken op +/- 2 milliseconde. Zelfs als ik het geheel op nanosecondes wil laten uitvoeren, dan blijft de overhead toch 2 milliseconde.

De aanpak die ik nu heb gekozen.
1. Initieer een timer.
2. Voeg een taak toe aan de timer pool in een sorted linked list.

3. Alle taken van 1 milliseconde worden uitgevoerd.
4. Van alle overige taken wordt nu 1 milliseconde afgetrokken (het is immers een sorted linked list).
5. De timer wordt gezet op de delay van de eerste taak en stap 3, 4, en 5 worden herhaald totdat de taken op zijn of er nieuwe taken worden toegevoegd.



De overhead lijkt te zitten in timer_settime. Als ik gewoon een loop maak tussen timer_settime -> callback -> timer_settime -> callback -> enz. dan haal ik nog geen hogere resolutie dan 2 milliseconde.

[Voor 5% gewijzigd door CurlyMo op 11-12-2015 17:31]

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 15:45

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

CurlyMo schreef op vrijdag 11 december 2015 @ 17:07:
Probleem is dus dat de resolutie blijft steken op +/- 2 milliseconde. Zelfs als ik het geheel op nanosecondes wil laten uitvoeren, dan blijft de overhead toch 2 milliseconde.
Hou er rekening mee dat printen naar console best veel overhead met zich mee kan brengen.
De aanpak die ik nu heb gekozen.
1. Initieer een timer.
2. Voeg een taak toe aan de timer pool in een sorted linked list.

3. Alle taken van 1 milliseconde worden uitgevoerd.
4. Van alle overige taken wordt nu 1 milliseconde afgetrokken (het is immers een sorted linked list).
5. De timer wordt gezet op de delay van de eerste taak en stap 3, 4, en 5 worden herhaald totdat de taken op zijn of er nieuwe taken worden toegevoegd.
Dat zou ik anders implementeren. Waarom overal tijd vanaf trekken, als je in plaats daarvan ook net zo goed kunt opslaan wanneer ze moeten optreden (ipv hoe lang het nog duurt, wat ook nog eens cumulatieve rekenfouten met zich mee gaat brengen)? Op het moment dat je iets wilt schedulen voor "over 3 milliseconden", dan pak je gewoon huidige tijd + 3 ms.
De overhead lijkt te zitten in timer_settime. Als ik gewoon een loop maak tussen timer_settime -> callback -> timer_settime -> callback -> enz. dan haal ik nog geen hogere resolutie dan 2 milliseconde.
Hoeft niet per se overhead te zijn, maar kan ook gewoon te maken hebben met de granulariteit van de timer. Als je echt milliseconde-precisie timings wilt hebben dan zul je sowieso al snel moeten overstappen op een realtime OS.

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • farlane
  • Registratie: maart 2000
  • Laatst online: 11:47
Welk platform hebben we het hier over eigenlijk? Je post impliceert Posix (Linux?), maar om een ms resolutie te halen zal je wel een RT versie moeten hebben .....

[edit]
Wat .oisyn zegt dus...

[Voor 12% gewijzigd door farlane op 11-12-2015 17:49]

Somniferous whisperings of scarlet fields. Sleep calling me and in my dreams i wander. My reality is abandoned (I traverse afar). Not a care if I never everwake.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Inderdaad een Posix Linux / FreeBSD. Ik dacht dat ms nog wel haalbaar zou moeten zijn.

Ik ga het een en ander eens anders proberen te doen en kijken welke resolutie dan haalbaar is.



Aanvullend op mijn timer_settime overhead opmerking. Als ik de timer interval op 1 milliseconde zet dan is hij heerlijk precies. De timer zelf kan het dus wel. De overhead zit er dan toch op een of andere manier in het updaten van de timer_settime.

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2015:12:11 18:35:48.290631
2015:12:11 18:35:48.291683
2015:12:11 18:35:48.292674
2015:12:11 18:35:48.293666
2015:12:11 18:35:48.294655
2015:12:11 18:35:48.296747
2015:12:11 18:35:48.297654
2015:12:11 18:35:48.298633
2015:12:11 18:35:48.299657
2015:12:11 18:35:48.300656
2015:12:11 18:35:48.301653
2015:12:11 18:35:48.302633
2015:12:11 18:35:48.303650
2015:12:11 18:35:48.304687
2015:12:11 18:35:48.305632
2015:12:11 18:35:48.306687

[Voor 66% gewijzigd door CurlyMo op 11-12-2015 18:37]

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • MSalters
  • Registratie: juni 2001
  • Laatst online: 11:45
CurlyMo schreef op vrijdag 11 december 2015 @ 09:44:
[...]
Of een sorted linked list? Waarin dus de eerste elementen altijd het eerste uitgevoerd dienen te worden.
Nogal duur om die sorted te houden. Insertion is O(N).

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Ander probleem wat ik al voorzag (via de threadpool uiteindelijk en met een iets ander doen dan louter printer :) ):
code:
1
2
3
4
5
2015:12:11 20:16:03.962865
2015:12:11 20:16:04.989180
2015:12:11 20:16:06.981
2015:12:11 20:16:07.19182
2015:12:11 20:16:08.21476


Een van de eisen is het printen van een klok. Echter mag deze klok geen secondes missen zoals je hier ziet. Dat gebeurt dus wel in de timer_settime > callback > timer_settime methode. Is dan de enige optie een dedicated timer gebruiken met een interval van 1 seconde?

Nu ook bezig met het omzetten naar de TIMER_ABSTIME. Lijkt inderdaad makkelijker.

[Voor 7% gewijzigd door CurlyMo op 11-12-2015 20:47]

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • farlane
  • Registratie: maart 2000
  • Laatst online: 11:47
Wat je ook probeert, het systeem zal er niet realtime door worden : vroeg of laat besluit je OS dat er iets anders belangrijker is.
Als je het doet doe het dan goed en neem een realtime systeem. Je zou (als je Linux gebruikt) eens kunnen kijken of de preempt-rt patch wat voor je kan betekenen.

[Voor 3% gewijzigd door farlane op 11-12-2015 20:53]

Somniferous whisperings of scarlet fields. Sleep calling me and in my dreams i wander. My reality is abandoned (I traverse afar). Not a care if I never everwake.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Ik kan me gewoon moeilijk voorstellen dat iets als het printen van een klok niet op ieder regulier OS stabiel zou moeten kunnen. Millisecondes als te hoge resolutie geloof ik wel. Ik kan er ook mee leven dat ik geen 100% garantie heb bij een klok, maar 99% zou toch moeten lukken met wanneer nodig een dedicated timer met een interval?

Het doel is uiteindelijk dat gebruikers deze regels kunnen maken (wat nu op zich goed werkt, maar dan op een niet houdbare manier met tientallen threads):
code:
1
IF datetime.seconds == 0 THEN ...

Dit mag desnoods ook best dit zijn:
code:
1
IF datetime.seconds == 0 OR datetime.second == 1 THEN ...

Moet toch kunnen?

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • Matis
  • Registratie: januari 2007
  • Laatst online: 16:02

Matis

Rubber Rocket

Als je realtime gedrag wilt, zul je een RTOS, bijvoorbeeld QNX (Linux) of ChibiOS moeten nemen.
Wanneer wij binnen onze embedded platformen zekerheid willen dat iets op gezette tijden gebeurt en dat het ook altijd even lang duurt, nemen we een FPGA of DSP.
Binnen een multithreaded OS kun je geen realtime gedrag eisen. Zelf met RT patches, blijf je afhankelijk van de kwaliteiten van de programmeur en de duur van je event handlers.

If money talks then I'm a mime
If time is money then I'm out of time


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Ik kom er net achter dat ik helemaal in de verkeerde unit aan het denken ben.

2000 voeren aan itimerspec betekend helemaal geen 2 milliseconde, maar 2 microseconde 8)7 Ik krijg dus geen microseconde resolutie, maar dat is ook helemaal niet nodig. Ik wil milliseconde resolutie, dus 2000000 nanoseconden. Dat werkt dus wel betrouwbaar genoeg :)

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • farlane
  • Registratie: maart 2000
  • Laatst online: 11:47
Dat werkt dus wel betrouwbaar genoeg :)
Strekking van het verhaal blijft hetzelfde: als het geen realtime OS is, heb je geen enkele garantie.
Matis schreef op vrijdag 11 december 2015 @ 23:51:
Binnen een multithreaded OS kun je geen realtime gedrag eisen.
Tuurlijk kun je dat wel eisen: QNX, ChibiOS en ook bv FreeRTOS zijn multithreaded realtime OSen.
Zelf met RT patches, blijf je afhankelijk van de kwaliteiten van de programmeur en de duur van je event handlers.
Dat blijf je altijd, ook op een realtime OS, ook als je het in hardware doet.

[Voor 14% gewijzigd door farlane op 12-12-2015 19:04]

Somniferous whisperings of scarlet fields. Sleep calling me and in my dreams i wander. My reality is abandoned (I traverse afar). Not a care if I never everwake.


  • Sissors
  • Registratie: mei 2005
  • Nu online
MSalters schreef op vrijdag 11 december 2015 @ 19:41:
[...]

Nogal duur om die sorted te houden. Insertion is O(N).
Waarbij in zulk soort situatie N ruwweg 10 ofzo zal zijn, oftewel enorm goedkoop. Het lijkt me ook niet dat je met een priority queue veel opschiet, je wilt gewoon de tijd hebben wanneer je volgende timer event moet plaatsvinden.

  • Gomez12
  • Registratie: maart 2001
  • Laatst online: 14:22
Sissors schreef op zondag 13 december 2015 @ 09:31:
[...]

Waarbij in zulk soort situatie N ruwweg 10 ofzo zal zijn, oftewel enorm goedkoop.
Let er met dat soort overwegingen wel goed op dat je alles monitored en logged etc.

Het zou niet de eerste keer zijn dat ik een situatie zie ontstaan waar er 11 per seconde binnenkomen en er maar 10 uitgaan en dat net zolang tot er een paar miljard in de queue staan na een paar dagen en dan zie je je systeem langzaam omvallen omdat sorted list sorteren steeds zwaarder wordt en aan het eind van de rit wel eens richting 100% cpu kan gaan.

  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Hier hebben inderdaad alle linked lists een maximale toegestane lengte welke normaal gesproken nooit gehaald mag worden.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 15:45

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

Sissors schreef op zondag 13 december 2015 @ 09:31:
Het lijkt me ook niet dat je met een priority queue veel opschiet, je wilt gewoon de tijd hebben wanneer je volgende timer event moet plaatsvinden.
Waarom zou dat niet opschieten met een priority queue? Het eerstvolgende event staat vooraan in de queue

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
.oisyn schreef op zondag 13 december 2015 @ 21:06:
[...]

Waarom zou dat niet opschieten met een priority queue? Het eerstvolgende event staat vooraan in de queue
Het doel is toch gewoon het voorsorteren van taken? Of dat nu via een gesorteerde linked list is of via een priority queue. Op dit moment heb ik (nog) geen aanwijzingen dat de linked list een bottleneck is.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 15:45

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

Lees nog eens goed waar ik op reageer :)

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
.oisyn schreef op zondag 13 december 2015 @ 21:37:
Lees nog eens goed waar ik op reageer :)
Dat zag ik :) Ik bedoel echter of het discussiëren over een sorted linked list vs priority queue niet een discussie in de marge is.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 15:45

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

Dat hangt natuurlijk van je use case af. Je kunt je echter afvragen of het in eerste instantie een handige keuze is geweest om voor een datastructuur te kiezen die niet automatisch al doet wat je wilt, zodat je die boilerplate er zelf omheen moet bouwen. Een prio queue is natuurlijk niet alleen efficienter (bij grote N) - conceptueel past het gewoon beter bij je requirements.

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Vanuit mijn situatie kan ik zeggen dat ik sowieso bezig ben met een grote inhaalslag met de kennis van nu. Dus heb nu een threadpool i.p.v. tientallen threads, een eventpool i.p.v. meerdere polls/selects, een timerpool i.p.v. een loop elke seconde. Dan komt het omzetten van een sorted linked list naar een priority queu later wel. Op dat laatste moet ik me nog even goed inlezen om het te kunnen implementeren :)

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • Sissors
  • Registratie: mei 2005
  • Nu online
@Oisyn, Waarom? Wat je conceptueel wil hebben is de tijd waarop het eerstvolgende event gaat gebeuren. Een sorted linked list lijkt me daarvoor conceptueel ideaal. En ik denk dat ik wat mis (met wikipedia ernaast), want ik zie niet echt het voordeel van een priority queue in. Als je die gebruikt om vervolgens in volgorde de events eruit te halen, dan doe je toch uiteindelijk gewoon hetzelfde? Uiteindelijk moet je iets van een sorting algoritme gebruiken om hem gesorteerd te houden.

  • Soultaker
  • Registratie: september 2000
  • Laatst online: 30-09 21:44
Een priority queue wordt meestal geïmplementeerd als een array met heap-structuur. Daarin kun je in O(log N) tijd elementen toevoegen, en in O(log N) het eerste element eruit halen. Ten eerste is dat efficiënter dan elementen toevoegen aan een linked list (dat kost O(N) tijd) en ten tweede is een array compacter en dus sneller dan een linked list (waarbij je geen spatial locality hebt omdat elk element op een willekeurige plek in het geheugen staat, en de cache dus minder benut wordt).

PGP public key


  • Sissors
  • Registratie: mei 2005
  • Nu online
Ah natuurlijk: Ik zat zelf te denken dat je ook gewoon binaire search tree om een sorted linked list kan doen bij invoegen, maar dat lukt natuurlijk niet omdat je niet weet waar het midden is, dus je moet gewoon van voor af aan beginnen. Duidelijk.

Dan is een priority queue inderdaad efficienter (effectief dus gewoon een array van tijden wanneer iets moet worden uitgevoerd + een pointer/ID of dat iets als ik het goed begrijp) (wel afhankelijk van of je misschien opzoeken belangrijker vindt om snel te gaan dan erin stoppen). Tegelijk blijft dit voor deze toepassing denk ik toch vooral een theoretisch probleem: Het lijkt me niet dat je snel meer dan een stuk of 10 elementen zal hebben hier.

  • MSalters
  • Registratie: juni 2001
  • Laatst online: 11:45
Met 10 elementen is een linked list sowieso niet zinnig, gebruik gewoon een array. Matige locality of reference is misschien wel de meest onderschatte oorzaak van slechte performance.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Wat zijn dan de vuistregels voor het gebruik van een array, linked list, heap, enz.? Nu pas ik zelf op alles gewoon een linked list toe. Desnoods als een FIFO.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • Zoijar
  • Registratie: september 2001
  • Niet online

Zoijar

Because he doesn't row...

Out of the box linked list gebruik je eigenlijk nooit. Elk element op de heap alloceren is killing voor performance op meerdere manieren. Neemt niet weg dat je linked-list-achtige structuren kan implementeren. Bv een contiguous vector storage met index references naar elementen, die kan je dan eens in de zoveel tijd opschonen.

  • Soultaker
  • Registratie: september 2000
  • Laatst online: 30-09 21:44
Ik zou het niet zo strikt stellen. Op hele kleine embedded systemen alloceer je geheugen meestal van te voren, maar dat kan net zo goed met de elementen van een linked list als met een array. Je next-pointers komen dan overeen met indices in je array, maar het is veel makkelijker om een free-list bij te houden dan een secundaire array met indices die je ook nog moet opschonen om de zoveel tijd.

Op iets minder kleinere systemen waar je bijvoorbeeld Linux op kan draaien, is heap allocatie niet altijd bezwaarlijk. Je moet je vooral laten leiden door de vraag welke eigenschappen van de datastructuur je nodig hebt. Ten opzichte van een dynamische array heeft een linked list het voordeel dat elementen niet verplaatst hoeven worden als je elementen toevoegt of verwijdert (pointers naar elementen blijven altijd geldig), and dat de performance van operaties voorspelbaar is (je hoeft nooit de hele lijst te heralloceren als je één element toevoegt of verwijdert, wat fijn is als je bijvoorbeeld in een interrupt handler een element wil verwijderen).

In het concrete geval van de TS is een linked list ongeschikt omdat de benodigde eigenschappen (toevoegen en verwijderen van elementen op volgorde) niet efficiënt te implementeren zijn, maar dat betekent niet dat een linked list "eigenlijk nooit" geschikt is. Niet voor niets zit de Linux kernel bijvoorbeeld vol met linked lists.

PGP public key


  • .oisyn
  • Registratie: september 2000
  • Laatst online: 15:45

.oisyn

Moderator Devschuur® / Cryptocurrencies

Demotivational Speaker

Sissors schreef op zondag 13 december 2015 @ 23:12:
Dan is een priority queue inderdaad efficienter (effectief dus gewoon een array van tijden wanneer iets moet worden uitgevoerd + een pointer/ID of dat iets als ik het goed begrijp)
Een binary heap is een binary tree die opgeslagen is als array, waarbij de children van de node op index n staan op plekken n*2 en n*2+1, en zijn parent op n/2. De root staat dan typisch op index 1 (want dat rekent makkelijker, al kun je het prima aanpassen dat de root op 0 staat). De boom is verder altijd gebalanceerd, want er staan geen lege plekken in de array.

In het geval van een priority queue is het geen gesorteerde boom. De enige garantie die er is is dat de parent node altijd kleiner is dan zijn twee child nodes. Dit betekent automatisch dat een node het kleinste element is van zijn eigen deelboom, en dus dat de root het kleinste element van de gehele boom is. Bij het 'poppen' van het eerste element van de priority queue ontstaat er een gat (want je neemt de root weg), die wordt opgevuld door de kleinste van de twee children. Dan ontstaat daar weer een gat, etc. Insertion gaat op een vergelijkbare manier, je zet het element achteraan in de array en dan verwissel je 'm recursief met zijn ancestors als het nieuwe element kleiner is dan zijn parent. Vandaar dus O(log n) insertion en O(log n) extraction.
Het lijkt me niet dat je snel meer dan een stuk of 10 elementen zal hebben hier.
Vandaar dat ik mijn voorlaatste opmerking nog veel essentieler vindt dan performance in dit geval - als je al beschikt over een datastructuur die exact doet wat je wilt, waarom zou je dan een generiekere datastructuur gebruiken waar je de gewenste logica (namelijk het gesorteerd zijn) zelf er nog omheen moet bouwen?

Maar goed, we hebben het hier natuurlijk wel over C, de taal zonder enige standaard containers whatsoever ;)

You see, killbots have a preset kill limit. Knowing their weakness, I sent wave after wave of my own men at them until they reached their limit and shut down. Kif, show them the medal I won.


  • CurlyMo
  • Registratie: februari 2011
  • Nu online

CurlyMo

www.pilight.org

Topicstarter
Aha, net even deze video gekeken en nu komt de clue binnen. Waar je denkt dat linked lists mooi lineair zijn, vragen ze eigenlijk een grote bulk aan random reads van je geheugen aangezien elke next pointer binnen de linked list naar een willekeurig ander geheugenblok wijst. Waar je denk dat je bij een vector / array moeilijker kan manipuleren en zoeken, ligt alles wel netjes in het geheugen waardoor het werken met een array vrijwel altijd sneller is. Ondanks het (hypothetisch) moeten verplaatsen van duizenden elementen bij het verwijderen van een element aan het begin.

geen vragen via PM die ook op het forum gesteld kunnen worden.


  • Soultaker
  • Registratie: september 2000
  • Laatst online: 30-09 21:44
.oisyn schreef op maandag 14 december 2015 @ 10:29:
Maar goed, we hebben het hier natuurlijk wel over C, de taal zonder enige standaard containers whatsoever ;)
POSIX heeft tenminste nog search.h :P (Ja ja, is niet "standaard C".)

PGP public key

Pagina: 1


Microsoft Xbox Series X LG CX Google Pixel 5 CES 2020 Samsung Galaxy S20 4G Sony PlayStation 5 Nintendo Switch Lite

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2020 Hosting door True