Effiziente Suche in Liste von eigener Klasse

Hallo,

ich habe ein kleines Programm zur Filme-Verwaltung geschrieben. Darin hab ich unter anderem eine Klasse "user_has_movie", in der jeweils die Bewertung eines Users für einen Film gespeichert wird. Mittlerweile sind es über 1000 Filme und ein halbes Dutzend User, was leider dazu führt, dass "getAllMovies()" ewig dauert. Ich habe deswegen bei "user_has_movie" mal IComparable verwendet und dachte nach der Sortierung würde es schneller gehen. Dies hat leider nicht viel gebracht, ich hoffe ihr habt einen Vorschlag, wie man das besser lösen kann, damit das "getAllMovies()" schneller geht.

Anbei die relevanten Stellen aus meinem Programm in gekürzter Version:

    static void Main() {
        database db = new database();
        // db befüllen...
        db.usersHasMovie.Sort();
        string test = getAllMovies(db);
    }

    public static string getAllMovies(database db) {
        string text = "";
        foreach (movie m in db.movies) {
            text += m.title;
            foreach (user u in db.users) {
                user_has_movie uhm = db.usersHasMovie.Find(o => o.movie_id == m.id && o.user_id == u.id);
                text += ";" + Convert.ToString(uhm.rated);
            }
            text += "\n";
        }
        return text;
    }

    class database {
        public List<movie> movies = new List<movie>();
        public List<user> users = new List<user>();
        public List<user_has_movie> usersHasMovie = new List<user_has_movie>();
    }

    class user_has_movie : IComparable<user_has_movie> {
        public int user_id = 0;
        public int movie_id = 0;
        public int rating = 0;

        public int CompareTo(user_has_movie uhm) {
            if (this.movie_id == uhm.movie_id) {
                if (this.user_id == uhm.user_id)
                    return 0;
                if (this.user_id > uhm.user_id)
                    return 1;
                else
                    return -1;
            }
            if (this.movie_id > uhm.movie_id)
                return 1;
            else
                return -1;

        }
    }

Vielen Dank für die Hilfe im Vorraus!

Das Sortieren hat wenig nutzen da trotzdem die gesamte Liste durchsucht wird.
Deine Listen kannst Du paralelisieren. Allerdings gehe ich davon aus das die meiste Zeit für die Stringverkettung drauf geht.

Lass mal testweise die Stringoperationen weg und schau obs schneller wird. Falls ja, nimm einen Stringbuilder statt einem String.

Du hast zwei foreach verschachtelt, die suchen deinen Angaben nach also etwa 6000 mal nach dem Inhalt einer Liste.
Was verstehst du unter "ewig"? Ich weiß jetzt nicht obs wirklich soooo lange dauert.
Hast du schon mal an eine Datenbank gedacht? Wäre für dein Vorhaben sicher sinnvoll.

Ich denke, wenn man die Entities sauber gestaltet, und Relationen zueinander bildet (beim Start der Anwendung zB eine XML serialisieren, oder was dahinter auch immer stecken mag) und der Flaschenhals des ständigen Suchens wäre weg.

Ok, das mit dem "ewig" war etwas übertrieben, aber es sind halt volle 2 Sekunden und das ist etwas lang. Ich verwende das im Zusammenhang mit einem DataGridView, bei welchem man in jeder Spalte suchen kann. Dies ging bisher auch sehr schnell, aber seit ich mehr als einen User habe, dauert es halt deutlich länger.

Ohne die String-Operationen dauert es tatsächlich nur halb so lang, da kann ich wohl auf jeden Fall noch was machen.

An eine Datenbank habe ich auch schon gedacht, aber bisher erschien mir das etwas Overkill für eine private Film-Liste.

Du kannst ein HashSet<user_has_movie> bilden. Allerdings muß usersHasMovie dann hashfähig gemacht werden.

Ok, vielen Dank für eure Antworten!

