Random Zahlen in einem Array Speichern

[Sirius3]

Du mußt den Rückgabewert an eine Variable binden.

Code: Alles auswählen

random_numbers = generate_random_numbers(17)
linear_search(random_numbers, 13)

Ein `else`-Block bei einer for-Schleife ohne break ist unsinnig, das ist äquivalent zu

Code: Alles auswählen

def linear_search(numbers, n):
    for i in range(0, len(numbers)):
            if numbers[i] == n:
                print(f"{n} found at index {i}")
    print("die Zahl ist nicht in der Liste vorhanden")

die letzte Zeile wird also immer ausgeführt, was falsch wäre, wenn n in der Liste ist.

[Fabio2002]

Danke für die HIlfe, also ich habe das nun so gemacht und es funktioniert:

Code: Alles auswählen

import random   

def generate_random_numbers(size): 
    numbers = []
    for i in range(size):
        numbers.append(random.randint(-100, 100))
    return numbers

def linear_search(random_numbers, n):
    for i in range(len(random_numbers)):
            if random_numbers[i] == n:
                print()
                print(f"{n} found at index {i}")
                break
    else:
        print()
        print("Nicht in der Liste")
        
        
        
def main():
    random_numbers = generate_random_numbers(100)        
    print(random_numbers)
    linear_search(random_numbers, 5)
    
    
main()

Gibt es in python eine andere Möglichkeit eine Leerzeile einzufügen als print().?
Habe ich hier wieder irgendwo eine Variable benutzt die ich nicht verwenden kann?

Weil meine nächste aufgabe ist die Binäre suche aus einer Zufälligen Liste, aber hierbei sollte ich ja den ersten Teil hier benutzen können?
Viel dank!

[__blackjack__]

@Fabio2002: Du könntest das Zeilenendezeichen ausgeben ('\n'), aber was ist an einem ``print()`` so schlimm? Und da die Leerzeile in beiden Fällen – gefunden und nicht gefunden – ausgegeben werden soll, könntest Du das vor der Schleife tun, und musst es deshalb nur *einmal* in den Code schreiben. Man könnte auch überlegen ob die Ausgabe der Leerzeile überhaupt in diese Funktion gehört, oder nicht doch eher Aufgabe des Aufrufers ist. Dann kann der nämlich entscheiden ob da eine Leerzeile ausgegeben werden soll oder nicht.

Ansonsten würde ich da noch die Einrückung einheitlich mit vier Leerzeichen pro Ebene machen.

Dann ist das ein bisschen ”asymmetrisch” das die „gefunden“-Ausgabe in Englisch, die „nicht gefunden“-Ausgabe aber in Deutsch ist. Ich würde da auch nicht von einer Liste sprechen, denn Du weisst an der Stelle ja gar nicht ob die Funktion tatsächlich mit einer Liste aufgerufen wurde. Deine Lösung funktioniert mit jedem Sequenztypen von dem man die Länge abfragen kann – nicht nur mit Listen.

An der Stelle noch mal der Hinweis, dass ``from i in len(range(sequence)):`` in Python ein „anti pattern“ ist. Man kann direkt über die Elemente von Sequenzen iterieren, ohne den Umweg über einen Index. Falls man zusätzlich noch eine laufende Zahl benötigt, gibt es die `enumerate()`-Funktion. Das hat den Vorteil das so eine Funktion nicht nur mit Sequenzen funktioniert, sondern mit jedem beliebigen iterierbaren Objekt.

Und falls man das wirklich nur für Sequenzen implementieren möchte, hat Sirius3 ja die Lösung dafür gezeigt die `index()`-Methode nicht noch einmal selbst zu implementieren.

Man sollte die Argumente auch anders bennenen, denn der Funktion ist es letztendlich ja völlig egal was in der übergebenen Sequenz enthalten ist, und auch `n` suggeriert dem Leser den Typ „ganze Zahl“. Die Funktion funktioniert aber mit Sequenzen die irgendwas enthalten. Du kannst da auch eine Liste mit den Namen von Eiscreme-Sorten übergeben und schauen an welchem Index 'Vanille' zu finden ist.

