Funktion vorhanden - wie auf Transitivität erweitern?

[Pida]

Hallo zusammen,

ich stehe vor einem größeren Performance-Problem: In einer Datenbank habe ich etwa 38 000 Wörter, die zueinander in unterschiedlichen Verhältnissen stehen können. Es gibt die Relation Teil/ Ganzes und die Relation Ober-/ Unterbegriff.

Beispiel:
- Ein Rad ist Teil eines Fahrrads.
- Fahrrad ist ein Unterbegriff von Fahrzeug.

Um diese Daten nutzen zu können, verwende ich eine vorgegebene API (leider sind API und Datenbank nicht frei verfügbar). Dort gibt es bereits die Funktionen

getTeile() // liefert eine Liste mit 'Teilen'
getGanze() // ... mit 'Ganzen'
getOberbegriffe() // ... mit Oberbegriffen
getUnterbegriffe() // ... mit Unterbegriffen

Nun muss ich in meinem Programm häufiger testen, ob Wort A in einer Relation zu Wort B steht. Dazu schaue ich nach, ob beispielsweise B im Array A.getTeile() enthalten ist.

Mein Problem: Die oben angegebenen Funktionen der API sind nicht transitiv. Ich möchte aber beispielsweise auch die Relation von Reifen zu Rad zu Auto finden. Idealerweise hätten die Funktionen ein Parameter für die Kantenzahl, aber das ist leider nicht der Fall.

Momentan mache ich in etwa Folgendes (Pseudocode!). Hier wird true zurückgegeben, da Heimtier quasi ein indirekter Oberbegriff von Dackel ist:

LISTE eineHoeher = Dackel.getOberbegriffe(); // Hund, ... (die Listen enthalten oft nur ein Element)
LISTE EineOderZweiHoeher;

for each (candidate in eineHoeher) {
    EineOderZweiHoeher.addAll(candidate.getOberbegriffe())  // Heimtier, ...
    EineOderZweiHoeher.addAll(eineHoeher);  // Hund, Heimtier, ...
}

if (eineOderZweiHoeher ENTHÄLT 'Heimtier') return true;

Das ist wohl sehr ineffektiv, denn es verlängert die Laufzeit einer Testanwendung auf 150 Sekunden. Demgegenüber läuft das Programm in etwa 3 Sekunden durch, wenn ich lediglich direkte Relationen suche.

Könnt ihr mir sagen, wie ich das Ganze optimieren kann?

Vielen Dank
Pida

 

[Marco13]

Ohne eine genaue API-Beschreibung, Doku oder Quellcode kann man da nur raten. Aber das mach ich dann mal :

LISTE eineHoeher = Dackel.getOberbegriffe(); // Hund, ... (die Listen enthalten oft nur ein Element)
LISTE EineOderZweiHoeher;

for each (candidate in eineHoeher) {
    EineOderZweiHoeher.addAll(candidate.getOberbegriffe())  // Heimtier, ...
    EineOderZweiHoeher.addAll(eineHoeher);  // Hund, Heimtier, ...
}

if (eineOderZweiHoeher ENTHÄLT 'Heimtier') return true;

Falls das kein Tippfehler war, wird da ja für jedes Element in 'eineHoeher' nochmal die komplette 'eineHoeher'-Liste zur EineOderZweiHoeher hinzugefügt. Es wäre also so auf jeden fall schonmal besser:

LISTE eineHoeher = Dackel.getOberbegriffe(); // Hund, ... (die Listen enthalten oft nur ein Element)
LISTE EineOderZweiHoeher;
EineOderZweiHoeher.addAll(eineHoeher);

for each (candidate in eineHoeher) {
    EineOderZweiHoeher.addAll(candidate.getOberbegriffe())  // Heimtier, ...
}

if (eineOderZweiHoeher ENTHÄLT 'Heimtier') return true;

Außerdem könnte man ein "early return" machen, so dann man nicht immer ALLE Listen zusammenfasst, sondern raushüpft, sobald man fertig ist

LISTE eineHoeher = Dackel.getOberbegriffe(); // Hund, ... (die Listen enthalten oft nur ein Element)

if (eineHoeher ENTHÄLT 'Heimtier') return true;	

LISTE EineOderZweiHoeher;
EineOderZweiHoeher.addAll(eineHoeher);

for each (candidate in eineHoeher) {
    EineOderZweiHoeher.addAll(candidate.getOberbegriffe())  // Heimtier, ...
}

if (eineOderZweiHoeher ENTHÄLT 'Heimtier') return true;

Dann wäre noch interessant, wofür "LISTE" genau steht. Nur eine Collection? Eine List? Ein Set vielleicht? (Bei einer List ist die Laufzeit für den Enthaltenseins-Test O(n), bei einem Set nur O(1)!!!)


In jedem Fall solltest du aber überlegen, ob du diese Listen überhaupt brauchst! Wenn es NUR darum geht (ein mal) abzufragen, ob diese Relation besteht, dann könntest du ja einfach suchen (quasi eine Breitensuche). Ich mache jetzt mal die "minimale" Annahme, dass die LISTE eine Collection ist

boolean inRelationUp(Object rootObject, Object toSearchInUpperObjects, int depth)
{
    return inRelationUp(rootObject.getOberbegriffe(), toSearchInUpperObjects, depth);
}