Das mit dem HashSet werd ich auch mal ausprobieren.

Hallo Comand

Mittlerweile sind es über 1000 Filme

Ich verwende das im Zusammenhang mit einem DataGridView

Ich bezweifle das ein Mensch mehr als (sind wir grosszügig) 100 Datensätze miteinander verarbeiten kann. Daher wäre da wohl Paging angebracht mit SKIP und TAKE. Deine 2 Sekunden werden dann wohl zu 2 milisekunden 😉

Beste Grüsse

Diräkt

Ich bezweifle das ein Mensch mehr als (sind wir grosszügig) 100 Datensätze miteinander verarbeiten kann.

Das kommt drauf an, wie man arbeitet. Ich mag z.B. Paging überhaupt nicht. Bei einer Filmverwaltung würde ich lieber schnell zu dem richtigen Buchstaben scrollen wollen. Oder schnell filtern oder suchen. Und tausend Einträge sind ja nun wirklich nicht so viel, dass es nicht schnell genug funktonieren würde.

Du hast zwei foreach verschachtelt, die suchen deinen Angaben nach also etwa 6000 mal nach dem Inhalt einer Liste.

Das mit den 6.000 Durchläufen ginge ja noch, leider sind es hier aber geschätzte 18 Mio Durchläufe! Wieso? Weil sich Komplexität gerne trügerisch kapselt. Wie sich List<T>.Find so einfach darstellt trügt einen davor, dass dies intern nichts anderes macht als eine (in dem Fall weitere) For-Schleife auf die Abfragemenge aufzubauen. Gehen wir davon aus, dass jeder Nutzer jeden Film bewertet hat (und anderenfalls würde der gepostete Quellcode eine Nullreference werfen...) macht dies für 6.000 Einträge, 3.000 Durchläufe für jeden Nutzer, für jeden Film -> 1.000 x 6 x 3.000 = 18 Mio. Die String-Concats tun dann bei 18 Mio Durchläufen ihr übriges. Hier sollte dann dringend auf relationales Design zurückgegriffen werden, Also bspw:

class user_has_movie : IComparable<user_has_movie> {
        public User user {get;set;}
        public Movie movie  {get;set;}
        public int rating = 0;

Die Relationen können mittels EntityFramework recht einfach aufgebaut werden (auf eager-loading achten) oder auch einfach per Linq Joins (siehe hier)

Die Liste der user_has_movie müßte dann genau so oft durchlaufen werden, wie Ratings vorhanden sind...

Auch ganz nett zum Lesen was beliebte Fehler anbelangt: 8 most common mistakes c# developers make

Grüße, Mica

Danke, hab alles auf relationales Design geändert. Hat ne Weile gedauert, aber es läuft jetzt tatsächlich spürbar schneller 😉
Deine Quellen werde ich mir dann morgen mal anschauen.

Und auch an die anderen fleißigen Antwort-Schreiber ein Dankeschön!

Grüße, Jens

Hallo Comand,

das was console hier geschrieben hat, habe ich neulich in einem ähnlichen Fall in Warum haben WinForms, DataGridView & LINQ eine gute Performance? geschrieben. Es sind also beträchtliche Beschleunigungen möglich, wenn man das naive(*) Vorgehen vermeidet. Insbesondere eine Abfrage, ob ein User einen bestimmten Film hat, lässt sich um eine Aufwandsklasse reduzieren, also z.B. O(n) statt O(n^2), wenn man statt eine Liste zu durchsuchen, ein HashSet verwendet, wie das witte oben schon geschrieben hat.

Ich möchte dich außerdem auf [Hinweis] Wie poste ich richtig? Punkt 1.1.1 hinweisen. Den richtigen Umgang mit Collections setzen wir als bekannt voraus. Bitte beachte das vor etwaigen Nachfragen.

herbivore

(*) Gemeint ist das Vorgehen ohne Berücksichtigung der Aufwandsklassen.