Bagaimana raster dapat dihitung secara efisien (dengan Python), diberikan satu set yang terdiri dari milyaran kotak pembatas (dibaca berurutan dari sebuah file), dan mengingat bahwa nilai-nilai raster untuk setiap sel harus memberikan jumlah kotak pembatas yang tumpang tindih?
Untuk raster 4000 * 4000
Saya sudah menghitung waktu pembuatan numpy matrix:
$ python -m timeit 'import numpy' 'a = numpy.zeros(shape=(4000,4000))'
10 loops, best of 3: 51.7 msec per loop
Pembuatan matriks python standar:
$ python -m timeit 'a = 4000*[0]' 'for i in range(4000):' ' a[i]=4000*[0]'
10 loops, best of 3: 218 msec per loop
Jadi numpy lebih cepat, tetapi masih 50 msec per loop, dengan satu miliar iterasi, menghasilkan waktu berjalan yang sama dengan sekitar satu tahun (0,05 msec * 1000000000/60/60/24/365 = 1,5 tahun)
Jadi ini bukan pilihan untuk mengambil sampel setiap poligon. Apa pendekatan khas untuk masalah ini?
Jawaban:
Anda
timeit
termasuk impor numpy, yang akan menambah beberapa overhead. Jadi mengapa Anda tidak menulis kode untuk subset dari kotak pembatas dan waktu loop itu, kemudian gandakan untuk memperkirakan total waktu berjalan?Memecahkannya pada komputer tunggal adalah serialnya, dan dengan operasi yang relatif sederhana, Anda mungkin tidak mendapatkan optimasi signifikan dari algoritma yang sudah sederhana. Anda dapat mencoba membaginya dalam semacam operasi pengurangan peta manual (saya tahu Anda memiliki peringatan "tanpa pengurangan peta"), dan menjalankan instance sebanyak yang Anda punya core. Mosaicking / penggabungan dan raster (langkah pengurangan) adalah operasi yang sangat cepat. Ini mungkin tidak akan terlalu menyakitkan untuk dikodekan daripada solusi multi-threaded.
Atau (atau tambahan), Anda dapat menulis sebuah program untuk menggabungkan kotak batas tertentu seperti yang tumpang tindih atau bersarang - ini akan memerlukan indeks spasial. Jika Anda tidak memilikinya, Anda mungkin menemukan membuat satu menguntungkan, terutama jika Anda secara lokal memparalelkan algoritma utama.
Juga, jangan abaikan paralelisasi multi-komputer dari tangan. Jika perkiraan terbaik Anda adalah lebih dari satu tahun, maka Anda perlu menambahkan berapa banyak uang waktu Anda untuk menjalankan versi komputer tunggal, dan menimbangnya dengan mempekerjakan beberapa waktu komputasi awan. Seperti yang dikatakan @whuber, 1024 GPU akan memeriksa data dengan begitu cepat, itu akan dikenakan biaya apa-apa, bahkan jika Anda menghabiskan seminggu untuk mendapatkan CUDA. Jika bos Anda melarang Anda mencobanya di lebih dari satu komputer, lakukan analisis biaya dan berikan padanya beberapa angka sulit - ia kemudian akan menimbang nilai data terhadap nilai waktu Anda.
sumber
Jika saya mengerti dengan benar, yang Anda inginkan seperti merender set miliaran kotak pembatas Anda ke gambar. Kecuali bahwa alih-alih "mengecat" setiap poligon di atas sel (piksel) Anda menghitung (atau mengakumulasikan) mereka.
Anda dapat menggunakan (relatif) kode sederhana (dalam OpenGL, Vulcan, Direct3D) untuk merender poligon dan mengakumulasikan jumlah dalam buffer stensil. Hati-hati agar poligon jatuh pada batas piksel dengan tepat, dan pilih tipe data untuk buffer stensil agar penghitungan tidak meluap. Saya harapkan itu berjalan dalam beberapa detik pada satu GPU ...
sumber