Zwei Zeiger und ein Schiebefenster – Wie KI Daten effizient scannt
Diese Lektion wurde automatisch ins Deutsche übersetzt und noch nicht von einem Menschen geprüft. Falls etwas seltsam klingt, gilt die englische Fassung.
Warum intelligentes Scannen wichtig ist
Stellen Sie sich eine KI vor, die einen Live-Video-Feed auf verdächtige Aktivitäten überwacht. Es kann nicht jede Sekunde die gesamte Aufnahme erneut ansehen – es muss ein Aufmerksamkeitsfenster über den Stream gleiten lassen und dabei gerade genug Kontext im Auge behalten. Das ist genau das, was die Muster zwei Zeiger und gleitendes Fenster für sequentielle Daten bewirken.
Beide Techniken verwandeln Brute-Force-O(n²)-Scans in elegante O(n)-Durchläufe.
Die Zwei-Zeiger-Technik
Platzieren Sie zwei Referenzen in einer Sequenz und verschieben Sie sie gemäß einer Regel. Es gibt zwei Hauptgeschmacksrichtungen.
Konvergierende Zeiger
Beginnen Sie an jedem Ende einen Zeiger und bewegen Sie ihn nach innen. Perfekt für sortierte Daten.
Klassisches Problem – Paarsumme: Finden Sie bei einem gegebenen sortierten Array zwei Zahlen, die sich zu einem Ziel addieren.
function pairSum(arr, target):
left = 0
right = arr.length - 1
while left < right:
sum = arr[left] + arr[right]
if sum == target: return (left, right)
if sum < target: left += 1
else: right -= 1
return null
Da das Array sortiert ist, erhöht das Verschieben von left nach rechts die Summe und das Verschieben von right nach links verringert sie – so wird garantiert, dass wir nie ein gültiges Paar verpassen.
Zeiger in die gleiche Richtung
Beide Zeiger bewegen sich vorwärts, allerdings mit unterschiedlicher Geschwindigkeit. Nützlich für Partitionierung oder Zykluserkennung.
Beispiel – Duplikate direkt entfernen: Ein langsamer Zeiger markiert die Schreibposition; Ein schneller Zeiger scannt vorwärts.
function removeDuplicates(arr):
slow = 0
for fast in 1..arr.length - 1:
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1
Diskussion
Anmelden um an der Diskussion teilzunehmen