Ist Sentinel lineare Suche besser als normale lineare Suche?

Question

In traditionellen linearen Suche, gibt es n Vergleich für den Vergleich mit der erforderlichen Anzahl und n + 1 für Looping-Bedingung, fasst bis 2n + 1 Vergleiche. Aber, wenn wir das folgende Verfahren befolgen, können wir unsere Antwort in n + 2 Vergleichen bei max bekommen.

def sentinelSearch(ar,n,l): 
# ar : array 
# n : item to be searched 
# l : size of array 
last = ar[l-1] # saving last element in other variable 
ar[l-1] = n # assigning last element as required 
i = 0 
while ar[i]!=n: 
    i+=1 
ar[l-1] = last 
if (i<l-1) or n==ar[l-1]: 
    print('Item found at',i) 
else: 
    print('Item not Found') 

Obwohl im schlimmsten Fall Zeit Komplexität beider Algorithmen ist O (n). Nur die Anzahl der Vergleiche wird reduziert, macht dies diese "Sentinel-lineare Suche" zu einem besseren Algorithmus für die Suche über unsortierte Arrays oder nicht?

Answer 1

Sie müssten es benchmarken. Aber es gibt mehrere Faktoren, die das Ergebnis beeinflussen können:

Verzweigungsprognose. Einige Bedingungen zu überprüfen ist weniger teuer als andere.

Compiler-Optimierungen. Viel Zeit wird die Schleife über Array abgerollt und Sie tatsächlich weniger als n Vergleiche für Looping-Bedingung.

Auch als Leute in Kommentaren erwähnt, muss Ihr Algorithmus das Array mutieren (in der Regel nicht gut) und Sie müssen besonderen Wert für Sentinel (nicht immer möglich) halten. Der tatsächliche Nutzen der Optimierung wäre also wirklich vernachlässigbar.