Skip to content

Instantly share code, notes, and snippets.

@sahib
Last active Dec 27, 2015
Embed
What would you like to do?
I haz problemz.

Folgendes Problem zu libmunin:

  • Ich hab eine Liste von Songs.

  • Um Aussagen über deren ähnlichkeit zu machen muss ich die untereinander vergleichen. Das ergibt für N Songs ((N - 1) ^ 2 / 2) Vergleiche. Für N=32k ne ganze Menge. (Abgeschätzte Zeit wären ca. 13h, also unakzeptabel.)

    for song_a, song_b in combinations(song_list):
        distance = Song.compute(song_a, song_b)
    
        # Aufwändig ist nur die Berechnung der Distanz oben.
        song_a.distance_add(song_b, distance)
        song_b.distance_add(song_a, distance)
  • Mögliche Lösungsideen:

    1. Gruppen bilden

    Nachteile:

    • Was ist das Splitkriterium? (Merke: Distanzen zu anderen Songs sind zu diesem Zeitpunkt noch nicht vorhanden)
    • Man hat danach viele Gruppen. Wie verbindet man diese wieder?
    1. Einführung einer "Heuristik" die entscheidet ob es lohnt 2 Songs zu vergleichen:

      for song_a, song_b in combinations(song_list):
          if heuristic(song_a, song_b):
              distance = Song.compute(song_a, song_b)
              # ...

      Vorteil: Ein ganzer Graph würde rauskommen. Nachteil: Wie wäre so eine Heuristik aufgebaut?

    2. Weitere Ideen?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment