python, compararea șirului nu funcționează?

Am fost însărcinat cu crearea unei căutări binare pe o listă de cuvinte, am venit cu 2 implementări (și în mod clar nu am pus-o într-un caz în care cuvântul nu este găsit încă, dar asta nu este o problemă încă), cu toate acestea când lista este restrânsă până la cuvântul pe care îl caut, funcția mea nu se termină, ci continuă să funcționeze până la depășirea adâncimii recursive maxime.

Am pus în imprimare și arată cu claritate cuvântul la dasList [mid] , și arată acest lucru de peste și peste până când în cele din urmă renunță.

def _bisect2(dasList, word):
    mid = int(len(dasList)/2)
    if word.lower() > dasList[mid].lower():
        return _bisect2(dasList[mid: len(dasList)], word)            
    if word.lower() < dasList[mid].lower():
        return _bisect2(dasList[0: mid], word)
    else:
        return mid

acest lucru este numit de către

print(_bisect2(fileList, input('Please type a word')))

Folosesc interpretul Python 3.0. Orice sugestii?

0
această eroare apare pentru ambele implementări.
adăugat autor Tony, sursa
Biblioteca standard include deja un modul bisect . Este temele?
adăugat autor Karl Knechtel, sursa
Doar curioasă, ați uitat să sortați fileList ?
adăugat autor K Z, sursa

3 răspunsuri

Implementarea dvs. (aproape) funcționează pentru mine (și nu arată comportamentul pe care l-ați descris cu intrarea mea pre-sortată). Presupun că ți-ai sortat fișierele de intrare? Un exemplu ușor modificat (de lucru) este afișat mai jos.

def _bisect2(dasList, word,lidx=0):
    mid = int(len(dasList)/2)
    if word.lower() > dasList[mid].lower():
        return _bisect2(dasList[mid:], word,lidx=lidx+mid)            
    elif word.lower() < dasList[mid].lower():
        return _bisect2(dasList[:mid], word,lidx=lidx)
    return lidx+mid

words=sorted(["one","two","three","four","five","twenty","foo"])
print (words)
print (_bisect2(words,'three'))

Rețineți că ați returnat indexul în ultima listă parțială (care va fi întotdeauna 0) ...

1
adăugat
Ei bine, asta va face;) Atunci cuvântul dvs. nu este în listă. Doar strip introducerea dvs. și ar trebui să fie OK.
adăugat autor mgilson, sursa
@Tony - Nu sunt sigur. încercați să utilizați raw_input în loc de input - deoarece doriți șiruri de caractere, probabil că este mai sigur.
adăugat autor mgilson, sursa
@ Tony - Ați uitat că ați folosit Python 3. Ne pare rău despre asta;).
adăugat autor mgilson, sursa
da, lista de cuvinte este deja sortată și da, ai dreptate, ar reveni la 0. Ce am observat totuși este cuvântul i intrare pare să atașeze un spațiu pe final. de ce ar fi asta?
adăugat autor Tony, sursa
super, multumesc. ^ De ce ar fi adăugat-o? este doar caracterul de linie nouă adăugat după ce enter este apăsat?
adăugat autor Tony, sursa
prin toate conturile, 'raw_input ()' a fost modificat pentru a introduce stackoverflow.com/questions/954834/… și după ce am investigat ".strip ()" am fugit în ".rstrip ()" care a făcut de asemenea. Multumesc pentru ajutor!
adăugat autor Tony, sursa
@Levon da, mă confundă și eu puțin, și nu pot vedea unde sau de ce se întâmplă. Aș putea lua în considerare obținerea v3.2.3 după acest debaclu
adăugat autor Tony, sursa
@mgilson toate bune, tu atleast mi-a indicat în direcția cea bună
adăugat autor Tony, sursa
@Tony Spațiul gol de la sfârșitul introducerii pe care vi-l solicitați este ciudat și nu pot reproduce acel comportament cu v 3.2.3
adăugat autor Levon, sursa

Acest lucru este bine pentru mine. Rețineți că indexul returnat la sfârșit va fi întotdeauna indexul cuvântului din lista minimă, nu indexul listei originale.

See also that the > compare doesn't do a len over the list again, it just iterates to the end. Slice syntax allows you to leave off the last number if you're iterating to the end.

words = "The quick brown fox jumped over the lazy dog".split()

def bisect(words, word):
    mid = int(len(words)/2)
    if word.lower() > words[mid].lower():
        return bisect(words[mid:], word)
    elif word.lower() < words[mid].lower():
        return bisect(words[0:mid], word)
    return mid

words = sorted(words)
print bisect(words, 'dog')
1
adăugat
Multumesc pentru sfat. Probabil că aș fi ratat asta!
adăugat autor Tony, sursa

De ce să nu utilizați modulul Python bisect ?

Recipe from the docs:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Exemplu:

>>> a = ['alfred','edward','mary','susan','thomas','wilma']
>>> index(a, 'mary')
2
>>> index(a, 'martha')
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 6, in index
ValueError
1
adăugat
pentru că este mai distractiv să dai seama de implementările ^^
adăugat autor Tony, sursa
@ Tony: Destul de corect. Dacă viteza este critică, utilizați modulul bisect.
adăugat autor Steven Rumbalski, sursa
Python România
Python România
100 participanți

Comunitatea pasionaților de Python din România.