Keskustelu: Ohjelmointikysymykset: Python: python: lukujen alkujen vertailun optimointi

moi,

vertaan 2 luvun alkuja toisiinsa, että kuinka paljon on yhteistä.
Siis vertaa(23,2567) antaa 1 ja vertaa(345,365) antaa 1. Koska molemmissa on 1. Luku samat ja toinen luku alkaa eroamaan.

Nykyinen toteutus on tyylillä:

x= str(x)
y= str(y)
c=0
for i in range(vertailupituus):
    if x[i]==y[i]:
        c += 1
    else:
        return c

onko nopeampaa tapaa vertailla lukujen alkuja kuin muuttaa niitä tekstiksi?

EDIT1: luvut ovat hyvin pitkiä tai siis toinen on joku 10 merkkiä mutta roinen on luokkaa 20000 mittainen

En tiedä, että olisi nopeampaa tapaa. Yksi vaihtoehto on käyttää nopeampaa kieltä (esim. C).

Yksi optimointitapa on ensin jakaa lukua suurilla kymmenen potensseilla, jotta tekstiksi muunnettavasta osasta saadaan lyhyempi. Nopeusero alkuperäiseen algoritmiin nähden on valtava, Python 3:lla vielä jonkin verran suurempi kuin 2:lla. (Tosin myös alkuperäinen algoritmi toimii uudella Pythonilla selvästi nopeammin.)

#/usr/bin/python

# Suora algoritmi.
def vertaa(a, b):
	a_str = str(a)
	b_str = str(b)
	n = 0
	for i in range(0, len(a_str)):
		if a_str[i] <> b_str[i]:
			break
		n += 1
	return n

# Luvut 10**(2**n) .. 100000000, 10000
# luvun odotetun koon mukaan suurimmat ensin.
vertaa2_jakajat = [10**(2**i) for i in range(16, 1, -1)]

def vertaa2(a, b):
	# Sijoitetaan b:hen aina suurempi luku.
	if b < a:
		a, b = b, a
	# Jaetaan b luvulla 10**n niin, että saadaan lähellä
	# a:ta oleva (mutta turvallisesti isompi) pala luvun alusta.
	raja = 10 * a
	for jako in vertaa2_jakajat:
		c = b / jako    # Python 2
		# c = b // jako # Python 3
		if c > raja:
			b = c
	# Sovelletaan uuteen lukuun vanhaa algoritmia.
	return vertaa(a, b)

# Nopeustesti:
a = 123456789
b_str = "123456789" + str(1 << (2**16))
b = int(b_str)
print("len(a) = %d, len(b) = %d" % (len(str(a)), len(b_str)))
print("vertaa(a, b) = %d" % (vertaa(a, b)))
print("vertaa2(a, b) = %d" % (vertaa2(a, b)))

for i in range(0, 300):
	#vertaa(a, b) # P2: 139,5 s   P3: 31,3 s
	vertaa2(a, b) # P2:   6,9 s   P3:  1,2 s
	# nopeussuhde   P2:  20 : 1   P3: 26 : 1