Treppenförmiges suchen

[CLI_Andreas_Schmidt]

Hallo @all,

ich habe folgendes Problem:

1. Dokument in der Ansicht
2. Im Dokument gibt es ein Feld mit einem Flag der zum Suchen des nächsten Dokuments genommen wird. Wenn ein Dokument gefunden wird, muss im gefundenen wieder das Flag-Feld ausgelesen werden und da nächste Dokument gesucht werden. usw....

3. Alle Dokumente befinden sich immer in einer Ansicht (Documentcollection)
4. Bei welchem Dokument angefangen wir zu suchen ist das unprocessedDocument


Ganz einfach erklärt. Es soll in jedem DokumentenPFAD (die Dokumente müssen nicht untereinander liegen) ein Wert gesetzt werden. Es gibt als Verbindung nur das Flagfeld und nicht vielleicht (das wäre schön) die docid.

Meine Frage ist jetzt: Wie kann man eine Schleife programmieren, wenn ich nicht weis wie oft sie durchlaufen wird.

Grüble schon einige Zeit

Danke für Hilfe im voraus

[m3]

Nicht Schleife, Rekursion!

[klaussal]

@andreas,

Ich würd den Schleifenzähler auf 99999999 setzen und in der Schleife abfragen, ob Flag gesetzt ist oder nicht. Wenn nicht, den Zähler "per Hand" auf 99999999999 setzten und schon ist aus die Maus.

klaus

[Sunrider]

zu 3. Documentcollection und Ansicht sind doch 2 Stiefel...
zu 4. DB.unprocessedDocuments gibt dir eine Documentcollection zurück... und kein einzelnes Document.

Was ist ein DokumentPFAD? ein Feld?

Ich weiss auch nie wie oft genau eine Schleife durchlaufen wird, aber ich weiss, das sie solange durchlaufen wird wie:
 ... es ein nächstes Dokument gibt.
 ... mein Wert = true ist
 ...

Ich denke die Bedingung ist auschlaggebend und nicht die aktuelle Anzahl der Durchläufe.
Wenn nicht:

i = 0
Schleife Start
  i = i + 1
Schleifen ende

Anzahl der Durchläufe: i

oder

du meinste eine Funktion, die nach ihrem Dokumenten sucht und für jedes gefundene Dokument sich selbst wieder aufruft. -> Rekursive Funktion

[CLI_Andreas_Schmidt]

Danke erst einmal für die Antworten.

Also zu: "Sunrider"

Die DocumentCollection brauche ich um nicht alle Dokumente zu durchsuchen. In der Ansicht sind ein bestimmte Auswahl von Dokumente, auf die nochmals gesucht wird. Also ---> documentcollection.

Die Collection unprocessedDocument wird auch benötigt, da mehrere PFADE ----> Antwort ein Pfad besteht aus allen zu suchenden Dokumenten. (KEIN FELD) Beispiel:

Im Dokumente 1 steht: 01 - 02
Im Dokuement 2 steht: 02 - 03
Im Dokuement 3 steht: 03 - 04

Jetzt will ich in Dokument 1 etwas ändern und muss die weiteren Dokumente suchen, die zur richtigen Reihenfolge gehören. Natürlich stehen zwischen den Dokumenten auch andere, die zu anderen PFADEN gehören.

Das Wort Rekursion von "m3 " finde ich interessant. Was genau ist das  und wie soll das gehen. Ich kann das Wort gar nicht richtig einordnen. Selbst nie benutzt.

Gruss

Andreas

[m3]

Rekursion -> siehe auch Rekursion. 

Rekursion allgemein:
http://de.wikipedia.org/wiki/Rekursion

Mit Lotus Script:
http://www.dominopower.com/issues/issue200003/recursion001.html

[Sunrider]

Rekursion
aus Wikipedia, der freien Enzyklopädie

