Sentinel (Programmierung) - Versionsgeschichte

Frankain: - Schweiz Zeichen

2024-09-16T17:59:25Z

- Schweiz Zeichen

← Nächstältere Version		Version vom 16. September 2024, 19:59 Uhr
Zeile 1:		Zeile 1:
	Als '''Sentinel''' (Aussprache: {{Audio\|en-us-sentinel.ogg\|sentinel}}, engl. für ''Wächter''), '''Wächterknoten''' oder '''Wächterwert''' (im engeren Sinn) bezeichnet man in der [[Informatik]], im Bereich der [[Programmierung]], ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis ~~»gefunden«~~ läuft.<ref>{{BibISBN\|9783540779773\|Seite=63}} 3 Representing Sequences by Arrays and Linked Lists</ref> Wenn so geschehen, wird nachträglich das Ergebnis auf ~~»nicht~~ ~~gefunden«~~ korrigiert.		Als '''Sentinel''' (Aussprache: {{Audio\|en-us-sentinel.ogg\|sentinel}}, engl. für ''Wächter''), '''Wächterknoten''' oder '''Wächterwert''' (im engeren Sinn) bezeichnet man in der [[Informatik]], im Bereich der [[Programmierung]], ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis „gefunden“ läuft.<ref>{{BibISBN\|9783540779773\|Seite=63}} 3 Representing Sequences by Arrays and Linked Lists</ref> Wenn so geschehen, wird nachträglich das Ergebnis auf „nicht gefunden“ korrigiert.

	Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.		Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.

Wruedt: Abschnittlink korrigiert

2021-04-29T09:46:28Z

Abschnittlink korrigiert

← Nächstältere Version		Version vom 29. April 2021, 11:46 Uhr
Zeile 18:		Zeile 18:

	=== Version mit Nullzeiger ===		=== Version mit Nullzeiger ===
	Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete ~~Liste~~\|terminiert]] durch den [[Nullwert#Nullwert als grundverschiedener Wert\|Nullzeiger]] <code>NULL</code>.<ref>Ein [[Zeiger (Informatik)\|Zeiger]], der den Wert 0 haben kann, muss vor der [[Dereferenzierung]] ohnehin auf 0 abgefragt werden, da die Dereferenzierung sonst auf den meisten Betriebssystem-Maschinen-Kombinationen zum Crash führt.</ref>		Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Listen\|terminiert]] durch den [[Nullwert#Nullwert als grundverschiedener Wert\|Nullzeiger]] <code>NULL</code>.<ref>Ein [[Zeiger (Informatik)\|Zeiger]], der den Wert 0 haben kann, muss vor der [[Dereferenzierung]] ohnehin auf 0 abgefragt werden, da die Dereferenzierung sonst auf den meisten Betriebssystem-Maschinen-Kombinationen zum Crash führt.</ref>
	<syntaxhighlight lang="c" line highlight="9,12">		<syntaxhighlight lang="c" line highlight="9,12">
	first = NULL; // Terminierung vor der ersten Einfügung		first = NULL; // Terminierung vor der ersten Einfügung

Nomen4Omen: Wording

2019-10-21T14:25:49Z

Wording

Nomen4Omen: Präzisierungen

2019-10-21T08:17:09Z

Präzisierungen

← Nächstältere Version		Version vom 21. Oktober 2019, 10:17 Uhr
Zeile 3:		Zeile 3:
	Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.		Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.

	Im weiteren Sinn gilt (insbesondere im englischen Sprachraum) jede Form eines Terminators einer Sequenz, so auch das [[Nullzeichen]] bei [[Zeichenkette#Repräsentation mit Abschlusszeichen\|Zeichenketten]], als Sentinel.		Im weiteren Sinn gilt (insbesondere im englischen Sprachraum) jede Form eines Terminators einer Sequenz als eines normalerweise nicht vorkommenden speziellen Objekts, so auch das [[Nullzeichen]] bei [[Zeichenkette#Repräsentation mit Abschlusszeichen\|Zeichenketten]], als Sentinel.

	== Beispiel ==		== Beispiel ==
	In den beiden folgenden [[C (Programmiersprache)\|C]]-Funktionen <code>Search</code> und <code>SearchWithSentinel</code> soll in einer [[Verkettete Liste\|verketteten Liste]] vom Typ		In den beiden folgenden [[C (Programmiersprache)\|C]]-Funktionen <code>Search</code> und <code>SearchWithSentinel</code> soll in einer einfach [[Verkettete Liste\|verketteten Liste]] vom Typ
	<syntaxhighlight lang="c" line>		<syntaxhighlight lang="c" line>
	struct sll_node // ein Knoten der verketteten Liste sll		struct sll_node // ein Knoten der verketteten Liste sll
Zeile 13:		Zeile 13:
	struct sll_node *next; // -> nächster Knoten oder Terminator der Liste		struct sll_node *next; // -> nächster Knoten oder Terminator der Liste
	} sll,		} sll,
	*first; // ~~globale~~ ~~Variable~~		*first; // Zeiger auf die verkettete Liste
	</syntaxhighlight>		</syntaxhighlight>
	nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.		nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.
Zeile 19:		Zeile 19:
	=== Version mit NULL ===		=== Version mit NULL ===
	Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Liste\|terminiert]] durch den [[Nullwert]] <code>NULL</code>.		Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Liste\|terminiert]] durch den [[Nullwert]] <code>NULL</code>.
	<syntaxhighlight lang="c" line highlight="10,13">		<syntaxhighlight lang="c" line highlight="9,12">
	// Global:
	first = NULL; // Terminierung vor der ersten Einfügung		first = NULL; // Terminierung vor der ersten Einfügung
	// NB: ~~Einfügung~~ nicht ~~gebracht.~~ ~~Sie~~ ~~hat~~ ~~aber~~ für ...		// NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
	// den immer gleichen Terminator (hier: Nullzeiger) zu sorgen.		// den immer gleichen Terminator (hier: Nullzeiger) zu sorgen.

