Warenkorb
0 Artikel | US$ 0,00
ID 7228
Korduan, Peter: Flächenverschneidung in GIS - Effizienzbetrachtung und stochastische
Modellierung
Hamburg: Diplomica GmbH, 2003
Zugl.: Technische Universität Berlin, Technische Universität, Diplomarbeit, 1997
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2003
Printed in Germany
3
Inhaltsverzeichnis Seite
1. Einleitung
1
1.1. Motivation
1
1.2 . Aufgabenstellung
1
1.3. Allgemeines
1
2. Datenstrukturen und Algorithmen
2
2.1. Speichertechniken
2
2.1.1. Lineare Felder
3
2.1.2. Mehrfach gekettete Speicherung
5
2.1.3. Dateispeicherung
5
2.1.4. Zwischen Unix und DOS
7
2.2. Zugriff auf Daten
7
2.2.1. Zugriff über Adressen
8
2.2.2. Suchalgorithmen
8
2.3. Sortieren von Daten
9
2.4. Relationale Datenstrukturen und Graphen
10
2.5. Raum - und Zeitkomplexität
12
2.5.1. Zeitkomplexität von Matrizenoperationen
12
2.5.2. Raumkomplexitäten der Matrizen beim VFG
14
3. Flächenverschneidung
23
3.1. Funktionales Modell
23
3.2. Methoden zur flächenhaften Findung von Schnittpunkten
24
3.2.1. Brut Force Methode
24
3.2.2. Uniform Grid Methode
24
4. Varianzfortpflanzung
24
4.1. Allgemeines
24
4.2. Stochastische Modelle
25
4.2.1. Best Case
26
4.2.2. Average Case
26
4.2.3. Worst Case
26
4.2.4. Kovarianzmodellierung
26
4.3. Besetzungsstrukturen der Matrizen und nötige Relationen
27
4.3.1. Funktionsmatrix F
28
4.3.2. Kovarianzmatrix der Ausgangspunkte
XX
Best Case
30
4.3.3. Matrix der Kovarianzen zwischen den Ausgangspunkten und den Schnittpunkten
F
XX
33
4.3.4. Kovarianzmatrix der Schnittpunkte
YY
35
5. Ableitungen der Schnittpunktkoordinaten nach den Punktkoordinaten
37
5.1. Formeln mit zyklischer Vertauschung
37
5.2. Formeln ohne zyklische Vertauschung
38
5.2.1. Sonderfall
39
6. Beschreibung der im Programm verwendeten Datentypen und
Algorithmen 40
6.1. Implementierte Datenstrukturen
40
6.1.1. Speicherung im Arbeitsspeicher
40
6.1.2. Speicherung in Dateien
44
6.2. Datenschnittstelle und Typen
49
6.3. Erzeugung des Beispieldatensatzes
49
6.3.1. Netzparameter
49
4
6.3.2. Dreiecksnetz
50
6.3.3. Wabennetz
50
6.4. Findung der Schnittpunkte
50
6.4.1. Aufstellen der Segmente-in-Zellen-Liste
50
6.4.2. Aufstellen der Schnittpunkt-Liste
51
6.5. Fehlerfortpflanzung Best Case
52
6.5.1. Datenextraktion
52
6.5.2. Aufstellen der Liste CovPS
54
6.5.3. Aufstellen der Liste CovSS
55
6.6. Fehlerrechnung Average Case
57
6.6.1. Datenextraktion
58
6.6.2. Aufstellen der Liste CovPP
58
6.6.3. Aufstellen der Liste CovPS
59
6.6.4. Aufstellen der Liste CovSS
60
6.7. Fehlerrechnung Worst Case
60
6.7.1. Aufstellen der Liste CovPP
60
6.7.2. Aufstellen der Liste CovPS
60
6.7.3. Aufstellen der Liste CovSS
60
6.8. Beschreibung des Viewers
60
6.8.1. Grafik der verschnittenen Flächen und Fehlerellipsen
60
6.8.2. Anzeige der Besetzungsstrukturen der Matrizen
61
7. Analyse der Laufzeiten und der Speicherbelegung
61
7.1. Konzept zur Ermittlung von Abhängigkeiten
61
7.2. Laufzeitanalyse
62
8. Zusammenfassung
66
9. Schlußbemerkung
67
10. Anlage A
68
Polygonnetze für die Flächenverschneidung
68
11. Anlage B
75
Besetzungsstrukturen von Matrizen bei der Varianzfortpflanzung
75
12. Anlage C
86
Approximierte Funktionen der Laufzeiten bei Speicherung im Arbeitsspeicher
86
Approximierte Funktionen der Laufzeiten bei Speicherung in Dateien
87
Literaturverzeichnis 90
1
1. Einleitung
1.1. Motivation
Geo-Informationssysteme sind seit geraumer Zeit in vieler Munde. Viele Bestrebungen sind in
Gang gesetzt worden, um alles mögliche in digitaler Form zu erfassen. Geo-Informationssysteme
werden in Zukunft einen großen Teil, der sonst noch manuell erstellten Arbeiten, an Raumdaten
ersetzen. Ist die Erfassung der Daten erst einmal abgeschlossen, wird damit begonnen, neue
Daten zu produzieren, aufzuarbeiten und darzustellen. Dabei werden Analysefunktionen
verwendet, die für den Bearbeiter auf Grund seiner Komplexität und Massenhaftigkeit nicht
mehr nachvollziehbar sein werden.
Die raumbezogenen Daten sind Meßgrößen. Jeder weiß, daß solche Größen immer fehlerbehaftet
sind. Bei der Gewinnung von neuen Informationen aus diesen fehlerbehafteten Daten übertragen
sich natürlich auch die Fehler. Um zunächst erst einmal Aussagen über die Qualität der
Ausgangsdaten in einem GIS treffen zu können, ist die Kenngröße Genauigkeit mit in den
Datenbestand aufzunehmen.
Es kann auch keine Aussage über die Qualität des Analyseergebnisses getroffen werden, wenn
man nicht weiß, wie sich die Fehler und in welchen Größenordnungen übertragen.
Diese beiden Dinge, also Genauigkeit von geometrischen Objekten und die Fehlerfortpflanzung
bei Datenanalysen sind wesentliche Voraussetzung für Qualitätsangaben in raumbezogenen
Informationssystemen.
Leider existieren keine GIS-Produkte auf dem kommerziellen Markt, die diese Aspekte
durchgreifend verwirklichen.
Zum einen liegt das daran, daß sich die Datenmengen bei mitgeführter Genauigkeit mehr als
verdoppeln würden, zum anderen, daß die herkömmlichen Algorithmen zur Berechnung der
Fehlerfortpflanzung sehr viel Zeit brauchen, die ganze Angelegenheit also uneffektiv zu sein
scheint.
Geodäten sind bekannt dafür, Meßgrößen hinsichtlich ihrer Genauigkeit zu beurteilen.
Ergebnisse ohne Genauigkeitsbetrachtung sind für ihn nicht aussagekräftig.
In der Zeit der schnellen Entwicklung der Computertechnik darf es nicht versäumt werden
diesen Aspekt von Seiten der Geodäsie und Photogrammetrie mit in Informationssysteme
einzubringen.
Noch befinden sich einige Konzepte für GIS in der Entwicklungsphase. Sind GIS aber überall
am Laufen, besteht auf Grund der Kosten kaum noch eine Möglichkeit zur Umstellung der
Software.
Ist ein Geoinformationssystem nicht in der Lage, Genauigkeiten zu erfassen und zu verarbeiten,
kann es keine sicheren und vertrauenswürdigen Ergebnisse erzielen.
1.2 . Aufgabenstellung
Am Beispiel der wichtigen Analysefunktion Flächenverschneidung soll gezeigt werden, daß es
bei sinnvoller Speicherung und angepaßten Algorithmen möglich ist, Fehlerfortpflanzung für
große Datenmengen effektiv zu berechnen.
Es soll ein Programm in der Programmiersprache C++ geschrieben werden, in welchem
effiziente Algorithmen für die Varianzfortpflanzung bei der Flächenverschneidung und
geeignete Visualisierungen für die Ergebnisse implementiert werden sollen.
1.3. Allgemeines
Zu Beginn der Arbeit wird ein Überblick über Datenstrukturen und Algorithmen gegeben. Dann
wird die Problematik der Flächenverschneidung erörtert. Anschließend werden stochastische
Modelle für die Flächenverschneidung vorgestellt, die entsprechenden Besetzungsstrukturen der
2
vorkommenden Matrizen beschrieben und Formeln für die Ableitung der
Schnittpunktkoordinaten nach den beteiligten Polygonpunktkoordinaten hergeleitet. In einem
nächsten Abschnitt wird die Implementation geeigneter Algorithmen in das Programm
"
VFGCUTAS
"
beschrieben und begründet. Eine Analyse der Laufzeiten und der
Speicherbelegung soll die Wirksamkeit der verwendeten Algorithmen herausstellen und
Schlußfolgerungen ermöglichen.
Wenn in dieser Arbeit von
"
dem oder das Programm
"
die Rede ist, wird damit das Programm
"
VFGCUTAS
"
gemeint.
Zur Abarbeitung größerer Datenmengen mit PC´s wurde zusätzlich zu
"
VFGCUTAS
"
ein
modifiziertes Programm erstellt, welches die verwendeten Daten und Ergebnisse ausschließlich
in Dateien speichert und davon zugreift. Dieses führt die Bezeichnung
"
VFGCUTDA
"
. Elemente
einer Matrix, die ungleich Null sind, sollen Nicht-Null-Elemente heißen und werden mit NNE
abgekürzt. Der Begriff Kovarianzmatrix wird verwendet für die Matrix, die Varianzen,
Kovarianzen sowie Kreuzkovarianzen enthält.
2. Datenstrukturen und Algorithmen
Strukturen sind die Beziehungen zwischen einzelnen Elementen einer Gruppe.
Ein Algorithmus ist eine Folge von definierten Schritten zur Lösung eines bestimmten Problems.
Jeder Algorithmus setzt eine bestimmte Datenstruktur voraus. Da die Wahl der Datenstruktur
von mehreren Faktoren abhängig ist, wie die Art der Daten und Häufigkeit der auszuführenden
Operationen, kann nicht in jedem Fall sichergestellt werden, daß der effizienteste Algorithmus
verwendet werden kann.
Es ist in jedem Fall ein Abwägen zwischen Speicherplatzbedarf und Rechenzeit erforderlich.
/Lipsch/
Aus diesem Grund wird hier zunächst auf verschiedene Speicherstrukturen sowie auf Zugriffs-
und Suchalgorithmen eingegangen.
2.1. Speichertechniken
Zur Untersuchung der Speicherung und Benutzung von Datenstrukturen mit Computern ist es
nach [Mau] zweckmäßig, von einem idealisierten Speicher auszugehen. Jede Zelle eines solchen
Speichers zerfällt in zwei Teile, den Datenteil und die Relationsteile . Der Datenteil dient zur
Speicherung des Wertes eines Knotens. Ein Relationsteil kann zur Realisierung einer Relation
verwendet werden, in dem er z.B. die Nachfolger des Knotens im Bezug auf die Relation
speichert.
Ein Speicher besteht aus einer endlichen Anzahl von Zellen, die von 1 bis n durchnumeriert sind.
Die Nummer einer Zelle heißt Adresse . Der Wert eines Relationsteiles ist ein Tupel von ganzen
Zahlen. Der Wert eins Datenteils ist ein Tupel von Zeichenfolgen.
Eine Datenstruktur heißt gespeichert, wenn jedem Knoten umkehrbar eindeutig eine Zelle
zugewiesen ist.
Eine Menge von aufeinanderfolgenden Zellen heißt Speicherbereich .
Relationen zwischen Datenzellen werden sequentiell oder gekettet realisiert. Bei sequentieller
Relation mit Schrittweite s sind aufeinanderfolgende Knoten in Zellen gespeichert, deren
Adressen sich um s unterscheiden. Bei geketteter Realisierung gibt der Relationsteil eines
Knotens die Adressen aller Nachfolger an.
Zur graphischen Darstellung von Zellen werden Rechtecke gezeichnet, die je nach Anzahl der
Relationen in Segmente verschiedener Anzahl unterteilt sind. In der Mitte befindet sich der
Wert des Knotens, an den Seiten Adressen zu den Nachfolgern bzw. Vorgängern entsprechend
den Relationen. Rechtecksegmente können auch mit Namen versehen werden, die dann außen
dazugeschrieben werden. Zur Realisierung einer Zelle, mit einem Daten- oder Relationenteil,
welcher aus mehreren Werten besteht, wird auch oft die indirekte Speicherung gewählt. Dabei
werden die Werte auf mehrere Zellen mit nur einem Wert im Datenteil verteilt.[Mau]
3
2.1.1. Lineare Felder
Es treten oft Datenbestände auf, bei denen der einzige Zusammenhang zwischen den Knoten
darin besteht, daß jeder Knoten mit Ausnahme des Endknotens genau einen Nachfolger hat.
Solche Strukturen werden lineare Felder genannt.
G r a p h i s c h e D a r s te l l u n g e i n e s l i n e a r e n F e l d e s
1 . K n o te n
i . K n o te n
n .K o te n
F i g . 2 .1 .1 .
Bei der Bearbeitung von linearen Feldern treten folgende Operationen häufig auf:
- Ein Knoten mit einer bestimmten Eigenschaft finden
- Den i-te Knoten eines linearen Feldes ist zu finden
- Einen weiteren Knoten vor oder nach einem gegebenen Knoten einfügen
- Entfernen eines gegebenen Knotens aus dem linearen Feld
- Umordnen eines gegebenen Knotens nach einer vorgegebenen Folge
Bei der Auswahl der Speichermethode für ein lineares Feld müssen folgende Fragen beantwortet
werden:
- Wie oft werden die Operationen ausgeführt?
- Wie schnell sollen die Operationen durchgeführt werden?
- Wie groß ist der zu erwartende Speicherbedarf?
Bei geketteter Speicherung zeigt der Endknoten zumeist auf Null, zusätzlich werden oft
Anfangs- und Endzeiger verwendet und ein sogenannter Ordnungszähler in einer Zelle
abgespeichert, der die Anzahl der Knoten enthält.
Sequentielle Speicherung
Die sequentielle Speicherung erfordert einen zusammenhängenden Speicherbereich, bei dem die
Zellen nacheinander angeordnet sind. Dadurch, daß die Adressen der einzelnen Zellen mit
gleicher Schrittweite aufsteigend sind, läßt sich ein Knoten sehr leicht über eine Ordnungszahl
finden und auf ihn zugreifen.
Adressen
FF02 FF04 FF06 FF08 FF0A
Speicherinhalt
4 122
51 68 11
Anfang der Liste
Ende der Liste
Fig.2.1.2. Liste in sequentieller Speicherung
Um sich so einen Block im Speicher zu reservieren, bietet C++ zwei Möglichkeiten. Zum einen
läßt sich ein Block von angegebener Größe reservieren, zum anderen läßt sich ein Block
zusätzlich noch mit Nullen initialisieren. Ist ein Block reserviert, kann er auch im nachhinein mit
einer dritten Funktion in der Größe verändert werden. Es ist also eine dynamische Erweiterung
des sequentiellen Speicherbereiches während der Laufzeit des Programmes möglich.
Soll ein Block um weitere Speicherplätze erweitert werden, prüft die entsprechende Funktion
zunächst, ob im Anschluß an die letzte reservierte Zelle noch freier Speicher zur Verfügung
steht. Ist dies nicht der Fall, wird ein neuer zusammenhängender freier Block im gesamten
Speicher gesucht. Ist er gefunden wird er reserviert, die Daten aus dem alten Bereich in den
neuen in der gleichen Anordnung übernommen und der alte Block für andere Reservierungen
freigegeben.
4
Ist die zu speichernde Datenmenge während der Laufzeit ansteigend, und muß zwischen zwei
Speicherblockerweiterungen für andere Variablen oder Blöcke Speicherplatz jeweils am Ende
des zu erweiternden Blockes reserviert werden, führt das dazu, daß immer an aufsteigenden
Adreßbereichen neuer Speicher belegt wird und der alte Bereich nicht mehr für die Erweiterung
der Datenmenge zur Verfügung steht.
Soll z.B. ein 100 Zellen großer alter Block um nur eine Zelle erweitert werden, wird ein neuer
Block mit 101 Plätzen belegt. Der alte Bereich, der freigegeben wurde, steht aber auf Grund
seiner geringeren Größe nicht mehr für neue größere Blöcke zur Verfügung und es sind 201
Plätze des Speichers verbraucht.
Bei großen Datenmengen ist der Platz dann sehr schnell verbraucht und der auszuführende
dynamische Algorithmus kann nicht erfolgreich durchgeführt werden.
Es liegen sozusagen zu viele Speicherbereiche auf Grund ihrer Größe brach. In diesem
Zusammenhang wird auch von Fragmentierung des Speichers gesprochen.
Dieser Nachteil der sequentiellen Speicherung kann aufgehoben werden, wenn vorher die Menge
der zu speichernden Daten ermittelt wird. Das führt zu einer Erhöhung der Rechenzeit. Im Fall
der Flächenverschneidung müßte der gesamte Algorithmus für die Schnittpunktfindung einmal
nur für die Bestimmung der Anzahl vorkommender Schnittpunkte durchgeführt werden, oder
beim Einlesen von Daten aus einer Datei müßte zweimal gelesen werden, einmal um die
Elemente zu zählen und einmal um sie in den Speicherbereich von bestimmter Größe zu
schreiben.
Die Rechenzeitvergrößerung durch solche Abzählaktionen ist proportional zur Datenmenge. Da
der gesamte Algorithmus der Flächenverschneidung in Größenordnungen um O(n²) läuft, kann
dies vernachlässigt werden.
Es ändert sich lediglich der Faktor der Zeitkomplexität, nicht die Klasse.
Ein zweiter Ausweg besteht darin, auf die gekettete Speicherung überzugehen. Das geht aber
auch mit dem Verlust der sonstigen Vorteile der sequentiellen Speicherung einher, insbesondere
geht das zu Lasten der Zugriffszeiten auf Elemente der Liste.
Variiert die Größe der zu reservierenden Blöcke, ist zwar auch mit einer gewissen
Fragmentierung zu rechnen, aber die fällt im Verhältnis zu oben genanntem Problem gering aus.
Neu reservierte Speicherblöcke werden dann nicht grundsätzlich hinten angehängt, sondern es
wird auch vorher freigegebener Speicherbereich wiederverwendet.
Gekettete Speicherung
Fig.2.1.3. zeigt eine einfach gekettete Liste. Diese Art von Speicherung besteht aus Zellen, die
über den gesamten Speicherbereich verteilt sein können. Die Verbindung zwischen den Zellen
sind über Adressen hergestellt. Bei jedem Datenelement ist die Adresse des Nachfolgers mit
abgespeichert.
FF02
15DF
F016
2
F016
67
FD08
15
13B2
Listenanfang
FD08
13B2
7
NULL
17
15DF
Listenende
Fig. 2.1.3 . Einfach gekettete Liste
Der Zugriff auf ein Datenelement kann hier nicht direkt über seine Position erfolgen, sondern
erfolgt durch Suche. Werden die Daten nur in der Reihenfolge gelesen wie sie gespeichert
wurden, fällt der Nachteil der Suche weg. Die Liste wird nacheinander durchlaufen.
5
Diese Datenstruktur verbraucht durch die Speicherung der Adressen der Nachfolger mehr
Speicherplatz. Der Bedarf steigt um n
sizeof(Adresse). Die Fragmentierung des
Arbeitsspeichers ist jedoch geringer, weil mehr kleine Speicherbereiche genutzt werden.
Das Einfügen, Löschen sowie das Umordnen von Listenelementen ist mit geketteten Listen
besser als mit sequentiellen durchzuführen.
2.1.2. Mehrfach gekettete Speicherung
Vorteile für Zugriffsoperationen können zusätzliche Verknüpfungen zwischen den
Datenelementen sein. Solche Listen heißen mehrfach verkettet.
Es besteht auch die Möglichkeit, Matrizen mit Hilfe mehrfach geketteter Listen abzuspeichern.
Matrixelement Zeilenindex
Zeiger auf nächstes
Element in Spalte
Spaltenindex Zeiger
auf
nächstes Element in
Zeile
Fig.2.1.4. Struktur eines Matrixelementes in einer mehrfach geketteten Speicherform
Zur Speicherung einer schwach besetzten Matrix wird in /Lewis/ S.190 angenommen, daß ein
Element 2 Speicherworte lang ist. Es wird angegeben, daß die Dichte einer n x n Matrix 0.5 ist.
Da die Dichte in einer linearen Liste 1 ist, liegt die Rentabilitätsgrenze bei 50% der dünn
besetzten Matrix. Allgemein gilt für die Rentabilitätsgrenze R einer mehrfach geketteten Liste
mit der Dichte D für eine dünn besetzte Matrix :
R = D
n²
Weiterhin sind nach /Lewis/ Prozeduren auf dünn besetzte Matrizen, die als gekettete Listen
implementiert sind, komplex und zeitaufwendig. Es sollten Strukturen mit hoher Dichte
verwendet werden, wenn der Speicherplatz begrenzt ist.
2.1.3. Dateispeicherung
Die Speicherung von Daten in Dateien kann binär oder im Textformat erfolgen. Daten, die in
Dateien gespeichert sind, sind physisch außerhalb des Arbeitsspeichers und sind deshalb bei
entsprechender Organisation auch nach der Laufzeit eines Programmes gespeichert.
Die Art der Speicherung in Dateien läßt sich ist im Prinzip ähnlich wie die im Arbeitsspeicher
organisieren. Bestimmte Mechanismen werden bei der Dateiarbeit aber vom Betriebssystem
gesteuert, auf die der Programmierer keinen Einfluß hat.
Der Umfang des für Dateien zur Verfügung stehenden Speicherplatzes ist bei Rechnern, die
unter Betriebssystemen von Microsoft (DOS) laufen, wesentlich größer als der für Daten im
Arbeitsspeicher. Festplatten mit einer Kapazität von über 1 GByte sind heute schon
Mindeststandard. Die Verwendung von beschreibbaren CD-ROM´s wird die Kapazität des
externen Speichers schnell vergrößern.
Um große Datenmengen verarbeiten zu können ist es bei DOS-Rechnern unumgänglich
Speicherkapazitäten auf der Festplatte und externen Datenträgern durch die Verwendung von
Dateien zu benutzen. (siehe auch Abs. 2.1.4.)
Beim Speichern in Dateien sind auch, ähnlich wie im Arbeitsspeicher, folgende Fragen im
Bezug auf die Effizienz zu stellen:
- Wie oft muß auf Daten zugegriffen werden?
- Wie schnell kann auf einzelne ausgewählte Daten zugegriffen werden?
- Wieviel Speicherplatz wird für die Speicherung einer bestimmten Datenmenge in einer
bestimmten Struktur benötigt?
- Wie können Daten angefügt, eingefügt, gelöscht oder geändert werden.
6
Textdateien
Textdateien haben hinsichtlich ihrer Lesbarkeit gegenüber Binärdateien einen praktischen
Vorteil. Diese Dateien bestehen aus lauter Textzeilen. Es existieren nur einzelne aneinander
gereihte Charakter, die mit einem carriage return am Ende einer jeden Zeile abgeschlossen sind.
Alle Datentypen sind vor der Speicherung in Text umzuwandeln. Entsprechende Befehle in der
Programmiersprache C++ können einfach zur Konvertierung aller Datentypen in Texttypen und
umgekehrt eingesetzt werden. So lassen sich also alle Daten in Textform abspeichern und auch
wieder lesen.
Textdateien sind von jedem Editor lesbar und bearbeitbar. Die Daten sind also gut im Handling
außerhalb der Laufzeit des Programmes.
Punktdaten lassen sich der Reihenfolge nach z.B. so in eine Textdatei speichern, daß die
Punktnummer, die Koordinaten, die Genauigkeit und das Attribut, getrennt durch jeweils ein
Leerzeichen, in je eine Zeile geschrieben werden. (siehe Fig. 2.1.4. und 2.1.5.)
1 1483.717 5427.325 0.100 0.100 1
2 1562.109 5437.660 0.100 0.100 1
3 1624.374 5458.008 0.100 0.100 1
4 1434.574 5424.618 0.100 0.100 1
5 1454.624 5425.725 0.100 0.100 1
6 1361.786 5228.244 0.100 0.100 2
7 1561.886 5439.099 0.100 0.100 2
8 1648.581 5222.256 0.100 0.100 2
9 1574.130 5444.434 0.100 0.100 2
10 1413.585 5422.033 0.100 0.100 2
11 1499.944 5430.315 0.100 0.100 2
12 1769.659 5332.065 0.100 0.100 2
1 17 66 1
2 82 77 1
3 52 81 1
4 29 52 1
5 1 44 1
6 106 17 1
7 52 62 1
8 84 111 2
9 68 66 2
10 64 68 2
11 32 84 2
12 72 73 2
Fig. 2.1.4. Punktdaten in Textdateiformat
Fig.2.1.5.Segmentdaten in Textdateiformat
Bei der Formatierung von Textzeilen ergeben sich Probleme, die Auswirkung auf den Zugriff zu
den Daten haben. Textzeilen lassen sich so formatieren, daß sie augenscheinlich die gleiche
Länge haben. Dies wird dadurch erreicht, daß die Stellen, die für die vorgegebene Zeilenlänge
fehlen, mit Leerzeichen ausgefüllt werden.
Die Zeichenkette einer Zeile wird mit einem Schreibbefehl ab einer bestimmten Position über
einen Buffer in die Datei geschrieben. Diese Positionen sind ganze Zahlen vom Typ long.
Leider sind die Anfangspositionen der Zeilen in der Datei nicht immer gleichmäßig
inkrementiert, obwohl bei der Ausgabe gleiche Formate verwendet werden.
Zum Setzen des Dateizeigers eines Streams auf eine Datei stehen verschiedene Funktionen
bereit. Grundsätzlich lassen sich alle Positionen in der Datei anspringen, jedoch setzt das voraus,
daß man weiß wo die Daten zu finden sind. Der Abstand in Bytes von einer festen Sprungstelle
aus zu einer Stelle in der Datei heißt Offset. Die Benutzerdokumentation von C++ gibt an, daß
für Streams in Text-Modus Offset 0 sein sollte, oder ein Wert, der von ftell geliefert wurde. Ftell
liefert den Wert, an dem der Datenzeiger momentan steht.
Um alle Zeilenanfänge zu erreichen, müßten also alle Offsets im Arbeitsspeicher gespeichert
werden, dort haben wir aber bei großen Datenmengen ein Raumproblem.
Werden die Zeilen nur nacheinander gelesen oder geschrieben sind keine Offsets erforderlich,
weil der Dateizeiger automatisch nach der Lese- oder Schreibaktion weitergesetzt wird.
Ein weiterer Nachteil von Textdateien ist der Umstand, daß Textzeilen nur eine bestimmte Länge
haben dürfen. Zeilen mit mehr als 256 Zeichen führen zu Fehlern. Insbesondere für die
Speicherung der Punkt-Nachbarliste kann diese Zahl Probleme mit sich bringen, wenn alle
Nachbarn eines Punktes in einer Zeile stehen sollen.
Um zusammengehörige Daten in mehreren Zeilen abspeichern zu können müssen extra
vordefinierte Trennzeichen verwendet werden. Dies führt zur Erhöhung des Speicher- und
7
Verwaltungsaufwandes. Im allgemeinen verbrauchen Textdateien immer mehr Speicherplatz als
Binärdateien mit dem gleichen Sachinhalt.
Binärdateien
Binärdateien sind hinsichtlich des Zugriffes auf ausgewählte Daten einfacher zu handhaben als
Textdatein. Der Dateispeicher ist in Segmente der Größe 1 Byte aufgeteilt, jedes Byte ist über
eine Nummer (Adresse) zu erreichen. Ein- und Ausgabe erfolgt über eine Anzahl von Bytes, die
sich über die Funktion sizeof(Datentyp) leicht ermitteln läßt und gut zu kontrollieren ist. Die
Offsets für die Sprünge vom Dateianfang lassen sich für sortierte Daten aus ihrer Punktnummer
berechnen.
Der Offsetwert für den Sprung vom Dateianfang zum 5. Punkt der Datenstruktur point ergibt
sich z.B. aus 4
sizeof(point).
Wird angenommen, daß der 1.Punktdatensatz nur für Infos verwendet wird und der 1.Punkt
sozusagen an 2. Stelle steht, ergibt sich der Offsetwert für den 5. Punkt aus
5
sizeof(point).
Sind Daten sequentiell abgespeichert ist der Zugriff also recht komfortabel und schnell. Es ist
aber, insbesondere wenn das Einfügen von Daten erleichtert werden soll, auf verkettete
Speicherung überzugehen.
2.1.4. Zwischen Unix und DOS
Unix ist hinsichtlich der Speicherverwaltung im Verhältnis zu DOS im Vorteil. Das
Speichersegment, welches in DOS durch die Größe des Arbeitsspeichers eingeschränkt ist, läßt
sich unter Unix auf die Kapazitäten der Festplatten erweitern. Dieses zwischenzeitliche
Auslagern von Daten nennt sich paging.
Die Organisation, was nun wirklich im Arbeitsspeicher, und was auf der Platte gespeichert wird,
läuft im Hintergrund. Der Programmierer als auch der Programmbenutzer braucht sich darum
nicht zu kümmern.
Unter DOS muß leidigerweise auf die Dateispeicherung übergegangen werden wenn der
Arbeitsspeicher zu klein ist. Die praktischen Funktionen in C++ zur Speicherreservierung, -
freigabe oder -veränderung sind nicht auf Dateiarbeit anwendbar. Die Speicherorganisation in
Dateien im Detail obliegt dem Programmierer.
Sollen nicht nur Datenmengen von statischer Größe verarbeitet werden ist der Aufwand zur
Speicherverwaltung sehr hoch. Dennoch bietet DOS Vorteile gegenüber Unix.
Unter DOS lassen sich Daten komfortabler und vielseitiger visualisieren. Die Programmierung
von Grafik für Programme, die unter Unix laufen sollen, ist schwieriger möglich. Die
Standardfunktionen zum Zeichnen, wie unter DOS, sind nicht unter Unix verfügbar. Außerdem
läuft DOS auf fast jedem PC in fast jeder Institution auf der ganzen Welt. Für die
Kommunikation ist Kompatibilität mit anderen Rechnern wichtig.
Es läßt sich vermuten, daß sich die einfache Speicherverwaltung unter Unix positiv auf die
Effizienz des Programmes auswirken würde, es wurde jedoch zu Gunsten der anderen Vorteile
darauf verzichtet.
2.2. Zugriff auf Daten
Es seien n Datensätze gegeben. Der Zugriff auf einen Datensatz erfolgt entweder über seine
Position im Speicher oder über einen Wert k, der einen Datensatz eindeutig identifiziert. Ein
Wert k heißt Primärschlüssel, wenn jeder Wert k
i
den Datensatz S
i
eindeutig identifiziert. Das
kann z.B. die Punktnummer oder die Liniennummer sein.
8
2.2.1. Zugriff über Adressen
Sequentieller Zugriff
Der gezielte Zugriff auf Daten setzt voraus, daß die Adresse, ab der der Datensatz im Speicher
steht, schon vor dem Zugriff bestimmt werden kann. Bei der sequentiellen Speicherung brauchen
die Daten nur in der Reihenfolge eines Primärschlüssels abgespeichert sein. Ist dies z.B. die
Punktnummer errechnet sich die Adresse des Punktes mit Nr. 5 aus Startadresse des
Speicherblockes + 5
sizeof (Datensatz).
Diese einfache Form der Adressrechnung erledigen vorgefertigte Datenkonstrukte in C++ von
selbst über eckige Klammern.
Zugriff über Hashfunktionen
Ein Hashverfahren ist ein Such- und Speicherverfahren, welches unabhängig von der Anzahl der
Datenelemente n ist. K sei wieder ein Schlüsselwert, über den ein Datenelement eindeutig
identifiziert ist.
Über eine Hashfunktion H(k) läßt sich jetzt eine Adresse berechnen, an der das Datenelement im
Speicher abgespeichert werden soll.
Es kommt aber auch vor, daß mit der Funktion aus verschiedenen Werten k die gleichen
Adressen berechnet werden. Diese Fälle werden Kollisionen genannt. Einen gute Hashfunktion
sollte leicht und schnell zu berechnen sein, und zu wenigen Kollisionen führen. In diesem
Zusammenhang spielt der Belegungsfaktor
, das Verhältnis der Datenzahl n zur Anzahl der
Speicheradressen m eine Rolle.
=n/m
Die Güte einer Hashfunktion mit Kollisionsbehandlung wird durch die mittlere Anzahl von
Speichervergleichen gemessen, die für die Bestimmung der Speicheradresse eines
Datenelementes notwendig sind. Günstig ist ein kleiner Belegungsfaktor, was folgende Formeln
belegen. /Lipsch/ S.356
mittlere Anzahl der notwendigen Vergleiche
erfolgreicher Zugriff erfolgloser Zugriff
1 1
S(
)=
(
1+
)
2 1
-
1 1
U(
)=
(
1+
)
2
(
1
-
)
²
Hashverfahren kommen zum Einsatz, wenn die Anzahl der Datenelemente im Verhältnis zur
Anzahl der zur Verfügung stehenden Speicherplätzen gering ist. Dies ist jedoch bei großen
Datenmengen nicht der Fall.
2.2.2. Suchalgorithmen
Die Komplexität von Suchalgorithmen wird durch die Anzahl der Vergleiche f(n) gemessen, die
notwendig sind, um ein bestimmtes Element in einem Datenfeld zu finden. Es wird meistens der
ungünstigste und der durchschnittliche Fall betrachtet.
Sequentielle Suche
Die sequentielle Suche erfolgt so, daß ein Datenelement nach dem anderen in einer bestimmten
Suchreihenfolge nacheinander mit einem Suchschlüssel verglichen wird. Stimmt der Schlüssel
mit dem eines Datenelementes überein, wird die Suche abgebrochen und gilt als erfolgreich.
Wird keine Übereinstimmung im ganzen Datensatz gefunden, war die Suche nicht erfolgreich.
Bei der sequentiellen Suche ist der ungünstigste Fall gegeben, wenn das Datenelement, nach
welchem gesucht wird, gar nicht im Datenfeld enthalten ist. Dabei müssen alle Datenelemente
9
mit dem Suchschlüssel verglichen werden. Die Laufzeit solch eines Algorithmus ist proportional
zu n.
f(n) =n+1
Für den durchschnittlichen Fall ist das Laufzeitverhalten günstiger. Die Anzahl notwendiger
Vergleiche entspricht also in etwa der Hälfte der Datenelementezahl.
(n+1)
f(n)=
2
Binäre Suche
Dieses Verfahren geht mit der sukzessiven Halbierung der Listen einher. Man vergleicht das
mittlere Element der Liste mit dem Suchschlüssel. Je nach dem ob der Wert des Elementes
größer, kleiner oder gleich im Verhältnis zum Schlüssel ist, kann die Suche in der oberen oder
unteren Hälfte der Liste fortgesetz werden, oder sie gilt als erfolgreich abgeschlossen. Diese Art
der Suche setzt immer eine sortierte Liste voraus, außerdem ist der Speicheraufwand bei der
Suche nach ganzzahligen Werten der Größe von 2 Byte 3 mal so groß wie in einer sequentiellen
Liste, weil pro Knoten neben dem Datenteil
(2 Byte) zwei Nachfolgeradressen (4 Byte) gespeichert werden müssen. Die Anzahl der
Vergleiche bei diesem Verfahren ist im ungünstigsten Fall genauso groß wie die Häufigkeit, mit
der man n durch 2 teilen kann.
f(n)= log 2
Im günstigsten Fall, wenn das gesuchte Element genau in der Mitte der Liste steht, ist nur ein
Vergleich erforderlich. /Lewis/
f(n)= 1
Auswahl der geeigneten Suchmethode
Bei der Wahl des Suchverfahrens steht die Rechenzeit im Konflikt mit dem Speicherverbrauch.
Im Programm
"
VFGCUTAS
"
wird ein Suchverfahren nur für das Auffüllen der Punkte-in-
Zellen-Liste benötigt. Da die Suche immer nur auf die Liste einer Zelle begrenzt ist, verringert
sich der Suchaufwand bei der sequentiellen Suche im ungünstigsten Fall nach angegebener
Formel. Dabei wurde vorausgesetzt, daß eine gleichmäßige Verteilung der Punkte auf die Zellen
des Uniform Grid vorliegt. (siehe Abs.3)
(n+1)
f(n)=
Anz Z
2.3. Sortieren von Daten
Gegeben seien n Datensätze S
1
,S
2
, . . . , S
n
i n einem Speicher. Die Datensätze zu sortieren
bedeutet nach /Lipsch/, sie entsprechend den Werten des Feldes k
1
, k
2
, . . . , k
n
zu ordnen. Das
Feld k heißt dann Sortierschlüssel.
Wenn B ein externer Speicher ist, besteht jeder Sortieralgorithmus prinzipiell aus folgenden
Operationen:
a) Vergleichen der Art Ai<Aj oder Ai<B.
b) Vertauschen der Inhalte von Ai und Aj oder Aj und B.
c) Zuweisung der Art B=Ai und Aj=B oder Aj=Ai.
10
Die ungefähre Anzahl und somit die Komplexität einiger Algorithmen ist in folgender Tabelle
dargestellt.
Algorithmus ungünstigster
Fall
Normalfall
Bubbel Sort
n
(n
-
1)
= O(n²)
2
n
(n
-
1)
= O(n²)
2
Quicksort
n
(n + 3)
= O(n²)
2
1.4
n
log n = O(n
log n)
Heapsort
3
n
log n = O(n
log n)
3
n
log n = O(n
log n)
Fig. 2.3.1. Zeitkomplexität einiger Suchalgorithmen /Lipsch/ S.339
O(n
log
2
n) ist der bestmöglichste Laufzeitwert für jeden denkbaren Sortieralgorithmus bei n
gegebenen Werten. /Lipsch/
2.4. Relationale Datenstrukturen und Graphen
In einem relationalen Datenmodell sind alle wesentlichen Objekte und Beziehungen jeweils in
Tabellen anzulegen. Für geometrische Objekte und Beziehungen ist das gut zu verwirklichen.
Bei der Flächenverschneidung werden alle Objekte in Segmente unterteilt. Ein Segment ist dann
also die kleinste Einheit und stellt eine Relation zwischen zwei Punkten dar. Die Theorie, in der
die Beziehungen zwischen Punkten beschrieben werden, nennt sich Graphentheorie.
Ein Graph G besteht aus zwei Mengen: den Knoten und den Kanten . Es existieren eine endliche
Menge Knoten, von denen je zwei, ein Paar <i,j>, eine Kante darstellen. Ist ein Graph <i,j>
gleich <j,i> wird er ungerichtet genannt, sonst gerichtet. Hier sollen nur noch ungerichtete
Graphen behandelt werden. Ein Knoten i ist dem Knoten j benachbart (oder adjazent), wenn die
Kante <i,j> existiert. Der Grad eines Knotens ist die Anzahl seiner Nachbarknoten.
b
a
d f
c e
Fig. 2.4.1. Ein Beispiel für einen Graphen
Für die Darstellung von Graphen werden in /Horo 81/ zwei Methoden verwendet. Sie werden als
sequentielle und als Zeiger-Darstellung bezeichnet. Die sequentielle Methode verwendet eine
quadratische Tabelle mit n Zeilen und n Spalten, wobei n die Anzahl der Knoten ist. Diese Form
wird als Nachbarschaftsmatrix (Adjacency matrix) bezeichnet. Ein Matrixelement (i,j)=1 stellt
eine Kante zwischen den Knoten der Spalte i und der Zeile j dar.
1 2 3 4 5
1
0 1 1 0 0
2
1 0 0 1 1
3
1 0 0 1 0
11
4
0 1 1 0 1
5
0 1 0 1 0 Knoten-Knoten
Relation
Fig. 2.4.2 Adjazenzmatrix des Graphen aus Fig 2.4.1.
Eine solche Matrix zu initialisieren, erfordert mindestens O(n²) Operationen. Daraus ergibt sich,
daß jeder Algorithmus, der mit dieser Darstellung arbeitet, Rechenzeit in dieser Größenordnung
benötigt. Hinzu kommt, daß auch der Speicherplatzbedarf n²
p, mit p= Größe eines
Speicherplatzes, erfordert . Unter der Beachtung der Tatsache, daß die Adjazenzmatrix von
ungerichteten Graphen immer eine symmetrische Matrix ist, lassen sich alle Informationen in
einer oberen oder unteren Dreiecksmatrix vollständig darstellen. Die Hauptdiagonalen sind dabei
unbesetzt.
Die Darstellung eines Graphen in einer Nachbarschaftsliste besteht aus n Listen. Jedem Knoten
ist eine Liste zugeordnet, die die Nachbarn desjenigen Knotens enthalten. Die Speicherung kann
auf verschiedenem Weg erfolgen. Für den Zugriff auf die Knoten günstig ist die sequentielle
Speicherung.
1 2
3
2 1 4 5
3 1
4
4 2 3 5
5 2
4
Fig. 2.4.3 Nachbarschaftsliste des Graphen aus Fig. 2.4.1
Werden die Kanten selbst in einer Tabelle mitgeführt, lassen sich auch die Kanten-Knoten
Relationen und die Kanten-Kanten Relationen darstellen. Die nächste Stufe wäre die Darstellung
z.B. von Flächen mit Hilfe von Kanten-Flächen Relationen oder Flächen-Flächen Relationen.
Verschiedene Objekte z.B. Knoten, Kanten oder Flächen können wieder in Listen oder
Matrizenform dargestellt werden. Eine Matrix, in der die Kanten-Knoten Beziehungen abgelegt
sind, ist eine Inzidenzmatrix.
1 2 3 4 5
a
1 0 1 0 0
b
1 1 0 0 0
c
0 0 1 1 0
d
0 1 0 1 0
e
0 0 0 1 1
f
0 1 0 0 1
Kanten-Knoten
Relation
Fig.2.4.4. Inzidenzmatrix des Graphen aus Figur 2.4.1.
Die Kanten-Knoten-Liste ist im Verhältnis zur Inzidenzenmatrix noch kleiner als die Knoten-
Knoten-Liste zur Adjazenzmatrix.
1 1 3 2 4 2
3 2 4 4 5 5
Fig.2.4.5. Knoten-Kanten-Liste des Graphen aus Figur 2.4.1
Wird die Inzidenzmatrix als C bezeichnet ergeben sich aus C
T
C die Knoten-Knoten-
Beziehungen in Fig.2.4.2. und aus C
C
T
die Kanten-Kanten-Beziehungen in Fig.2.4.5.
a b c d e f
12
a
0 1 1 0 0 0
b
1 0 0 1 0 1
c
1 0 0 1 1 0
d
0 1 1 0 1 1
e
0 0 1 1 0 1
f
0 1 0 1 1 0
Kanten-Kanten
Relation
Fig.2.4.6. Kanten-Kanten-Matrix des Graphen aus Figur 2.4.1.
2.5. Raum - und Zeitkomplexität
Die Komplexität eines Algorithmus ist eine Funktion f(n), die die Rechenzeit und/oder den
Speicherplatzbedarf bei Anwendung auf n Datenelemente angibt. Der Versuch, die Rechenzeit
und den Speicherplatz zu optimieren, führt zu einem Konflikt. Die Verkleinerung der einen
Größe führt in der Regel zu Vergrößerung der anderen Größe. /Lipsch/ Für die Lösung jedes
Problem gibt es beliebig viele verschiedene Algorithmen. Es läßt sich zeigen, daß es einen
Algorithmus gibt, der das Problem am schnellsten löst. Es gibt jedoch keinen automatischen
Algorithmus, um diesen schnellsten Algorithmus zu finden. Dies ist Aufgabe des
Programmierers. Die Komplexität wird in Klassen oder Ordnungen eingeteilt. Die Ordnung z.B.
n² zeigt an, daß der geringst mögliche Zeitverbrauch für den Algorithmus mit der Datenmenge
quadratisch zunimmt. Diese Ordnung wird noch mit einem Faktor versehen, der nie kleiner 1
sein kann.
Folgender Ausdruck gibt die Laufzeit eines Algorithmus an:
k
O(f(n)) , mit k
1
Vordringliches Ziel bei der Bestimmung eines effizienten Algorithmus ist die Findung der
niedrigsten Ordnung. Ist die niedrigste Ordnung gefunden, ist der Algorithmus nur noch durch
den Faktor k zu verbessern. Je größer die Datenmengen sind, desto weniger spielt der Faktor k
eine Rolle für die Laufzeit. Die Ordnung eines Algorithmus, der sich aus einer Folge von
Algorithmen zusammensetzt, ist so groß wie die Ordnung des schlechtesten Teilalgorithmus. Die
Einteilung der nachfolgenden Abschnitte in Best-, Average- und Worst Case beziehen sich auf
die stochastischen Modelle, die in Abs. 4.2. beschrieben sind.
2.5.1. Zeitkomplexität von Matrizenoperationen
Die Zeitkomplexität von Matrizenoperationen soll an Hand der Anzahl der auszuführenden
Operationen untersucht werden. Die Betrachtungen beziehen sich auf das zweifache
Matrizenprodukt in dem Varianzfortpflanzungsgesetzes (VfG).
YY
=F
XX
F
T
Dabei treten folgende Dimensionen auf:
m
n
m
m
XX
F
T
n
F
F
XX
YY
mit: n =2
Anzahl der Schnittpunkte
m=2
Anzahl der mit den Schnitten
korrelierenden Punkte
Fig. 2.5.1. Dimensionen beim Matrizenprodukt des VFG, Zeitkomplexität
13
Die folgenden Angaben beziehen sich zunächst nur auf die mathematischen Operationen, die für
die Produktberechnung erforderlich sind.
Vollbesetzte Matrizen
Wird die Matrizenmultiplikation ohne Rücksicht auf den Inhalt der Matrizen durchgeführt,
gelten die Matrizen als voll besetzt. Dabei ergeben sich folgende mathematische Operationen:
Anzahl der auszuführenden Additionen: (m-1)
m
n + (m-1)
n
n =
Additionen:
n
(m+n)
(m
-
1)
Anzahl der auszuführenden Multiplikationen: m
(m
n) + m
(n
n) =
Multiplikationen:
m²
n+m
n²
Beispiel: mit m= 10 und n=4 ergeben sich 504 Additionen und 560 Multiplikationen.
Da eine Addition im Verhältnis zu einer Multiplikation nur sehr wenig Rechenzeit benötigt, und
zudem noch eine geringere Anzahl hat, wird die Komplexität des Algorithmus zur
Matrizenmultiplikation nur durch die Anzahl der Multiplikationen gemessen. /Lipsch/
Schwach besetzte Matrizen
Die Anzahl der auszuführenden Operationen bei einer schwach besetzten Matrix ist bei
herkömmlicher Matrizenmultiplikation die gleiche wie bei einer vollbesetzten Matrix.
Da aber Multiplikationen mit Null ohne Wirkung auf das Endergebnis sind, können diese auch
weggelassen werden. Dazu zählen die Operationen Null
Null und Null
NNE.
Rechenoperationen sollen nur zwischen NNE durchgeführt werden. Es ist sicher leicht
vorstellbar, daß die Anzahl der Multiplikationen stark abhängig ist von der Verteilung der NNE
in den Matrizen. Für die Betrachtung ist also eine Kenntnis über die Besetzungsstruktur der
Matrizen erforderlich. Für eine allgemeine Abschätzung können wieder Fälle definiert werden.
Fall 0:
Im günstigsten Fall sind die NNE so verteilt, daß es zu keinen Produktpaaren kommt. Dieser Fall
tritt praktisch bei der Varianzfortpflanzung nicht auf, weil die Hauptdiagonale der Matrix
XX
immer besetzt ist.
Best Case:
Der eigentlich günstigste Fall ist der, bei dem nur die Hauptdiagonale der Matrix
XX
besetzt
ist. Die Matrix F enthält für den Geradenschnitt immer 8 NNE pro Zeile und die transponierte F
T
8 NNE pro Spalte. Das Zwischenergebnis F
XX
hat die gleiche Sparse-Besetzung wie F. Jedes
Element von F
XX
entsteht aus genau einer Multiplikation. Daraus ergibt sich für das
Zwischenergebnis:
Anzahl der Multiplikationen: 8
n
Für die Hauptdiagonalen der Matrix
YY
gilt auch: 8
n
Die Nebenelemente von
YY
, die ja die Korrelationen zwischen den Schnittpunkten darstellen,
sind nicht eindeutig vorhersehbar. (siehe Abs. 4.3.) Im einfachsten Fall entstehen keine
Nebenelemente und die Anzahl der Multiplikationen ist: 8
n + 8
n =
ohne Korrelationen zwischen den Schnittpunkten:
16
n
nach obigem Beispiel: Anzahl = 64
Im ungünstigsten Fall des Best Case kommen für jedes Nebenelement der Matrix
YY
6
Multiplikationen vor. Da wegen der Symmetrie der Matrix
YY
nur die Hälfte aller
Nebenelemente berechnet werden müssen, ist die Gesamtanzahl an Multiplikationen: 16
n +
8
n/2+6
n(n
-
2)/2 =
mit vollbesetzten Nebendiagonalen:
16
n + 3
n ²
-
2
n
nach obigen Beispiel: Anzahl = 104
Worst Case :
14
Der ungünstigste Fall insgesamt ist sicher der, wenn die NNE so in den Matrizen verteilt sind,
daß jedes NNE der einen Matrix ein Produktpaar mit einem NNE der anderen Matrix bildet. Dies
ist z.B. gegeben, wenn die Matrix
XX
voll besetzt ist. Die Zwischenmatrix F
XX
und auch
YY
wären dann voll besetzt und es ergeben sich folgende Multiplikationen:
8
m
n+m
n+m
n(n
-
1)/2 =
alle Matrizen voll außer F und FT:
(n+17)
m
n / 2
nach obigen Beispiel: Anzahl = 420
Selbst wenn bei der herkömmlichen Matrizenmultiplikation nur die eine Seite der
Nebenelemente der Matrix
YY
berechnet werden würde, also 560
-
m
n
(n
-
1)/2 = 500
Multiplikationen, ist ein Sparse-Algorithmus von der Anzahl der Multiplikationen hergesehen
noch im ungünstigsten Fall um 16% besser.
Algorithmen für Multiplikationen von Sparse-Matrizen sind um einiges komplizierter, als für
vollbesetzte Matrizen und es werden einige Vorarbeiten für die entsprechenden
Speichervarianten benötigt. Die Überlegenheit eines Sparse-Algorithmus kommt um so stärker
zum tragen je geringer der Anteil an NNE ist und desto günstiger die Verteilung der NNE im
Matrizenfeld ist.
Messen von Laufzeiten in C
Das Messen von Laufzeiten in der Programmiersprache C läuft auf die Bestimmung von
Zeitdifferenzen hinaus. Zur Bestimmung von Zeitdifferenzen in der Größenordnung von
Sekunden stehen die Funktionen
"
difftime
"
(difference time) und
"
clock
"
zur Verfügung.
"
difftime
"
berechnet den Unterschied zwischen zwei Zeitangaben in Sekunden direkt aus.
"
clock
"
hingegen liefert die seit dem Start des Programms vergangene Zeit in
"
Ticks
"
zurück. Die
Zeitdifferenz wird hier durch Differenzbildung der Tickgrößen und anschließende Division
durch eine in der Bibliothek
"
time.h
"
definierten Konstante CLK_TCK berechnet. Ein
"
Tick
"
ist
in diesem Zusammenhang eine systemspezifische Einheit der
"
CPU-Zeit
"
. Durch die
Verwendung der ebenfalls systemspezifischen Konstante
"
CLK_TCK
"
ist die Darstellung der
Zeitdifferenz maschinen- und systemunabhängig. /Schäp/ Aus diesem Grunde wurde diese Art
der Zeitdifferenzmessung in das Programm implementiert. Da von Rechenzeiten im Bereich von
einigen Sekunden bis bei großen Datenmengen von einigen Minuten ausgegangen wird, kann auf
die Darstellung von Minuten oder gar Stunden und Tage verzichtet werden. C bietet auch
Funktionen, die die Zeit in diesen Größenordnungen zurückliefern. In dem Programm erfolgt die
Ausgabe ausschließlich in Sekunden.
2.5.2. Raumkomplexitäten der Matrizen beim VFG
Die Raumkomplexität von Matrizenoperationen soll an Hand der Anzahl der durch die Matrizen
im Speicher besetzen Bytes untersucht werden. Die Betrachtungen beziehen sich auf das
zweifache Matrizenprodukt in dem Varianzfortpflanzungsgesetz.
YY
=F
XX
F
T
. Die dabei
auftretenden Dimensionen sind in Fig. 2.5.2. abgebildet. Zur Speicherung einer Kovarianz oder
einer Ableitung soll ein float, also 4 Bytes, zur Verfügung stehen. Für Speicherung einer Adresse
oder einer Punktnummer bzw. eines Indizes wird ein unsigned integer, also 2 Bytes, angesetzt.
An dieser Stelle wird ausschließlich der Verbrauch für die Elemente der Matrizen betrachtet,
keine Speicherung für irgendwelche Laufvariablen, oder Zeiger oder Funktionsparameter oder
sonstiger Verbrauch für Variablen des Algorithmus bzw. des Programms. Diese sind ohnehin bei
großen Datenmengen gegenüber den Matrizendaten verschwindend gering.
Es wird von einer Besetzung ausgegangen, bei der nur die Ausgangspunkte beteiligt sind, die an
der Verschneidung direkt, als Begrenzungspunkte von sich schneidenden Segmenten oder
indirekt als korrelierende Punkte beteiligt sind.
Um diese Besetzung zu erreichen, muß vor der Flächenverschneidung eine Datenextraktion über
das für die Flächenverschneidung gewählte Gebiet erfolgen. Das geht zwar wieder auf Kosten
der Rechenzeit, bringt aber erheblichen Raumgewinn, denn die Anzahl an nicht beteiligten
15
Punkten und Segmenten, kann durchaus viel höher sein, als die der beteiligten. Warum also den
Speicher unnötig mit diesen unbenutzten Daten belasten?
p
s
p
p
XX
FT
s
F
F
XX
YY
mit: s= Anzahl der Schnittpunkte
p= Anzahl der mit den Schnitten korrelierenden
Punkte
Fig. 2.5.2. Dimensionen beim Matrizenprodukt des VFG, Raumkomplexität
Für die Formelangaben und den Größenvergleich in den nächsten Abschnitten werden als
Beispiel Flächen mit den Dimensionen p=101 und s=49 verwendet. Die Begriffe Best-,
Average- und Worst Case sind hinsichtlich des stochastischen Modells, welches sie bezeichnen
in Abs. 4.2. beschrieben.
Zweidimensionale Feldspeicherung
Um den Speicherverbrauch besser in den Zusammenhang mit der Anzahl der Ausgangs- und
Schnittpunkte zu bringen, werden die Komponenten yy,yx,xy und xx jeweils zunächst zu
einzelnen Submatrizen zusammengefaßt, die Anzahl der benötigten Submatrizen berechnet und
dann vervierfacht um die Anzahl der kleisten Elemente im Feld zu bestimmen. Bei der
Deklaration eines zweidimensionalen Arrays werden grundsätzlich alle Speicherplätze reserviert,
unabhängig davon, ob die Plätze belegt sind oder nicht.
Vollständige Speicherung
Werden alle Matrizen abgespeichert, ergibt sich der Speicherbedarf folgendermaßen:
F
= p
s
4 Plätze
4 Bytes
= 16ps
= 79184
XX
= p
p
4 Plätze
4 Bytes
= 16p ²
= 163216
F
XX
= p
s
4 Plätze
4 Bytes
= 16ps
= 79184
FT
= s
p
4 Plätze
4 Bytes
= 16ps
= 79184
YY
= s
s
4 Plätze
4 Bytes
= 16s²
= 38416
gesamt:
16s ² + 16p ² + 48 ps
= 439184 Bytes
Best Case
Der Speichermethode soll jedoch auch die Möglichkeit der Ausnutzung von Vorinformationen
für die Speicherreservierung zugesprochen werden. So wird für den Best Case auch nur ein
Vektor an Stelle der ganzen Matrix
XX
angesetzt und vorausgesetzt, daß sich die Matrizen
F
XX
und
YY
zeilenweise aufbauen lassen, so daß jeweils nur für die 4 am Schnitt beteiligten
Punkte Plätze in F reserviert werden müssen.
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
2 Plätze
4 Bytes
= 8p
= 808
F
XX
= p
s
4 Plätze
4 Bytes
= 16ps
= 79184
FT
F wird mitbenutzt
= 0
= 0
YY
= s ²
4 Plätze
4 Bytes
= 16s ²
= 38416
gesamt:
16s ²+ 16ps + 8p + 64
= 118472 Bytes
Average Case
16
In diesem Falle wird für F wieder nur ein Vektor für 4 Punkte benötigt, jedoch für
XX
ein
vollständiges Array. F
T
wird nicht gespeichert.
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
p
4 Plätze
4 Bytes
= 16p ²
= 163216
F
XX
= p
s
4 Plätze
4 Bytes
= 16ps
= 79184
FT
= F wird mitbenutzt
= 0
= 0
YY
= s
s
4 Plätze
4 Bytes
= 16s²
= 38416
gesamt:
16 (p² + ps + s² +4 )
= 280880 Bytes
Worst Case
In diesem Fall kann die Matrix F wieder durch eine Zeile für 4 Punkte ersetzt werden und
XX
ist voll besetzt.
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
p
4 Plätze
4 Bytes
= 16p ²
= 163216
F
XX
= p
s
4 Plätze
4 Bytes
= 16ps
= 79184
FT
= F wird mitbenutzt
= 0
= 0
YY
= s
s
4 Plätze
4 Bytes
= 16s²
= 38416
gesamt:
16(p ² + ps + s ²+ 4 )
= 280880 Bytes
YY
als diagonale Matrix
Es sei noch darauf hingewiesen, daß auch
YY
mit nur diagonaler Besetzung vorkommen kann.
Diese Fälle können aber nicht ohne genaue Kenntnis der Topologie der Flächen vorhergesagt
werden. Die Speicherung könnte z.B. zunächst in einem Vektor erfolgen, und wenn Kovarianzen
zwischen Schnittpunkten auftreten, wird in ein zweidimensionales Feld übergegangen. Hier wird
die Formel für den Fall einer diagonalen Besetzung von
YY
angegeben.
YY
= s
2 Plätze
4 Bytes
= 8s
= 392
gesamt:
8s
= 392 Bytes
Im Falle einer diagonalen Besetzung sind also von dem Gesamtverbrauch jeweils
(16s²-8s) abzuziehen, laut Beispiel also (38416-392)= 38024 Bytes.
Speicherung in komprimierenden Listen im Arbeitsspeicher
Bei der Speicherung in komprimierten Listen, wie in Abs. 6.1. beschrieben, werden nur die NNE
der Matrizen im Arbeitsspeicher abgespeichert. Jedoch kommen noch Speicherplätze für
Indizierungen, die Datenfelder an den 0-ten Positionen der Listen mit Zusatzinformationen und
die Zeiger in den Kopfzeilen hinzu.
Der große Vorteil der Listenspeicherung liegt darin, daß die Strukturen dynamisch sind.
Während der Laufzeit des Programmes wird also nur so viel Speicher eingenommen, wie aktuell
benötigt wird. Der Speicherbedarf steigt mit der Laufzeit an und bleibt am Ende bei einer
bestimmten Größe stehen. Die Speicherstrukturen reagieren also auf die anfallenden
Datenmengen. Es lohnt sich deswegen auch die 3 Fälle Best- , Average- und Worst Case
hinsichtlich des Speicherverbrauchs zu unterscheiden. Für die Matrix F werden in allen 3 Fällen
immer nur Speicherplätze für 4 Punkte benötigt, weil der Aufbau der anderen Matrizen
zeilenweise erfolgt.
Vollständige Speicherung in Listen
Werden alle Listen, die zur Verfügung stehen, maximal ausgelastet werden, also ein
vollbesetzter Fall aller Matrizen simuliert wird, ergibt sich folgender Speicherbedarf:
17
F
= (p
s + p + 1)
18 Bytes + (p + 1)
2 Bytes
= 18ps+20p+20
= 91122
XX
= (p
p + p + 1)
18 Bytes + (p + 1)
2 Bytes
= 18p²+20p+20
= 185658
F
XX
= (p
s + p + 1)
18 Bytes + (p + 1)
2 Bytes
= 18ps+20p+20
= 91122
FT
= (s
p + p + 1)
18 Bytes + (p + 1)
2 Bytes
= 18ps+20p+20
= 91122
YY
= (s
s + s + 1)
18 Bytes + (s + 1)
2 Bytes
= 18s ²+20s+20
= 44218
gesamt: 18p²+18s²+54ps+80p+20s+100
=503242Bytes
Dieser Fall kommt bei der Varianzfortpflanzung nicht vor, weil F nie voll besetzt ist und zudem
F
XX
auch recht selten. Die Zahl ist jedoch gut verwendbar, um den Mehraufwand der Listen
durch die Indizes, die Köpfe usw zu zeigen. Durch die vielen NNE wird dieser Anteil aber weit
mehr als aufgewogen.
Best Case
F wird nur für 4 Punkte benötigt.
XX
ist nur ein Vektor und F
T
ist mit F abgedeckt.
Desweiteren kommt hier zum Tragen, daß F
XX
in jeder Zeile nur für 4 Punkte Speicher
benötigt. Ein Datensatz der Kovarianzlisten verbraucht 18 Bytes. 16 Bytes für die Kovarianzen
und 2 Bytes für die Nummern der Schnittpunkte.
a)
YY
sei diagonal besetzt
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
2 Plätze
4 Bytes
= 8p
= 808
F
XX
= (4 Punkte
s + p+1)
18 Bytes + (p+1)
2 Bytes
= 72s+20p+20
= 5568
FT
= F wird mitbenutzt
= 0
= 0
YY
= (s + s + 1)
18 Bytes + (s+1)
2 Bytes
= 38s+20
= 1882
gesamt:
28p+110s+104
= 8322 Bytes
b)
YY
sei voll besetzt
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
2 Plätze
4 Bytes
= 8p
= 808
F
XX
= (4 Punkte
s + p+1)
18 Bytes + (p+1)
2 Bytes
= 72s+20p+20
= 5568
FT
= F wird mitbenutzt
= 0
= 0
YY
= (s²
-
(s²
-
s)/2 +s+1)
18 Bytes + (s+1)
2 Bytes
= 9s ²+29s+20
= 23050
gesamt:
9s ²+28p+101s+104
= 29490 Bytes
Average Case
Der ungünstigste Average Case ist hinsichtlich der Matrix
XX
identisch mit dem Worst Case.
Der günstigste Fall eines Average Case kommt der Besetzung von
XX
im Best Case nahe. Das
heißt, daß es theoretisch keinen richtigen mittleren Fall hinsichtlich der Besetzung der Matrizen
gibt. Die Besetzung von
XX
ist im Average Case immer von der Topologie abhängig. Eine
durchschnittliche Polygonseitenverknüpfung (Punkt-Nachbar Beziehung) läßt sich nicht
vorhersagen, höchstens an Hand von vielen Beispielen empirisch ermitteln. Selbst dann ist die
Streuung der Besetzungsstruktur so groß, daß der Mittelwert nicht repräsentativ wäre für die
Angabe eines notwendigen Speicherplatzverbrauches. Die Angabe eines mittleren
Speicherplatzverbrauches ließe sich gegebenenfalls aus dem arithmetischen Mittel zwischen
dem Verbrauch von Best Case und Worst Case angeben. Grundsätzlich muß beim Average Case
aber damit gerechnet werden, daß der Verbrauch in die Größenordnung von Worst Case geht,
und diesen Speicher auch zur Verfügung stellen, um nicht einen Speicherüberlauf zu riskieren.
Obwohl der Speicherverbrauch durchaus stark schwanken kann, wird hier versucht, für den
18
Average Case ein sinnvolles Beispiel anzugeben, welches durchaus auch mehrmals vorkommen
kann.
Von allen an Schnitten beteiligten Punkten habe jeder nur 2 Nachbarn z.B. bei nicht vernetzten
Polygonen. Von den Nachbarn sei je einer gleichzeitig auch Begrenzungspunkt eines Segmentes,
welches sich mit einem anderen schneidet. (siehe dazu Fig. 2.5.3.)
Fig. 2.5.3. Nicht vernetzte Polygone
Die Matrix
XX
ist dadurch neben der Hauptdiagonale auch noch mit je zwei Positionen in jeder
Zeile besetzt. Die Besetzung der
XX
ist durch die Punkt-Nachbarliste repräsentiert. Darin besetz
jeder Nachbar nur 2 Byte. Die Kovarianzen dazu werden über eine Funktion bei Bedarf
berechnet, brauchen also nicht gespeichert sein. Die Varianzen sind in der Punktliste in Form der
Standardabweichungen gespeichert. Die Matrix F
XX
ist neben den NNE, die auch in F zu
finden sind, noch zusätzlich mit 4 NNE pro Zeile besetzt. F
T
ist wieder mit F abgespeichert und
es wird unterschieden zwischen
YY
voll oder diagonal besetzt.
a)
YY
sei diagonal besetzt
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
2 Plätze
4 Bytes+p
2 Punkte
2 Bytes
= 12p
= 1212
F
XX
= 72s+20p+20 + 4 Punkte
s
4 Plätze
4 Bytes
= 144s+20p+20
= 9096
F
T
= F wird mitbenutzt
= 0
= 0
YY
= (s + s + 1)
18 Bytes + (s+1)
2 Bytes
= 38s+20
= 1882
gesamt:
32p+182s+104
= 12254 Bytes
b)
YY
sei voll besetzt
F
= 4 Punkte
4 Plätze
4 Bytes
= 64
= 64
XX
= p
2 Plätze
4 Bytes+p
2 Punkte
2 Bytes
= 12p
= 1212
F
XX
= 72s+20p+20 + 4 Punkte
s
4 Plätze
4 Bytes
= 144s+20p+20
= 9096
F
T
= F wird mitbenutzt
= 0
= 0
YY
= (s²
-
(s²
-
s)/2 +s+1)
18 Bytes + (s+1)
2 Bytes
= 9s ²+29s+20
= 23050
gesamt:
9s ²+32p+173s+104
= 33422 Bytes
Worst Case
Für diesen Fall lassen sich zwei verschiedene Speichermodelle konstruieren. Einiges gilt für
beide Modelle. Alle Matrizen bis auf F sind voll besetzt und F
T
mit F abgespeichert. Die Werte
von
XX
werden, bis auf die Varianzen, vor dem Gebrauch berechnet. Es wird jeweils nur ein
Kovarianzdatensatz zwischengespeichert. Eine Punkt-Nachbar-Liste ist nicht nötig, weil von
Korrelationen zwischen allen Punkten ausgegangen wird.
Die Unterscheidung besteht hinsichtlich der Listenverknüpfung.
Die Matrix F
XX
könnte auf Grund ihrer Vollbesetztheit ohne Listenkopf und Nummern für
Schnittpunkte abgespeichert werden, also wie in einem Array. Warum sollen jedoch vollbesetzt
Matrizen in Listenform abgespeichert werden, wenn sie in Arrayspeicherform doch weniger
Ende der Leseprobe aus 98 Seiten
- nach oben
Details
- Arbeit zitieren
- , 1997, Flächenverschneidung in GIS, Hamburg, Bedey Media GmbH, https://www.diplom.de/document/222532
Deutschlands größter Sharing Community
Jetzt Zusammenfassungen, Skripte und Klausuren kostenlos downloaden!
Uniturm.de
Ihre Vorteile als Autor
Geld verdienen Für jedes verkaufte Exemplar erhalten Sie Autorenhonorar - bis zu 40%.Kostenlose Buchveröffentlichung
Als eBook-Studie im Original und / oder auf Wunsch zusätzlich als hochwertiges Fachbuch in unserem renommierten Buchverlag.
Renommee als Fachbuchautor
Präsentieren Sie sich als Fachfrau oder Fachmann in Ihrem Fachgebiet und machen Sie sich bekannt.
Persönliche Betreuung
Unser Lektorat wird Sie persönlich betreuen und ist auch telefonisch unter +49(0)176-85996762 erreichbar.
Weltweit im Buchhandel
Ihr Buch ist weltweit im Buchhandel und Online-Buchhandel wie z.B. amazon erhältlich.
Jetzt Autor werden!
Kommentare