Name des Algorithmus gesucht

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo Freunde,

ich verwende in einem Programm einen Alg. zum Vergleich zweier Listen, der mir die Unterschiede wiederum in 2 Listen zurückgibt.
Diesen habe ich von einem Kollegen genannt bekommen, er funktioniert auch einwandfrei, ich benötige jedoch den Namen, da ich diesen in einer schriftlichen Arbeit erwähnen möchte.

Prinzipielle Funktionsweise:
Es gibt 2 Listen a und b. Diese enthalten sortierte Werte der Menge M. Es gilt: M ist die Vereinigung von a und b. M wird nicht verändert, es können lediglich Werte von a nach b, bzw. von b nach a verschoben werden.

Und genau dies ist das Gefragte:
Welche Werte waren vorher nicht in a bzw. wurden von a nach b verschoben?

Legende:

  • a und b sind sortierte Listen von Integer-Werten
  • anhand von aPos und bPos wird jeweils bis zu den Enden (aSize und bSize) der Listen gewandert
  • die in a eingefügten Werte werden in einer Liste inserted aufgenommen
  • die in a gelöschten Werte werden in einer Liste deleted aufgenommen

Kleines Beispiel:
M = {1,2,3,4,5,6,7,8,9}
a = {1,2,3,4,5,6}
b = {7,8,9}
Nach Verschieben von Elementen:
a = {1,2,3,7,8}
b = {4,5,6,9}
=> inserted = {7,8}
=> deleted = {4,5,6}

while( 1 )
{
 if( posa Append( aa );
 posa++;
 }
 else if( aa \> bb )
 {
 inserted-\>Append( bb );
 posb++;
 }
 }
 else if( aa == -1 )
 {
 // Rest von b an inserted hängen
 while( posb Append( b[posb] );
 posb++;
 }

 break;
 }
 else if( bb == -1 )
 {
 // Rest von a an deleted hängen
 while( posa Append( a[posa] );
 posa++;
 }
 break;
 }
 else
 break;
}

Ich bin dankbar, wenn mir jemand den Namen dieses Alg. veraten kann.

Ciao, Bill

#2

evl. ‚alternierende Listensuche‘
Hallo Bill,

ich bin mir zwar nicht ganz sicher, ob es das richtige ist - aber das könnte evl. die „alternierende Listensuche“ sein.

ich verwende in einem Programm einen Alg. zum Vergleich zweier
Listen, der mir die Unterschiede wiederum in 2 Listen
zurückgibt.

Hatte jedenfalls vor einiger Zeit in einem Artikel was über einen als „alternierende Listensuche“ bezeichneten Algorithmus gelesen, der in der Art und Weise arbeitet.

Würde aber nicht wetten, dass es wirklich das ist :wink:

Gruß,
Nina

#3

Hi Bill,

also die Erklärungen Deines Alg. sind einfach unvollständig. Ich habe mir mal die Mühe gemacht und das von Dir angegeben Listing in ein c+±Programm zu kopieren. Dann habe ich das von Dir angeführte Beispiel mit dem Code ausgeführt. Das Ergebnis ist:

Vor Sortierung:
 a = {1,2,3,4,5,6,}
 b = {7,8,9,}

Nach Sortierung:
 a = {1,2,3,4,5,6,}
 b = {7,8,9,}
 inserted = {7,8,9,}
 deleted = {1,2,3,4,5,6,}

Die Analye des von Dir angegeben Listing bestätigt auch das Ergebnis: die Listen a und b werden ja in dem gesamten Code nicht verändert, es werden lediglich Position für Position die Werte verglichen, falls der Wert von a kleiner ist als b, wird er in ‚deleted‘ eingefügt, falls er gleich ist passiert gar nichts, ansonsten wird er in inserted eingefügt.

Das von Dir angefügte Beispiel ist auch nicht selbsterklärend: also ich kann nicht festellen, nach welchen Alg. die Werte hin - und hergeschoben werden.

Wenn ich das Problem richtig deute, dann handelt es sich bei dem Vergleichs-Alg. um ein sog. ‚lexicographical_compare‘ also um ein lexikografisches Vergleichen der Elemente in den beiden Listen (d.h. position für Position werden die Elemente anhand von operator ’
// main.cpp

#include
#include
#include
#include

using namespace std;

typedef vector IntVector;

void sortLists(IntVector& a,IntVector& b,IntVector& inserted,IntVector& deleted)
{
// clear results
inserted.clear();
deleted.clear();

// initializing of locals
int aa = 0,
bb = 0;

size_t posa = 0,
posb = 0,
sizea = a.size(),
sizeb = b.size();

while( 1 )
{
if( posa bb )
{
inserted.push_back( bb );
posb++;
}
}
else if( aa == -1 )
{
// Rest von b an inserted hängen
while( posb (cout,","));
cout(cout,","));
cout(cout,","));
cout(cout,","));
cout(cout,","));
cout(cout,","));
cout

#4

Hi Rolf,

ich hatte mich bissel unverständlich ausgedrückt, da geb ich dir Recht. Dies liegt aber daran, dass ich meinen eigentlich verwendeten Alg. auf ein minimales herunterbrechen will. Im Wesentlichen nutze ich ihn, um in einer Datenbank die Relationstabelle einer M:N-Beziehung zu manipulieren, daher inserted und deleted.

Also nochmal einfacher:

Dieser Algorithmus vergleicht zwei sortierte Listen a und b anhand ihrer Elemente, wobei a die ursprüngliche Liste ist. Alle in b hinzugefügten Elemente werden in eine Liste inserted geschrieben, alle in b entfernten Elemente werden in eine weitere Liste deleted geschrieben.

Aber du hast das Problem schon erkannt. Danke auch für den Quellcode, ich habe ebenfalls einen in C++ geschrieben, der mir dann lediglich die unterschiedlichen Elemente via STDOUT ausgibt. Dieser ist absichtlich ganz einfach gehalten, da er eben nur zur Demo dient.

Danke für deine Mühen
Bill

#include 

int main()
{
 int a[6] = {1,2,3,4,5,6};
 int b[5] = {1,2,3,7,8};

 int posa = 0;
 int posb = 0;

 int sizea = 6;
 int sizeb = 5;

 int aa, bb;

 while( 1 )
 {
 if( posa bb )
 {
 cout