`generate_random_numbers()` würde ich als „list comprehension“ formulieren. Das wurde hier ja bereits in einem Beitrag gezeigt.

Code: Alles auswählen

#!/usr/bin/env python3
import random


def generate_random_numbers(size):
    return [random.randint(-100, 100) for _ in range(size)]


def linear_search(items, needle):
    for i, item in enumerate(items):
        if item == needle:
            print(f'{needle} found at index {i}')
            break
    else:
        print(f'{needle} not found')


def main():
    random_numbers = generate_random_numbers(100)
    print(random_numbers)
    print()
    linear_search(random_numbers, 5)


if __name__ == '__main__':
    main()

[Fabio2002]

Okei, nice, Danke!
(das mit den comprehension sollen wir noch nicht machen)
Dann hätte ich noch eine Frage die nicht ganz ins Forum passt glaub ich aber ich stelle Sie einfach mal:

Dies ist meine Aufgabenstellung:
Implementieren Sie die Algorithmen zur linearen Suche, binären Suche und Interpolationssuche, wobei die Arrays mit
Zufallszahlen initialisiert werden sollen. Für aufsteigend sortierte Zufallszahlen, addieren Sie die neugenerierte Zufallszahl mit
der zuletzt generierten Arrayzahl.

Und folgend mein bisheriger code, wie Ihr bereits gesagt habt muss ich den noch verbessern, aber er sollte erst einmal funktionieren.
Die Interpolationssuche muss ich erst noch angehen.
Für die binäre Suche muss ich meine Liste zB ja sortieren, kann ich das wie folgt machen?

Code: Alles auswählen

import random   


def generate_random_numbers(size): 
    numbers = []
    for i in range(size):
        numbers.append(random.randint(-100, 100))
    return numbers


#Algorithmen zur linearen Suche, binären Suche und Interpolationssuche

def linear_search(random_numbers, n):
    print(random_numbers)
    for i in range(len(random_numbers)):
            if random_numbers[i] == n:
                print()
                print(f"{n} found at index {i}")
                break
    else:
        print()
        print("is not present")
    

def binary_search(random_numbers, n):
    random_numbers = list(set(random_numbers))
    random_numbers.sort()
    print(random_numbers)
    min = 0
    max = len(random_numbers) - 1
    while min <= max:
        mid = int(min + (max - min) / 2)
        if(random_numbers[mid] == n):
            print()
            print(f"{n} found at index {mid}")
            break
        elif(random_numbers[mid] < n):
            min = mid + 1
        else:
            max = mid - 1
    else:
        print()
        print("is not present")
        
        
    
    
        
 #Main Funktion       
        
def main():
    random_numbers = generate_random_numbers(100)            
    linear_search(random_numbers, 5)
    binary_search(random_numbers, 7)
    
main()

Aber die eigentlich Frage war ob jemand mir das hier erklären kann, also wie das gemeint ist:

Für aufsteigend sortierte Zufallszahlen, addieren Sie die neugenerierte Zufallszahl mit
der zuletzt generierten Arrayzahl

[__blackjack__]

@Fabio2002: Die binäre Suche darf da kein `set()` draus und sie darf die Zahlen auch nicht sortieren. Binäre Suche erwartet eine sortierte Sequenz. Auf unsortierten Sequenzen funktioniert die nicht. Ich denke auch Du hast das bisher falsch gemacht, dass Du die Ausgabe in die Suchfunktionen geschrieben hast. Das wurde ja auch schon mal angesprochen. Man erwartet von Suchfunktionen eher das sie den Index zurückgeben oder eine Ausnahme auslösen falls der zu suchende Wert nicht gefunden wurde.

