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 :-)
Sortieren (qsort etc.) und danach in einem linearen Lauf über den sort. Vektor gehen: Ist Zahl != vohergehender Zahl, Zähler um eins erhöhen.
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.
:
Bearbeitet durch Moderator
Das hier sieht sehr interessant aus: http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array/1533667#1533667
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
Christian J. schrieb: > K.M. schrieb: > >> Sortieren (qsort etc.) Ahh! Wurde schon zweimal vorgeschlagen. Zu spät gesehen
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 |
2 | // Battery RAM ist nur 32 Bit ansprechbar. |
3 | typedef struct |
4 | {
|
5 | uint32_t stunde, |
6 | minute, |
7 | sekunde, |
8 | tag, |
9 | monat, |
10 | jahr, |
11 | wtag, |
12 | jahrtag; |
13 | } zeit_t; |
14 | |
15 | |
16 | |
17 | // Anzeige einer Digitaluhr + Datum |
18 | // Def. zeit_t: rtc.c |
19 | void LCD_Uhrzeit_2(zeit_t *zeit) |
20 | {
|
21 | static const char str[] = "Sonntag\0" "Montag\0" "Dienstag\0" "Mittwoch\0" "Donnerstag\0" "Freitag\0" "Samstag\0" ; |
22 | |
23 | const char *p; |
24 | uint32_t i; |
25 | |
26 | // Lege p-Pointer auf das i.te Element |
27 | |
28 | for (p = str,i = 0; i != zeit->wtag && *p; i++) {
|
29 | while(*p++ !=0 ); |
30 | } |
31 | |
32 | sprintf(lcdbuf[0],"Tag: %s", p); |
33 | LCD_Write(); |
34 | } |
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.
:
Bearbeitet durch User
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.