Zeile 38:		Zeile 37:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	Die <code>for</code>-Schleife enthält pro Schleifenschritt die zwei (gelb ~~hinterlegte~~) Abfragen		Die <code>for</code>-Schleife enthält pro Schleifenschritt die zwei (gelb hinterlegten) Abfragen
	* <code>if (node != NULL)</code> und		* <code>if (node != NULL)</code> und
	* <code>if (node->key == search_key)</code>.		* <code>if (node->key == search_key)</code>.

	=== Version mit Sentinel ===		=== Version mit Sentinel ===
	Der ~~global zugreifbare~~ [[Zeiger (Informatik)\|Zeiger]] <code>sentinel</code> zum ~~für die Schleife gezielt zu präparierenden~~ Objekt <code>Sentinel</code> dient als Terminator der Liste <code>sll</code>.		Der [[Zeiger (Informatik)\|Zeiger]] <code>sentinel</code> zum Objekt <code>Sentinel</code> dient als Terminator der verketteten Liste <code>sll</code>.
			Das Objekt <code>Sentinel</code> ist für die Schleife gezielt zu präparieren.
⚫	<syntaxhighlight lang="c" line highlight="16">
			(In diesem Sinn ist es Teil der Datenstruktur <code>sll</code>.)
	// Globale Variable:
		⚫	<syntaxhighlight lang="c" line highlight="14">
	struct sll_node Sentinel, *sentinel = &Sentinel;		struct sll_node Sentinel, *sentinel = &Sentinel;
	// Global:
	sentinel->next = sentinel;		sentinel->next = sentinel;
	first = sentinel; // Terminierung vor der ersten Einfügung		first = sentinel; // Terminierung vor der ersten Einfügung
	// NB: ~~Einfügung~~ nicht ~~gebracht.~~ ~~Sie~~ ~~hat~~ ~~aber~~ für ...		// NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
	// den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.		// den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.

