Pertanyaan Kode C - akses / preempsi memori


Saya telah menulis sebuah kode di mana data:

unsigned char buf[4096]; // data in chunks of size 4k
unsigned counter[256];

Saya menambahkan data i / p untuk setiap 3 byte yang berdekatan dan menyimpan ans. contoh: temp [4096]; temp [0] = buf [0] + buf [1] + buf [2]; ... hingga 4096

Kemudian histogram dihasilkan dari hasil temp menggunakan kode:

for(i = 0; i < 4096; i++)
counter[temp[i]]++;

Histogram diurutkan (bubble sort) dan kemudian top 8 nilai yang paling berulang diambil. Kode dijalankan di kernel linux (2.6.35)

Masalah yang saya hadapi adalah bahwa jika saya menghapus bagian pengurutan, waktu yang dibutuhkan untuk menjalankan kode sangat cepat (6 microsec di laptop saya, diukur menggunakan gettimeofday func). Tapi setelah memperkenalkan pemilahan, prosesnya sangat melambat (44 microsec). Fungsi pengurutan itu sendiri membutuhkan 20 microsec, saya tidak bisa mengerti mengapa waktu kemudian meningkat begitu banyak. Saya melakukan analisis memori menggunakan cachegrind, hasilnya normal dan saya bahkan mencoba menonaktifkan preemption ubut tetap saja tidak menunjukkan perbedaan. Jika ada yang bisa membantu saya di sini. Terima kasih!


6
2017-07-05 13:41


asal


Jawaban:


Bubble sort lambat, ia membandingkan dan menukar nilai Anda hingga 4096 * 4096 = 16.777.216 kali. Jika Anda hanya membutuhkan 8 nilai terbaik, 1 pilihan sapuan tentu lebih cepat. Sesuatu seperti itu.

 const uint_t n = 8;
 uint_t best[n] = {0};
 uint_t index[n] = {0};
 uint_t j;

 for(uint_t i=0; i<4096; i++) {

   if(counter[i] > best[n-1]) {
     for(j=n-2; j && counter[i] > best[j]; j--);           /* Find the insertion position, as our value might be bigger than the value at position n-1. */
     memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]);      /* Shift the values beyond j up 1  */
     memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]);
     best[j] = counter[i];                                 /* Put the current best value at the top */
     index[j] = i;                                         /* Store the index in the second array to know where the best value was. */
   }
 }

Dengan itu, Anda membandingkan nilai Anda hanya sekali dan biaya memmove dapat diabaikan karena array pilihan Anda kecil. Tidak perlu mengurutkan larik, algo ini adalah O (nm) dengan n ukuran larik Anda dan m ukuran pilihan Anda. Yang terbaik adalah O ((n.log2 n) .m). Jadi jika m kecil dan n besar, itu tidak ada duanya oleh algoritma semacam generik.

EDIT: Saya menambahkan larik untuk indeks.

EDIT2: Diperkenalkan kedua untuk memperbaiki bug mendasar yang saya miliki pada awalnya.

EDIT3: Komentar: memmove dengan ukuran 0 diperbolehkan dan pada dasarnya adalah sebuah nop.


2
2017-07-05 14:02



Bubble sort lambat ... O (N ^ 2) kompleksitas ... jika Anda ingin kinerja lebih cepat, gunakan struktur data seperti heap, atau jalankan algoritma quick-sort pada array Anda, yang keduanya akan memberi Anda O (N log N) kompleksitas untuk proses penyortiran. Selain itu, kedua metode ini juga akan bekerja dengan baik pada larik dengan panjang tetap.


1
2017-07-05 13:56