Rekursion bedeutet Selbstbezüglichkeit (von lateinisch recurrere = zurücklaufen). Sie tritt immer dann auf, wenn etwas auf sich selbst verweist.
Rekursion ist ein allgemeines Prinzip zur Lösung von Problemen. In vielen Fällen ist die Rekursion eine von mehreren möglichen Problemlösungsstrategien, sie führt oft zu "eleganten" mathematischen Lösungen. Als Rekursion bezeichnet man den Aufruf oder die Definition einer Funktion durch sich selbst. Ohne geeignete Abbruchbedingung geraten solche rückbezüglichen Aufrufe in einen so genannten infiniten Regress (umgangssprachlich Endlosschleife).

Zur Vermeidung von infinitem Regress insbesondere in Computerprogrammen bedient man sich der semantischen Verifikation von rekursiven Funktionen. Der Beweis, dass kein infiniter Regress vorliegt, wird dann zumeist mittels eine Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer möglich (siehe Halteproblem).


D.h. für dich:

findeDoc(docMe)
{
  docNext = wo feldwert docMe.x(0) ist 
  call findeDoc(docNext)
}

Viel Glück

[Marinero Atlántico]

2. Im Dokument gibt es ein Feld mit einem Flag der zum Suchen des nächsten Dokuments genommen wird. Wenn ein Dokument gefunden wird, muss im gefundenen wieder das Flag-Feld ausgelesen werden und da nächste Dokument gesucht werden. usw....

Ich finde deinen Gebrauch von flag hier ein bischen irreführend oder ich verstehe die nicht vorliegende Anwendung nicht. Es handelt sich wohl eher um "Pointer" auf die "nächsten Dokumente". Flag ist für mich irgendwie binär. Flag gesetzt oder nicht. Wahr oder Falsch.

Meine Frage ist jetzt: Wie kann man eine Schleife programmieren, wenn ich nicht weis wie oft sie durchlaufen wird.

Wie schon angemerkt, schreit dieses Problem nach einer rekursiven Lösung.
Rekursion kommt relativ häufig vor. V.a. bei solchen Baum-artigen Datenstrukturen.
Schaue es dir auf jeden Fall im Debugger gut an.
Ein Problem hast du bei Rekursion immer, wenn zirkuläre Referenzen möglich sind. Dann kann es zu einer Art Endlosrekursion kommen.
Beispiel:
Struktur 1: Doc-Blau referenziert Doc-Grün und Doc-Gelb
Struktur 2: Doc-Grün referenziert Doc-Rot
Struktur 3: Doc-Rot referenziert Doc-Blau (PROBLEM!)
Struktur 4: Doc-Gelb referenziert NICHTS
Du hast jetzt die folgenden Pseudo-Code-Funktion rekursiv:

Code

