[Alg] Optimalisatie van palindromen zoeken.*

[Diadem]

Ik zit een opgave van het Nederlands Kampioenschap Programmeren te maken (van vorig jaar).

De opgave luidt simpel gezegd als volgt: Schrijf een algoritme dat als input een string krijgt en als output het minimaal aantal letters geeft dat je weg moet laten om een palindroom te vormen.

voorbeeld: "Programmeerwedstrijd" geeft als output 14. Het langste palindroom hierin is 'rrmmrr' of 'rreerr'. Een palindroom hoeft dus geen bestaand woord te zijn, en hoeft ook niet aaneengesloten te staan.

Ik heb een werkend algoritme geschreven. Dit krijgt als input een string en de lengte van deze string (zodat ik hem niet telkens hoef uit te rekenen), en geeft als output de lengte van het langste te maken palindroom.

C++:

char *paling(char *p, int begin, int eind)
{
  char *c;
  c = (char *) malloc(sizeof(char) * (eind-begin+1));
  strncpy(c,(p+begin),eind-begin);
  c[eind-begin]=0;
  return c;
}   

int palindroom(char *p, int leng)
{
  int pos, max;
  int terug1=0;
  int terug2=0;
  char *a;

  if (leng==0) return 0;
  if (leng==1) return 1;

  pos = strrchr(p, p[0]) - p;
  if (pos) {
    a = paling(p,1,pos);
    terug1 = 2 + palindroom(a,pos-1);
    free(a);
  }
  if (pos!=leng-1) {
    a = paling(p,1,leng);
    terug2 = palindroom(a,leng-1);
    free(a);
  }
  if (terug1>terug2) max=terug1; else max=terug2;
  if (max<1) max=1;

  return max;
}

Mijn probleem is dat het een complexiteit heeft van 2^n ofzo. Volgens de opgave is de invoer een string van 200 tekens. Tot 100 tekens geeft mijn manier een oplossing binnen een seconde. Bij 120 tekens is ie echter al zo een halve minuut of zoiets gemiddeld. Met 200 tekens is hij denk ik niet klaar voordat mijn achterkleinkinderen bejaard zijn.

Mijn uitdaging is dus het schrijven van een sneller algoritme.

Heeft iemand ideeën?

NB: Het gebruik van java of pascal ipv c/c++ is ook toegestaan.

[Pooh]

Ideetje


Pseudocode:

palindroom(string) {
1. pak string[0]
2. if string[0] maar 1 keer in string => string = string[1], goto 1
2b. else zoek hoogste x waar string[x] = string[0]
3 als x-0 < strlen()-x (dus 2e helft is groter) => palindroom(string[x])
3b else palindroomlengte +=2, palindroom(string[1 tot x-1])
}

Hmm... zowel 't pad in 3a als in 3b moet volledig doorzocht worden zie ik nu. (dus even complex als de jouwe)

[Janoz]

Je voorbeeld is fout. Ik weet wel een langere rreperr waardoor het antwoord 13 zou worden.

euhm .. je hoeft alleen het aantal terug te geven?

Dan kun je het natuurlijk ook eens stukje simpeler doen he .. Gewoon een 'letter histogram' maken alle waarden in dat histogram floor(waarde/2), histogram waarden sommeren en, waneer er nog letters over zijn er 1tje bijop tellen voor de palindromen van oneven lengte.. Tadaa, een algoritme van O(N)


NB: hmm .. dit geldt natuurlijk alleen als volgorde niet van belang is

[Pooh]

Naar mijn idee horen de letters wel op volgorde te staan... Alleen niet aaneengesloten...

parterxyzretrap mag dus wel parterretrap worden, maar parterparter niet.

[Verwijderd]

Ik vraag me af of dat zo bedoeld wordt. Er staat:

... en hoeft ook niet aaneengesloten te staan.

Nu weet ik niet of dat betekent dat je alleen letters ertussenuit mag halen, of ook met de volgorde mag sjoemelen. Als dat tweede het geval is heeft Janoz gelijk, anders niet.

[Diadem]

Het moet natuurlijk wel op volgorde.
Anders wordt het wel makkelijk.

Sorry voor de onduidelijkheid

[kvdveer]

Ik denk dat je je stringcopy zooi er uit moet halen.. Scheelt enorm!

code:

char* pBuffer;
int lBuffer; // gewoon voor het net... ;-)


int palindroom() {
  return lbuffer - _palindroom(0,lBuffer-1);
}

int _palindroom(int pos_L, int pos_R,boolean reverse) {
  if(pos_L == pos_R) return 0;
  if(pBuffer[pos_L] != pBuffer[pos_R]) {
    return max(
      _palindroom(pos_L + 1, pos_R),
      _palindroom(pos_L, pos_R - 1));  
  } else {
    return _palindroom(pos_L + 1, pos_R+1) + 2;    
  }
}

Worst case = O(n^2);
BestCase = O(n);

edit:

Heb je trouwens een linkje naar die opgaven?

[ Voor 0% gewijzigd door kvdveer op 23-09-2002 16:44 . Reden: Code opgeleukt ]

[Verwijderd]

De truc van deze opgave is sla de lengte van langste palindroom op van elke mogelijke substring.

edit:
Weg met mijn buggy prutscode: zie verderop de verbeterde versie

