lineare Suche

[e.le]

Hallo,

Ich habe die Aufgabe bekommen das Verfahren lineare Suche zu implementieren.
Jedoch weiß ich nicht, wie ich mein Programm dazu bringen soll, dass er mir die Anzahl an Vergleichen und die benötigte Zeit für die Suche liefert.
Ich weiß wie man die Vergleiche global zählt, jedoch ist dies nicht gefragt.
Könnt Ihr mir bitte helfen ?



Aktuelle Version:

def search_lin(word_list,word):
for index in range(len(word_list)):
if word_list[index] == word:
return index
else:
index = index + 1
return index

Mit freundlichen Grüßen
e.le

[Sirius3]

Das händische Index-Hochzählen ist unnötig, da das die for-Schleife schon macht. Wenn das Wort nicht gefunden wird, einen Index zurückzuliefern sieht für mich falsch aus.
Keine Abkürzungen verwenden, was soll ›lin‹ denn bedeuten? Keine Typen in Variablennamen, word_list -> words.
In Python iteriert man auch direkt über die Elemente einer Liste; falls man zusätzlich einen Index braucht, gibt es `enumerate`:

Code: Alles auswählen

def search_linear(words, word):
    for index, item in enumerate(words):
        if item == word:
            return index
    return None

Du zählst bereits die Anzahl der Vergleiche. Zum Zeitmessen gibt es das `time`-Modul.

[e.le]

So sollen wir die Funktion implementieren:

search_lin(word_list,word):
- input:
word_list(list[str]) - list of words that will be sorted
word(str) - word that is looked for in words_list

- Returns:
(int) - index(between 0 and len(word_list)-1) of word in word_list;
otherwise index=len(word_list))
(int) - sum of all swaps and compassions
(float) - used time in ms

[Sirius3]

Ja, so eine Aufgabenbeschreibung animiert dazu, seltsame Dinge zu programmieren. Das ist halt das Problem, wenn der Aufgabensteller eine bestimmte Lösung im Sinn hat.

Wieviele Swaps gibt es denn bei einer Suche? Hast Du jetzt noch eine Frage?

[e.le]

Habe die Funktion überarbeitet:



def search_lin(word_list, word):
for index in range(len(word_list)):
if word_list[index] == word:
return index
return len(word_list)

def user_lin():
word_list = []
num = int(input("Enter size of list: \t"))

for n in range(num):
numbers = int(input("Enter any number: \t"))
word_list.append(numbers)
word = int(input("\nEnter number to search: \t"))

return search_lin(word_list, word)

print(user_lin())

[e.le]

Meine frage ist noch immer, wie ich den Vergleich Zähler in die Funktion def search_lin() einbauen soll.

[Sirius3]

Wie viele Vergleiche machst Du denn?

Zum Code: benutze `enumerate`, das ist der Weg, wie man es mit Python macht.
Warum darf man nur Nummern eintippen, wenn es doch ein Stringvergleich ist?

[e.le]

Ich habe mir überlegt zwei Funktionen zu implementieren, die die Zeit und die Vergleiche messen, jedoch darf ich es nicht machen, da dies innerhalb der Funktion gefordert ist. Dies kriege ich irgendwie nicht hin und bräuchte deshalb Hilfe.

[__blackjack__]

@e.le: Was sind denn „compassions“ und wie zählt man die?

Die Vergleiche zählst Du doch schon implizit. Und ``for index in range(len(word_list)):`` ist in Python immer noch ein „anti pattern“ – wenn man zusätzlich zu den Elementen noch einen Index/Zähler haben will, verwendet man immer noch `enumerate()`.

Da drei Rückgabewerte angegeben sind, man aber nur einen Wert zurückgeben kann, wirst Du wohl ein Tupel mit den drei Werten zurückgeben müssen.

Benutzer für eine Liste die `word_list` heisst, aufzufordern Zahlen einzugeben ist ein bisschen verwirrend. `numbers` ist als Name auch unpassend, weil es sich dabei ja nicht um Zahlen (Mehrzahl) handelt, sondern nur um eine Zahl.

Wenn man aus syntaktischen Gründen einen Namen schreiben muss, den aber nicht wirklich verwendet, wie bei das bei `n` der Fall ist, dann nennt man diese Variable per Konvention `_` (ein einfacher Unterstrich), damit der Leser weiss, dass es Absicht ist, das der Name dann nicht verwendet wird, und kein Versehen oder unfertiger Code.

`user_lin()` ist auch ein schlechter Name. Zum einen wegen der Abkürzung – so etwas sollte man genau wie Grunddatentypen in Namen – vermeiden. Zum anderen weil Funktions- und Methodennamen üblicherweise die Tätigkeit beschreiben die von der Funktion oder Methode ausgeführt wird. `user_lin` beschreibt aber keine Tätigkeit. `main()` tut das auch nicht, *das* wäre aber ein konventioneller Name für die Hauptfunktion.

[e.le]

Wie viele Vergleiche machst Du denn?

Zum Code: benutze `enumerate`, das ist der Weg, wie man es mit Python macht.
Warum darf man nur Nummern eintippen, wenn es doch ein Stringvergleich ist?

