Pencarian array multi-dimensi vs pencarian array datar dengan komputasi

Question

Selama simulasi Monte-Carlo (MC) pada kisi dimensi $(L_1,L_2,\ldots,L_D)$, semua varibales situs sering disimpan sebagai file$D$array dimensi array. Untuk mencari varibale situs, seseorang hanya perlu$D$redup. coord coord.

Misalnya pada kisi 2 D, larik 2 D dapat dibuat di mana setiap elemen adalah beberapa variabel situs (dimensi atau sifat variabel situs itu sendiri tidak relevan). Untuk mencari var pada coord={x,y}satu kegunaan,Extract[array,coord]

Seringkali simulasi dilakukan dalam sapuan. Setiap sapuan terdiri dari$N=L_1L_2\ldots L_D$ pencarian acak pada array.

Ini adalah pencarian yang banyak, terutama saat simulasi mungkin memiliki no sapuan yang besar.

Karena memori pada akhirnya disimpan sebagai larik datar berurutan, mungkin lebih baik untuk melakukan pencarian pada larik datar sebagai gantinya.

flatArray=Flatten@array

Sekarang pencarian lebih sederhana

flatArray[position]

Seperti sebelumnya $N$ posisi acak dihasilkan per sapuan.

1. Apakah ini benar? Apakah pencarian array datar lebih cepat daripada pencarian bersarang? (untuk kasus uji ambil$D=3$ pada suatu $48\times 48\times48$ kisi)

Namun, untuk array yang diratakan, struktur kisi akan hilang. Untuk melakukan kalkulasi yang membutuhkan struktur tersebut, dibutuhkan koordinat situs dalam kisi. Meskipun ini dapat dihitung setiap saat, seseorang mungkin juga melakukan pencarian sebagai gantinya.

allCords=Flatten[Array[{##}&,{L1,L2,...,LD}],D-1]
toCoord[pos_]:=allCoords[[pos]]

1. Apakah benar untuk mengasumsikan bahwa komputasi coord lebih lambat daripada pencarian coord? Perlu diingat bahwa penghitungan ini untuk umum$D$.

2. Dengan syarat membutuhkan lattice coord juga (via compute atau lookup), apakah jawaban untuk 1. masih sama?

Asumsikan di atas bahwa memori itu murah tetapi waktu mahal.

Answer 1

Pertama izinkan saya mengatakan bahwa mungkin bermanfaat untuk digunakan Partdaripada Extract. Tetapi ini mungkin memerlukan pemfaktoran ulang kode Anda dan mungkin menyebabkan kemunduran di tempat lain. Jika indeks acak Anda muncul sebagai indeks tiga kali lipat, maka itu Extractadalah pilihan yang cukup bagus. Tetapi jika Anda dapat membuat indeks linier secara langsung, Partmungkin itu pilihan yang lebih baik:

n = 48;
m = 1000000;
A = RandomReal[{-1, 1}, {n, n, n}];
a = Flatten[A];

r1 = Extract[A, RandomInteger[{1, n}, {m, 3}]]; // RepeatedTiming // First
r2 = Part[a, RandomInteger[{1, n^3}, {m}]]; // RepeatedTiming // First

0,027

0,011

Bahkan mungkin bermanfaat untuk melewati pembuatan indeks dengan menggunakan RandomChoice:

r3 = RandomChoice[a, m]; // RepeatedTiming // First

0,0092

Namun, ini akan membuat tidak mungkin untuk mengakses koordinat kisi, jadi ini mungkin bukan yang Anda cari.

Di 1 .: array yang dikemas Mathematica memang daftar datar dengan pencarian bersarang diterapkan persis seperti yang Anda sarankan. Jadi pada dasarnya tidak ada perbedaan antara panggilan memori datar Partyang Anda gunakan untuk menghitung indeks linier dari koordinat secara manual atau jika Anda melakukan panggilan memori bersarang (dan biarkan Mathematica melakukan penghitungan indeks linier dari koordinat). Tentu saja, dalam praktiknya, bagaimanapun mungkin ada sedikit perbedaan dalam kinerja (misalnya, Mathematica juga melakukan beberapa pemeriksaan keamanan yang memakan waktu lebih lama atau melakukan beberapa caching pintar yang mungkin mempercepat sedikit). Biasanya, ketika saya Compilemenggunakan kode dan Compile`GetElementbukanPart untuk panggilan memori, kemudian menggunakan pengindeksan linier atau bersarang membuat sedikit perbedaan.

At 2 .: Seperti yang telah Anda ketahui, pencarian dalam memori cenderung lebih memakan waktu daripada komputasi dalam bilangan bulat mesin dan float mesin (ganda), karena kelambatan memori dan bandwidth terbatas. (Perkembangan memori tidak sesuai dengan perkembangan CPU dalam beberapa tahun terakhir.) Jadi terkadang , ada baiknya untuk menghitung ulang sesuatu dengan data yang sudah ada daripada harus menunggu hasil panggilan memori . Secara umum, seseorang hanya perlu mencoba beberapa implementasi alternatif untuk menemukan implementasi yang berkinerja terbaik pada kelas masalah yang ingin dipecahkan.

Pada 3 .: Jika Anda benar-benar ingin pergi ke rute itu, saya sarankan untuk menggunakan Quotientdan Modmenghitung koordinat kisi dari indeks linier. (Anda juga dapat menggunakan IntegerDigits(dengan MixedRadix, jika dimensi array tidak semuanya sama), tetapi tampaknya performanya kurang.) Jawaban lengkapnya sangat bergantung pada seberapa besar tabel pemeta (misalnya, apakah tabel tersebut akan cache meleset).

Sebagai pernyataan terakhir, izinkan saya mengatakan bahwa Mathematica adalah bahasa tingkat tinggi dengan banyak tujuan. Ini tidak dimaksudkan untuk dan tidak mampu menghasilkan kode kinerja tinggi terbaik yang mungkin dioptimalkan. Tetapi Mathematica menebusnya dengan cukup banyak mempercepat pembuatan prototipe. Jadi jika Anda harus menyelesaikan masalah yang terikat memori dan jika Anda harus melakukannya secepat mungkin, pada titik tertentu, Anda harus mempertimbangkan untuk mem-port algoritma Anda ke bahasa yang lebih dekat dengan mesin, misalnya, C, C ++ , atau FORTRAN.