Laut Aufgabenstellung sollen die Zufallszahlen für die binäre Suche auch nicht sortiert werden, sondern schon beim erstellen, soll dafür gesorgt werden, dass die Zahlen aufsteigend sortiert sind. In dem die jeweils nächste Zufallszahl auf den vorherigen Wert addiert wird. Ich würde ja jetzt sagen da leistet `itertools.accumulate()` gute Dienste, aber das dürft iher wahrscheinlich wieder nicht benutzen.

Und Du darfst da natürlich keine negativen Zufallszahlen erzeugen.

``if`` und ``elif`` sind keine Funktionen – die Klammern um die Bedingungen gehören da nicht hin.

[Fabio2002]

arg okei :S
aber die lineare suche sollte doch so passen?

Ich denke auch Du hast das bisher falsch gemacht, dass Du die Ausgabe in die Suchfunktionen geschrieben hast

Da handelt es sich ja nur um die Printfunktion oder?
Die habe ich eigentlich nur eingefügt um zu checken ob es auch funktioniert, wenn nur das die Ausgabe ist, weil ich die Aufgabe präsentieren muss und sicherlich dann zeigen aus welcher Liste die Lösungen kommen

Laut Aufgabenstellung sollen die Zufallszahlen für die binäre Suche auch nicht sortiert werden, sondern schon beim erstellen, soll dafür gesorgt werden, dass die Zahlen aufsteigend sortiert sind. In dem die jeweils nächste Zufallszahl auf den vorherigen Wert addiert wird.

Aber wie mache ich das? - das mit dem accumulate dürfen wir leider nicht und wenn ich ehrlich bin finde ich es auch in den Folien nicht die wir haben
Also nur positive zahlen generieren, okei
das mit den Klammern, okei

[Fabio2002]

nochmal ich:
also habe mich erstmal entschieden das ganze so zu schicken und dann einfach jetzt noch weiter zu probieren und es zu verbessern.

Code: Alles auswählen

import random   


def generate_random_numbers(size): 
    numbers = []
    for i in range(size):
        numbers.append(random.randint(0, 100))
    return numbers


#Algorithmen zur linearen Suche, binären Suche und Interpolationssuche

def linear_search(random_numbers, n):
    print(random_numbers)
    for i in range(len(random_numbers)):
            if random_numbers[i] == n:
                print()
                print(f"{n} found at index {i}")
                break
    else:
        print()
        print("is not present")
    

def binary_search(random_numbers, n):
    random_numbers = list(set(random_numbers))
    random_numbers.sort()
    print(random_numbers)
    min = 0
    max = len(random_numbers) - 1
    while min <= max:
        mid = int(min + (max - min) / 2)
        if random_numbers[mid] == n:
            print()
            print(f"{n} found at index {mid}")
            break
        elif random_numbers[mid] < n:
            min = mid + 1
        else:
            max = mid - 1
    else:
        print()
        print("is not present")
        

def interpolation_search(random_numbers, n):
    random_numbers = list(set(random_numbers))
    random_numbers.sort()
    print(random_numbers)
    min = 0
    max = n - 1
    while(min <= max):
        if(random_numbers[min] == random_numbers[max] == n):
            return min
        if(n < random_numbers[min] or n > random_numbers[max]):
            return -1
        i = int(min + (max - min) * (n - random_numbers[min]) /
                                                (random_numbers[max] - random_numbers[min]))
        if(random_numbers[i] == n):
            print()
            print(f"{n} found at index {i}")
        if(random_numbers[i] < n):
            min = i + 1
        else:
                max = i - 1
    else:
        print()
        print("is not present")
    return -1        
        
    
    
        
 #Main Funktion       
        
def main():
    random_numbers = generate_random_numbers(50)            
    linear_search(random_numbers, 5)
    print()
    binary_search(random_numbers, 7)
    print()
    interpolation_search(random_numbers, 8)
    
main()

