Programmierwettbewerb - Palindrome

i_hasser

i_hasser

Grand Admiral Special
Mitglied seit
06.06.2002
Beiträge
18.964
Renomée
85
Standort
IO 0x60
Hi

Thx erstmal @Sargnagel, der die Idee gehabt hat :)

Wir haben ja lange keinen Prog Wettbewerb mehr gehabt, also wirds mal wieder Zeit ;)


Es geht um Palindrome. OTTO und ANNA sind zb. welche, weil die Leserichtung keinen Unterschied macht.
Ziel ist es, solche Palindrome in längeren Ketten herauszusuchen (mit Unterbrechungen). Also sowas zb:

ASDFLKJDSFBALKJSLFDASLDJ

-> DFLLFD wäre das Palindrom

Der einfachste Alg würde einfach jedes Zeichen mit dem Rest der Kette vergleichen, damit läge der Aufwand bei O=n^2.

Ein paar Grundbedingungen brauchen wir auch noch:
- Für eine Ziffer soll es sagen wir 256 verschiedene Möglichkeiten geben (also ein char für eine Ziffer)
- die Kette für Vergleichsbenches muss nach einem bestimmten Muster erzeugt werden, ich werd nachher einen Zufallsgeneratorcode posten der dann mit den selben Startwerten immer die selbe Kette ausspuckt.
- Sagen wir die kürzesten Palindrome sollen 3 Zeichen umfassen, also sowas wie AESFASLDHSAD kommt ein bisschen zu häufig vor und würde den Alg nur zusätzlich belasten (in der Praxis sind eh die längsten Ketten die interessantesten).


Als Sprache kommt natürlich erstmal alles in Frage - egal, ob Java, C, C++, oder was eben gerade da ist. Mit VB braucht ihr aber garnicht erst anzufangen, das ist durchgehend viel zu langsam.


Tja, dann wünsch ich mal fröhliches Programmieren ;) - gesucht ist der schnellste Alg :] ;)
 
So, ich denk da fangen wir mit einer Kette von 1024^2 Ziffern an.



Dabei ist x[n]=((x[n-1]*rx+rc)%rm);

x[0] soll einfach mal 0 sein und die restlichen Werte bleiben konstant.

rx=132;
rc=945;
rm=256;


 
Zuletzt bearbeitet:
Original geschrieben von intel_hasser
Ach ja, nochwas - überlappende Palindrome sind auch gültig, also zb. sowas:

ANABXYKBWOITFBKYXBAXDVMNXMYCBHD

Was da wären

ABXY YXBA und
XYKB BKYX
Zum Vergrößern anklicken....
Hmm??? Das ist aber nur ein einziges Palindrom!
ABXYKB BKYXBA
 
lollerskates.gif


Wenn Du wüßtest, was mir alles "tolles" eingefallen ist, als ich die Palindromsuche das erste Mal implementierte ... meine Güte! *chatt*
 
Tja, jetzt ist mir noch ne sinnvolle Bedingung eingefallen *chatt*

Also die Palindrome müssen genau 1mal getrennt sein (und zwar in der Mitte). Damit fallen auch Palindrome ungerade Länge heraus, wie zb. ABA. Also immer der Form [x0][x1][x2...xn] ... [xn...x2][x1][x0].

Wobei die Länge eines der Teile (und entsprechend auf des anderen Teils) eben 3 nicht unterschreiten darf.
 
Original geschrieben von intel_hasser
Tja, jetzt ist mir noch ne sinnvolle Bedingung eingefallen *chatt*

Also die Palindrome müssen genau 1mal getrennt sein (und zwar in der Mitte). Damit fallen auch Palindrome ungerade Länge heraus, wie zb. ABA. Also immer der Form [x0][x1][x2...xn] ... [xn...x2][x1][x0].

