Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011

Stack och kö

Hej!

Skulle behöva lite hjälp med a) uppgiften här:

. Förstår inte riktigt hur man ska tänka, hur kan man implementera två stackar i en vektor så de inte blir overflow? På vilket sätt kan man skapa två olika stackar för en vektor?

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007

Enligt frågeställningen så ska stackarna tillsammans kunna ha lika många element som vektorn. Fundera på vart stackarna måste börja någonstans, och åt vilket håll de måste växa åt, för att det ska vara möjligt.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av perost:

Enligt frågeställningen så ska stackarna tillsammans kunna ha lika många element som vektorn. Fundera på vart stackarna måste börja någonstans, och åt vilket håll de måste växa åt, för att det ska vara möjligt.

Alltså stacken börjar ju i botten liksom och man plockar ur element på toppen. Om man tänker sig att man har en lista från 0 till n-1 så börjar den ju på 0 och växer åt höger där sista elementet är n-1. Är väl samma sak i en stack?

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
Skrivet av mhj:

Alltså stacken börjar ju i botten liksom och man plockar ur element på toppen. Om man tänker sig att man har en lista från 0 till n-1 så börjar den ju på 0 och växer åt höger där sista elementet är n-1. Är väl samma sak i en stack?

I detta fall har du dock inte en lista, utan en vektor med fast storlek. Du kan alltså fritt välja vart varje stack ska börja någonstans, och åt vilket håll i vektorn de ska växa åt.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av perost:

I detta fall har du dock inte en lista, utan en vektor med fast storlek. Du kan alltså fritt välja vart varje stack ska börja någonstans, och åt vilket håll i vektorn de ska växa åt.

Okej men är inte helt med på vad man ska välja för att inte få overflow. En är ju att den börjar på 0 och sen slutar vid n. Det är väl den som är "standard".

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
Skrivet av mhj:

Okej men är inte helt med på vad man ska välja för att inte få overflow. En är ju att den börjar på 0 och sen slutar vid n. Det är väl den som är "standard".

Det där med overflow betyder bara att båda stackarna tillsammans ska få plats med totalt n element, utan att skriva utanför vektorn eller skriva över varandra. Så säg att en av stackarna börjar på 0 och växer uppåt mot n, hur ska den andra stacken placeras för att få plats med så många element som möjligt? Notera också att jag sa "växer uppåt" istället för "slutar". Eftersom stackarna delar på en vektor så har de ingen fast kapacitet, hur många element de kan lagra beror på hur stor den andra stacken är.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av perost:

Det där med overflow betyder bara att båda stackarna tillsammans ska få plats med totalt n element, utan att skriva utanför vektorn eller skriva över varandra. Så säg att en av stackarna börjar på 0 och växer uppåt mot n, hur ska den andra stacken placeras för att få plats med så många element som möjligt? Notera också att jag sa "växer uppåt" istället för "slutar". Eftersom stackarna delar på en vektor så har de ingen fast kapacitet, hur många element de kan lagra beror på hur stor den andra stacken är.

Okej men då borde den andra stacken börja på n och växa nedåt mot 0. Men känns konstigt hur man kan popa och pusha och hantera två stacker samtidigt i en vektor men kanske är jag som tänker fel.

Trädvy Permalänk
Medlem
Plats
Finland
Registrerad
Maj 2004

@mhj: Inte särskilt konstigt om du har koll på var respektive stacks topp ligger.

Trädvy Permalänk
Medlem
Plats
Malmö
Registrerad
Feb 2006
Skrivet av mhj:

Okej men då borde den andra stacken börja på n och växa nedåt mot 0. Men känns konstigt hur man kan popa och pusha och hantera två stacker samtidigt i en vektor men kanske är jag som tänker fel.

Det är rätt. Inte särskilt svårt att hålla koll på.
lite pseudokod som exempel

class 2stacks 2stacks(size n){ stack1pos = 0 stack2pos = n - 1 array = new array[n] } push(stack, value){ if(stack = 1){ array[stack1pos] = value stack1pos++ } else { array[stack2pos] = value stack2pos-- } } pop(stack){ if(stack = 1){ return array[stack1pos--]; } else { return array[stack2pos++] } }

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Tazavoo:

@mhj: Inte särskilt konstigt om du har koll på var respektive stacks topp ligger.

Skrivet av Killbom:

Det är rätt. Inte särskilt svårt att hålla koll på.
lite pseudokod som exempel

