Der leistungsstärkste Ansatz, um die engste Übereinstimmung aus der ungeordneten Sammlung zu finden ⇐ Python

[Anonymous]

Ich frage mich, was der beste Ansatz für die am nächsten stehende Übereinstimmung mit einem bestimmten Wert aus einer Sammlung von Elementen ist. Der wichtigste Teil ist die Nachbesserungszeit in Bezug auf die Eingangsgröße. Die Daten können so weit wie möglich herumgemischt und bewegt werden, solange die Suche schneller ist.

Code: Select all

MAX = 1_000_000
MIN = 0

target: float = 333_333.0
collection: set[float] = {random.uniform(MIN, MAX) for _ in range(100_000)}

# --- Code here to find closest as fast as possible, now and for future lookups ---

assert closest in collection and all(abs(target - v) >= delta for v in collection)

Ansatz 1
Iterieren Sie alle Werte und aktualisieren Sie am nächsten entsprechend. Sehr einfach, aber sehr langsam für große Sammlungen. < /P>

Code: Select all

closest: float = next(iter(collection))  # get any element
delta: float = abs(closest - target)

for v in collection:
tmp_delta = abs(v - target)

if tmp_delta  < delta:
closest = v
delta = tmp_delta
< /code>
 Ansatz 2 < /h2>
Daten sortieren und dann über binäre Suche am nächsten finden. Sortierzeit ist o (n log n), aber zukünftige Lookups werden nur O (log n) Zeit nehmen, um zu finden! < /P>
sorted_collection: list[float] = sorted(collection)

idx = bisect.bisect_right(sorted_collection, target)

if idx == 0:
return sorted_collection[0]
if idx == len(sorted_collection):
return sorted_collection[-1]

before, after = sorted_collection[idx - 1], sorted_collection[idx]
return before if target - before