mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Duplikate in einem array finden


Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Programmiere gerade einen ATmega8 in c und suche einer 
schnellstmöglichen Methode, in einem Array aus n Elementen die 
Duplikate los zu werden, d.h. das  array soll letztendlich jeden Wert 
nur noch einmal enthalten.

Kennt da jemand eine vorteilhaftere Methode als ein paar mal eine 
Schleife durchlaufen zu lassen?
Ist bei vorherigem Sortieren der Werte der Gesamtaufwand eventuell 
kleiner ?

Autor: SiMa (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn die Werte schon sortiert sind, musst Du natürlich nur einmal durchs 
Array. Wenn Du aber sortierst, kannst Du schon beim Sortieren die 
Duplikate rauswerfen

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit nem schnellen Algorithmus sortieren und dann einmal durchlaufen und 
die Duplikate entfernen. Geht auch anders ist aber (aus dem Bauch raus) 
bestimmt langsamer.

Ah da faellt mir ein: Modifizier den Algorithmus gleich so dass er keine 
Duplikate speichert, is noch schneller ;)

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke schon einmal für die Antworten.

Eine Sortierung ist nicht zwingend notwendig, nur interessant, wenn es 
Geschwindigkeitsvorteile beim auffinden von Duplikaten bringt.

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ah da faellt mir ein: Modifizier den Algorithmus gleich so dass er keine
>Duplikate speichert, is noch schneller ;)

klatsch
Logisch, das wäre eventuell auch eine eine Möglichkeit. Brett vorm Kopf 
:)

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Falls Du keinen weiteren Speicherplatz zur Verfügung hast:

  Zwei Schleifen mit Indices i,j, i!=j:
    a(i)==a(j) => mehrfaches Vorkommen

  (hat aber O(n*n) Rechenaufwand, ist also nicht rechenoptimal, aber
  speicheroptimal!)

sonst:

  "erzeuge" zweites Array B mit gleicher Anzahl Elemente wie Dein
  Array A, aber speichere in dieses die Indices von 0..n-1

  Fasse nun die Elemente von Array A und B zusammen: (a,i), wobei a
  aus A, i aus B ist

  Definiere Grösser-Operator:
    (a1,i1) > (a2,i2) falls (a1 > a2) oder (a1 == a2 und i1 > i2)

  Sortiere nun die so zusammengefassten Elemente mittels
  Grösser-Operator

  Dann musst Du nur noch durch das Array laufen und testen, ob
  benachbarte Elemente (a1,i1),(a2,i2) mit a1==a2 existieren
  => mehrfaches Vorkommen!!!

  Falls Du die ursprüngliche Reihenfolge wieder herstellen möchtest:
  die steht im Array B in Form der Indices

  (hat O(n*log(n)) Rechenaufwand, ist also rechenoptimal, aber
  diesmal NICHT speicheroptimal!)

Autor: Professor (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mehr Input zu den Randbedingungen, bitte!

  - Welcher Wertebereich der Elemente im Array?
  - In-Place-Algorithmus?
  - Größenordnung des Arrays?
  - Zur Verfügung stehender Arbeitsspeicher während des Algorithmus?

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.