class 2stacks 2stacks(size n){ stack1pos = 0 stack2pos = n - 1 array = new array[n] } push(stack, value){ if(stack = 1){ array[stack1pos] = value stack1pos++ } else { array[stack2pos] = value stack2pos-- } } pop(stack){ if(stack = 1){ return array[stack1pos--]; } else { return array[stack2pos++] } }

Sant då är jag med! Har ni något förslag på hur man kan göra b)? Vad menas med en ringbuffer?

Trädvy Permalänk
Medlem
Plats
Malmö
Registrerad
Feb 2006
Skrivet av mhj:

Sant då är jag med! Har ni något förslag på hur man kan göra b)? Vad menas med en ringbuffer?

En ringbuffer är en rund buffer Tänk dig att du mäter på något, och inte vet hur snabbt du kommer kunna avverka värden. Du vill heller inte spara undan hur många värden som helst. Då kan du använda en ringbuffer. Den kommer alltså börja skriva över det nyaste värdet hela tiden.

Förklaras även enkelt med pseudo kod

class ringbuffer buffer size pos ringbuffer(size n) buffer = new array[n] size = n pos = 0 add(value) buffer[pos] = value pos = (pos + 1) % size get() toReturn = buffer[pos] pos--; if pos < 0 pos = n - 1 return toReturn

Här ser den skarpsynte att man kan "getta" runt runt runt, vilket man skulle behöva lägga in stöd för, så man inte kan hämta samma värde två gånger. Exempelvis skulle man kunna sätta värdet till "tomt" eller dylikt. Man skulle även kunna hålla koll på sina positioner.

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Killbom:

En ringbuffer är en rund buffer Tänk dig att du mäter på något, och inte vet hur snabbt du kommer kunna avverka värden. Du vill heller inte spara undan hur många värden som helst. Då kan du använda en ringbuffer. Den kommer alltså börja skriva över det nyaste värdet hela tiden.

Förklaras även enkelt med pseudo kod

class ringbuffer buffer size pos ringbuffer(size n) buffer = new array[n] size = n pos = 0 add(value) buffer[pos] = value pos = (pos + 1) % size get() toReturn = buffer[pos] pos--; if pos < 0 pos = n - 1 return toReturn

Här ser den skarpsynte att man kan "getta" runt runt runt, vilket man skulle behöva lägga in stöd för, så man inte kan hämta samma värde två gånger. Exempelvis skulle man kunna sätta värdet till "tomt" eller dylikt. Man skulle även kunna hålla koll på sina positioner.

Okej hänger inte riktigt med på varför du tar pos + 1 och sen modulus med size och är inte helt med på get metoden heller, men antar att get häntar en position sen minskar steget med 1 och hämtar värdet på den där osv. Men på frågan b) borde inte svaret bli d? För först har man a,b och c i kön. Sen tar man bort hela kön två gånger och sen lägger man till d.

Trädvy Permalänk
Medlem
Plats
Malmö
Registrerad
Feb 2006
Skrivet av mhj:

Okej hänger inte riktigt med på varför du tar pos + 1 och sen modulus med size och är inte helt med på get metoden heller, men antar att get häntar en position sen minskar steget med 1 och hämtar värdet på den där osv. Men på frågan b) borde inte svaret bli d? För först har man a,b och c i kön. Sen tar man bort hela kön två gånger och sen lägger man till d.

Modulot innebär att den kommer hoppa tillbaka till samma position. Har man en maxstorlek kommer pos alltså gå
0 -> 1 -> 2 -> 0 -> 1 ....

Frågan får du tänka ut själv

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011
Skrivet av Killbom:

Modulot innebär att den kommer hoppa tillbaka till samma position. Har man en maxstorlek kommer pos alltså gå
0 -> 1 -> 2 -> 0 -> 1 ....

Frågan får du tänka ut själv

Aha okej så den går sådär om maxstorleken är 3? Men facit svarar såhär på frågan: http://puu.sh/kjkiD/576184ad8d.png - förstår inte riktigt deras lösning.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011

@mhj: Enklaste sättet att implementera en ringbuffer är att ha två index, en för produktion (index där nästa Enqueue() ska placera sitt värde) och en för konsumtion (index där nästa Dequeue() ska hämta sitt nästa värde).

Om vi kallar dessa index för prod och cons så blir Front i bilden du postade lika med "cons" och längden är "(prod-cons) mod RING_CAPACITY".

Så logiken för Enqueue är

array[prod] = newElem prod = prod + 1 if prod == RING_CAPACITY prod = 0