Voor andere oplossingen en de officiele invoer en uitvoer zie http://www.nkp2001.nl/files/nkp2001-uitw.zip

[Verwijderd]

Je mag alleen letters verwijderen, dus niet verwisselen. Janoz' opmerking klopt dus niet, want er staat geen "p" tussen de twee "m"s cq "e"s.

offtopic:
Alweer te laat Leuk zo'n modem tussen de kabelaars/adsl'ers

[kvdveer]

Verwijderd schreef op 23 september 2002 @ 16:44:
De truc van deze opgave is sla de lengte van langste palindroom op van elke mogelijke substring.

code:

...

Voor andere oplossingen en de officiele invoer en uitvoer zie http://www.nkp2001.nl/files/nkp2001-uitw.zip

Hmm. Dat is ook O(n^2), zowel bestcase als worstcase. Mijn oplossing lijkt dus beter... Of snap ik het nou niet?

[Verwijderd]

kvdveer schreef op 23 september 2002 @ 16:46:
Hmm. Dat is ook O(n^2), zowel bestcase als worstcase. Mijn oplossing lijkt dus beter... Of snap ik het nou niet?

Jouw oplossing is helaas in worst case O(2^n)
bijvoorbeeld als de string uit allemaal verschillende tekens betaat.

Worst case = O(n^2) moet O(2^n) zijn

alle opgaven van vorig jaar

[kvdveer]

Verwijderd schreef op 23 september 2002 @ 16:59:
[...]

Jouw oplossing is helaas in worst case O(2^n)
bijvoorbeeld als de string uit allemaal verschillende tekens betaat.

Daar heb je gelijk in, dat staat er ook bij, maar mijn bestcase (als het al een palindroom is) is o(n).

[Verwijderd]

Overigens, voor meer van dit soort opgaven, en een mogelijkheid om de oplossingen online te laten testen, zie http://acm.uva.es/problemset/

Enjoy

[Diadem]

kvdveer schreef op 23 september 2002 @ 16:40:
Ik denk dat je je stringcopy zooi er uit moet halen.. Scheelt enorm!

Dat ik daar zelf niet aan gedacht heb

Even kijken...

Heb je trouwens een linkje naar die opgaven?

Nee, had ik dus niet. Maar het is al gegeven door borganism

[edit]
Ik heb dit nu geimplementeerd, en hij is inderdaad sneller. Maar het probleem is dat de complexiteit nog steeds gelijk is, dus het gaat nog steeds helemaal mis als ik een string van 200 tekens meestuur.

Toch eens borganism's methode bekijken.

[Janoz]

Verwijderd schreef op 23 september 2002 @ 16:45:

offtopic:
Alweer te laat Leuk zo'n modem tussen de kabelaars/adsl'ers

offtopic:
Wat nou kabel/adsl... Waar ik nu zit haal ik net zo snel mijn bestanden van de fileserver als ik ze van internet afhaal

Maar wie heeft hier trouwens wel eens meegedaan met het NKP? * Janoz in 99.

[Verwijderd]

/me heeft meegedaan in 93 en 94
Ja, ik ben oud, so shut up already!

edit:
Ik heb ook weleens meegedaan aan de "Northwestern European Regional Programming Contest" in 94 (6e geworden op het NKP), maar dat was niet echt om over naar huis te schrijven helaas.

[Verwijderd]

Ik heb nooit mee gedaan en het vorig jaar gemist , maar ik doe dit jaar wel mee.
Zijn er hier nog meer die dit jaar mee gaan doen?

[eek]

Ik heb in 2000 meegedaan heb hiero nog zo'n mooi t-shirt als bewijs liggen.
Was de eerste keer, maar ging niet slecht. Geen voor compentitie op school
en zeer weinig oefening

[Diadem]

Ik ga dit jaar meedoen met het NKP. Tenminste, proberen, moet natuurlijk eerst het UKP doorkomen dan (Utrechts Kampioenschap).

Is nog niet zeker trouwens. We zoeken nog een derde man voor ons team.

Overigens wordt het een ramp als ik dit zo bekijk...

[Verwijderd]

Diadem ... een tip is om niet de eerste de beste opgave proberen op te lossen, maar goed te zoeken naar de eenvoudigste. Liever een uur zoeken voor 3 opgaven die ieder in een half uur geprogrammeerd kunnen worden dan dat je een probleem pakt waarmee je 3 uur bezig bent. Nou denk ik niet dat deze opgave ontzettend complex is, maar triviaal is hij zeker ook niet.

Succes

[Diadem]

Verwijderd schreef op 23 september 2002 @ 16:44:
De truc van deze opgave is sla de lengte van langste palindroom op van elke mogelijke substring.

Delphi:

function maxpalin(str : string): integer;
var
    maxp : array[0..200,0..200] of integer;
    len,i,j : integer;
begin
len := length(str);
if len > 1 do
begin
   for i := 0 to len-1 do array[i,0] := 0;
   for i := 0 to len-1 do array[i,1] := 1;
   for j := 2 to len do
   begin
      for  i := 0 to len-j do
      begin
     if str[i] == str[i+j-1] then
        maxp[i,j] := maxp[i+1,j-2]+2;
     else
        maxp[i,j] := max(maxp[i,j-1],maxp[i+1,j-1]);
      end;
   end; 
   maxpalin := maxp[0,len];
