Datenvergleich in Fortran 95 < Fortran < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:36 Mo 28.02.2005 | | Autor: | blops |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe folgendes Problem. Zwei Datensaetze mit den gleichen Daten nur in unterschiedlicher Reihenfolge. Jetzt moechte ich wissen, ob eine der Daten fehlt und wenn eine fehlt welche fehlt. ich kann das nur programmieren,wenn die daten in gleicher Reihenfolge aufgefuehrt sind, das ist aber nicht das was ich wissen will, weil mir dann angezeigt wird das eine daten fehlt, obwohl sie gar nicht fehlt sondern an anderer stelle steht.
ich hoffe ihr versteht mein problem und es kann mir jemand helfen.
danke schonmal fuer die muehe.
babsi
|
|
| |
|
Hallo blops!
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> Ich habe folgendes Problem. Zwei Datensaetze mit den
> gleichen Daten nur in unterschiedlicher Reihenfolge. Jetzt
> moechte ich wissen, ob eine der Daten fehlt und wenn eine
> fehlt welche fehlt. ich kann das nur programmieren,wenn die
> daten in gleicher Reihenfolge aufgefuehrt sind, das ist
> aber nicht das was ich wissen will, weil mir dann angezeigt
> wird das eine daten fehlt, obwohl sie gar nicht fehlt
> sondern an anderer stelle steht.
> ich hoffe ihr versteht mein problem und es kann mir jemand
> helfen.
Also, so ganz sicher bin ich mir nicht, ob ich dich richtig verstehe...
Ich würde es naiv so programmieren: du nimmst das erste Datum der ersten Reihenfolge und suchst es einfach in der zweiten Reihenfolge. Ist es nicht vorhanden, so weißt du bereits, dass eins fehlt, ist es vorhanden nimmst du das zweite der ersten Reihenfolge und suchst die zweite Reihenfolge wieder komplett durch, usw.
Das ist sicher nicht die beste Möglichkeit, aber die erste, die mir einfiel.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:38 Mo 28.02.2005 | | Autor: | Lizard |
Also, wenn du nicht die bereits vorgeschlagene "naive" Version mit [mm] n^2 [/mm] Vergleichen durchführen willst, sehe ich eigentlich nur die Option, beide "Datensätze" (was auch immer das genau sein soll) mit dem gleichen Verfahren zu sortieren, und die Ergebnisse dann schrittweise zu vergleichen. Ich setze einfach mal voraus, daß einer der beiden Datensätze kanonisch ist, also alle erforderlichen Daten beinhaltet - wäre es anders, müsstest du beide Datensätze (voneinander unabhängig) mit einem dritten Satz vergleichen, der alle Daten enthält. Tust du dies nicht, ist das Szenario vorstellbar, daß irgendein Attribut (oder so, das hängt von deinen Daten ab) bei beiden Datensätzen fehlt, und du dessen Fehlen so überhaupt nicht feststellen kannst (da du Fehlen ja dann definiert hättest als "ist im einen Datensatz enthalten, aber im anderen nicht"). OK?
Das ganze geht dann in $O(n [mm] \log [/mm] n)$, ist also asymptotisch schneller als die Version mit [mm] \Theta(n^2) [/mm] Vergleichen.
Wenn du immer noch Probleme hast, oder das nicht so ganz nachvollziehen kannst, schreib vielleicht mal etwas genauer, was dein Problem ist. Möglicherweise können wir dann besser helfen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:07 Mo 28.02.2005 | | Autor: | blops |
ok, also, ich beschreibe mal genauer.
datensatz 1: datensatz 2:
ARD01 ARD01
MDR02 RTL02
PRO07 ZDF03
RTL02 MDR02
ZDF03 PRO07
usw. usw.
jetzt sind in beiden datensaetzen die gleichen daten nur in unterschiedlicher reihenfolge. was jetzt bei mir passiert an diesem beispiel ist, es fehlen alle daten bis auf die erste, weil ja nur die erste stelle gleich ist. ich moechte aber, dass er mir angibt, dass diese datensaetze gleich sind. und ausserdem moechte ich, dass wenn das nicht so waere, wenn also eine fehlen wuerde, dass wer mir das auch sagt.
vielen vielen dank fuer eure antworten, haette ja nicht gedacht, dass das so schnell geht.
babsi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:21 Mo 28.02.2005 | | Autor: | Lizard |
Hallo,
> datensatz 1: datensatz 2:
> ARD01 ARD01
> MDR02 RTL02
> PRO07 ZDF03
> RTL02 MDR02
> ZDF03 PRO07
> usw. usw.
>
> jetzt sind in beiden datensaetzen die gleichen daten nur in
> unterschiedlicher reihenfolge.
Gut. Bei meiner Lösung würdest du jetzt beide Datensätze zunächst sortieren (mit einem Sortieralgorithmus deiner Wahl; Quicksort ist zum Beispiel gut geeignet und sollte auch bekannt sein - wenn nicht, googlen oder Forum anschauen, gab neulich eine Frage dazu). Dann erhältst du bei lexikographischer Sortierung, d.h. nach Anfangsbuchstabe:
datensatz 1: datensatz 2:
ARD01 ARD01
MDR02 MDR02
PRO07 PRO07
RTL02 RTL02
ZDF03 ZDF03
usw. usw.
Nun gehst du beide Datensätze durch und vergleichst jeweils die Elemente. Dabei hilft dir die folgende Beobachtung: Sind zwei Elemente nicht gleich, dann ist das "fehlende" Element genau das mit der niedrigeren Ordnung. Dazu ein Beispiel: Wir nehmen an, in Datensatz 2 fehlt MDR02:
datensatz 1: datensatz 2:
ARD01 ARD01
MDR02 PRO07
PRO07
Wir vergleichen zunächst ARD01 und ARD01 - in Ordnung, beide gleich. Dann vergleichen wir MDR02 und PRO07 - es tritt ein Fehler auf, irgendetwas stimmt hier nicht. Wir vergleichen also die beiden gefundenen Elemente, und stellen fest: M kommt im Alphabet vor P, also gilt "MDR02 < PRO07" (bildhaft gesprochen). Wir notieren also: MDR02 fehlt in Datensatz 2. Nun merken wir uns die Stelle in Datensatz 2, an der PRO07 steht, und gehen in Datensatz 1 weiter - es wäre ja denkbar, daß die "Lücke" größer ist, also mehr als ein Element fehlt. Wir vergleichen das nächste Element vom Datensatz 1 mit PRO07 aus Datensatz 2 und erhalten: PRO07 = PRO07. Damit ist die Lücke wieder geschlossen, und wir können festhalten, daß MDR02 das einzige Element war, das in Datensatz 2 gefehlt hat.
Zwei andere Situationen hätten auftreten können: Wir hätten eine "vergrößerte" Lücke erhalten können, also der Anfangsbuchstabe vom nächsten Element in Datensatz 1 hätte immer noch kleiner sein können als das P von PRO07 - oder wir hätten eine Lücke in Datensatz 1 feststellen können. Dies wäre entsprechend der Fall gewesen, wenn auf einmal der Anfangsbuchstabe des nächsten Elements von Datensatz 1 größer als P gewesen wäre. Das sollte soweit hoffentlich klar sein, oder?
> und ausserdem moechte ich, dass wenn das nicht so
> waere, wenn also eine fehlen wuerde, dass wer mir das auch
> sagt.
Bei diesem Ansatz hast du das gegeben, allerdings nur partiell - wenn ein Element in beiden Datensätzen fehlt, gibt es keine Möglichkeit, das festzustellen. Ich weiß nicht, ob das bei dir relevant ist, aber falls ja, bleibt dir nur noch, einen dritten Datensatz anzulegen, in dem alle potentiell annehmbaren Werte stehen, und deine anderen Datensätze dagegen abzugleichen. Sollte dann aber auch nicht mehr wirklich ein Problem darstellen.
> vielen vielen dank fuer eure antworten, haette ja nicht
> gedacht, dass das so schnell geht.
Gern geschehen, dafür hat man ja Ferien ;)
|
|
|
|