En variant i C99 som löser det specifika fallet, men som har en väldigt lurig bug, så skriv inte av detta

#include <stdio.h> #define RING_CAP 3 #define RING_INITIALIZER { 0, 0, { [0 ... RING_CAP-1] = '*' } } typedef char elem_t; typedef struct { unsigned prod; unsigned cons; elem_t storage[RING_CAP]; } ring_t; void ring_enq (ring_t * ring, elem_t elem) { ring->storage[ring->prod++ % RING_CAP] = elem; } elem_t ring_deq(ring_t * ring) { return ring->storage[ring->cons++ % RING_CAP]; } void ring_show(ring_t *ring) { unsigned i; for (i = 0; i < RING_CAP; i++) { printf("%c", ring->storage[i]); } printf(" Front = %u, Length = %u\n", ring->cons % RING_CAP, ring->prod - ring->cons); } int main() { ring_t r = RING_INITIALIZER; ring_enq(&r, 'a'); ring_show(&r); ring_enq(&r, 'b'); ring_show(&r); ring_enq(&r, 'c'); ring_show(&r); ring_deq(&r); /* 'a' */ ring_show(&r); ring_deq(&r); /* 'b' */ ring_show(&r); ring_enq(&r, 'd'); ring_show(&r); }

Dold text

Denna skriver ut

a** Front = 0, Length = 1 ab* Front = 0, Length = 2 abc Front = 0, Length = 3 abc Front = 1, Length = 2 abc Front = 2, Length = 1 dbc Front = 2, Length = 2

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Linköping
Registrerad
Jun 2007
Skrivet av mhj:

Aha okej så den går sådär om maxstorleken är 3? Men facit svarar såhär på frågan: http://puu.sh/kjkiD/576184ad8d.png - förstår inte riktigt deras lösning.

De använder två variabler för att hålla reda på hur kön ser ut: front pekar på var kön börjar och length håller reda på hur lång buffern är. När ett element läggs till i kön så ökas length med 1, inga konstigheter med det. När ett element tas bort med Dequeue så ökas front med 1 så att början på kön flyttas fram, och length minskas med 1 eftersom ett element försvunnit. Element som tas bort ur kön med Dequeue ligger alltså kvar i buffern tills dess att de skrivs över av något annat element. Så i slutändan innehåller kön endast elementen c och d, men b ligger fortfarande kvar i buffern eftersom inget skrivit över den.

Trädvy Permalänk
Medlem
Plats
i din garderob
Registrerad
Sep 2007
Skrivet av Yoshman:

int main()
{
ring_t r = RING_INITIALIZER;

ring_enq(&r, 'a');
ring_show(&r);

ring_enq(&r, 'b');
ring_show(&r);

ring_enq(&r, 'c');
ring_show(&r);

ring_deq(&r); /* 'a' */
ring_show(&r);

ring_deq(&r); /* 'b' */
ring_show(&r);

ring_enq(&r, 'd');
ring_show(&r);
}
[/code]

Nyfiken och kanske dum fråga då jag inte programmerat C på över 15 år: varför väljer du att hålla r som ett värde istället för en pekare till ring_t? Det ser omständigt ut att hämta referensen vid varje anrop till ring_enq/ring_show, men förmodligen missar jag något

Bilanaloger är som Volvo — varenda svenne kör med dem

Trädvy Permalänk
Medlem
Plats
Malmö
Registrerad
Feb 2006
Skrivet av mhj:

Aha okej så den går sådär om maxstorleken är 3? Men facit svarar såhär på frågan: http://puu.sh/kjkiD/576184ad8d.png - förstår inte riktigt deras lösning.

Jag har väldigt svårt att se vad du inte förstår.
Först är listan tom, första elementent är 0 och elementen i listan är * * *
Sedan lägger man in a. Listan har längden 1 och elementet man kommer plocka ut om man frågar ligger på plats 0 -> a * *
Sedan lägger man in b, listan har längden 2 men man kommer fortfarande plocka a om man frågar -> a b *
...
...
De använder front och length för att, precis som jag beskrev, inte plocka ut samma item två gånger.

Trädvy Permalänk
Datavetare
Plats
Stockholm
Registrerad
Jun 2011
Skrivet av Teknocide:

Nyfiken och kanske dum fråga då jag inte programmerat C på över 15 år: varför väljer du att hålla r som ett värde istället för en pekare till ring_t? Det ser omständigt ut att hämta referensen vid varje anrop till ring_enq/ring_show, men förmodligen missar jag något