Die Aufgabe war ja diese 3 Sucheweisen zu implementieren, die nächste aufgabe ist nun zu schauen wie lange diese jeweils für verschieden große Liste brauchen.
Dafür kann ich eine analytische Funktion benutzen - nun meine Frage, haben diese Funktionen wie ich sie gemacht habe verschiedene Zeiten? Ich hoffe doch
Danke schon mal

[__blackjack__]

@Fabio2002: Du kannst/sollst ja sicher Ausgaben machen, aber die gehören halt nicht in die Suchfunktionen, sondern dort hin wo die Funktion aufgerufen wird. Die Funktion selbst muss ein sinnvollen Ergebnis zurück liefern. Und das ist wichtig, weil Du in der nächsten Aufgabe zeiten messen sollst, und Ausgaben können Zeitmessungen verfälschen, denn man misst dann ja nicht nur die Suche, sondern auch die Ausgabe, also wie schnell das System die Ausgabe darstellen kann. Das ist ja gar nicht so trivial bei einem System mit grafischer Oberfläche. Und wenn man das Remote irgendwo ausführt, käme da auch noch die Zeit für den Netzwerkverkehr dazu.

Wie schon gesagt sollte keine der Suchfunktionen die Eingabe sortieren oder gar Elemente entfernen. Denn dann ist der Indexwert ja völlig unnütz, weil der Aufrufer gar nicht weiss wie die Liste in der dann gesucht wird, eigentlich aussieht, weil das gar nicht die Liste ist, die er übergeben hat.

Bei `interpolation_search()` hast Du jetzt wieder die Klammern bei ``if``.

Ausserdem sind in der Funktion jetzt plötzlich ``return``-Anweisungen drin, und zwar in anderen Zweigen als die Ausgaben, die dort auch drin sind. Es kann also sein das das Ergebnis nicht gefunden wird, aber auch keine Ausgabe stattfindet, oder das das Ergebnis gefunden wird, aber keine Ausgabe stattfindet.

[Fabio2002]

Okei, habe ich verstanden, und habe die print Funktionen rausgenommen.
Bei der zweiten aufgabe habe ich das mit time.time gelöst, stimmt das so, also gibt mir das tatsächlich zurück wie lange der Rechner gebraucht hat?

Code: Alles auswählen

def linear_search(random_numbers, n):
    #print(random_numbers)
    start = time.time()
    for i in range(len(random_numbers)):
            if random_numbers[i] == n:
                print()
                print(f"{n} found at index {i}")
                break
    else:
        print()
        print("is not present")
    ende = time.time()
    print("linear_search_time "'{:5.3f}s'.format(ende-start))

Weil ich muss zeigen dass eben lineare suche langsamer ist als binär und die wiederum als interpolar. Und dies auch mit ganz großen zahlen.
Aber mein Problem ist nicht dass die einzelnen suchfunktionen zu lange brauchen, sondern es sehr lange dauert bis die Liste oder Array sortiert und kontrolliert ist :S
aber irgendwie muss ich das ganze ja ordnen damit ich binäre suche überhaupt machen kann. Irgendwie dreh ich mich nur im Kreis

bzw habe ich noch das hier probiert und es aus den einzelnen Funktionen rausgemacht, aber macht das Sinn?

Code: Alles auswählen

def generate_random_numbers(size): 
    start = time.time()
    numbers = []
    for i in range(size):
        numbers.append(random.randint(0, 10000000))
    numbers = list(set(numbers))
    numbers.sort()
    print(numbers)
    ende = time.time()
    print("sort_time "'{:5.3f}s'.format(ende-start))
    return numbers

[__deets__]

Du hast doch immer noch prints in deiner Suchfunktion. Das verfälscht das Ergebnis.

[Fabio2002]

Du hast doch immer noch prints in deiner Suchfunktion. Das verfälscht das Ergebnis.

Achso, auch die Ausgabe wo es gefunden wurde?
Ich dachte nur die ausgabe der gesammten Liste. Dann muss ich mir das noch einmal iwie anders anschauen

