Vergleichalgorithmus

[babuschka]

Hallo zusammen

Ich suche nach einem performanten Vergleichsalgorithmus, um die folgende Aufgabe zu erledigen:

Gegeben:

Ein Projekt besitzt eine Projektnummer. Mehrere Projekte können die selbe Projektnummer besitzen. Jedes Projekt kann (muss aber nicht) bis zu 8 Meilensteine mit jeweils einem Datum besitzen.

Gesucht:
Ein Algorithmus, der sämtliche Meilensteine eines Projekts, mit den Meilensteinen eines anderen Projekts mit der selben Projektnummer vergleicht. Dabei soll jedes Projekt mit jedem anderen Verglichen werden.

Lösung:
Ich habe bereits eine funktionierende Version programmiert. Mich würde interessieren, ob bereits entwickelte Vergleichsalgorithmen existieren, die meine Aufgabe möglichst performant lösen?

Meine Lösung:
Enumeration über alle Projekte
Enumeration über alle Meilensteine
Fetche alle gleichen Meilensteine in den anderen Projekten
Enumeration über alle gleichen Meilensteine
Wenn Datum von Meilenstein != Datum von gleichem Meilenstein && Meilenstein nicht in Dictionary
Füge Meilensteine dem Dictionary hinzu
Gibt Fehlermeldung aus

Das Dictionary brauche ich, damit ein Treffer nicht "x^anzProjekte mit ungl. MeilensteinDatum" mal angezeigt wird.

Vielen Dank für euere Bemühungen!

Gruss

 

[Marco13]

Ein paar Codeschnipsel könnten helfen, aber evtl. kann man da nicht sooo viel dran drehen. Vielleicht kann man ausnutzen, wenn die Meilensteine nach Datum sortiert sind, oder man verwendet Sets und macht was mit removeAll/retainAll, aber das ist nur ins Blaue geraten...

 

[babuschka]

Enumeration projectsToCheck = allProjects.objectEnumerator();
      NSMutableArray milestonesToCheck = new NSMutableArray();
      
      // get all milestones of selected projects
      while(projectsToCheck.hasMoreElements() == true){
        Project aProject  = (Project)projectsToCheck.nextElement();
        milestonesToCheck.addObjectsFromArray(aProject.ProjectMilestoneSorted());
      }

      // for each milestone in array
      for (int i=0; i < milestonesToCheck.count(); i++){
        ProjectMilestone aMilestone = (ProjectMilestone)milestonesToCheck.objectAtIndex(i);
        
        // get equal milestones in other projects
        Enumeration equalMilestones = aMilestone.equalMilestones().objectEnumerator();

        while(equalMilestones.hasMoreElements() == true){
          ProjectMilestone aEqualMilestone = (ProjectMilestone)equalMilestones.nextElement();

          // check if dates are different
          if(aMilestone.milestoneDate().equals(aEqualMilestone.milestoneDate()) == false){
            
            // remove equal milestone from array, so we do not compare twice
            milestonesToCheck.removeObject(aEqualMilestone);
            setMessage("Ausgabe");
          }     
        }
      }

 

[SlaterB]

die Aufgabe ist ziemlich unklar hinsichtlich der Vergleiche (müssen alle Milestone in zwei Projekten gleich sein oder nicht)
und hinsichtlich der Folge, was soll überhaupt passieren wenn was gleich ist oder nicht oder in China ein Sack Reis umfällt,

an deinem Programm fällt mir auf dass du dich weniger auf ganze Projekte sondern mehr auf einzelne Milestone konzentrierst,
inwiefern das gut oder schlecht ist, ist wie gesagt ohne genaue Vorgaben/ Beispiele schwer zu beurteilen

ein einfacherer Ansatz ohne große Komplexität wäre, jedes Projekt mit jedem anderen zu vergleichen,
vielleicht sortiert, damit nicht A mit B und später noch B mit A verglichen wird,
wie zwei Projekte verglichen werden ist dann die zweite Stufe in einer Untermethode


--------

und einen strukturellen Fehler dürftest du haben:
du entfernst aus der Liste/ Enumeration, während du darüber iterierst,

wenn i == 0 ist, dann wird das erste Element A aus der Enumeration geholt,
sollte dieses in Zeile 24 entfernt werden, verschwindet A aus der Liste und wahrscheinlich nimmt doch das nächste Element B den Platz auf Index 0 ein,
beim nächsten Schleifendurchlauf ist der Schleifenindex i == 1, an Position 1 in der Liste steht C, denn B steht ja an Index 0
-> es wird mit C weiter gemacht, B übersprungen

was stört dich überhaupt daran, A in der Liste zu belassen?
hat doch letztlich keine Auswirkungen, welche Objekte in der Liste verbleiben und welche nicht?

 

[babuschka]

Hallo SlaterB,

Erst mal Danke für deine Unterstützung

die Aufgabe ist ziemlich unklar hinsichtlich der Vergleiche (müssen alle Milestone in zwei Projekten gleich sein oder nicht)

Die Meilensteine sind vom Namen her gleich (Normalisiert in der Datenbank statisch eingetragen), besitzen aber ein unterschiedliches Datum. Das Ziel ist es, den Benutzer darauf hinzuweisen, dass ein Meilenstein in einem anderen Projekt, ein anderes Datum besitzt.

und einen strukturellen Fehler dürftest du haben:

Jap, den hab ich auch gerade bemerkt und versuche ihn zu lösen.

was stört dich überhaupt daran, A in der Liste zu belassen?

Ich wollte dieses "Vergleiche A mit B, aber B mit A nicht mehr" erreichen und dachte, dass dies so funktionieren würde. War aber offensichtlich eine Fehlüberlegung.

 

[Marco13]

Wie viel Freiraum hast du bezüglich der Verwendung von Alternativen zu "Enumeration" (veraltet) und "NSMutableArray" (was auch immer das ist) ? Mit Lists, Sets und vernünftigen hashCode/equals-Methods könnte man das vermutlich recht kompakt und intuitiv aufschreiben, nahe am Pseudocode

for (Project pa : projects)
{
    for (Project pb : projects)
    {
        Set<Milestone> ms = new HashSet<Milestone>();
        ms.addAll(pa.getMilestones());
        ms.removeAll(pb.getMilestones());

        // Jetzt sind in ms nur die unterschiedlichen Milestones von pa und pb
    }
}