Skip to content

Instantly share code, notes, and snippets.

@sahib

sahib/problem.rst

Last active December 27, 2015 12:39
Show Gist options
  • Save sahib/7327137 to your computer and use it in GitHub Desktop.
Save sahib/7327137 to your computer and use it in GitHub Desktop.
Download ZIP
I haz problemz.
Raw
problem.rst

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