boolean inRelationUp(Collection collection, Object toSearchInUpperObjects, int depth)
{
    if (collection.contains(toSearchInUpperObjects)) return true;
    if (depth > 1)
    {
        for (Object root : collection)
        {
            if (inRelationUp(root, toSearchInUpperObjects, depth-1))
            {
                return true;
            }
        }
    }
    return false;
}

// Aufruf:
inRelationUp("Dackel", "Heimtier", 2); // Liefert true
inRelationUp("Dackel", "Hund", 1); // Liefert true
inRelationUp("Dackel", "Heimtier", 1); // Liefert false

Das ist ungetestet, aber vom Prinzip her müßt's passen. Ggf. gibt's das gleiche dann eben für "inRelationDown".

 

[Pida]

Hallo Marco,

das werde ich mir morgen mal genauer anschauen. Vielen Dank.

Mehr Infos zur API habe ich leider nicht. Die liegt mir als jar vor; ich weiß nicht, wie ich da an den Quelltext komme.
Bei Bedarf werde ich weitere Infos zu meinem bisherigen Ansatz nachliefern, leider habe ich da eben noch nichts 'Fertiges'.

Viele Grüße
Pida

 

[Tobias]

Naja, aber eine Dokumentation wird doch hoffentlich dabei sein, oder?

mpG
Tobias

 

[Pida]

So, da bin ich doch nochmal.

@Marco: Ich denke, dein Ansatz wird mir helfen.
@Tobias: Ja, es gibt ein Javadoc. Da steht aber leider nur drin, dass z.B. einWort.getOberbegriffe() ein Array mit Oberbegriffen zurückgibt, mehr nicht.


Ich habe leider noch ein weiteres - und vielleicht zentraleres - Problem.

Die API liefert mir die Möglichkeit, z.B. Oberbegriffe für ein Wort zu finden. Der Objekttyp Wort ist Teil der API. Ich selbst arbeite aber mit dem selbst erstellten Objekttyp Eintrag, der eben unter anderem genau ein Wort enthält. Meinen eigenen Ansatz (den hatte ich vereinfacht) und Marcos Tipps habe ich nun versucht, als Methoden für Eintrag zu implementieren.

Das bringt aber Probleme mit sich: Es gibt nicht für jedes Wort einen Eintrag. Ich suche also nach Oberbegriffen für einen Eintrag und erhalte eine Liste von Wörtern. Jetzt will ich wieder für jedes davon nach Oberbegriffen suchen, aber das geht nicht - denn die Methode will ja von einem Eintrag-Objekt angefordert werden.

Für mich wäre die offensichtliche Lösung, meine Methoden in der Klasse Wort zu implementieren. Aber wie beschrieben ist die Bestandteil eines jar-Files...

Was macht man in einem solchen Fall? Kann ich an die Klasse im jar rankommen? Oder muss ich eine Klasse schreiben, die Wort erweitert (nicht, dass ich das mit meinem aktuellen Kenntnisstand könnte ;-)?

Vielen Dank
Pida

 

[Pida]

So, ich habe es nun mit Vererbung versucht.

Ich habe die Klasse Wort und möchte die um ein paar Funktionen erweitern. Also habe ich Folgendes probiert:

public class Wort extends Wort {
   // erstmal gar nichts, später meine Zusatzfunktionen
}

Das klappt nicht, da Klassen sich nicht selbst erweitern können.

public Class ExtWort extends Wort {
   // erstmal gar nichts, später meine Zusatzfunktionen
}

Das wird nicht akzeptiert, wenn auf der rechten Seite des Zuweisungsoperators ein Wort steht. Leider ist genau dies in meinem Programm immer der Fall:

// FEHLER:
// ExtSynset cannot be resolved tom a type
// Type mismatch: Cannot convert from Wort to ExtWort
ExtWort thisWort = getLink(j).getWort();

Was muss ich tun?

Vielen Dank
Pida

 

[Marco13]

Hm. Warum du die Methoden jetzt konkret für "Eintrag" implementiert hast, weiß ich nicht - ich weiß ja nichtmal was ein "Eintrag" ist (d.h. was für Fields/Methoden noch dazukommen, wenn du von "Wort" erbst)

Aber eigentlich sollte die Methode an sich ja auch auf "reinen" Worten (d.h. Wörtern :wink: ) arbeiten können. (Sie ist ja eigentlich eine Art Utility-Funktion, die statisch sein könnte, und dann ist "egal", in welcher Klasse sie liegt)

class Eintrag 
{
    private Wort wort;
    ...

    // Können beide static sein und auf "Wort"-Objekten arbeiten...
    public static boolean inRelationUp(Wort rootWort, Wort toSearchFor, int depth) { ... }
    public static boolean inRelationUp(Collection<Wort> coll, Wort toSearchFor, int depth) { ... }

}

Aufrufen kann man sie dann entweder von außen

Eintrag eintrag = ...
Wort wort = ...
boolean inRelation = Eintrag.inRelationUp(eintrag.getWort(), wort, 3);

oder innerhalb von "Eintrag", wenn das bequemer oder schöner ist

class Eintrag 
{
    ...
    public boolean inRelationUp(Wort toSearchFor, int depth)
    {
        return Eintrag.inRelationUp(this.wort, toSearchFor, depth);
    }

    // Können beide static sein und auf "Wort"-Objekten arbeiten...
    public static boolean inRelationUp(Wort rootWort, Wort toSearchFor, int depth) { ... }
    public static boolean inRelationUp(Collection<Wort> coll, Wort toSearchFor, int depth) { ... }

}

// Verwendung
boolean inRelation = eintrag.inRelationUp(wort, 3);