GAP Tabellen

[Bruno]

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

[Bebu]

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.

[Xin]

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

Die Arrays entsprechen nicht den Datensätzen. Aus dem Array kann ich nicht lesen, ob die 2 und die 8 enthalten sind.

Hat jemand eine Idee, wie man das intelligent in einen Algorithmus packt?

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:
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)

[Bruno]

Hallo!

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

Die Arrays entsprechen nicht den Datensätzen. Aus dem Array kann ich nicht lesen, ob die 2 und die 8 enthalten sind.

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.

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);
}

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

[Xin]

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

Grundsätzlich spricht nichts gegen Deine Idee, statt eines Baums legst Du eine Liste an.

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.