mikrocontroller.net

Forum: PC-Programmierung Mustererkennungsprogramm < 1kB!


Autor: ME (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen

In einem anderen Beitrag auf dieser Seite habe ich einen Link auf diesen 
ganz unterhaltsamen Text gefunden:

http://www.leo.org/information/freizeit/fun/pascal.html

Da wird behauptet:

"Angeblich soll es einem Echten Programmierer sogar gelungen sein, in 
ein paar hundert Byte unbenutzten Speichers innerhalb der Voyager-Sonde 
ein Mustererkennungsprogramm zu pressen, das einen neuenn Mond des 
Jupiters suchte, fand und photographierte."

(siehe: http://www.leo.org/information/freizeit/fun/pascal.html#kap7)

Ist so etwas wirklich möglich bei einer Codelänge < 1 kB?
Oder gehört das einfach zu den sonstigen humoristischen Übertreibungen 
dieses Texts?

Wenn ich sehe wie schon sehr kurze Programme für einfache Probleme bald 
mal ein paar kB brauchen, kann ich das kaum glauben! Aber man weiss ja 
nie, was WIRKLICH TALENTIERTE Leute hinkriegen!

Zum Vergleich: Das Projekt Uhr braucht bereits 746 Bytes.

Autor: User (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man weiß ja nicht, was im benutzten Speicher schon an Funktionen 
vorhanden war.

Autor: Chris L. (kingkernel)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So siehts aus, wenn ich schon alle funktionen habe und nur noch 50 Byte 
+ Stack brauche, um diese funktionen aufzurufen, ist das sehrwohl 
möglich!

Autor: User (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Falls 'Stack' und 'Funktion' überhaupt schon Begriffe für diese 
Prozessoren waren.

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Auch ist unklar, was für Muster überhaupt erkannt werden sollten und ob 
die schon irgendwie vorverarbeitet waren.

> Zum Vergleich: Das Projekt Uhr braucht bereits 746 Bytes.

Das ist aber wahrscheinlich nicht darauf ausgelegt, jedes Byte, auf das 
man irgendwie verzichten kann, einzusparen.

Autor: Sigint 112 (sigint)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sowas geht heute bei Windows gar nicht mehr, weil da schon alleine der 
Header vom EXE-File so groß ist ;-)

Autor: Drachenbändiger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Gast2 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rolf Magnus schrieb:
> Sowas geht heute bei Windows gar nicht mehr, weil da schon alleine der
> Header vom EXE-File so groß ist ;-)

Na zum Glück war damals kein Windows an Bord, sonst wär die Sonde in die 
Sonne geflogen. =)

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> Sowas geht heute bei Windows gar nicht mehr, weil da schon alleine der
>> Header vom EXE-File so groß ist ;-)
>
> Na zum Glück war damals kein Windows an Bord, sonst wär die Sonde in die
> Sonne geflogen. =)

Das hatte sich zwar eher auf den Link von "Sigint 112" bezogen, aber 
jetzt muß ich irgendwie an eine Raumsonde denken, die sich in den Tod 
stürzt, und in der Kapsel ist ein Bildschirm angebracht, auf dem ein 
Bluescreen zu sehen ist ;-)

Autor: Christian R. (supachris)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da die Ammis sich immer noch nicht an das metrische Einheitensystem 
gewöhnen wollen, brauchen die nicht mal Windows, um ihre Sonden zu 
verlieren....

Autor: ME (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Argument mit den fertigen Funktionen überzeugt. Klar: Wenn die alle 
benötigten Funktionen (damals wohl eher Unterprogramme) schon im 
Speicher haben und dann diese nur noch angesprungen werden müssen, 
braucht das wirklich nicht allzu viel zusätzlicher Code.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gast2 schrieb:
> Na zum Glück war damals kein Windows an Bord, sonst wär die Sonde in die
> Sonne geflogen. =)

nee, vorher abgestürzt

Autor: Sigint 112 (sigint)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christian R. schrieb:
> Da die Ammis sich immer noch nicht an das metrische Einheitensystem
> gewöhnen wollen, brauchen die nicht mal Windows, um ihre Sonden zu
> verlieren....

Naja, dafür können wir Europäer nicht zwischen einer Ganzzahl und einer 
Gleitkommazahl unterscheiden. ;-)

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sigint 112 schrieb:
> Christian R. schrieb:
>> Da die Ammis sich immer noch nicht an das metrische Einheitensystem
>> gewöhnen wollen, brauchen die nicht mal Windows, um ihre Sonden zu
>> verlieren....
>
> Naja, dafür können wir Europäer nicht zwischen einer Ganzzahl und einer
> Gleitkommazahl unterscheiden. ;-)

Und verwenden Programme für die eine Rakete in der anderen.

kawwwwwwummmmm

Matthias

Autor: Christian Berger (casandro) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also ein Kilobyte sind doch eigentlich recht viel. Dass das Uhr Projekt 
so viel braucht liegt wohl primär daran, dass es in C geschrieben wurde. 
C ist eine Bloatsprache.

Ich glaube die Kunst darin besteht darin, das richtige Design zu wählen. 
Beispielsweise ist es manchmal sinnvoll, einen Interpreter zu schreiben, 
welcher dann kompakteren Code interpretiert. Das kann zum Beispiel bei 
Zustandsautomaten viel bringen.