end
else maxpalin := len;
end;

Volgens mij klopt er niets van dit algoritme.

code:

   for i := 0 to len-1 do array[i,0] := 0;

Moet daar niet staan 'maxp' ipv 'array'?

Maar zelfs dan lijkt het nog niet te kloppen. Ik heb het uitgeprobeerd, en krijg altijd 2 terug.

[ Voor 0% gewijzigd door Diadem op 23-09-2002 18:06 . Reden: tags goed gezet ]

[Knutselsmurf]

* Knutselsmurf heeft meegedaan in '96 '97 en '98.

uit mijn hoofd 2 keer en 3e en 1 keer een 5e plaats.......

[Glimi]

Zijn deze wedstrijden echt gericht op 'snelle code' en niet op onderhoudbare code?

[Verwijderd]

Glimi schreef op 23 september 2002 @ 19:01:
Zijn deze wedstrijden echt gericht op 'snelle code' en niet op onderhoudbare code?

Nee, gewoon gericht op oplossingen die snel/efficient genoeg zijn. Er is een max aan de tijd die een oplossing mag draaien, en die's (geloof ik) 2 x de tijd die de oplossing van de jury nodig had.

Je moet in x uur (meestal 5 geloof ik) zo veel mogelijk opgaven oplossing in een team van 3 mensen, met 1 computer, uit een probleemset van y opgaven (meestal 10).

[Verwijderd]

Diadem schreef op 23 september 2002 @ 18:05:
Volgens mij klopt er niets van dit algoritme.

code:

   for i := 0 to len-1 do array[i,0] := 0;

Moet daar niet staan 'maxp' ipv 'array'?

Maar zelfs dan lijkt het nog niet te kloppen. Ik heb het uitgeprobeerd, en krijg altijd 2 terug.

Ehm ik moet geen code posten zonder het uit te proberen, zal even debuggen.
Ik was even vergeten dat string[0] de lengte is niet het eerste teken. Maar het algoritme klopt volgens mij wel.

zo deze werkt bij mij na een stuk of 10 bugs tehebben verwijderd.
Let op maxpalin returnt de lengte van de palindroom en niet het aantal letters die je weg moet laten.

Delphi:

function max(a,b : integer): integer;
begin
  if a > b then max := a
  else max := b;
end;

function maxpalin(str : string): integer;
var
    maxp : array[0..200,0..200] of integer;
    len,i,j : integer;
begin
len := length(str);
if len > 1 then
begin
   for i := 0 to len-1 do maxp[i,0] := 0;
   for i := 0 to len-1 do maxp[i,1] := 1;
   for j := 2 to len do
   begin
      for  i := 0 to len-j do
      begin
        if str[i+1] = str[i+j] then maxp[i,j] := maxp[i+1,j-2]+2
        else maxp[i,j] := max(maxp[i,j-1],maxp[i+1,j-1]);
      end;
   end;
   maxpalin := maxp[0,len];
end
else maxpalin := len;
end;

[Verwijderd]

Mja, dit topic bloedt dood hoewel het potentie heeft volgens mij

Daarom nu de kwisvraag*: de oplossing die borganism heeft gegeven is een optimalisering van een algemene recursieve oplossing (borganism's optimalisering bestaat uit het opslaan van tussengegevens in tabel maxp). Geef de algemene recursieve oplossing.

^{* uitgesloten van deze kwis zijn: mensen met een informaticaopleiding op hbo-niveau of hoger en mensen die met een dergelijke opleiding bezig zijn. (niet voorzeggen dus)}

[MSalters]

Janoz schreef op 23 september 2002 @ 17:11:
Maar wie heeft hier trouwens wel eens meegedaan met het NKP? * Janoz in 99.

Vorig jaar. Ik geloof dat we 3^e bij de bedrijven werden.

'k Vond het wel flauw dat C++ niet gebruikt mocht worden, ook al zeiden de organisatie vantevoren van wel. C with Classes is echt al 15 jaar passé; dat heeft niets met C++ te maken. Maar ja, professioneel programmeren is op zo groot mogelijke schaal problemen niet oplossen ( maar het vinden van een eerdere oplossing ) - iets heel anders.

[Verwijderd]

Schop, even plagen. Is er geen animo, of is het te moeilijk een functie met een body van zo'n 3 regels te schrijven?

[Pooh]

Verwijderd schreef op 24 september 2002 @ 16:20:
Schop, even plagen. Is er geen animo, of is het te moeilijk een functie met een body van zo'n 3 regels te schrijven?

Ja, hoor 's... eerst sluit je iedereen die 't kan van deelname uit, daarna ga je schoppen? Wat wil je nou?

[Verwijderd]

Poohbear schreef op 24 september 2002 @ 16:33:
Ja, hoor 's... eerst sluit je iedereen die 't kan van deelname uit, daarna ga je schoppen? Wat wil je nou?

Wat ik wil is een bepaalde groep op dit forum, die normaal volgens de shotgun-methodiek* ontwikkelt, eens animeren na te denken over algoritmiek Iedereen die een jaartje of twee programmeert moet dit kunnen, of hij nu een informatica opleiding volgt of niet.

^{* shotgun-methodiek = als het werkt is het goed, ook al begrijp ik mijn eigen code niet.}

[Diadem]

Verwijderd schreef op 23 september 2002 @ 21:27:
Mja, dit topic bloedt dood hoewel het potentie heeft volgens mij

Daarom nu de kwisvraag*: de oplossing die borganism heeft gegeven is een optimalisering van een algemene recursieve oplossing (borganism's optimalisering bestaat uit het opslaan van tussengegevens in tabel maxp). Geef de algemene recursieve oplossing.

^{* uitgesloten van deze kwis zijn: mensen met een informaticaopleiding op hbo-niveau of hoger en mensen die met een dergelijke opleiding bezig zijn. (niet voorzeggen dus)}

Deze algemene vorm is toch in feite gewoon mijn algoritme?

[Verwijderd]

Mietje : bedoel je dit?

Gegeven string str :

1)
Zijn er letters die vaker dan 1 keer voorkomen in <str>?
Nee : palindroomlengte = 1
Ja : ga naar 2

2)
Zoek 2 letters, a en b, in <str> zodat deze gelijk zijn en het verst uit elkaar liggen binnen <str>,
Zij i,j de offset binnen <str> van a en b, zodat i < j
i - j = 1?
Nee : palindroomlengte = 2 + palindroomlengte van letters in <str> tussen i en j (dus str[i+1] is de eerste letter van de nieuwe string, str[j-1] de laatste)
Ja : palindroomlengte = 2