[__deets__]

Wenn ein Marathonläufer 10 Minuten ins Mikrofon labert, bevor er durchs Ziel läuft (wo seine Zeit gemessen wird), hat er dann 10 Minuten mehr auf der Uhr oder nicht?

[Sirius3]

Eine Funktion zum Suchen soll weder etwa ausgeben, noch etwas sortieren, noch die Zeit messen, sondern nur eine Zahl suchen.
Jetzt hasz Du ein generate_random_numbers, das gar nicht size Zahlen liefert, sondern unter Umständen weniger.
Die Lösung zu Deinem Problem steht schon in der Aufgabenstellung. Einfach immer zur letzten Zahl eine positive Zufallszahl draufaddieren.

[Fabio2002]

Eine Funktion zum Suchen soll weder etwa ausgeben, noch etwas sortieren, noch die Zeit messen, sondern nur eine Zahl suchen.
Jetzt hasz Du ein generate_random_numbers, das gar nicht size Zahlen liefert, sondern unter Umständen weniger.
Die Lösung zu Deinem Problem steht schon in der Aufgabenstellung. Einfach immer zur letzten Zahl eine positive Zufallszahl draufaddieren.

Code: Alles auswählen

def linear_search(random_numbers, n):
    for i in range(len(random_numbers)):
            if random_numbers[i] == n:
                print()
                print(f"{n} found at index {i}")
                break
    else:
        print()
        print("is not present")

also ist hiermit die Funktion fertig?
bzw muss ich diese Prints auch noch entfernen oder?

Code: Alles auswählen

def linear_search(random_numbers, n):
    for i in range(len(random_numbers)):
            if random_numbers[i] == n:
                break

[Sirius3]

Jetzt bräuchte die Funktion noch einen Rückgabewert. Und wir hatten ja auch schon mal enumerate gezeigt.

[Fabio2002]

Jetzt bräuchte die Funktion noch einen Rückgabewert. Und wir hatten ja auch schon mal enumerate gezeigt.

Über einen Index zu iterieren, ist schlecht, wenn man auch direkt über die Elemente iterieren kann (mit enumerate, falls man den Index braucht), richtig wäre also:

Code: Alles auswählen

def linear_search(numbers, n):
    for i, num in enumerate(numbers):
            if num == n:
                print(f"{n} found at index {i}")

Wenn Du wissen willst, ob es überhaupt vorkommt, kannst Du Dir das z.B. mit einem Flag merken.[/i]

Das war der Post dazu. nur verstehe ich ihn nicht ganz.
bzw wie ich dann diese Funktion auf die generierte Liste anwenden kann..
Da das generieren bei mir ja ewig dauert wie es scheint

Code: Alles auswählen

def generate_random_numbers(size): 
    numbers = []
    for i in range(size):
        numbers.append(random.randint(0, 10000))
    numbers = list(set(numbers))
    numbers.sort()
   
    return numbers

das hier ist also kompletter Käse?

[Sirius3]

Inzwischen hast Du ja verraten, was Deine eigentliche Aufgabe ist, und dass Du eine Funktion schreiben sollst, die den Index zurückgibt, also brauchst Du ein `return`.

[Fabio2002]

Inzwischen hast Du ja verraten, was Deine eigentliche Aufgabe ist, und dass Du eine Funktion schreiben sollst, die den Index zurückgibt, also brauchst Du ein `return`.

Code: Alles auswählen

def linear_search(random_numbers, n):
    for i, num in enumerate(random_numbers):
            if num == n:
                print(f"{n} found at index {i}")
    return linear_search

?
kein plan mehr -.-

[__deets__]

Was könntest denn ein interessanter wert für die Rückgabe sein? Was ist denn die Aufgabe der Funktion? Was ist der Wert, den sie ermittelt? Was machs du mit dem? Und was sollst du NICHT damit machen? Weil es Zeit kostet?