Autor: Mark Brandis (markbrandis)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christian Berger schrieb:
> C ist eine Bloatsprache.

Du beliebst zu scherzen. Aktuelle C-Compiler optimieren so gut, dass man 
selbst mit handoptimiertem Assembler selten effizienter ist.

> Ich glaube die Kunst darin besteht darin, das richtige Design zu wählen.
> Beispielsweise ist es manchmal sinnvoll, einen Interpreter zu schreiben,
> welcher dann kompakteren Code interpretiert. Das kann zum Beispiel bei
> Zustandsautomaten viel bringen.

Und der Interpreter plus der kompaktere Code verbrauchen dann zusammen 
weniger Speicher (ich meine damit das fertig kompilierte und ausführbare 
Binary) als eine herkömmliche Lösung? Da würde mich jetzt mal ein 
konkretes Beispiel interessieren. Link please

Autor: Claudio H. (bastelfinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn ich mich recht an meine Bilverarbeitungsvorlesung erinnere, so ist 
das Erkennen eines runden Objektes (Ich gehe mal davon aus, dass der 
Mond als Kreis oder Kreisabschnitt sichtbar war) so ziemlich das 
einfachste, was es an Mustererkennung gibt (wurde glaube ich über die 
Hough-Transformation gelöst). Das war auch der Vorteil bei automatischen 
Andockmaneuvern: Durch die kreisrunde Form ging die automatische 
Erkennung sehr schnell.

Autor: Christian Berger (casandro) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mark Brandis schrieb:
> Und der Interpreter plus der kompaktere Code verbrauchen dann zusammen
> weniger Speicher (ich meine damit das fertig kompilierte und ausführbare
> Binary) als eine herkömmliche Lösung? Da würde mich jetzt mal ein
> konkretes Beispiel interessieren. Link please

Link hab ich hier jetzt nicht, aber stell Dir mal die typische 
"Ampelsteuerung" vor. Einmal "klassisch" Programmiert, und einmal über 
eine Zustandstabelle.
Klassisch hast Du für fast jedes Datenwort was Du ausgibst ein LDI und 
ein OUT, zusätzlich zu einigen IFs um den Zustand zu wechseln. Das 
brauchst Du für jeden Zustand.
Mit einer Zustandstabelle hast Du nur einmal den Code um aus der Tabelle 
die Daten auszulesen und musst am Ende nur noch die Adresse für den 
nächsten Zustand auslesen. Diesen Code brauchst Du nur einmal.

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wenn die Inbterpretersprache nur ein Subset des eigendlichen µCs ist, 
kannst du ein Befehll mit weniger Bytes Codieren, als in asm.
Ab einer Bestimmten größe des interpretierten Codes übersteigt die 
Einsparung die Interpretergröße.

Beispiel:
Angenommen dein Interpreter braucht 1k
und die Instruktionen sind im Schnitt 3 Byte lang (2 Byte befehl + 
eventuell 2 Byte Daten/Adressen)
Dein Bytecode-Interpreter unterstützt aber nicht den vollen Adressraum 
und kommt mit einem Byte pro Befehl aus
macht im Schnitt 1,5 Byte Pro Instruktion

x: Anzahl Instruktionen
ucInstructionlength*x > InterpreterInstructionLength*x + Interpretersize
3*x > 1,5*x + 1024
3x - 1,5x > 1024
1,5x > 1024
x > 683


ab einer codegröße 683 Instruktionen ist dein interpretierter Code 
inklusive Interpreter also kürzer als direkt geschriebener Code

Autor: Christian Berger (casandro) Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, ein anderer Punkt ist wenn Du zum Beispiel eine Stackmaschine mit 
Fließkommazahlen emulierst.
Dann kann aus:
Adressee von A laden
Addresse von B laden
Addresse von C laden
Unterprogramm X aufrufen (oder hier statisch reinschreiben)

einfach ein Byte werden, welches als "Nehme die oberen beiden Werte vom 
Stack und addiere sie" interpretiert wird. Damit kann man schnell sehr 
viel sparen. Und den Fließkommacode bräuchte man ja so oder so.

Autor: Mustererkenner (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie Claudio schon geschrieben hat, müsste man sich erst die Frage 
stellen, welche Art von Mustererkennung werwendet wurde. Es muss noch 
nicht mal das Erkennen von Mustern in Bildern sein, könnten auch ganz 
andere Sensor-Daten sein. Je nachdem wie viel man schon vorher weiss, 
wie ungefähr das Muster aussieht wonach man sucht, kann man den Code 
nochmal reduzieren.

Zitat aus Wikipedia: "Mustererkennungsverfahren befähigen Computer, 
Roboter und andere Maschinen, statt präziser Eingaben auch die weniger 
exakten Signale einer natürlichen Umgebung zu verarbeiten."

Danach kann man sich bestimmt besser vorstellen, dass "Mustererkennung" 
sogar mit weniger als 100 Byte funktionieren kann. ;)

Autor: Helmut Lenzen (helmi1)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe das mal in einem Windowsprogramm gemacht. Mal vom ganzen 
Windows Overhead abgesehen war der eigentliche Suchalgorithmus selbst in 
'C' nur 760 Bytes lang.

Gruss Helmi

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.