[Verwijderd]

Eerste poging is te omslachtig : hier dan de tweede

Gegeven string str :

1) is de lengte van de string 0?
Ja : palindroomlengte = 0
Nee : ga naar 2

2) is de lengte van de string 1?
Ja : palindroomlengte = 1
Nee : ga naar 3

3) is de eerste letter uit de string gelijk aan de laatste?
Ja : palindroomlengte = 2 + palindroomlengte(string behalve eerste en laatste letter)
Nee : ga naar 4

4) is de eerste letter uit de string gelijk aan de enalaatste OF is de tweede letter uit de string gelijk aan de laatste?
Ja : palindroomlengte1 = 2 + palindroomlengte(string behalve eerste en laatste twee letters)
palindroomlengte2 = 2 + palindroomlengte(string behalve eerste twee en laatste letters)
palindroomlengte = MAX(palindroomlengte1,palindroomlengte2)
Nee : palindroomlengte = palindroomlengte(string behalve eerste en laatste letter)

hier code (MAX macro niet uitgeschreven )

code:

unsigned int palinlen(char *sz)
{
  unsigned int i_min = 0;              //laagste index van letter
  unsigned int i_max = strlen(sz);     //hoogste index van letter
  unsigned int i_len = 0;              //lengte van palindroom

  switch(i_max)
  {
  case 0 : return 0; //Lengte van de string is 0, dus palindroomlengte is 0
  case 1 : return 1; //Lengte van de string is 1, dus palindroomlengte is 1
  default :
    i_max--; //Max index van letter is <stringlengte> - 1
    if (sz[i_min] == sz[i_max]) //Eerste letter = laatste letter
    {
      sz[i_max] = '\0';
      i_len = 2 + palinlen(sz + 1);
    }
    else if ( (sz[i_min + 1] == sz[i_max]) || (sz[i_min] == sz[i_max - 1]) )
    { 
      if (sz[i_min + 1] == sz[i_max]) //Tweede letter = laatste letter
      {
        sz[i_max] = '\0';
        i_len = 2 + palinlen(sz + 2);        
      }
      if (sz[i_min] == sz[i_max - 1]) //Eerste letter = enalaatste letter
      {
        sz[i_max - 1] = '\0';
        i_len = MAX(i_len,2 + palinlen(sz + 1));        
      }
    }
    else //Eerste en laaste letter in de string doen niet meer mee, strippen en opnieuw
    {
        sz[i_max - 1] = '\0';
        i_len = palinlen(sz + 1);
    }
  }
  return i_len;
}

in het gunstigste geval dus O(n), in het ongunstigste O(2^n) (komt hier overigens niet voor )

[edit1] sterker nog, gewoon O(n) dus... toch? [/edit1]
[edit2] zit nog een klein foutje in, zien jullie em? [/edit2]
[edit3] Soultaker heeft gelijk. Er worden gewoon enorm veel mogelijkheden overgeslagen, algoritme is dus onjuist...[/edit3]

[Soultaker]

Je hebt het idee wel te pakken, Akhorahil, maar ik twijfel nog een beetje aan je implementatie. Ik het idee dat je erg veel nul-karakters invoegd die je niet meer herstelt.

Verder kloppen de gevallen die je onderscheid niet helemaal. Wat gebeurt er bijvoorbeeld met "aacbc"? Ik denk dat je stap 4 van je algoritme even moet herzien.

