3. list oder vector oder array oder ???

list oder vector oder array oder ???

  • Y

    Hallo,
    leider ist mir kein prägnanterer Titel eingefallen 😉
    Also, mein Problem ist, dass ich zwei Datensätze mit je einem x- und einem y-Wert habe.
    Ich muß diese beiden Datensätze vergleichen und um Unterschiede herauszufinden, die Differenz bilden. Es handelt sich um zwei Meßreihen mit je ca. 7000 Datenpunkten. Leider können die x-Werte unterschiedlich sein (es können zusätzliche Werte auftreten aber auch welche fehlen), so daß ich nicht einfach zwei Arrays anlegen und dann die Werte pro Position voneinander abziehen kann.
    Ich muß also eigentlich zwei Listen durchlaufen, schauen, ob die x-Werte übereinstimmen, wenn ja, dann einfach diesen Wert übernehmen und die zugehörigen y-Werte voneinander subtrahieren, wenn nein, dann den 'speziellen' x- mit seinem y-Wert an die richtige Position einfügen. 🙄
    Ich muß also suchen, sortieren und das Ganze soll natürlich möglichst schnell gehen.
    Welche Lösung haltet ihr da für am Besten 😕

    Ich hoffe, ich habe mich einigermaßen verständlich ausgedrückt 🙂

    Viele Grüße
    Yvonne

    0
  • G

    Füge doch einfach in jede Struktur alle x-Werte der anderen mit entsprechend interpoliertem y ein.

    Dazu würde ich die eine (doppeltverkettete, sortierte) linked-List empfehlen.

    0
  • J

    Frage:
    Du schreibst es können Werte zusätzlich auftreten oder Fehlen. Heisst das, beide
    Messreihen haben nicht die gleiche Anzahl von Werten zum Vergleich, oder füllst du
    fehlende Werte mit "Default"-Einträgen auf. 😕

    Du kannst auch für konventionelle arrays "STL-Sort" verwenden. Aber, da die Anzahl
    der Werte, falls ich richtig verstanden habe, nicht von vornherein festliegt, solltest
    du dennoch keinen array verwenden. Da du deine Elemente ausschliesslich ans Ende
    anfügst, Sortierung anschliessend, halte vector für die passende Lösung.

    :xmas1:

    mfg JJ

    0
  • Y

    Danke für den Vorschlag. Gibt es eine linked-list schon als template oder ist es besser diese komplett selber zu schreiben?
    Gibt es noch andere Vorschläge?
    Grüße
    Yvonne

    0
  • Y

    Ach ja, noch etwas...
    Die Daten liegen als 2-spaltige 'Tabelle' im .dat oder .txt -Format vor.
    Welchen 'Einlesestream' verwende ich am Besten für dieses Format?
    ???
    :xmas1:

    Grüße
    Yvonne

    0
  • G

    Yvonne schrieb:

    Danke für den Vorschlag. Gibt es eine linked-list schon als template oder ist es besser diese komplett selber zu schreiben?
    Gibt es noch andere Vorschläge?
    Grüße
    Yvonne

    include <list>

