Saya sedang memecahkan masalah menemukan jumlah terbesar. Saya tahu solusi untuk masalah ini tetapi saya tidak dapat memahami apakah metode yang berbeda untuk menggabungkan dua angka akan membuat perbedaan dalam waktu berjalan. Saya menggunakan python 3.7.

Metode 1

Mengonversi kedua angka dalam string dan menggabungkannya kemudian mengonversinya kembali menjadi integer.

def concatenate(num1, num2):
    num1 = str(num1)
    num2 = str(num2)
    num1 += num2
    return int(num1)

Metode 2

Menghitung banyaknya angka pada salah satu bilangan dan menjumlahkan bilangan nol yang sama pada bilangan lain.

def concatenate(num1, num2):
    digits = len(str(num2))
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

Apakah perbedaan teknik membuat perbedaan? Mengubah angka dalam string atau operasi aritmatika (perkalian) mana yang lebih cepat dan mengapa? Apakah perubahan ke bahasa lain akan membuat perbedaan seperti bahasa berbasis kompiler (C++)?

Sunting:

Metode 1 - Waktu eksekusi 6.604194641113281e-05 detik

Metode 2 - Waktu eksekusi 5.245208740234375e-06 detik

Waktu yang dibutuhkan oleh konversi tipe data lebih tetapi mengapa demikian dan apakah hanya untuk bahasa yang ditafsirkan seperti python bukan untuk bahasa berbasis kompiler seperti C++?

0
sajan kumar 12 Mei 2021, 20:49

2 jawaban

Jawaban Terbaik

Tentu akan ada perbedaan! Cukup mudah untuk melihat sendiri:

import timeit

def concatenate1(num1, num2):
    num1 = str(num1)
    num2 = str(num2)
    num1 += num2
    return int(num1)

def concatenate2(num1, num2):
    digits = len(str(num2))
    num1 = num1 * (10**digits)
    num1 += num2
    return num1


num1 = int("1"*10000)
num2 = int("2"*10000)

t1 = timeit.timeit('concatenate1(num1, num2)', 'from __main__ import concatenate1, num1, num2', number=100)
t2 = timeit.timeit('concatenate2(num1, num2)', 'from __main__ import concatenate2, num1, num2', number=100)

print("t1=", t1, "; t2=", t2)
# Output:
# t1= 0.772663099996862 ; t2= 0.30340000000433065

Jelas, t1 adalah ~2 kali t2. Mungkin penyerap waktu besar sedang merangkai angka? Mari kita coba implementasi lain yang menggunakan math.log10 untuk mengetahui jumlah digit:

import math
def concatenate3(num1, num2):
    l = math.log10(num2)
    digits = int(l) + 1
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

Pengaturan waktu fungsi ini dengan dua lainnya memberikan:

t1= 0.8134238999919035 ; t2= 0.32444419999956153 ; t3= 0.11973479999869596

Ini tampaknya mendukung argumen bahwa mengonversi bilangan bulat menjadi string membutuhkan banyak waktu.

Mengapa demikian? Karena mengubah bilangan bulat menjadi string melibatkan interpretasi nilai biner dalam penyimpanan dengan menggunakan angka desimal dan kemudian menetapkan karakter untuk setiap digit. Saat menambahkan dua angka, yang Anda lakukan hanyalah menjumlahkan angka binernya.

Anda akan melihat perilaku seperti itu dalam bahasa yang ditafsirkan dan yang dikompilasi. Namun, bahasa yang berbeda akan memiliki tingkat pelambatan yang berbeda terkait dengan metode yang berbeda berdasarkan cara kerja internal mereka.

1
Pranav Hosangadi 12 Mei 2021, 18:13

Sementara jawaban yang diberikan oleh @pranav-hosangadi bagus, dan saya menggemakan pernyataannya bahwa akan ada perbedaan.

Saya ingin menunjukkan bahwa apa solusi "terbaik/tercepat" untuk satu set input mungkin bukan yang terbaik untuk semua input. Mengetahui seperti apa "tampilan" data input Anda dapat menjadi penting saat mencari solusi yang lebih baik/lebih cepat.

Untuk input yang dipilih @pranav-hosangadi (string angka yang sangat besar), concatenate3()-nya jelas tercepat. Pilihan input mereka tampaknya lebih masuk akal mengingat pertanyaannya adalah tentang menentukan sesuatu tentang angka "besar".