De recursieve variant (zonder een of andere vorm van 'caching' om 'm quasi-dynamisch te maken) hoort gewoon O(2^N) te zijn. Dat je uitkomt op O(N) zou al een indicatie moeten zijn dat er iets mis is.

Het kan allemaal veel korter en eenvoudig trouwens. Succes!

[Diadem]

Akhorahil's implementatie werkt niet. Als ik in zijn script "aafedccdef" dan kom ik in de laatste else terecht en roept hij zichzelf weer aan met 'afedccde' waarmee je dus niet bij de goede oplossing komt.

Volgens mij gaat elk recursief algoritme een complexiteit van O(2^n) geven. Iets wat niet de bedoeling is, want dan lukt het je nooit om strings van 200 tekens te doorlopen, en dat is wel de opgave.

Ik heb het algoritme wat ik in de eerste post gaf inmiddels super geoptimaliseerd, maar het is nog steeds hopeloos traag. Ik heb echter ook borganism's algoritme herschreven naar c, en dat werkt als een trein.

Complexiteit is keurig netjes O(n^2). Is toch een verbetering ten opzichte van 0(2^n)

offtopic:
Toen ik dat algoritme ging testen op strings van 1000 tekens ging m'n computer over de zeik. Hij crasht als ik " int maxp[1000][1000]; " doe. Wat flauw dat ik geen 4 meg geheugen in 1x mag reserveren

[Verwijderd]

Ik het idee dat je erg veel nul-karakters invoegd die je niet meer herstelt.

Klopt idd, maar dat is maar op 1 plaats een probleem :

code:

if (sz[i_min + 1] == sz[i_max]) //Tweede letter = laatste letter
      {
        sz[i_max] = '\0';
        i_len = 2 + palinlen(sz + 2);        
      }
      if (sz[i_min] == sz[i_max - 1]) //Eerste letter = enalaatste letter
      {
        sz[i_max - 1] = '\0';
        i_len = MAX(i_len,2 + palinlen(sz + 1));        
      }

Voor de eerste check moet ik even een kopie aanmaken, anders is bij de tweede check de originele string reeds verminkt.

Akhorahil's implementatie werkt niet. Als ik in zijn script "aafedccdef" dan kom ik in de laatste else terecht en roept hij zichzelf weer aan met 'afedccde' waarmee je dus niet bij de goede oplossing komt.

idd. zie ik zelf ook ineens. Jammer want mijn algoritme gedraagt zich O(n log n).
Terug naar de tekentafel dus

Toen ik dat algoritme ging testen op strings van 1000 tekens ging m'n computer over de zeik. Hij crasht als ik " int maxp[1000][1000]; " doe. Wat flauw dat ik geen 4 meg geheugen in 1x mag reserveren

Dat mag wel, maar niet op de stack idd. Gewoon als volgt doen :

code:

int **maxp;
maxp = (int **)malloc(1000 * sizeof(int *));
for (int i = 0; i < 1000; i++) maxp[i] = (int *)malloc(1000 * sizeof(int));

Dan moet het wel goed gaan. Als de maximumlengte van een string overigens 200 letters is kun je hier beter unsigned chars gebruiken (scheelt een factor 4).

En dat je met borganisms caching een sneller algoritme krijgt : nogal wiedes

[Verwijderd]

Nieuwe poging

Gegeven string str :

1) is de lengte van de string 0?
Ja : palindroomlengte = 0
Nee : ga naar 2

2) is de lengte van de string 1?
Ja : palindroomlengte = 1
Nee : ga naar 3

3) is de lengte van de string 2?
Ja : palindroomlengte = OF 1 (letters ongelijk) OF 2 (letters gelijk)
Nee : ga naar 4

4) is de eerste letter uit de string gelijk aan de laatste?
Ja : palindroomlengte = 2 + palindroomlengte(string behalve eerste en laatste letter)
Nee : ga naar 5

5) palindroomlengte1 = palindroomlengte(string behalve eerste letter)
palindroomlengte2 = palindroomlengte(string behalve laatste letter)
palindroomlengte = MAX(palindroomlengte1,palindroomlengte2)

bijbehorende code :

code:

unsigned int palinlen(char *sz)
{
  i_recurse++;
  unsigned int i_min = 0;                //laagste index van letter
  unsigned int i_max = strlen(sz);       //hoogste index van letter
  unsigned int i_len = 0,i_len1,i_len2;  //lengte van palindroom

  switch(i_max)
  {
  case 0 : return 0; //Lengte van de string is 0, dus palindroomlengte is 0
  case 1 : return 1; //Lengte van de string is 1, dus palindroomlengte is 1
  case 2 : 
    if (sz[i_min] == sz[i_max - 1])
      return 2;
    else
      return 1;
  default :
    i_max--; //Max index van letter is <stringlengte> - 1
    if (sz[i_min] == sz[i_max]) //Eerste letter = laatste letter
    {
      sz[i_max] = '\0';
      i_len = 2 + palinlen(sz + 1);
    }
    else 
    { 
      char *sz_Temp = strdup(sz);
      sz_Temp[i_max] = '\0';
      i_len1 = palinlen(sz_Temp);
      free(sz_Temp);
      i_len2 = palinlen(sz + 1);
      i_len = MAX(i_len1,i_len2);        
    }
    return i_len;
  }
}

Alleen is dat volgens mij nou precies het algoritme wat Diadem al had

edit:
En JA, natuurlijk kan dit korter/optimaler, ik heb de implementatie met opzet eenvoudig gehouden zodat het algoritme duidelijk blijft

[Soultaker]

Diadem schreef op 25 september 2002 @ 11:05:
Ik heb het algoritme wat ik in de eerste post gaf inmiddels super geoptimaliseerd, maar het is nog steeds hopeloos traag. Ik heb echter ook borganism's algoritme herschreven naar c, en dat werkt als een trein.

De echte optimalisatie zit 'm er in dat je geen dingen dubbel berekent. Als je een cache aanlegt in je functie, waar alle functiewaarden in passen, is 'ie net zo efficient als de iteratieve variant.