Zeile 72:		Zeile 71:
	* <code>if (node->key != search_key)</code>.		* <code>if (node->key != search_key)</code>.
	;Bemerkung		;Bemerkung
			Die Einführung des Wächterknotens macht aus der Operation Suchen, die ohne ihn eine [[Speicherzugriff\|Nur-Lese-Operation]] wäre, eine ''modifizierende'' Operation (ähnlich Einfügen und Löschen).
	Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch das Suchen per <code>SearchWithSentinel</code> ~~(modifizierende Operationen wie Einfügen und Löschen sowieso)~~ in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss~~. Dieser Nachteil kann wesentlich schwerer wiegen als der marginale Vorteil durch das Einsparen einer Abfrage pro Schleifenschritt~~.		Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch das Suchen per <code>SearchWithSentinel</code> in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss.
			Dieser zusätzliche Aufwand kann schwerer wiegen als das Einsparen einer Abfrage pro Schleifenschritt.

	== Siehe auch ==		== Siehe auch ==
	* [[Binärer Suchbaum#Suchen ohne Duplikate (iterativ und mit Sentinel)]] Wächterknoten in einem ~~Binären~~ Suchbaum		* [[Binärer Suchbaum#Suchen ohne Duplikate (iterativ und mit Sentinel)]] Wächterknoten in einem binären Suchbaum
	* Sentinel-Lymphknoten, siehe [[Wächterlymphknoten]]		* Sentinel-Lymphknoten, siehe [[Wächterlymphknoten]]

Nomen4Omen: /* Beispiel */ leichte Vereinheitlichung

2019-10-20T15:22:55Z

Beispiel: leichte Vereinheitlichung

← Nächstältere Version		Version vom 20. Oktober 2019, 17:22 Uhr
Zeile 11:		Zeile 11:
	{		{
	int key;		int key;
	struct sll_node *next; // ~~end~~-~~of-list-Indikator~~ oder -> ~~nächster~~ ~~Knoten~~		struct sll_node *next; // -> nächster Knoten oder Terminator der Liste
	} sll,		} sll,
	*first; // globale Variable		*first; // globale Variable
	</syntaxhighlight>		</syntaxhighlight>
	nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.		nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.
Zeile 22:		Zeile 22:
	// Global:		// Global:
	first = NULL; // Terminierung vor der ersten Einfügung		first = NULL; // Terminierung vor der ersten Einfügung
	// NB: Einfügung nicht gebracht. Sie hat aber		// NB: Einfügung nicht gebracht. Sie hat aber für ...
	// ~~für~~ den immer gleichen Terminator (hier: Nullzeiger) zu sorgen.		// den immer gleichen Terminator (hier: Nullzeiger) zu sorgen.

	struct sll_node *Search(int search_key)		struct sll_node *Search(int search_key)
Zeile 38:		Zeile 38:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	Die <code>for</code>-Schleife enthält pro Schleifenschritt die zwei Abfragen		Die <code>for</code>-Schleife enthält pro Schleifenschritt die zwei (gelb hinterlegte) Abfragen
	# <code>if (node != NULL)</code> und		* <code>if (node != NULL)</code> und
	# <code>if (node->key == search_key)</code> ~~(beide gelb hinterlegt)~~.		* <code>if (node->key == search_key)</code>.

	=== Version mit Sentinel ===		=== Version mit Sentinel ===
Zeile 50:		Zeile 50:
	sentinel->next = sentinel;		sentinel->next = sentinel;
	first = sentinel; // Terminierung vor der ersten Einfügung		first = sentinel; // Terminierung vor der ersten Einfügung
	// NB: Einfügung nicht gebracht. Sie hat aber		// NB: Einfügung nicht gebracht. Sie hat aber für ...
	// ~~für~~ den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.		// den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.

	struct sll_node *SearchWithSentinel(int search_key)		struct sll_node *SearchWithSentinel(int search_key)
Zeile 61:		Zeile 61:
	for (node = first;		for (node = first;
	node->key != search_key;		node->key != search_key;
	node = node->next) {}		node = node->next)
			{
			}
	if (node != sentinel)		if (node != sentinel)
	return node; // gefunden		return node; // gefunden
Zeile 67:		Zeile 69:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	Die <code>for</code>-Schleife enthält pro Schleifenschritt nur die eine Abfrage		Die <code>for</code>-Schleife enthält pro Schleifenschritt nur die eine (gelb hinterlegte) Abfrage
	#<code>if (node->key != search_key)</code> ~~(gelb hinterlegt)~~.		* <code>if (node->key != search_key)</code>.
	;Bemerkung		;Bemerkung
	Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch <code>SearchWithSentinel</code> (modifizierende Operationen sowieso) in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss.		Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch das Suchen per <code>SearchWithSentinel</code> (modifizierende Operationen wie Einfügen und Löschen sowieso) in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss. Dieser Nachteil kann wesentlich schwerer wiegen als der marginale Vorteil durch das Einsparen einer Abfrage pro Schleifenschritt.

	== Siehe auch ==		== Siehe auch ==

Nomen4Omen: /* Version mit Sentinel */

2019-10-20T13:23:05Z

Version mit Sentinel

← Nächstältere Version		Version vom 20. Oktober 2019, 15:23 Uhr
Zeile 63:		Zeile 63:
	node = node->next) {}		node = node->next) {}
	if (node != sentinel)		if (node != sentinel)
	return node; // gefunden		return node; // gefunden
	return NULL; // nicht gefunden		return NULL; // nicht gefunden
	}		}
	</syntaxhighlight>		</syntaxhighlight>

