Indexdefekte

Arbeitsschritte

Eine Heranführung an Indexdefekte

Indexdefekte treten auf, wenn man einen ungültigen Index beim Durchlaufen eines Arrays oder einer anderen Datenstruktur benutzt. Viele Sprachen benutzen nullbasierte Indizes. Das heißt, dass gültige Indizes bei einem Array der Größe N von 0 bis N-1 gehen. Dies führt zu häufigen Indexdefekten, wenn man mittels einer Schleife durch so eine Datenstruktur läuft und mit dem Index 1 statt 0 beginnt. Das sollte man beispielsweise in Python bei der Nutzung der Funktion range(1, n) beachten, die die Zahlen von 1 bis n-1 beinhaltet.

1
2

for i in range(1, n):
    # code that processes array[i]

Wenn Sie die Indizierung bei 1 statt bei 0 beginnen, verpasst der Code das erste Element des Arrays. In Python kann man range(n) als Abkürzung für range(0,n) schreiben, wodurch dieser Defekt seltener auftritt. Der gleiche Defekt kann aber auch auf der anderen Seite des Arrays auftauchen: indem man nämlich i <= n als Fortsetzungsbedingung benutzt und fälschlich einen letzten Durchlauf mit i == n bekommt, der gar nicht funktioniert.

Manchmal werden solche Defekte auch als Off-By-One-Error bezeichnet. Was genau hinter solchen Defekten steckt, können Sie in der Aufgabe "Off By One"-Defekte herausfinden. Allerdings können Indexdefekte auch deutlich größer sein als nur eine Verschiebung um 1, besonders wenn der Index Teil einer Berechnung ist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def check(array_entry):
    ... # do some stuff with array_entry

def process_array(my_array):
   for k in range(len(my_array)):
     index_to_check: int 
     if k < len(my_array) // 2:
         index_to_check = k
     else:
         index_to_check = len(my_array) + k
     check(my_array[index_to_check])

Dieser Code berechnet index_to_check im else-Ausdruck völlig falsch.

Ihre Aufgabe

Im Folgenden sollen Sie eine Funktion debuggen, in der ein Indexdefekt vorliegt. Die Funktion findet einen Substring in einem String. Die Rückgabe ist ein Tupel mit zwei Elementen:

• Das erste Element ist der Teil des Strings vor dem Substring.
• Das zweite Element ist der Rest des Strings, beginnend mit dem Substring.

Wird der Substring nicht gefunden, enthält das erste Element den vollen String und das zweite Element ist ein leerer String.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def find_substring(outer_string: str, sub_string:str) -> (str, str):
    """Finds the first occurrence of sub_string within outer_string.

       Returns a tuple of the part of the string
       before the first occurrence of sub_string,
       and the part starting at the first occurrence
       of sub_string. If not found, the second tuple
       is empty.
    """

    outer_len = len(outer_string)
    sub_len = len(sub_string)
    flag = 1
    i = 0   # declaring i beforehand so we can use it in the return statement

    for i in range(outer_len):
        for j in range(sub_len):
            if outer_string[i+j] != sub_string[j]:
                break
        else:
            # wind up here if for j loop terminates naturally
            flag = 0
            break  # break out of i loop

    return outer_string[:(i+flag)], outer_string[(i+flag):]


print(find_substring("Hello", "l"))

Hier sind einige Vorschläge, um an den Code heranzutreten:

1. Betrachten Sie die Variable flag. Sie hat einen sehr unglücklich gewählten Namen. Bestimmen Sie, wofür flag benutzt wird, und benennen Sie die Variable um.
2. Finden Sie heraus, welche Situationen in diesem Code auftreten können (wie beispielsweise, dass der Substring gar nicht gefunden wird).
3. Sehen Sie sich die Stellen an, an denen outer_string und sub_string indiziert werden. Welche Einschränkungen gibt es für die Indizierung in diesen Zeichenketten und was bedeutet das für die Einschränkung der verwendeten Variablen?
4. Überlegen Sie, wann genau das else der for-Schleife in Zeile 19 ausgelöst wird. Falls for-else nicht bekannt ist, hilft ein Blick in die Python-Dokumentation.

• Defekt gefunden? Prima. Dann jetzt bitte in Indexierungsdefekte.py korrigieren.
• Machen sie einen Commit Indexierungsdefekte corrected, der nur genau diese modifizierte Datei enthält.
• 1 git -P show HEAD