code:

int cache[200][201]; // cache initialiseren op -1 

int maxLengte(const char *str, int fst, int len)
{
    if(len == 0) return 0;
    if(len == 1) return 1;
    if(cache[fst][len] >= 0) return cache[fst][len];

    // doe hier het echte werk, met je recursieve aanroep naar maxLengte

    return (cache[fst][len] = <resultaat> );
}

Maar dat is natuurlijk valsspelen.

Hier is wel duidelijk te zien dat het aantal berekening dat uitgevoerd hoeft te worden niet meer dan de helft van de lengte van de string in het kwadraat is. Elke deeloplossing (van een deelstring) wordt immers uniek gekarakteriseerd door de beginpositie in de hoofdstring en de lengte.

Als je er dan in slaagt om een complexer algoritme te vinden dan O(N^2), dan moet je wel dubbel werk aan 't doen zijn.

[Soultaker]

Verwijderd schreef op 25 september 2002 @ 11:44:
Nieuwe poging

En die is correct!

Ik vraag me echter af waarom je zo moeilijk zit te doen met al die stringmanipulatie. De enige strings waar je ooit mee hoeft te werken, zijn de invoerstring en deelstrings daarvan. Je kan dus prima altijd met dezelfde reeks van karakters werken (desnoods zelfs in een globale variabele) en je functie alleen de positie van het eerste en laatste karakter meegeven (of in plaats van het laatste karakter de lengte van de deelstring).

Dat scheelt je ten eerste een hoop stringmanipulatie, ten tweede een aantal dure aanroepen van strlen en ten derde een hoop gereallocceer met strdup. Maar de oplossing en sich is correct, dus ik zal verder niet zeuren.

En JA, natuurlijk kan dit korter/optimaler, ik heb de implementatie met opzet eenvoudig gehouden zodat het algoritme duidelijk blijft

Ik denk dat een efficientieverbetering vaak ook een verbetering in duidelijkheid met zich mee brengt, aangezien de code er korter en overzichterlijk op kan worden (minder regels code is snellere executie; minder variabelen is minder geheugengebruik en waarschijnlijk ook snellere executie).

De 'geoptimaliseerde' variant van jou algoritme is in een regel of 10 te schrijven en bevat voornamelijk de structuur van het algoritme en een stuk minder 'vies werk'.

[Diadem]

Verwijderd schreef op 25 september 2002 @ 11:41:

idd. zie ik zelf ook ineens. Jammer want mijn algoritme gedraagt zich O(n log n).
Terug naar de tekentafel dus

0(n log n) is natuurlijk wel erg mooi. Ik weet niet of het mogelijk is alleen voor dit probleem. De snelste sorteer algoritmes zijn 0(n log n), en dit is een soort van sorteren. Dus misschien kan het, maar ik zou geen algoritme kunnen bedenken.

Dat mag wel, maar niet op de stack idd. Gewoon als volgt doen :

code:

int **maxp;
maxp = (int **)malloc(1000 * sizeof(int *));
for (int i = 0; i < 1000; i++) maxp[i] = (int *)malloc(1000 * sizeof(int));

Dat weet ik, maar daar was ik dus te lui voor

Dan moet het wel goed gaan. Als de maximumlengte van een string overigens 200 letters is kun je hier beter unsigned chars gebruiken (scheelt een factor 4).

Maar als hij max 200 tekens is boeit het toch niet zoveel. 200x200x4b is maar 160kb. Who cares.

Verwijderd schreef op 25 september 2002 @ 11:44:

Alleen is dat volgens mij nou precies het algoritme wat Diadem al had

Niet helemaal. Mijn algoritme werkt als volgt:

1) Als lengte van de string==0, return 0
2) Als lengte van de string==1, return 1
3) Zoek laatst voorkomen van eerste karakter in string.
(noem deze plek pos)
4) Roep jezelf aan als pos>0 (dus als eerst karakter nog een keer voorkomt) op de string tussen 1 en pos-1. Palindroomlengte1 is 2 plus dit.
5) Als pos niet het laatste karakter van de string is roep je jezelf aan met als nieuwe string alles behalve het eerste teken. Dit is palindroomlengte2
6) palindroomlengte = max(palindroomlengte1, palindroomlengte2)

in c:

C++:

char *p; // Bevat te onderzoeken string
int palindroom(int begin, int eind)
{
    int pos, max;
    int terug1=0;
    int terug2=0;

    if (begin>=eind) return 0;
    if (eind-begin==1) return 1;

    for (pos=eind; pos>=begin;pos--)
        if (p[begin]==p[pos])
            break;
    if (pos>begin)
        terug1 = 2 + palindroom(begin+1,pos-1);
    if (pos!=eind)
        terug2 = palindroom(begin+1,eind);
    if (terug1>terug2) max=terug1; else max=terug2;
    if (max<1) max=1;

    return max;
}

[ Voor 0% gewijzigd door Diadem op 25-09-2002 12:18 . Reden: klein foutje verbeterd. ]

[Verwijderd]

Diadem : je vergeet dat
begin = eind : string is lengte 1
begin-eind = 1 : string is lengte 2

[Verwijderd]

Hier dan de geoptimaliseerde versie :

code:

//Gebruik globale variabele g_szPalin, scheelt overhead
//Caching in g_pCache
unsigned int palinlen(unsigned int i_start, unsigned int i_len)
{
  unsigned int i_len1,i_len2;
  switch (i_len)
  {
  case 0 : return 0;
  case 1 : return 1;
  case 2 : return (g_szPalin[i_start] == g_szPalin[i_start + 1]) ? 2 : 1;
  default :
    if (g_pCache[i_start][i_len] != 0xFF) return g_pCache[i_start][i_len];
    else
    {
      i_recurse++;
      if (g_szPalin[i_start] == g_szPalin[i_start + i_len - 1])
      {
        i_len1 = 2 + palinlen(i_start + 1,i_len - 2);
        g_pCache[i_start][i_len] = i_len1;
        return i_len1;
      }
      else
      {
        i_len1 = palinlen(i_start,i_len - 1);
        i_len2 = palinlen(i_start + 1,i_len - 1);
        if (i_len1 > i_len2)
        {
          g_pCache[i_start][i_len] = i_len1;
          return i_len1;
        }
        else
        {
          g_pCache[i_start][i_len] = i_len2;
          return i_len2;
        }
      }
    }
  }
}

[Verwijderd]

Ik post de oplossing maar, in C++ omdat ze dan het elegantste is

C++:

std::size_t paling(const char *str, std::size_t len)
{
    if(len < 2) return len;
    if(str[0] == str[len - 1]) return paling(str + 1, len - 2) + 2;
    return std::max(paling(str, len - 1), paling(str + 1, len - 1));
}

Als je d'r C van wilt maken moet je een eigen max() bakken, met C++ #include <algorithm> doen.

[Verwijderd]

mietje : da's dezelfde oplossing als mijn laatste oplossing. Enige wat ik andes doe is
- cachen uitkomsten
- len = 2 als apart geval beschouwen (dat scheelt onnidige function call overhead)
- de string als globale variabele nemen, dan hoeft het adres niet steeds over de stack geworpen te worden

edit:
wat ik bedoel is dat het algoritme an sich overeenkomt met het jouwe

[Verwijderd]

De echte optimalisatie zit 'm er in dat je geen dingen dubbel berekent. Als je een cache aanlegt in je functie, waar alle functiewaarden in passen, is 'ie net zo efficient als de iteratieve variant.

Niet helemaal, wegens de geringere function call overhead is de iteratieve variant altijd efficienter/sneller. Algoritmisch maakt dat natuurlijk geen zak uit, maar toch. Houd ook rekening met eventuele stack overflows in recursieve functies. Niet dat dat bij een string van 200 letters nou een probleem zal zijn, het is meer in zijn algemeenheid dat recursieve functies niet zo erg best 'schalen'.

[Soultaker]

Verwijderd schreef op 25 september 2002 @ 13:32:
mietje : da's dezelfde oplossing als mijn laatste oplossing. Enige wat ik andes doe is
- cachen uitkomsten

Het doel was geloof ik een recursief algoritme te schrijven, om de 'betekenis' van het probleem helder te krijgen. Als je de resultaten toch cached, kun je net zo goed direct de iteratie variant schrijven (die sowieso beter is).

- len = 2 als apart geval beschouwen (dat scheelt onnidige function call overhead)

Je kunt len = 3 ook wel als apart geval beschouwen - waar houdt het op? Len = 0 en 1 zijn vereist - ik zou er zelf voor kiezen om het daar dan ook bij te houden. Dat is wel zo duidelijk. De overhead mag de compiler proberen wegwerken, al is dat in 't geval van een dergelijke recursieve functie natuurlijk erg moeizaam.

- de string als globale variabele nemen, dan hoeft het adres niet steeds over de stack geworpen te worden

mietje gebruikt de character pointer om aan te geven waar de deelstring begint, zoals jij daarvoor een integer meegeeft. Er wordt hier dus hetzelfde op de stack gezet (aangenomen dat een pointer en een integer/size_t even groot zijn).

Eerlijkheidshalve moet ik bekennen dat ikzelf zowel een pointer als twee integers gepassed had, aangezien ik geen fan ben van globale variabelen, maar dit is eigenlijk een veel mooiere oplossing, aangezien je hier niet meer parameters hebt dan strikt noodzakelijk, zonder een globale variabele te hoeven introduceren.

[Verwijderd]

Verwijderd schreef op 25 september 2002 @ 13:32:
mietje : da's dezelfde oplossing als mijn laatste oplossing. Enige wat ik andes doe is
- cachen uitkomsten
- len = 2 als apart geval beschouwen (dat scheelt onnidige function call overhead)

Mja, het ging mij er om dat je achter het generieke, ongeoptimaliseerde algortime kwam. Dat algemene algoritme kun je dus neerpennen in 3 regels code.

- de string als globale variabele nemen, dan hoeft het adres niet steeds over de stack geworpen te worden

Dit is een non-argument. Door de stringpointer op de stack te zetten geef ik zowel de string als de startindex door. Ik heb dus een variable minder dan jij in gebruik. (Daarom is de C(++) versie eleganter dan oplossingen in de meeste andere talen).

[Diadem]

Deze thread is echt leerzaam.