Wobei die Länge eines der Teile (und entsprechend auf des anderen Teils) eben 3 nicht unterschreiten darf.
Zum Vergrößern anklicken....
Hmmm ... was meinst Du mit getrennt? Meinst Du, daß nicht nach klassischen Palindromen (d.h. zusammenhängenden wie OTTO, ANNA) gesucht wird, sondern nur nach den nicht zusammenhängenden? Nach beiden zu suchen, ist sinnvoller. Oder fallen Dir für die nicht zusammenhängenden bessere Optimierungen ein? ;D
Also, sowohl ABCDDCBA als auch ABCXYZCBA sind suchenswerte Palindrome.
 
Moin,
sind das deine bedingungen oder alllgemeine die für ein palindrom gelten, den aba ist eins :), denke ich :].
mfg
 
Original geschrieben von Hannnibal
Moin,
sind das deine bedingungen oder alllgemeine die für ein palindrom gelten, den aba ist eins :), denke ich :].
mfg
Zum Vergrößern anklicken....
Du hast recht. Aber ABA ist statistisch nicht signifikant. Es taucht zu oft auf. Also, warum damit belasten? ;)
 
Ok... mein Alg verdaut auch zusammenhängende Palindrome *g*

Momentan brauch ich für dem Mammut-Teil O=c*n, für einen wesentlich kleineren Teil brauch ich dann O=n^2 oder noch mehr.

Der Source ist aber noch in keinster Weise geschrieben, da werd ich mich nachher vielleicht dranmachen.


PS Sind meine Bedingungen - zumindest ein Teil davon. Ich formuliere die letzte Bedingung mal etwas um:

Alle gefundenen Palindrome müssen sich in 2 Teile die je dem anderen rückwärts gelesen entsprechen zerlegen lassen. Das schließt alle ungerader Länge aus.

Nochmal zu den zusammenhängenden Palindromen: Die sind erlaubt - hatte vorhin nur ein schlechtes Beispiel rausgegriffen.

Also sowas: [...] ABCXY [...] YXCBA [...] XCB [...] enthält 2 Palindrome, nämlich:

ABCXY YXCBA und BCX XCB - es ist egal, dass ein Teil des 2. Palindroms auch in einem Teil des ersten Palindroms enthalten ist.
 
Original geschrieben von intel_hasser
Alle gefundenen Palindrome müssen sich in 2 Teile die je dem anderen rückwärts gelesen entsprechen zerlegen lassen. Das schließt alle ungerader Länge aus.
Zum Vergrößern anklicken....
Könntest Du das noch etwas klarer ausdrücken?

Wie definierst Du Länge? Die Anzahl der einen Hälfte der Buchstaben, die das Palindrom bilden? D.h. Länge von ABCCBA = 3 oder die gesamte Länge = 6?
Mit ungerader Länge meinst Du doch bestimmt eine solche Sequenz: ABCDCBA. Das ist aber nach wie vor ein Palindrom ... nur mit einer Unterbrechung ("D").

Man kann den Begriff Palindrom noch etwas schwammiger fassen:

AXHDABSWFBAILYA

Da steckt auch was nettes drinne. ;)
 
Jup, nämlich Arbeit für die CPU *buck* - dürfte sowas die O=n^4 sein *chatt*

Aus der Aussage folgt, dass Palindrome ungerader Länge nicht berücksichtigt werden - da bleibt doch nur die Gesamtlänge übrig, ein Palindrom mit der Teillänge 3 ließe sich ja in 2 Teile der Länge 3 teilen - Bedingung erfüllt ;)
 
Original geschrieben von intel_hasser
Jup, nämlich Arbeit für die CPU *buck* - dürfte sowas die O=n^4 sein *chatt*
Zum Vergrößern anklicken....
Nö. Bei mir sind das immer noch O((n^2)/2). ;)
Original geschrieben von intel_hasser
Aus der Aussage folgt, dass Palindrome ungerader Länge nicht berücksichtigt werden - da bleibt doch nur die Gesamtlänge übrig, ein Palindrom mit der Teillänge 3 ließe sich ja in 2 Teile der Länge 3 teilen - Bedingung erfüllt ;)
Zum Vergrößern anklicken....
Ok. Das heißt, wenn ich Dich richtig verstehe, werden die Palindrome ungerader Länge (z.B. ABCDCBA) als geteilte Palindrome detektiert. D.h. [ABC] ... [CBA] - gut, dann ist alles klar.
 