Nomen4Omen: /* Version mit NULL */

2019-10-20T13:21:41Z

Version mit NULL

← Nächstältere Version		Version vom 20. Oktober 2019, 15:21 Uhr
Zeile 35:		Zeile 35:
	return node; // gefunden		return node; // gefunden
	}		}
	// nicht gefunden:		return NULL; // nicht gefunden
	return NULL;
	}		}
	</syntaxhighlight>		</syntaxhighlight>

Nomen4Omen: /* Beispiel */ Zeilennummern line mit highlight

2019-10-20T13:18:43Z

Beispiel: Zeilennummern line mit highlight

← Nächstältere Version		Version vom 20. Oktober 2019, 15:18 Uhr
Zeile 7:		Zeile 7:
	== Beispiel ==		== Beispiel ==
	In den beiden folgenden [[C (Programmiersprache)\|C]]-Funktionen <code>Search</code> und <code>SearchWithSentinel</code> soll in einer [[Verkettete Liste\|verketteten Liste]] vom Typ		In den beiden folgenden [[C (Programmiersprache)\|C]]-Funktionen <code>Search</code> und <code>SearchWithSentinel</code> soll in einer [[Verkettete Liste\|verketteten Liste]] vom Typ
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c" line>
		⚫	struct sll_node // ein Knoten der verketteten Liste sll
⚫	// ~~Globale~~ Variable:
			{
⚫	struct sll_node { // ein Knoten der verketteten Liste sll
	int key;		int key;
	struct sll_node *next; // end-of-list-Indikator oder -> nächster Knoten		struct sll_node *next; // end-of-list-Indikator oder -> nächster Knoten
	} sll, *first;		} sll,
		⚫	*first; // globale Variable
	</syntaxhighlight>		</syntaxhighlight>
	nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.		nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.
Zeile 18:		Zeile 19:
	=== Version mit NULL ===		=== Version mit NULL ===
	Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Liste\|terminiert]] durch den [[Nullwert]] <code>NULL</code>.		Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Liste\|terminiert]] durch den [[Nullwert]] <code>NULL</code>.
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c" line highlight="10,13">
	// Global:		// Global:
	first = NULL; // Terminierung vor der ersten Einfügung		first = NULL; // Terminierung vor der ersten Einfügung
	// NB: Einfügung nicht gebracht.		// NB: Einfügung nicht gebracht. Sie hat aber
	// ~~Sie hat aber~~ für den immer gleichen Terminator zu sorgen.		// für den immer gleichen Terminator (hier: Nullzeiger) zu sorgen.

	struct sll_node *Search(int search_key) {		struct sll_node *Search(int search_key)
			{
	struct sll_node *node;		struct sll_node *node;
	for (node = first; node != NULL; node = node->next) {		for (node = first;
			node != NULL;
			node = node->next)
		⚫	{
	if (node->key == search_key)		if (node->key == search_key)
	return node; // gefunden		return node; // gefunden
	}		}
	// nicht gefunden:		// nicht gefunden:
Zeile 36:		Zeile 41:
	Die <code>for</code>-Schleife enthält pro Schleifenschritt die zwei Abfragen		Die <code>for</code>-Schleife enthält pro Schleifenschritt die zwei Abfragen
	# <code>if (node != NULL)</code> und		# <code>if (node != NULL)</code> und
	# <code>if (node->key == search_key)</code>.		# <code>if (node->key == search_key)</code> (beide gelb hinterlegt).

	=== Version mit Sentinel ===		=== Version mit Sentinel ===
	Der global zugreifbare [[Zeiger (Informatik)\|Zeiger]] <code>sentinel</code> zum für die Schleife gezielt zu präparierenden Objekt <code>Sentinel</code> dient als Terminator der Liste <code>sll</code>.		Der global zugreifbare [[Zeiger (Informatik)\|Zeiger]] <code>sentinel</code> zum für die Schleife gezielt zu präparierenden Objekt <code>Sentinel</code> dient als Terminator der Liste <code>sll</code>.
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c" line highlight="16">
	// Globale Variable:		// Globale Variable:
	struct sll_node Sentinel, *sentinel = &Sentinel;		struct sll_node Sentinel, *sentinel = &Sentinel;
	// Global:		// Global:
	sentinel->next = sentinel;		sentinel->next = sentinel;
	first = sentinel; // Terminierung vor der ersten Einfügung		first = sentinel; // Terminierung vor der ersten Einfügung
	// NB: Einfügung nicht gebracht.		// NB: Einfügung nicht gebracht. Sie hat aber
	// ~~Sie hat aber~~ für den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.		// für den immer gleichen Terminator (hier: Zeigerwert) zu sorgen.

	struct sll_node *SearchWithSentinel(int search_key) {		struct sll_node *SearchWithSentinel(int search_key)
			{
	struct sll_node *node;		struct sll_node *node;
	~~sentinel->key = search_key;~~ // gezielte Präparation		// gezielte Präparation:
			sentinel->key = search_key;

	for (node = first; node->key != search_key; node = node->next) {		for (node = first;
			node->key != search_key;
			node = node->next) {}
⚫	}
	if (node != sentinel)		if (node != sentinel)
	return node; // gefunden		return node; // gefunden
	// nicht gefunden:		return NULL; // nicht gefunden
	return NULL;
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	Die <code>for</code>-Schleife enthält pro Schleifenschritt nur die eine Abfrage		Die <code>for</code>-Schleife enthält pro Schleifenschritt nur die eine Abfrage
	#<code>if (node->key != search_key)</code>.		#<code>if (node->key != search_key)</code> (gelb hinterlegt).
	;Bemerkung		;Bemerkung
	Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch <code>SearchWithSentinel</code> (modifizierende Operationen sowieso) in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss.		Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch <code>SearchWithSentinel</code> (modifizierende Operationen sowieso) in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss.

2001:4CA0:0:F293:7CE0:F9C6:10BC:6FD8: Ich habe das Wort "dort" gelöscht. Es war stilistisch unschön.

2019-07-26T16:35:21Z

Ich habe das Wort "dort" gelöscht. Es war stilistisch unschön.

← Nächstältere Version		Version vom 26. Juli 2019, 18:35 Uhr
Zeile 1:		Zeile 1:
	Als '''Sentinel''' (Aussprache: {{Audio\|en-us-sentinel.ogg\|sentinel}}, engl. für ''Wächter''), '''Wächter''' oder '''Wächterwert''' (im engeren Sinn) bezeichnet man in der [[Informatik]], ~~dort~~ im Bereich der [[Programmierung]], ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis »gefunden« läuft.<ref>{{BibISBN\|9783540779773\|Seite=63}} 3 Representing Sequences by Arrays and Linked Lists</ref> Wenn so geschehen, wird nachträglich das Ergebnis auf »nicht gefunden« korrigiert.		Als '''Sentinel''' (Aussprache: {{Audio\|en-us-sentinel.ogg\|sentinel}}, engl. für ''Wächter''), '''Wächter''' oder '''Wächterwert''' (im engeren Sinn) bezeichnet man in der [[Informatik]], im Bereich der [[Programmierung]], ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis »gefunden« läuft.<ref>{{BibISBN\|9783540779773\|Seite=63}} 3 Representing Sequences by Arrays and Linked Lists</ref> Wenn so geschehen, wird nachträglich das Ergebnis auf »nicht gefunden« korrigiert.

	Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.		Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.

Nomen4Omen: /* Version mit Sentinel */ paralleler Zugriff

2016-10-26T17:00:30Z

Version mit Sentinel: paralleler Zugriff

← Nächstältere Version		Version vom 26. Oktober 2016, 19:00 Uhr
Zeile 63:		Zeile 63:
	Die <code>for</code>-Schleife enthält pro Schleifenschritt nur die eine Abfrage		Die <code>for</code>-Schleife enthält pro Schleifenschritt nur die eine Abfrage
	#<code>if (node->key != search_key)</code>.		#<code>if (node->key != search_key)</code>.
			;Bemerkung
			Wird auf die Datenstruktur [[Parallele Programmierung\|parallel]] (konkurrent) zugegriffen, dann gehört auch <code>SearchWithSentinel</code> (modifizierende Operationen sowieso) in einen [[Kritischer Abschnitt\|kritischen Abschnitt]], der durch ein [[Mutex]] abgesichert werden muss.

	== Siehe auch ==		== Siehe auch ==

← Nächstältere Version		Version vom 21. Oktober 2019, 16:25 Uhr
Zeile 1:		Zeile 1:
	Als '''Sentinel''' (Aussprache: {{Audio\|en-us-sentinel.ogg\|sentinel}}, engl. für ''Wächter''), '''~~Wächter~~''' oder '''Wächterwert''' (im engeren Sinn) bezeichnet man in der [[Informatik]], im Bereich der [[Programmierung]], ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis »gefunden« läuft.<ref>{{BibISBN\|9783540779773\|Seite=63}} 3 Representing Sequences by Arrays and Linked Lists</ref> Wenn so geschehen, wird nachträglich das Ergebnis auf »nicht gefunden« korrigiert.		Als '''Sentinel''' (Aussprache: {{Audio\|en-us-sentinel.ogg\|sentinel}}, engl. für ''Wächter''), '''Wächterknoten''' oder '''Wächterwert''' (im engeren Sinn) bezeichnet man in der [[Informatik]], im Bereich der [[Programmierung]], ein Konstrukt, welches eine Sequenz derart terminiert, dass die Programmlogik nach einer erfolglosen Inspektion aller echten Fälle abschließend (mit unechtem Erfolg) auf das Ergebnis »gefunden« läuft.<ref>{{BibISBN\|9783540779773\|Seite=63}} 3 Representing Sequences by Arrays and Linked Lists</ref> Wenn so geschehen, wird nachträglich das Ergebnis auf »nicht gefunden« korrigiert.

	Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.		Mit diesem Trick wird die Anzahl der Abfragen ''innerhalb'' der Suchschleife um ''eine'', nämlich die Abfrage auf das Ende der Sequenz, verringert – auf Kosten geringfügig komplizierterer Erfordernisse und Aktionen ''außerhalb'' der Schleife.

	Im weiteren Sinn gilt (insbesondere im englischen Sprachraum) jede ~~Form eines Terminators~~ einer Sequenz ~~als~~ ~~eines~~ normalerweise nicht ~~vorkommenden~~ ~~speziellen~~ ~~Objekts~~, so ~~auch~~ das [[Nullzeichen]] bei [[Zeichenkette#Repräsentation mit Abschlusszeichen\|Zeichenketten]], als Sentinel.		Im weiteren Sinn gilt (insbesondere im englischen Sprachraum) jede Terminierung einer Sequenz durch ein normalerweise dort nicht vorkommendes spezielles Objekt, so bspw. das [[Nullzeichen]] bei [[Zeichenkette#Repräsentation mit Abschlusszeichen\|Zeichenketten]], als Sentinel.

	== Beispiel ==		== Beispiel ==
Zeile 17:		Zeile 17:
	nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.		nach einem Schlüsselwert <code>search_key</code> gesucht werden – bei gleichem Suchergebnis.

	=== Version mit ~~NULL~~ ===		=== Version mit Nullzeiger ===
	Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Liste\|terminiert]] durch den [[Nullwert]] <code>NULL</code>.		Die Liste <code>sll</code> wird [[Liste (Datenstruktur)#Einfach verkettete Liste\|terminiert]] durch den [[Nullwert#Nullwert als grundverschiedener Wert\|Nullzeiger]] <code>NULL</code>.<ref>Ein [[Zeiger (Informatik)\|Zeiger]], der den Wert 0 haben kann, muss vor der [[Dereferenzierung]] ohnehin auf 0 abgefragt werden, da die Dereferenzierung sonst auf den meisten Betriebssystem-Maschinen-Kombinationen zum Crash führt.</ref>
	<syntaxhighlight lang="c" line highlight="9,12">		<syntaxhighlight lang="c" line highlight="9,12">
	first = NULL; // Terminierung vor der ersten Einfügung		first = NULL; // Terminierung vor der ersten Einfügung
	// NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...		// NB: Die (nicht gezeigten) Operationen Einfügen und Löschen haben für ...
	// den immer gleichen Terminator (hier: ~~Nullzeiger~~) zu sorgen.		// den immer gleichen Terminator (hier: NULL) zu sorgen.

	struct sll_node *Search(int search_key)		struct sll_node *Search(int search_key)