function processWorkflowTree(Document doc) {
 // do Stuff
 Collection col = doc.getNextInWorkflow("fieldName");
  if (col.count > 0) {
     docNext = col.getFirstDocument()
      while not (docNext is Nothing)  {
               processWorkflowTree(docNext); // REKURSIVER Aufruf !!!
                set docNext = col.getNextDocument();
        }
}

Wenn man das durchlaufen lässt, wird bei Struktur 3 wieder  doc-Blau gefunden und das ganze fängt ewig von vorne an.
Man kann sich aber davor schützen. wenn du dir ausserhalb der rekursiven Funktion - also z.B. in einer globalen Variable - dir alle document merkst, die bereits bearbeitet worden sind.

Rekursion muss man einfach mal gemacht haben. Dann ist es garnicht mehr so schwierig. Schaue es dir auf jeden Fall gut im Debugger an.
Eine aufrufende Routine ruft sich selber als aufgerufene Routine auf. Sobald die aufgerufene Routine abgearbeitet ist, geht der "Kontext" wieder zurück auf die aufrufende Routine.

Poste bis Sonntag mal ein Beispiel.

Rekursion begegnet mir relativ oft bei Baumstrukturen:
- xml/xslt
- Tree(?) in swt oder JTree in Swing, d.h. Gui-Widgets die so aussehen wie die rechte Seite im Windows-File Explorer.

Gruß Axel

[Marinero Atlántico]

infiniten Regress (umgangssprachlich Endlosschleife).

Protest. Ich würd sagen, dass ist was anderes. Endlosschleife ist für mich sowas wie

while (true)

loop

infiniter regress wie du es beschreibst, ist etwas anderes (kannte das Wort vor deiner Definition nicht).
(ja, ich bin so)

dass kein infiniter Regress vorliegt, wird dann zumeist mittels eine Schleifeninvariante geführt (siehe auch Invariante). Dieser Beweis ist allerdings nicht immer möglich (siehe Halteproblem).

Kann mir den Teil vielleicht mal jemand erklären. Den verstehe ich nämlich nicht. Jens? Bernhard? Sunrider?

[TMC]

Zum Thema rekusiver Aufruf: das ist eigentlich sehr mächtig, hatte ich aber bisher fast noch nie eingesetzt.

Hier mal ein Beispiel wie mal ein Einsatz von mir war.


Eine Anforderung war mal, Dokumenten incl. allen Antworten (mehrstufig) ein Archiv-Flag mitzugeben.

Der User hat also ein Hauptdokument ausgewählt in der View, und per Buttonklick sollte dieses Dok mit allen AW-Dokumenten archiviert werden.

Dabei hat die aufgerufene Routine dann folgende Sub aufgerufen (hier übergebe ich das Hauptdokument als NotesDocument):

Code

Sub ArchiveResponses(doc As NotesDocument)
	
	Dim dc As NotesDocumentCollection
	Dim tmpDoc As NotesDocument
	Dim dummy As NotesDocument
	
	Set dc = doc.Responses
	Set dummy = dc.GetFirstDocument
	While Not (dummy Is Nothing)
		Set tmpDoc = dc.GetNextDocument(dummy)
		Call ArchiveResponses(dummy)
		Call dummy.ReplaceItemValue("Archive","Yes")	
		Call dummy.Save(True, True)	
		Set dummy = tmpDoc
	Wend
	
End Sub

Danach wird dann noch das doc selbst mit "doc.Archive = "Yes"" archiviert.

[koehlerbv]

@Axel:

Eine Invariante ist eine Bedingung, die in jedem Programmzustand erfüllt sein muss. Bei der Implementierung einer Schleife muss beispielsweise innerhalb dieser immer gelten, dass die Schleifenvariable kleiner ist als der Wert der Abbruchbedingung. Invarianten können zum Beweis der Korrektheit von Algorithmen verwendet werden.

Das schreibt der Wikipedia-Eintrag, auf den ja Bezug genommen wird.
Dort steht aber auch (noch): "Zu umständlich beschrieben - der Beitrag ist in der Diskussion".

Ich verstehe das so (und praktiziere das ggf. auch so):
Eine globale Variable hat einen vorab definierten Zustand, zum Bleistift "False". Auf diesen Zustand wird in den nachfolgenden Routinen permanent geprüft. Tritt eine bestimmte Bedingung ein, wird die Variable in einen anderen Zustand versetzt ("True"). Die nächste Prüfung innerhalb der abhängigen Routinen (beispielsweise innerhalb einer Rekursion) schlägt jetzt fehl (naja, das ist falsch - die Prüfung stellt den neuen Zustand fest) und bricht jetzt alle Folgeaktionen - egal, welche noch aufgerufen werden, ab.

Im Problem vom CLI könnte das auch die Lösung für den Abbruch der Rekursion sein: Die Routine, die die "verlinkten" Dokumente (ich sag' das jetzt mal so, da uns das Verfahren ja noch vollkommen unklar ist) verfolgt und aktualisiert, meldet als Function das Ergebnis zurück: True -> weitermachen, False -> Fehler oder fehlende weitere Verknüpfung oder - wie schon richtig angemerkt - ein Rückverweis und damit eine "In Ewigkeit, Amen, sprach die Endlosschleife", also "Ende Gelände".

Bernhard

PS: Der CLI sollte sich unbedingt vom Begriff "Treppenförmiges Suchen" trennen, das kann zu argen Begriffsverwirrungen führen, weil das einen geraden Weg impliziert. Hier geht es aber wirklich um Rekursion (also eigentlich überhaupt keinen Zusammenhang zur "Schleife", die irgendwie geradlinig oder von mir aus auch "treppenförmig" ist) oder ist - um in den Metaphern zu bleiben - eher an das (theoretische) Matrjoschka-Prinzip angelehnt.