Genau :)

ABA oder ABCBA sind dann natürlich ein klein wenig kurz (A A bzw. AB BA), wesswegen die nicht berücksichtigt werden (da die Teile ja je mindestens die Länge 3 haben sollen).


Also ich seh nicht warum mein Alg nicht funktionieren sollte. Die Umsetzung fang ich allerdings erst morgen an.
 
Original geschrieben von intel_hasser
ABA oder ABCBA sind dann natürlich ein klein wenig kurz (A A bzw. AB BA), wesswegen die nicht berücksichtigt werden (da die Teile ja je mindestens die Länge 3 haben sollen).
Zum Vergrößern anklicken....
Darüber braucht man gar nicht streiten. Einfach den Algorithmus anwenden und die statistische Signifikanz dieser mehrteiligen Palindrome untersuchen:
AXHDABSWFBAILYA

*buck*
 
Der Aufwand mit dem einfachsten Alg entspricht ja n^Teileanzahl (da ich für jeden Teil schauen muss ob es einen korrespondierenden Teil gibt).

Der Aufwand für solche Kombinationen ist also etwas höher als sonst ;)
 
Original geschrieben von intel_hasser
Der Aufwand mit dem einfachsten Alg entspricht ja n^Teileanzahl (da ich für jeden Teil schauen muss ob es einen korrespondierenden Teil gibt).

Der Aufwand für solche Kombinationen ist also etwas höher als sonst ;)
Zum Vergrößern anklicken....
Also, ich weiß ja nicht, was Dir für ein Algorithmus vorschwebt, aber bei meinem einfachen Algorithmus ist das alles in den O((n^2)/2) inklusive. Der checkt einfach durch, ob die jeweils korrespondierenden Zeichen der Teilstücke gleich sind. Übersteigt die Anzahl dieser palindromisch angeordneten Zeichen einen gewissen Wert, so wird diese Sequenz als Palindrom erkannt und der Anfangs- und Endpunkt gespeichert.
Die Zeichenfolge ist dabei als Matrix angeordnet. Soll heißen, daß die Sequenz einmal in x- und einmal in y-Richtung aufgetragen ist. Dann werden entlang der Diagonalen von links unten nach rechts oben die Zeichen verglichen. Natürlich wird nur bis zur Mitte der betrachteten Teilsequenz verglichen, da dann dieselbe Zeichenfolge in umgekehrter Reihenfolge folgt.
Selbstverständlich wird alles in einem einzigen Array mit entsprechenden Indizes abgehandelt, die diese matrixartige Anordnung simulieren.
 
Ok, ich bin jetzt von der einfachsten Implementierung ausgegangen - man nimmt das erste Zeichen und geht die Folge von hinten durch - findet man das erste Zeichen irgendwo wieder vergleicht man, ob das 2. Zeichen mit dem nächsten Zeichen von hinten übereinstimmt usw.


Aber Speicherfreundlich ist dein Alg auch nicht gerade - bei der 1024^2 Kettenvorgabe macht das ja 1024^4 Zeichen die du speichern musst, oder eben 1TB.

hmmm... mein Alg dürfte für 1024^2 Zeichen... hmmm... puh, das ist garnet so einfach - hängt von der Kette ab.

Im Worst Case dürften 787456 Byte an Verwaltungsdaten + (der Speicherplatz für die Kette)*4 Byte draufgehen.

Also bei der 1024^2 Kette 4.75MB. Die Verwaltungsdaten sind übrigens fix für jede Kette - aber auch für den Worst Case, bestenfalls nehmen die Verwaltungsdaten weniger als 1kb ein.



So, ich geh jetzt ins Bett :)
 
