Den Rang eines Users herausfinden, ohne alle Users aufzulisten

Aufrufe: 195     Aktiv: vor 2 Monaten, 1 Woche

0

Ich habe die Frage auch bei mathefragen.de gestellt

Ich habe folgende Problemstellung:

es gibt 100 Tausend Users. Gegeben ist ein User A mit einem Punktestand von 3231. Ich will jetzt den Rang von User A herausfinden, abhängig von seinem Punktestand. Das Problem ist, ich möchte nicht alle 100k Users nach Rang sortiert auflisten und den Index von User A nehmen, was schon funktionieren würde, aber Hauptspeicher von meinem kleinen Laptop ist dafür zu wenig.

meine Frage: Kann man mathematisch den Punkte-Rang leichter herausfinden, mit diesen Informationen:

  • es gibt insgesamt 100k Users (oder Liste von nach Punkte sortierten Users)
  • ID und Punkte von User A

zu vermeiden ist die Liste von allen 100k Users.

Vielen Dank im Voraus

gefragt vor 2 Monaten, 1 Woche
h
holymoly,
Punkte: 12

 
Kommentar schreiben Diese Frage melden
1 Antwort
1

Eine unsortierte Liste musst du zuerst (zumindestens teilweise) sortieren

Wenn die bestehende Liste aber schon nach Punkten vollständig sortiert/indiziert ist, und nun lediglich die Frage im Raum steht, wo in dieser bestehenden, sortierten Liste der neue User A mit seinen Punkten einsortiert werden soll, musst du, wenn du das "Einsortieren" wirklich "händisch" machen willst, natürlich nicht mehr alle 100k Einträge durchgehen.

Ein Algortihmus wäre, immer A mit dem User zu vergleichen, der genau in der Mitte einer Teilmenge ist. Das kann man rekursiv und damit sehr kurz implementieren.

n = 100'000 (erste Teilmenge ist die Gesamtmenge)

  1. Schritt: A < U_n/2 ? (hat A weniger Punkte als User auf Platz 50'000?)

Wenn ja, dann muss A ja einen Rang zwischen 1 und (n/2-1) einnehmen Wenn nein, dann ist der Rang zwischen n/2 und n

mal angenommen, er gehört zur 2. Hälfte, nämlich n/2 bis n (zweite Teilmenge also nur noch 50'000 bis 100'000)

  1. Schritt: A < U_(3/4 n) (wir schauen also, ob A kleiner als Platz 75'000 ist)

Wenn ja, dann muss A ja einen Rang zwischen n/2 und (3/4 n -1) einnehmen (also 50'000 und 74'999) Wenn nein, dann ist der Rang zwischen 3/4 n und n (also in deinem Beispiel 75000 und 100000)

... usw. ... diesen Algorithmus als Schleife oder rekrusiv implementieren ...

Hinweis: Wenn dir das Arbeiten mit 100k Einträgen aber schon ein Problem mit dem RAM bringt, ist es weniger eine mathematische Frage, sondern eher eine Frage, wie du die Daten modelliert und wie genau implementiert hast. 100k Zeilen sortieren kann ja selbst Excel ... in SQL oder Pandas ist alles schon eingebaut, was du benötigst, um dieses Problem zu lösen - ohne Basis-Algorithmen wie sortieren/indizieren/filtern/einfügen/ändern etc. neu schreiben zu müssen.

geantwortet vor 2 Monaten, 1 Woche
p
p.o.
Punkte: 35
 
Kommentar schreiben Diese Antwort melden