Hallo,
ich habe gestern eine Lösung programmiert, die mir in einem kleinen
Array (512 Elemente) die Anzahl verschiedener Zahlen ausgeben soll. Ziel
war es wiederkehrende Muster zu erkennen. Ich bin immer noch dabei mein
"Game of Life" zu optimieren und eine statistische Auswertung des Feldes
zu machen.
Typischer Fall:
16....20....45...5...16....20....45...5 als 4er Wiederhol Muster was
immer weiter läuft aber die zahlen können auch deutlich größer werden.
Wertebereich der Zahlen 16 Bit
Mir fiel nur die Lösung ein einen verschwenderischen 64k grossen Array
aufzumachen und die Vorkommnisse der Zahlen dann in dem jeweiligen
Tabellenfeld zu addieren.
for .....
zaehlung[array[zahl]]++;
In einem zweiten Lauf schaue ich wieviele Felder > 0 sind und habe damit
die Anzahl verschiedener Zahlen. Bei wiederkehrenden Muster sinkt diese
ab bis sie schliesslich konstant bleibt.
Wie würden es die Profis machen?
512 Elemente, davon jedes beliebig zwischen 0 - 0xffff.
Christian J. schrieb:> Mir fiel nur die Lösung ein einen verschwenderischen 64k grossen Array> aufzumachen
Das ist sicher nicht die schlechteste Idee. 64k sind auf einem PC nicht
viel.
> und die Vorkommnisse der Zahlen dann in dem jeweiligen> Tabellenfeld zu addieren.
Statt eines Zählers genügt ein Bool-Wert: Zahl kommt vor / kommt nicht
vor.
> In einem zweiten Lauf schaue ich wieviele Felder > 0 sind und habe damit> die Anzahl verschiedener Zahlen. Bei wiederkehrenden Muster sinkt diese
Das kannst du schon im ersten Durchlauf machen: Jedesmal, wenn der
Bool-Wert für eine Zahl von False auf True wechselt, wird die Anzahl
verschiedener Zahlen inkrementiert.
Speichersparender, aber nicht ganz so laufzeiteffizient wäre die
Verwendung einer auf einem Binärbaum basierende Mengendatenstruktur
(Set), wie sie in der Standardbibliothek der meisten Programmiersprachen
enthalten ist. Das funktioniert auch dann noch gut, wenn du es statt
16-Bit- mit 32-Bit-Zahlen zu tun hast.
Yalu X. schrieb:> Speichersparender, aber nicht ganz so laufzeiteffizient wäre die> Verwendung einer auf einem Binärbaum basierende Mengendatenstruktur> (Set), wie sie in der Standardbibliothek der meisten Programmiersprachen> enthalten ist. Das funktioniert auch dann noch gut, wenn du es statt> 16-Bit- mit 32-Bit-Zahlen zu tun hast.
Die Idee ist gut, muss ich mir mal anschauen. Ist allerdings kein PC
sondern meine Z80 "Kiste". Ich dachte mir, dass es vielleicht Lösungen
gibt, die pfiffig sind und speichersparend aber ums Zaehlen kommt man
wohl nicht herum.
Ob Bool "BITSET" oder "INC" ist eigentlich egal, beides kostet das
Gleiche an Zeit.
Mir schwebt da noch vor den Array zu kopieren, da dieser nicht verändert
werden darf und von außen als Ringpuffer gefüttert wird. und dann von 0
an durchzulaufen, 0 als referenz, dann Feld 1,2,3... und die
Wiederholungen "abzustreichen". Die 0 kommt nie vor, daher könnte man
die als Marke nehmen.
Jedes Abstreichen würde mitgezaehlt für die Referenzzahl auf Feld 0. Mit
fortschreitendem Durchlaufen entstehen immer mehr 0 Felder, die
übergangen werden.
Stift, Papier.... ich muss mal eben ein "UML" machen :-)
Christian J. schrieb:> Ob Bool "BITSET" oder "INC" ist eigentlich egal, beides kostet das> Gleiche an Zeit.
... aber unterschiedlich viel Speicher. Bei 512 Eingabewerten braucht
man mindestens 10 Bits (d.h. 2 Bytes) für die Zähler, während man bei
Bool-Werte mit 1 Byte oder sogar 1 Bit auskommt.
> Mir schwebt da noch vor den Array zu kopieren, da dieser nicht verändert> werden darf und von außen als Ringpuffer gefüttert wird. und dann von 0> an durchzulaufen, 0 als referenz, dann Feld 1,2,3... und die> Wiederholungen "abzustreichen".
Das hat die Zeitkomplexität O(n^2), wenn n die Anzahl der Eingabewerte
ist. Die Lösung mit dem Binärbaum geht in O(n·log n). Man könnte das
Array auch kopieren, sortieren und anschließend die Sprünge in der
sortierten Folge zählen, was ebenfalls O(n·log n) braucht.
Da n nach oben (auf 512) begrenzt ist, kann es aber duchaus sein, dass
sich in der Praxis ein O(n²)-Algorithmus besser schlägt als ein anderer
mit O(n·log n).
Edit:
Die Idee mit dem Sortieren hatte auch schon K.M.
K.M. schrieb:> Sortieren (qsort etc.) und danach in einem linearen Lauf über den sort.> Vektor gehen: Ist Zahl != vohergehender Zahl, Zähler um eins erhöhen.
Super Idee! Da ich Code sparen muss (max 16kb EPROM, 11kb sind schon
voll) würde ich qs aber nicht nehmen, sondern ein Bubble Sort was
einfacher ist. Geschwindigkeit ist egal.
Yalu X. schrieb:> Das hier sieht sehr interessant aus:>> http://stackoverflow.com/questions/1532819/algorit...
Interesante Doktorarbeit aber man müsste erst herausfinden, was davon
richtig ist was fehlerhaft. Die Coddes sind teilweise nicht trivial.
Element in array[1] will be compared with array[0]. If they are
different, then value in array[NewLength] will be modified with array[1]
and increment NewLength. If they are same, NewLength will not be modifie
Das scheint mir ganz clever zu sein. NewLength zb auf 512 setzen und für
jeden erfolgreichen Vergleich um 1 erniedrigen. Am Schluss entspricht
NewLenght der Anzahl verschiedener Werte.
Christian J. schrieb:> Wie würden es die Profis machen?
Keine Ahnung - bin keiner.
Bisher habe ich Dein Problem noch nicht verstanden. Irgendwo
fallen 16bit-Ganzzahlen an, und Du möchtest jetzt wissen,
wie viele unterschiedliche Werte vorkommen. Ist das richtig?
> 512 Elemente, davon jedes beliebig zwischen 0 - 0xffff.
Prinzipskizze:
- Liste mit allen auftretenden Zahlen anlegen
- Liste sortieren
- Liste durchmustern, bei jeder Änderung Zähler erhöhen
Den Code hier verstehe ich nicht ganz, so eine for Schleife habe ich
noch nie gesehen, C macht es wohl möglich, dass da alles drin geht.
current = array + 1
Was bewirkt das? array ist für sich selbst ein Pointer die array[0].
current zeigt dann auf array[1] ?
void rmdup(int *array, int length)
{
int *current , *end = array + length - 1;
for ( current = array + 1; array < end; array++, current = array + 1
)
{
while ( current <= end )
{
if ( *current == *array )
{
*current = *end--;
}
else
{
current++;
}
}
}
}
Zum Verständnis:
Manche machen Kreuzworträtsel, ich knoble lieber Software Sachen aus. Es
gehgt um die Abbruchbedingung wann das "Game of Live" einen Zustand
erreicht hat, wo es entweder statisch ist oder nur noch "Blinker"
auftreten oder "Gleiter". All diese End-Muster haben eines gemeinsam,
nämlich dass sich die Anzahl der Veränderungen (das delta) von einem
Zustand N nach N+1 stetig wiederholt. Ich habe den Z80 tagelang rechnen
lassen und Tabellen auf dem PC abspeichern, wo diese Werte drin sind. Es
gibt Muster, die nur 2 Zyklen haben oder solche mit 3 oder 4.
Und diese Zyklik will ich erkennen. Ihr Merkmal ist, dass immer wieder
die gleiche "Anzahl Modifikationen" in einem Vektor auftritt, der
mitschreibt. Im Rush-Hour Zustand kommt keine Zahl mehr als 1 Mal vor,
erst der End Zustand erzeugt diese Zykliken oder Stillstand.
Es macht Spass sich darüber ein wenig Gedanken zu machen, wie ich das
einem Computer beibringen kann. Uwe Beger hier, der die STM32 Seite
betreut, war schon "angesteckt" dass er das auf dem STM32F429 Disco
Board mit LCD sehr schön realisiert hat.
Der verlinkte Stackoverflow ist für den Z80 denke ich zu teuer. (Für die
Aufgabenstellung zu kompliziert vielleicht auch)
Eine andere Idee:
Einmal über dein großes Array laufen. Im Array enthaltene Zahlen werden
einem zweiten (kleineren) Array hinzugefügt, wenn die Zahl dort noch
nicht enthalten war.
Das zweite Array startet zu Beginn leer, es wird sortiert gehalten,
Zahlen werden per Insert-Sort eingefügt (d.h. alle größeren Zahlen eins
nach oben geschoben)
Das ist nicht so teuer wie es klingt:
- feststellen, ob eine Zahl enthalten ist geht per
Intervallhalbierungsverfahren im kleinen (teilgefüllten) Array
- Zahlen hinzufügen muss man nicht so oft
Bei der Idee, eine mögliche Periodizität zu finden musste ich an die
Autokorrelationsfunktion denken.
Tilo Renz schrieb:> Einmal über dein großes Array laufen. Im Array enthaltene Zahlen werden> einem zweiten (kleineren) Array hinzugefügt, wenn die Zahl dort noch> nicht enthalten war.
Frage ist wieviel Schritte dazu nötig sind. Ein Computer sieht ja nicht
das ganze Bild wie der Mensch sondern muss immer erst nachschauen. Das
mit dem zweiten Array wo alle Zahlen reinkommen habe ich auch schon
angedacht.
Ich brauche die Zahlen nachher nicht, nur wieviele es sind. Kleiner 4
verschiedene ist Abruch. Der Z80 "rennt" mit 0,5 Mips (hust) bei bis zu
20 Zyklen pro Befehl.
512 ist nicht viel, ich kann das auch kleiner machen. Bubblesort läuft
da dann n*m drüber und sortiert mir das durch. BS ist einfach, langsam
und verbraucht nicht viel Code. Zweiter Durchlauf "vergleiche N mit
N+1".
Im absoluten Extrem (wozu es einige Dokotoren und Professoren brauchte)
wird das im SETI Projekt durchgeführt, wo genau diese Musterkennung auf
Milliarden von Werten angewendet wird. Das übesteigt aber mein problem
bei weitem.
Christian J. schrieb:> Und diese Zyklik will ich erkennen. [...]
Das verstehe ich.
> Im Rush-Hour Zustand kommt keine Zahl mehr als 1 Mal vor,
Ja, eben.
Du hast das Problem meiner Meinung nach von einer ungünstigen
Seite her formuliert. Solange eine Liste mit N Zahlen nämlich
nur verschiedene Zahlen enthält, ist die Länge der Liste
(=Anzahl der Listenelemente) genau gleich der Anzahl
unterschiedlicher Werte. (Das ist ja eine Tautologie.)
Wenn Du jetzt eine weitere, N+1te Zahl betrachtest, können
zwei Fälle eintreten:
a) die neue Zahl steht noch nicht in der Liste.
Dann kannst Du sie an die Liste anhängen, und die Liste
enthält wieder nur unterschiedliche Werte.
b) die neue Zahl steht schon in der Liste.
Im Fall b) weisst Du folgendes:
- Du hast einen Zyklus gefunden.
- Die Kette vom 1. Listenelement bis zum ersten Auftreten der
Zahl ist die Zustandsfolge, die nur einmal durchlaufen wird.
- Der Teil vom ersten Auftreten der Zahl bis zum Listenende ist
der Zyklus.
> erst der End Zustand erzeugt diese Zykliken oder Stillstand.
Richtig.
Es ist nie erforderlich, zu zählen, wie oft irgendwas auftritt.
Im Gegenteil: Wenn eine Zahl das zweite Mal auftritt, bist Du
fertig - dann weisst Du alles, was sich wissen lässt.
Possetitjel schrieb:> Richtig.> Es ist nie erforderlich, zu zählen, wie oft irgendwas auftritt.> Im Gegenteil: Wenn eine Zahl das zweite Mal auftritt, bist Du> fertig - dann weisst Du alles, was sich wissen lässt.
Nein, nicht ganz. Es kommt immer mal wieder vor, dass zwei Bilder die
gleiche Anzahl Modifikationen haben. Aktuell zaehle ich 512 Generationen
mit. Eine Zyklik ist nicht so ganz einfach zu erkennen. Es kann ja auch
eine unscharfe Zyklik geben, wo man einer daneben ist.
Ich bin hier grad unter Knoppix drin, weil ich ein Backup laufen lasse
was noch 3h dauert, daher kkann ich kein Video nach youtube laden aber
dann würde ich zeigen können was ich meine.
Guck dir, wenn Interesse mal bei youtube ein GOL Bild an. Nicht diese
Designer Dinger, sondern was normales. Das wuselt erst richtig rum, dann
wird es immer weniger und irgendwann ist Ende. Nur noch Inseln und
Blinker.
Auf dem STM32 LCD mit 160 Mhz sehr schön zu sehen, weil der deutlich
fixer rechnet als der Z80.
Ich packs mal hier drunter, einen Thread ist es nicht wert.
Das ist alter Code von mir, 6 jahre oder so. Vermutlich habe ich da aber
was von irgendwoher kopiert, da ich dieses Konstrukt nicht kenne.
for (p = str,i = 0; i != zeit->wtag && *p; i++) {
while(*p++ !=0 );
}
Hier wird aus einem const Array ein String heraus gesucht. Die for
Schleife ist als solche kaum mehr zu erkennen finde ich.
Reicht da nicht einfach ein
sprintf(lcdbuf[0],"Tag: %s", str[zeit->wtag]);
wenn man den str als 2D Feld auslegt und Kommas zwischen die Tage macht?
Also str[8][]= {"Sonntag","Montag",....)
Oder ist da mal jemand ganz schlau gewesen und hat heraus gefunden dass
diese Lösung effizienterb ist? 2D Arrays sind nicht grad code sparend
wegen der Offsets..
????
Kann das nicht ausprobieren grad aber ist das überhaupt guter Coding
Style, das mit der For Schleife?
Gruss,
Christian
1
// Dieser Struct liegt im Battery RAM und enthält die aktuelle Zeit
Eine Datenstruktur die nur unterschiedliche Werte enthält nennt man
allgemein ein Set. Oft als Hashset implementiert, oder über einen Baum.
Eine Einfügeoperation in ein Set gibt normalerweise zurück ob der Wert
schon vorhanden war oder neu ist.
Man könnte sich jetzt einen gleitenden Mittelwert über die letzten 5 /
10 / 20 Werte vorstellen (Ringspeicher), der angibt wie viele dieser
Werte Doubletten waren. Übersteigt dieser Wert einen Schwellwert, dann
ist man in dem Bereich angekommen wo nichts neues mehr passiert.
Christian J. schrieb:> so eine for Schleife habe ich> noch nie gesehen
Es wird mit Pointern gearbeitet.
current zeigt auf die Startadresse +1
und array auf Startadresse.
Bei jedem Durchlauf werden array und current um eins inkrementiert.
Wobei in der while-Schleife dies auch passiert und auch end
dekrementiert wird.
Es werde Duplikate gesucht und gelöscht.