Original geschrieben von intel_hasser
Aber Speicherfreundlich ist dein Alg auch nicht gerade - bei der 1024^2 Kettenvorgabe macht das ja 1024^4 Zeichen die du speichern musst, oder eben 1TB.
Zum Vergrößern anklicken....
Nein, die Matrix wird ja nur mittels Indizes, die auf einem 1D-Array operieren, simuliert (s.o.). Gespeichert werden nur die Start- und Endposition eines gefundenen Palindromes. Ich habe mir da schon Gedanken gemacht, denn bei nur 256MB RAM muß man knauserig sein. Die gefundenen Palindrome in ~13MB Protein-Sequenzen belegten ca. 85 MB Speicher. Aber es kommt da ganz auf die Filter an, durch die man die gefundenen Palindrome jagt.
Für weitergehende Statistiken muß ich dann zwar immer wieder in die Sequenzen an die abgespeicherte Position springen und das Palindrom untersuchen, aber das ist bei dem geringen RAM leider nicht anders möglich und dennoch erstaunlich performant.
Original geschrieben von intel_hasser
So, ich geh jetzt ins Bett :)
Zum Vergrößern anklicken....
dito
 
Tag allerseits :)

Auch wenn ich fast alles, was nach dem ersten Post kam nicht mehr verstehe, mach ich diesmal auch mit ;)

Könnte vielleicht jemand mal einen Text erstellen und hier posten mit der benötigten Zeit und den allen Palindromen die drin sind?
Interessiert mich noch, wieviel langsamer ich bin als ihr und ob mein Programm mit einer grösseren Anzahl Palindromen zurechtkommt ;)
 
Hallo,

warte einfach ab, bis intel_hasser seinen Zufallsgenerator gepostet hat, der mit demselben Startwert immer dieselbe Zeichenkette generiert. Für bestimmte Eingaben können wir dann vielleicht mal Listen aller enthaltenen Palindrome posten (hoffentlich bleiben die Listen klein genug), um den eigenen Algorithmus zu überprüfen.
 
Original geschrieben von intel_hasser
So, ich denk da fangen wir mit einer Kette von 1024^2 Ziffern an.



Dabei ist x[n]=((x[n-1]*rx+rc)%rm);

x[0] soll einfach mal 0 sein und die restlichen Werte bleiben konstant.

rx=132;
rc=945;
rm=256;
Zum Vergrößern anklicken....

;)

Also ~1 Millionen Zeichen gibts, der Alg steht ja auch dabei.

Wir können ja noch eine Testkette mit 10'000 Zeichen nehmen.
 
Klingt gut. Aber wolltest Du nicht noch einen "kleinen" Zufallsgenerator zur Verfügung stellen? Oder habe ich ihn übersehen?

P.S.: Ich bin erst in ein paar Stunden wieder hier ... Haupt- u. Nebenrechner umbauen und alles neu installieren ... *ächz* ... bis später.
 
Hab gestern den halben Tag an meinem Server gesessen - ich kanns mir vorstellen :P

Das oben ist ja schon der Alg für den Zufallsgenerator. Musst du nur noch in einer Schleife einpacken, also so hier ungefähr:

Code: 
int *x;
x=malloc(sizeof(int)*1024*1024);

x[0]=0;

rx=132;
rc=945;
rm=256;

int i;

for(i=1;i<1024*1024;i++) x[i]=(x[i-1]*rx+rc)%rm;

Das erzeugt immer die selbe Zufallsliste.
 
Zuletzt bearbeitet:
hmmm hab heute leider wieder keine Zeit - schon wieder ein Referat am Hals :(

Morgen kann ich aber definitiv ein bisschen was machen ;D - hab in meinem Alg noch immer keinen Fehler gefunden ;)... ich hab schon wieder dieses Fingerjucken :]
 

Ähnliche Themen

PuckPoltergeist
Vorbereitung - Programmierung Linksammlung
Antworten
0
Aufrufe
20K
PuckPoltergeist
PuckPoltergeist
D
Was ich so bei meiner Hotline erlebte...
Antworten
7
Aufrufe
2K
Dr. Zoidberg [np]
Dr. Zoidberg [np]
Nero24
Config-Guide: AMD und die Stabilität - wir räumen auf
Antworten
0
Aufrufe
75K
Nero24
Nero24
Zurück
Oben Unten