Främst två orsaker i detta exempel:
1. minnet hanteras automatiskt.
2. går att låta kompilatorn generera all kod för att initiera en variabel till en tom ring.

I detta fall spelar det ingen större roll hur man gör, är så pass enkelt. Men rent generellt så vill man hålla så mycket som möjligt i automatiska variabler i C, dels är det överlägset snabbaste sättet och kanske ännu viktigare är att sådan kod kan typiskt alltid skrivas så den överhuvudtaget inte kan gå fel -> inga felfall att tänka på -> enklare.

ring_enq() och ring_deq() måste ju ta en pekare för att ändra innehållet i strukturen, ring_show() skulle kunna ta sitt argument "by-value" eller som en const ring_t *, tyckte det var en koherent och ta pekare överallt.

Tycker just denna uppgift kring ring-buffert var lite "elak" då storleken inte är en potens av två. Den absolut vanligaste anledningen till varför man väljer en ring-buffert är för att man måste ha absolut högsta möjliga prestanda. Än viktigare blir det i på dagens multicore-system, en ring-buffert baserad kö men exakt en tråd som producerar och en som konsumerar går att skriva korrekt helt utan lås. En kö med multipla läsare/skrivare går fortfarande att skriva utan traditionella lås (mutex eller liknande), räcker med en s.k. compare-and-swap (CAS) som typiskt är väldigt hårt optimerad i moderna CPUer.

Buggen i mitt program ovan kommer när man köar sitt 2^32:e element, 3 är inte jämt delbart med 2^32 så där kommer det bli fel. Problemet om en ring-buffert inte har en kapacitet som är en potens av två är att en rad optimeringar blir omöjliga, bara en sådan sak som att hålla reda på om kön är helt tom eller helt full blir komplicerat om man kör med ett index för konsumtion och ett index för produktion...

Det "elaka" är att det blir fler specialfall om storleken inte är en potens av två. Slog mig att det är nog orsaken till att man i detta fall föreslår front och length som tillstånd. Pseudokoden för Enqueue blir då i stället

Enqueue(elem) array[(front + length) mod RING_CAPACITY] = elem ; lagra elementet, index för produktion är index för konsumtion plus nuvarande längd length++ ; antal element i kön har ökat med ett

och Dequeue blir

Dequeue() elem = array[front] ; 'front' är index för konsumtion front = (front + 1) mod RING_CAPACITY ; 'front' är index till nästa position för konsumtion length-- ; antal element i kön minskar med ett return elem

En korrekt C implementation där man har restriktionen att kapaciteten måste vara en potens av två, notera total avsaknad av dyra operationer som "mod/%", check för något specialfall vid wrap-around. Många periferienheter använder också ring-bufferts som gränssnitt då det är lätt att designa sådant i maskinvara, nätverkskort är ett exempel som använder ring-bufferts för inkommande och utgående paket.

#include <stdio.h> #define RING_ORDER 2 /* Convenience macros derived from RING_ORDER */ #define RING_CAP (1U << RING_ORDER) #define RING_MASK (RING_CAP - 1) #define RING_INITIALIZER { 0, 0, { [0 ... RING_CAP-1] = '*' } } typedef char elem_t; typedef struct { unsigned prod; unsigned cons; elem_t storage[RING_CAP]; } ring_t; void ring_enq(ring_t *ring, elem_t elem) { ring->storage[ring->prod++ & RING_MASK] = elem; } elem_t ring_deq(ring_t *ring) { return ring->storage[ring->cons++ & RING_MASK]; } void ring_show(const ring_t *ring) { unsigned i; for (i = 0; i < RING_CAP; i++) { printf("%c", ring->storage[i]); } printf(" Front = %u, Length = %u\n", ring->cons & RING_MASK, ring->prod - ring->cons); } int main() { ring_t ring_storage = RING_INITIALIZER; ring_t *r = &ring_storage; ring_enq(r, 'a'); ring_show(r); ring_enq(r, 'b'); ring_show(r); ring_enq(r, 'c'); ring_show(r); ring_enq(r, 'x'); ring_show(r); ring_deq(r); /* 'a' */ ring_show(r); ring_deq(r); /* 'b' */ ring_show(r); ring_enq(r, 'd'); ring_show(r); /* "dbcx Front = 2, Length = 3" */ }

Dold text

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Trädvy Permalänk
Medlem
Plats
Stockholm
Registrerad
Mar 2011

Alright då är jag med på allt, tack för hjälpen alla!