list<x_und_y> lala
    0
  • G

    Yvonne schrieb:

    Die Daten liegen als 2-spaltige 'Tabelle' im .dat oder .txt -Format vor.

    Wie sehen denn die Daten aus?

    222.33 324
    223.11 323
    .
    .
    .

    0
  • J

    Wie schon gesagt, wenn du nur ans Ende/Anfang anfügst ist ein vector schneller als
    eine list.

    mfg JJ

    0
  • P

    Yvonne schrieb:

    Ach ja, noch etwas...
    Die Daten liegen als 2-spaltige 'Tabelle' im .dat oder .txt -Format vor.
    Welchen 'Einlesestream' verwende ich am Besten für dieses Format?

    Wie wärs mit ifstream? 😉

    0
  • G

    John Doe schrieb:

    Wie schon gesagt, wenn du nur ans Ende/Anfang anfügst ist ein vector schneller als
    eine list.

    mfg JJ

    Aber die Aufgabe verlangt es ja gerade, sortiert einzufügen ⚠

    0
  • J

    Was glaubst du wohl was schneller ist.
    1.) alle Einträge einfügen und anschliessend (einmalig) sortieren oder.
    2.) alle Einträge einzeln sortiert einzufügen.

    Ich dachte Geschwindigkeit sei das Hauptkriterium. 😕

    mfg JJ

    0
  • G

    John Doe schrieb:

    Was glaubst du wohl was schneller ist.
    1.) alle Einträge einfügen und anschliessend (einmalig) sortieren oder.

    Es muss ja nach jedem Einfügen sortiert werden. Die beiden Nearest-Neighbors jedes beliebigen x-Wertes müssen ja schnell interpoliert werden. Wenn du jetzt zwischen einem alten und einem eingefügten Punkt interoplieren willst, muss der eingefügte natürlich richtig einsortiert sein.

    BSP.

    1 2 7 8 9
    3 4 5

    sollen "verschmolzen" werden.

    3 einfügen (y von 3 wird aud 2 u. 7 interpoliert)
    1 2 3 7 8 9

    4 einfügen...
    -> Spätestens hier muss die Liste wieder sortiert sein.

    Ein Array und ein einfaches Sortierverfahren (Bubblesort, bloss nicht Quicksort) nach jedem Schritt wäre eine Alternative.

    0
  • J

    Ich glaub wir verstehen die Aufgabe irgendwie nicht gleich. 🙂
    Bis zur Klärung des Problems zieh ich mich hiermit zurück 😃 😃

    mfg JJ

    0
  • Y

    Um alle Unklarheiten zu beseitigen (hoffentlich)...
    Es handelt sich z.B. um folgende Datensätze (die tatsächlich ungleich lang sein können):
    1.Datensatz:
    100.0 0.5
    100.5 1.0
    101.1 2.3
    101.7 3.0

    2.Datensatz:
    100.0 0.3
    100.3 0.7
    101.4 2.0

    Das ergibt z.B. 1.Datensatz minus 2.Datensatz:
    100.0 0.2
    100.3 -0.7
    100.5 1.0
    101.1 2.3
    101.4 -2.0
    101.7 3.0

    Ich hoffe, damit ist die Problemstellung klar.
    Vielen Dank, dass meine Frage hier so umfangreich diskutiert wird.

    Zu dem ifstream-Vorschlag:
    Habe zwar mit anderen Programmiersprachen schon etwas Erfahrung, aber mit C++ leider noch relativ wenig.
    Dachte ifstream liest nur einzelne char's ein, oder liege ich da falsch 😕

    Grüße
    Yvonne

    0
  • ?

    John Doe schrieb:

    Wie schon gesagt, wenn du nur ans Ende/Anfang anfügst ist ein vector schneller als
    eine list.

    mfg JJ

    Auuu, einfügen in einen vector am Anfang ist so ziemlich das langsamste was es gibt. Was du willst ist eine std::deque.

    0
  • Y

    zu list:
    list<x_und_y> lala

    ist das so gedacht
    list<float float> ???

    zu deque:
    wo finde ich ein Beispiel dazu außer im MSDN (finde ich nicht so ergiebig)?

    Grüße
    Yvonne

    0
  • Y

    Noch eine Anfängerfrage 🙄
    wie bekomme ich die Zitate anderer eigentlich in so schöne Kästchen?
    😉

    0
  • G

    Yvonne schrieb:

    Noch eine Anfängerfrage 🙄
    wie bekomme ich die Zitate anderer eigentlich in so schöne Kästchen?
    😉

    Einfach auf "Zitieren" geklickt und fertig.

    zu "x_und_y" damit meine ich eine Datenstruktur, z.B. eine Klasse oder auch ein struct:

    struct x_und_y {
	int x, y;
};

    x_und_y samplepoint;

    samplepoint.x = 22;
    samplepoint.y = 11;

    Edit: du wirst aber wohl eher eine Klasse "SamplePoint" brauchen, die auch eine Sortierreihenfolge definiert...

    0
  • P

    Yvonne schrieb:

    Zu dem ifstream-Vorschlag:
    Habe zwar mit anderen Programmiersprachen schon etwas Erfahrung, aber mit C++ leider noch relativ wenig.
    Dachte ifstream liest nur einzelne char's ein, oder liege ich da falsch

    Ja, liegst du 😉 ifstream kann nicht nur einzelne Zeichen einlesen sondern auch komplette Zeilen.

    0
  • V

    Informationen allgemein zur STL:

    http://www.sgi.com/tech/stl/stl_index.html

    Speziell deque:

    http://www.sgi.com/tech/stl/Deque.html

    mfg
    v R

    0
Anmelden zum Antworten