Also mit Vergleichen ist gemeint, wie viele Versuche die Funktion braucht, bis sie das Element gefunden hat, z.B. word_list = {1,2,3,4,5}, suche das Element 3 .....
das Programm sagt mit, dass das Element an 2 Stelle gefunden wurde und außerdem möchte ich, dass es mir liefert, dass es 3 Versuche(Vergleiche) benötigt hat, das Element zu finden.

[e.le]

Wie viele Vergleiche machst Du denn?

Zum Code: benutze `enumerate`, das ist der Weg, wie man es mit Python macht.
Warum darf man nur Nummern eintippen, wenn es doch ein Stringvergleich ist?

Also mit Vergleichen ist gemeint, wie viele Versuche die Funktion braucht, bis sie das Element gefunden hat, z.B. word_list = {1,2,3,4,5}, suche das Element 3 .....
das Programm sagt mit, dass das Element an 2 Stelle gefunden wurde und außerdem möchte ich, dass es mir liefert, dass es 3 Versuche(Vergleiche) benötigt hat, das Element zu finden.

Und noch die benötigte Zeit für die Suche, habe jetzt statt numbers elements geschrieben

[Sirius3]

Da hast Du ja dann Deine Antwort. Für die Zeit gibt es das time-Modul. Und wie __blackjack__ schon geschrieben hat, kann man mehrere Werte als Tuple zurückgeben.

[e.le]

Habe den Zeitmessen eingefügt, jedoch es nicht, ich habe keine Ahnung was hier falsch ist.



import time

def search_lin(word_list,word):
start = time.time()
for index in range(len(word_list)):
if word_list[index] == word:
return index
return len(word_list)
end = time.process_time
time = end - start
return time

[e.le]

Habe den Zeitmessen eingefügt, jedoch es nicht, ich habe keine Ahnung was hier falsch ist.



import time

def search_lin(word_list,word):
start = time.time()
for index in range(len(word_list)):
if word_list[index] == word:
return index
return len(word_list)
end = time.process_time
time = end - start
return time

.....*jedoch funktioniert es nicht

[Sirius3]

Eine Funktion wird beim ersten `return` verlassen. Wenn Du mehrere Rückgabewerte haben willst, mußt Du ein Tuple zurückgeben.
process_time ist eine Funktion, die man auch aufrufen sollte; Du mußt Dich entscheiden ob Du `time` oder `process_time` verwenden willst, beides gemischt geht nicht.
Benutze `enumerate`!

[e.le]

Das händische Index-Hochzählen ist unnötig, da das die for-Schleife schon macht. Wenn das Wort nicht gefunden wird, einen Index zurückzuliefern sieht für mich falsch aus.
Keine Abkürzungen verwenden, was soll ›lin‹ denn bedeuten? Keine Typen in Variablennamen, word_list -> words.
In Python iteriert man auch direkt über die Elemente einer Liste; falls man zusätzlich einen Index braucht, gibt es `enumerate`:

Code: Alles auswählen

def search_linear(words, word):
    for index, item in enumerate(words):
        if item == word:
            return index
    return None

Du zählst bereits die Anzahl der Vergleiche. Zum Zeitmessen gibt es das `time`-Modul.

Könntest du mir zeigen, wie es aussehen würde, wenn man hier das Time Modul anwendet ?

[e.le]

Eine Funktion wird beim ersten `return` verlassen. Wenn Du mehrere Rückgabewerte haben willst, mußt Du ein Tuple zurückgeben.
process_time ist eine Funktion, die man auch aufrufen sollte; Du mußt Dich entscheiden ob Du `time` oder `process_time` verwenden willst, beides gemischt geht nicht.
Benutze `enumerate`!

Wie genau gebe ich ein Tupel zurück, das habe ich noch nicht verstanden.

[__blackjack__]

@e.le: Man misst am Anfang die Zeit und am Ende und zieht die Zeiten voneinander ab. Ich würde `time.monotonic()` verwenden.

Tupel zurückgeben geht wie mit jedem anderen Wert auch mit ``return``. Danach muss dann halt der Ausdruck stehen der das Tupel erstellt das Du zurückgeben möchtest.

Bitte setz Deinen Code doch mal in [ code ]-Tags, damit man den auch vernünftig lesen kann, mit Einrückung und so.

[__deets__]

Zum messen von Zeitstempeln benutzt man https://docs.python.org/3.7/library/tim ... .monotonic

Und

Code: Alles auswählen

def foo():
      return 10, 100

a, b = foo()
print(a, b)

ist tuple-return und unpacking.

[__blackjack__]

Code: Alles auswählen

#!/usr/bin/env python3
import time


def linear_search(items, item):
    start_time = time.monotonic()
    try:
        index = items.index(item)
    except ValueError:
        index = len(items)

    return (
        index,
        index + (index != len(items)),
        time.monotonic() - start_time,
    )


def main():
    values = list(range(1_000_000))
    for needle in [
        # This isn't in the list at all.
        "can't be found",
        # Last element, should need the same amount of comparisons than the
        # „not found“ case.
        values[-1],
        # Smack in the middle of it, so expected runtime is about half as for
        # the other two cases.
        values[len(values) // 2],
    ]:
        print(linear_search(values, needle))


if __name__ == "__main__":
    main()