Bagaimana saya bisa meningkatkan kinerja kode berikut?

self.adverts = set() # Around 11k rows
self.old_adverts= set() # Around 11k rows
self.advs = []

...

# Find modified items
for item in self.new_items:
   for old_item in self.old_items:
       if item.id == old_item.id and item.price != old_item.price:
          self.advs.append(
                    {
                    'delete': old_item,
                    'new': item,
                    'archive': old_item
                    }
          )

Item kelas:

class Item(Base):
   ...

   id = Column(String(25), nullable=False, primary_key=True)
   price = Column(Numeric(precision=8), nullable=False, primary_key=True)

   # Another multiple additional fields
   ...

   def __eq__(self, other):
       return self.id == other.id

   def __hash__(self):
       return hash(self.id)

Perbandingan data di atas membutuhkan terlalu banyak waktu. Saya tidak tahu bagaimana cara berpuasa.

UPD: Namun, di bawah ini saya telah berhasil meningkatkan kinerja kode lain:

# for item in self.items:
#   if item not in self.old_items:
#       self.insert_items_db.add({'new': item})

# Find absolutely new items
for new_item in self.items- self.old_items:
    self.advs.append({'new': new_item})

Objek memiliki fungsi __eq__ dan __hash__ yang telah ditentukan sebelumnya:

def __eq__(self, other):
    return self.id == other.id

def __hash__(self):
    return hash(self.id)
0
Viktor V. 11 Agustus 2017, 02:50

2 jawaban

Jawaban Terbaik

Saya tidak sepenuhnya mengikuti kode Anda, tetapi Anda dapat mempercepat membandingkan dua daftar dengan menggunakan kamus. Ini adalah O(n) daripada O(n^2) karena pengecekan keberadaan dikurangi dari O(n) menjadi O(1).

Sebagai contoh. Katakanlah Anda memiliki banyak objek dengan variabel id, nilai, warna.

for x in list1:       #N operations
    for y in list2:   #N operations
        if x.id == y.id:  #O(1)
            #do stuff

Sebagai gantinya Anda bisa melakukan ini:

#create two dictionaries where each key is the ID and each value is the
#object, data, other things etc.
dict1 = { x.id:x for x in list1}   
dict2 = { y.id:y for y in list2}   

Dan kode Anda sekarang menjadi:

for x in dict1.keys():     #O(N)
    if x in dict2:         #O(1)
         #Do some stuff

Yang merupakan waktu O(n) sekarang.

Sekarang jika Anda ingin membandingkan harga menjadi rumit. Jika kita memiliki beberapa elemen Id (misalnya ada tabrakan di set yang sama) maka kita dapat mengonversi setiap entri dalam kamus menjadi daftar objek. Ini secara teoritis masih operasi O(N^2) tetapi ini merupakan peningkatan besar dari iterasi melalui SEMUA elemen 11k.

Mari kita asumsikan tidak ada Id yang berulang. Kode tersebut kemudian menjadi:

for x in dict1.keys():     #O(N)
    if x in dict2:         #O(1)
        if dict1[x].price != dict2[x].price:  #or any other comparison
             #do stuff

Jika ada Id berulang maka struktur kamus seharusnya terlihat seperti berikut:

my_dict = {\
    1001: [ obj1, obj2, obj3]\  #where obj1.id == obj2.id == obj3.id
    1002: [obj4, obj5, obj6]\   #where obj4.id == obj5.id == obj6.id
    }

Dengan kode yang diadaptasi untuk mencerminkan sesuatu seperti berikut

for x in dict1.keys():     
    if x in dict2:   
        if x in dict2:
            for my_object_type in dict2[x]:     #something about this seems familiar.....
                if x.other_identifier == my_object_type.other_identifer:
                #finally do some stuff!

Inilah bagian paling gila dari semuanya!

Dalam kode di atas saya telah menambahkan loop for lainnya. Ini lagi O(N) kecepatan itulah sebabnya kode telah dikurangi menjadi O(N^2) lagi. Namun jika kita memiliki pengenal lain, katakan "Id2" atau "color_of_left_toe" maka kita dapat membuat KAMUS LAIN!!

Pada titik ini struktur akan berkembang menjadi kamus kamus objek Anda. Cukup rumit tapi!! Waktu akses dapat tetap O(1)!

Mengapa "dalam dict" lebih cepat?

Dalam contoh kode pertama Anda mengulangi daftar pertama dan sekali lagi Anda mengulangi daftar lain.

Jadi untuk elemen pertama di list1 Anda mengulanginya melalui len(list2), atau N

Karena Anda mengulang loop ini untuk setiap elemen di X, Anda melakukan ini N kali.

N + N + N + N ............N

\~~~~~~N kali~~~~~~/

Atau O(N^2)

Sekarang mengapa dict lebih cepat?

Kamus meng-hash setiap elemen dan kemudian menyimpannya berdasarkan hash ini. Ini berarti Anda tidak perlu melihat melalui pohon atau larik biner yang kompleks untuk menemukan apa yang Anda cari. Alih-alih, Anda melakukan sedikit matematika waktu O(1) dan Anda memiliki poin yang perlu Anda periksa segera berdasarkan kunci yang Anda berikan.

1
Erich 11 Agustus 2017, 00:45

Hal ini sangat bergantung pada apa yang dimaksud dengan "melakukan sesuatu". Jika ini adalah pembaruan catatan sederhana, lupakan implementasi set ini dan gunakan kamus. Gunakan data lama untuk membuat kamus lama, dengan memasukkan ID produk. Kemudian perbarui dengan data baru.

catalog =       {self.id: [ <remainder of the row> ] for self in old_data}
catalog.update( {self.id: [ <remainder of the row> ] for self in new_data} )
0
Prune 11 Agustus 2017, 00:06