Als ik nu terugkijk naar het algoritme waarmee ik deze thread begon vraag ik me af hoe ik dat ooit zo heb kunnen schrijven. Maar goed, ik was toen 1 dag bezig met c (plus een paar middagen op universiteit de basis, maar dat telt nauwelijks), dus dat verklaard een hoop.

Dat laatste algoritme van mij is sneller dan dat van mietje. (iteratieve variant uitgezonderd). Mietje's algoritme splitst alleen niet af als het eerste en laatste teken gelijk zijn, iets dat bijna weinig gebeurd. Mijn algoritme splitst daardoor minder vaak. Ik heb daarintegen wel een extra for-lus nodig, maar een for-lus is 0(n) en een splitsing O(2^(n-1)). Dus deze for-lus (en de paar extra tests) is het ruimschoots waard.

Daar komt nog bij dat mijn algoritme bij een splitsing 1 van de 2 takken met meer dan 1 (minimaal 3) zal inkorten.

[Verwijderd]

Diadem>> ik zat ook op jouw oplossing te broeden, maar er zit volgens mij een fout in: je gaat er van uit dat de "buitenste" gelijke karakters altijd tot het langste palindroom leiden, maar dat is niet zo.

Voorbeeld: "abcacb". Als je van jouw algoritme uitgaat is het langst vormbare palindroom 3 karakters lang ("a?a"), terwijl het daadwerkelijk langste palindroom lengte 5 heeft ("bcacb").

[Verwijderd]

Het doel was geloof ik een recursief algoritme te schrijven, om de 'betekenis' van het probleem helder te krijgen. Als je de resultaten toch cached, kun je net zo goed direct de iteratie variant schrijven (die sowieso beter is).

Als het doel was een recursief algoritme te schrijven. En het is nu toch recursief? Als je de caching niet wilt, is dat wel echt HEEL makkelijk uit mijn code te halen hoor... Iteratieve variant omzetten naar recursieve is echt wel ietsje meer werk. Vandaar dat ik ook niet de niet-cachende variant heb gepost...

Je kunt len = 3 ook wel als apart geval beschouwen

Da's waar, maar die is een STUK minder eenvoudig dan len=2. Len=2 is namelijk maar 1 branch, len=3 een boel meer. Dat betekent dus relatief veel extra code en een stuk minder performancevoordeel, wat je bij 2 nog wel hebt, anders wordt de palinlen() nog 3 keer extra aangeroepen.
Ik kies er dus m.b.t. performance dus nadrukkelijk wel voor om len=2 apart te nemen, noodzakelijk is dat natuurlijk niet...

mietje gebruikt de character pointer om aan te geven waar de deelstring begint, zoals jij daarvoor een integer meegeeft. Er wordt hier dus hetzelfde op de stack gezet (aangenomen dat een pointer en een integer/size_t even groot zijn).

ik ben echt aan vakantie toe geloof ik... mijn fout

Dat algemene algoritme kun je dus neerpennen in 3 regels code.

Ja met std::max wel... Maak dan gelijk mylib::palin, kan het in 1 regel
Ben niet zo heel erg bekend met de STL, aangezien dat niet altijd lekker met MFC combineert en ik voornamelijk voor win32 prog (+ beetje OS/2).

[Verwijderd]

Mietje : daarom zit in diadem's algoritme ook dit regeltje :

5) Als pos niet het laatste karakter van de string is roep je jezelf aan met als nieuwe string alles behalve het eerste teken. Dit is palindroomlengte2

[Diadem]

Verwijderd schreef op 25 september 2002 @ 15:06:
Diadem>> ik zat ook op jouw oplossing te broeden, maar er zit volgens mij een fout in: je gaat er van uit dat de "buitenste" gelijke karakters altijd tot het langste palindroom leiden, maar dat is niet zo.

Voorbeeld: "abcacb". Als je van jouw algoritme uitgaat is het langst vormbare palindroom 3 karakters lang ("a?a"), terwijl het daadwerkelijk langste palindroom lengte 5 heeft ("bcacb").

Nee, niet.

Stel je voert "abcacb" in.
Hij zoekt eerst de laatste a op, dat is dus die op positie 3.
Vervolgens doet hij: terug1 = 2 + palindroom(begin+1,pos-1);. Dat komt dus overeen met zichzelf aanroepen met als string "bc".
Daarna merkt hij op dat de laatst gevonden a niet het laatste karakter is van de string, en daarom roept hij zichzelf nog een keer aan: terug2 = palindroom(begin+1,eind);. Dit komt dus overeen met de string "bcacb".

De eerste tak levert inderdaad een palindroom op van lengte 3, de tweede van lengte 5, en deze geeft hij dus door.

Verwijderd schreef op 25 september 2002 @ 12:40:
Diadem : je vergeet dat
begin = eind : string is lengte 1
begin-eind = 1 : string is lengte 2

Je hebt gelijk. Dit moet er bij de laatste versie ingeslopen zijn, want hij werkte eerst wel goed op strings van 0 of 1 tekens. Dit is gelukkig heel simpel te verhelpen door die twee regels aan te passen in:

code:

if (begin>eind) return 0;
if (begin==eind) return 1;

Het programma wordt er nog simpeler van ook

[ Voor 0% gewijzigd door Diadem op 25-09-2002 15:56 . Reden: tekentje weggevallen ]

[Verwijderd]

Hmm klopt, ik heb er overheen gekeken en zat vanuit mijn eigen algoritme te simuleren