Namun, jika masalah di mana mendefinisikan angka besar menjadi angka hingga sepuluh digit (masih cukup besar dalam beberapa kasus) maka metode concatenate3() mereka sebenarnya lebih lambat daripada dua metode pertama dan metode keempat:

def concatenate4(num1, num2):
    return int(f"{num1}{num2}")

Adalah yang lebih cepat dari ketiganya (setidaknya di laptop saya).

Sama pentingnya, concatenate4() baru ini tidak lebih cepat secara universal dan untuk input dalam rentang yang digunakan oleh @pranav-hosangadi, kinerjanya "buruk". Sementara concatenate3() mereka menghancurkan yang lain.

import timeit
import math

def concatenate1(num1, num2):
    num1 = str(num1)
    num2 = str(num2)
    num1 += num2
    return int(num1)

def concatenate2(num1, num2):
    digits = len(str(num2))
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

def concatenate3(num1, num2):
    l = math.log10(num2)
    digits = int(l) + 1
    num1 = num1 * (10**digits)
    num1 += num2
    return num1

def concatenate4(num1, num2):
    return int(f"{num1}{num2}")

num1 = int("1"*10)
num2 = int("2"*10)

t1 = timeit.timeit('concatenate1(num1, num2)', 'from __main__ import concatenate1, num1, num2', number=1000)
t2 = timeit.timeit('concatenate2(num1, num2)', 'from __main__ import concatenate2, num1, num2', number=1000)
t3 = timeit.timeit('concatenate3(num1, num2)', 'from __main__ import concatenate3, num1, num2', number=1000)
t4 = timeit.timeit('concatenate4(num1, num2)', 'from __main__ import concatenate4, num1, num2', number=1000)

print("t1=", 100_000*t1, "; t2=", 100_000*t2, "; t3=", 100_000*t3, "; t4=", 100_000*t4)

Hasil:

t1= 63.25999999999971 ; t2= 58.6299999999998 ; t3= 64.32999999999994 ; t4= 40.889999999999674

Di laptop saya, concatinate3() hanya menjadi yang tercepat saat menggabungkan angka dengan masing-masing lebih dari 35 digit.

Ayo Coba Jawab Alasannya:

Mari kita intip beberapa waktu kasar untuk masing-masing langkah concatenate3() dan concatenate4(). Perhatikan bahwa biaya sebenarnya dari masing-masing langkah ditutupi oleh overhead panggilan fungsi dan dengan demikian merupakan perkiraan kasar tetapi masih didasarkan pada tes waktu nyata dan menggambarkan poin yang menarik.

Untuk 10 digit angka lebih dari 1000 run concatenate3():

def concatenate3(num1, num2):  # 59 time units (accurate)
    l = math.log10(num2)       # 18 time units
    digits = int(l) + 1        # 14 time units
    num1 = num1 * (10**digits) # 12 time units
    num1 += num2               #  7 time units
    return num1

Untuk 10 digit angka lebih dari 1000 run concatenate4():

def concatenate4(num1, num2):  # 45 time units (accurate)
    tmp = f"{num1}{num2}"      # 30 time units
    tmp = int(tmp)             # 20 time units
    return tmp

Untuk 1000 digit angka lebih dari 1000 run concatenate3():

def concatenate3(num1, num2):  # 1400 time units (accurate)
    l = math.log10(num2)       #   23 time units
    digits = int(l) + 1        #   15 time units
    num1 = num1 * (10**digits) # 1341 time units
    num1 += num2               # 2119 time units
    return num1

Untuk 1000 digit angka lebih dari 1000 run concatenate4():

def concatenate4(num1, num2):  # 5700 time units (accurate)
    tmp = f"{num1}{num2}"      # 3500 time units
    tmp = int(tmp)             # 3100 time units
    return tmp

Jadi, apa yang bisa kita lihat? Pertama, perkalian dan penambahan secara intrinsik lebih cepat daripada penggabungan dan casting. Itu seharusnya tidak mengejutkan.

Bagian yang menarik adalah bahwa meskipun biaya untuk menghitung digits tidak tergantung pada ukuran input dan menghilang ke dalam kesalahan pembulatan dengan input yang lebih besar, dengan input yang lebih kecil, biaya ini menjadi komponen yang signifikan dari total.

2
JonSG 13 Mei 2021, 00:28