Hallo!
Ich stehe vor folgendem Problem:
Ich habe in mehreren Dateien Elemente, die mit IDs belegt sind. Nun darf keine dieser IDs zweimal auftauchen und ich möchte überprüfen, ob das so ist.
Beispieldatensatz 1:
GRID 1
GRID 2
GRID 3
GRID 5
GRID 6
Beispieldatensatz 2:
GRID 7
GRID 8
GRID 9
GRID 1
GRID 4
Mein erster Ansatz war, daß ich einfach alle IDs nacheinander in ein Array (daß ich vorher mit Nullen initialisiert habe) schreibe und dabei prüfe, ob ein Arrayeintrag ungleich Null ist, um dann eine Fehlermeldung zu geben. D.h. für das obige Beispiel: die ID 1 taucht doppelt auf
Das ist allerdings für die weitere Verarbeitung unhandlich, denn es können reichlich Fehlermeldungen kommen, mit denen ich die Anwender dann überfordern würde.
Daher würde ich gerne prüfen, ob es für jede Datei zusammenhängende ID-Bereiche gibt (in unserem Jargon heißen diese GAP-Tabellen).
Ein weiterer Vorteil wäre, daß ich aus vorhandenen GAP-Tabellen zusammenhängende ID-Bereiche identifizieren könnte, die noch unbelegt sind und die ich für neue Datensätze verwenden kann.
Für den 1. Datensatz also: 1 bis 3, 5 bis 6 oder kurz als Array: 1,3,5,6
Für den 2. Datensatz dann: 1, 4, 7 bis 9 oder als Array 1,4,7,9
Dann müßte ich prüfen, ob diese GAP-Tabelle überschneidungsfrei sind und hätte die Anzahl der Fehlermeldungen reduziert ohne Informationen zu verlieren.
Hat jemand eine Idee, wie man das intelligent in einen Algorithmus packt?
Ciao
Bruno
GAP Tabellen
GAP Tabellen
"21" ist nur die halbe Wahrheit...
- Bebu
- Beiträge: 562
- Registriert: Mi Okt 21, 2009 6:19 pm
- Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!
Re: GAP Tabellen
Ich stehe vor einem ähnlichen Problem und arbeite mit der folgenden Lösung: Ich packe alles in ein Array, sortiere es nach dem gesuchten Wert, z. B. mit std::sort und überprüfe dann, ob gleiche Werte nebeneinander liegen. Damit kannst du Überschneidungen in nur einem Durchlauf durch das Array finden. Implementierung kann ich dir keine bieten, daran feile ich selber noch.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!
- Xin
- nur zu Besuch hier
- Beiträge: 8859
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: GAP Tabellen
Die Arrays entsprechen nicht den Datensätzen. Aus dem Array kann ich nicht lesen, ob die 2 und die 8 enthalten sind.Bruno hat geschrieben:Für den 1. Datensatz also: 1 bis 3, 5 bis 6 oder kurz als Array: 1,3,5,6
Für den 2. Datensatz dann: 1, 4, 7 bis 9 oder als Array 1,4,7,9
Du kannst Bäume mit Bereichen in den Knoten verwenden. Ein einzelner Knoten kann den Bereich 2 (2 bis 2) haben und Kinder, die größer bzw. kleiner sind. Bekommst Du 5, 2, 3, 1, 6 geliefert, erstellst Du einen Knoten:Bruno hat geschrieben:Hat jemand eine Idee, wie man das intelligent in einen Algorithmus packt?
5: => (5-5)
2: => (soviel kleiner, dass es nicht vor 5 passt) (5-5)->kleiner(2-2) (wir haben zwei Knoten 5 zeigt auf einen Knoten 2, der kleiner ist)
3: => (soviel kleiner, dass es nicht vor 5 passt) (5-5)->kleiner(2-3)
1: => (soviel kleiner, dass es nicht vor 5 passt) (5-5)->kleiner(1-3)
6: => (soviel größer, dass es genau nach 6 passt ) (5-6)->kleiner(1-3).
4 bekannt?
4 ist kleiner als (5-6). 4 ist größer als (1-3). Es gibt nichts, was größer als (1-3) ist => 4 ist nicht bekannt.
4 einfügen:
4: => Vier passt genau vor 5. (4-6)->kleiner(1-3). Prüfe ob der Knoten, der kleiner ist genau vor die 4 passt. Passt. Kleineren Knoten auflösen, Fertiges Produkt: (1-6)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Re: GAP Tabellen
Hallo!
Beispiel Array: 1,2,3,4,5,7,8,9,10,11,25
Dazu habe ich mich gefragt, wie ich Bereiche von IDs (1-5 und 7-11) von einzeln auftretenden Werten (25) trennen kann.
Meine Idee ist, daß ich ein Array aus Wertepaaren anlege. Sind die zwei Wertepaare ungleich, dann habe ich einen ID-Bereich, ist das Wertepaar gleich, dann einen Einzelwert.
Mit dem Beispiel oben würden sich dann 3 Wertepaare ergeben: 1,5,7,11,25,25
Das mache ich wie folgt:
Damit ich weiß wieviele Wertepaare in dem Array sind definiere ich das als Numlist, d.h. im "nullten" Eintrag steht die Anzahl der Werte.
Das Array sieht dann vollständig so aus:
gap[0]=6
gap[1]=1
gap[2]=5
gap[3]=7
gap[4]=11
gap[5]=25
gap[6]=25
Der Parameter step ist für folgenden Fall da:
Es gibt aus bestimmten prozeßtechnischen Gründen Dateien ("Eigenschaftsdateien"), in denen die IDs in 1000er Schritten vergeben werden (100,200,300,400,500,600,700).
Wäre der step=1, dann würde man hier keinen zusammenhängenden Bereich von 100-700 erkennen, sondern "nur" 7 Einzelwerte.
Da aber vereinbarungsgemäß die "Eigenschaftsdateien" diese 1000er Schritte haben, kann ich für diese mit der gleichen Funktion die GAP-Tabelle erstellen.
Dann muß man "nur" noch prüfen, ob die GAP-Tabelle der einzelnen Dateien überschneidungsfrei sind.
Ciao
Bruno
Letzteres ist mir dann bei näherer Beschäftigung damit auch aufgegangen... und gestern abend hatte ich eine Idee die funktioniert und ich Euch nicht vorenthalten will.Xin hat geschrieben:Die Arrays entsprechen nicht den Datensätzen. Aus dem Array kann ich nicht lesen, ob die 2 und die 8 enthalten sind.Bruno hat geschrieben:Für den 1. Datensatz also: 1 bis 3, 5 bis 6 oder kurz als Array: 1,3,5,6
Für den 2. Datensatz dann: 1, 4, 7 bis 9 oder als Array 1,4,7,9
Beispiel Array: 1,2,3,4,5,7,8,9,10,11,25
Dazu habe ich mich gefragt, wie ich Bereiche von IDs (1-5 und 7-11) von einzeln auftretenden Werten (25) trennen kann.
Meine Idee ist, daß ich ein Array aus Wertepaaren anlege. Sind die zwei Wertepaare ungleich, dann habe ich einen ID-Bereich, ist das Wertepaar gleich, dann einen Einzelwert.
Mit dem Beispiel oben würden sich dann 3 Wertepaare ergeben: 1,5,7,11,25,25
Das mache ich wie folgt:
Code: Alles auswählen
int gaptable(int dim, int *array,int *gap, int step){
int k=1;
int i=0;
for (i=1;i<2*dim;i++){
gap[i]=0;
}
qsort( array, dim, sizeof( int ), cmp );
gap[1]=array[0];i<dim-1;i++){
if (array[i+1] - array[i] != step) {
k++;
gap[k]=array[i];
k++;
gap[k]=array[i+1];
}
}
k++;
gap[k]=array[dim-1];
gap[0]=k;
return (0);
}
Das Array sieht dann vollständig so aus:
gap[0]=6
gap[1]=1
gap[2]=5
gap[3]=7
gap[4]=11
gap[5]=25
gap[6]=25
Der Parameter step ist für folgenden Fall da:
Es gibt aus bestimmten prozeßtechnischen Gründen Dateien ("Eigenschaftsdateien"), in denen die IDs in 1000er Schritten vergeben werden (100,200,300,400,500,600,700).
Wäre der step=1, dann würde man hier keinen zusammenhängenden Bereich von 100-700 erkennen, sondern "nur" 7 Einzelwerte.
Da aber vereinbarungsgemäß die "Eigenschaftsdateien" diese 1000er Schritte haben, kann ich für diese mit der gleichen Funktion die GAP-Tabelle erstellen.
Dann muß man "nur" noch prüfen, ob die GAP-Tabelle der einzelnen Dateien überschneidungsfrei sind.
Ciao
Bruno
"21" ist nur die halbe Wahrheit...
- Xin
- nur zu Besuch hier
- Beiträge: 8859
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: GAP Tabellen
Grundsätzlich spricht nichts gegen Deine Idee, statt eines Baums legst Du eine Liste an.Bruno hat geschrieben:Hallo!
Meine Idee ist, daß ich ein Array aus Wertepaaren anlege. Sind die zwei Wertepaare ungleich, dann habe ich einen ID-Bereich, ist das Wertepaar gleich, dann einen Einzelwert.
Mit dem Beispiel oben würden sich dann 3 Wertepaare ergeben: 1,5,7,11,25,25
Als Informatiker und Entwickler, der sich regelmäßig unfreiwillig mit verkorkstem Code rumärgern darf rate ich Dir DRINGENDST klare Datenstrukturen anzulegen, die Deinen Gedanken abbilden. Also erstelle eine Struktur, die Deine Idee "Datenpaar" abbildet und bilde davon ein Array.
Arrays von int kapiert kein Mensch und Arrays von ints, die in Paaren auftreten sollen, sorgen nur dafür, dass irgendwann mal eins fehlt und damit alles durcheinander kommt.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.