Kontainer STL mana yang harus saya gunakan untuk FIFO?

93

Wadah STL mana yang paling sesuai dengan kebutuhan saya? Saya pada dasarnya memiliki wadah lebar 10 elemen di mana saya terus push_backelemen baru sementara pop_frontelemen tertua (sekitar satu juta kali).

Saat ini saya menggunakan std::dequeuntuk tugas tersebut tetapi bertanya-tanya apakah a std::listakan lebih efisien karena saya tidak perlu mengalokasikan ulang sendiri (atau mungkin saya salah mengira std::dequea std::vector?). Atau adakah wadah yang lebih efisien untuk kebutuhan saya?

PS Saya tidak perlu akses acak

Gab Royer
sumber
5
Mengapa tidak mencobanya dengan keduanya dan waktu untuk melihat mana yang lebih cepat untuk kebutuhan Anda?
KTC
5
Saya akan melakukan ini, tetapi saya juga mencari jawaban teoretis.
Gab Royer
2
yang std::dequetidak akan dialokasikan kembali. Ini adalah hibrida dari a std::listdan di std::vectormana ia mengalokasikan potongan yang lebih besar daripada a std::listtetapi tidak akan dialokasikan seperti a std::vector.
Harga Matt
2
Tidak, berikut adalah jaminan yang relevan dari standar: "Memasukkan satu elemen baik di awal atau akhir deque selalu membutuhkan waktu konstan dan menyebabkan satu panggilan ke konstruktor salinan T."
Matt Harga
1
@ John: Tidak, itu mengalokasikan lagi. Mungkin kita hanya mencampurkan istilah. Menurut saya, realokasi berarti mengambil alokasi lama, menyalinnya ke alokasi baru, dan membuang yang lama.
GManNickG

Jawaban:

198

Karena ada banyak sekali jawaban, Anda mungkin bingung, tetapi untuk diringkas:

Gunakan a std::queue. Alasannya sederhana: ini adalah struktur FIFO. Anda menginginkan FIFO, Anda menggunakan file std::queue.

Itu membuat niat Anda jelas bagi orang lain, dan bahkan diri Anda sendiri. A std::listatau std::dequetidak. Sebuah daftar dapat disisipkan dan dihapus di mana saja, yang tidak seharusnya dilakukan oleh struktur FIFO, dan dequedapat menambah dan menghapus dari kedua ujungnya, yang juga merupakan sesuatu yang tidak dapat dilakukan oleh struktur FIFO.

Inilah mengapa Anda harus menggunakan file queue.

Sekarang, Anda bertanya tentang kinerja. Pertama, selalu ingat aturan praktis yang penting ini: Kode bagus dulu, performa terakhir.

Alasannya sederhana: orang yang mengupayakan penampilan sebelum kebersihan dan keanggunan hampir selalu menjadi yang terakhir. Kode mereka menjadi omong kosong, karena mereka telah meninggalkan semua yang baik untuk benar-benar mendapatkan apa-apa darinya.

Dengan menulis kode yang bagus dan dapat dibaca terlebih dahulu, sebagian besar masalah kinerja Anda akan teratasi sendiri. Dan jika nanti Anda menemukan kinerja Anda kurang, sekarang mudah untuk menambahkan profiler ke kode Anda yang bagus dan bersih, dan mencari tahu di mana masalahnya.

Itu semua dikatakan, std::queuehanya adaptor. Ini menyediakan antarmuka yang aman, tetapi menggunakan wadah yang berbeda di dalam. Anda dapat memilih wadah dasar ini, dan ini memungkinkan banyak fleksibilitas.

Jadi, wadah dasar mana yang harus Anda gunakan? Kita tahu bahwa std::listdan std::dequekeduanya memberikan fungsi yang diperlukan ( push_back(), pop_front(), dan front()), jadi bagaimana kita memutuskan?

Pertama, pahami bahwa mengalokasikan (dan membatalkan alokasi) memori bukanlah hal yang cepat untuk dilakukan, umumnya, karena melibatkan keluar ke OS dan memintanya untuk melakukan sesuatu. A listharus mengalokasikan memori setiap kali ada sesuatu yang ditambahkan, dan mengalokasikannya ketika hilang.

A deque, di sisi lain, mengalokasikan dalam potongan. Ini akan mengalokasikan lebih jarang dari a list. Anggap saja sebagai daftar, tetapi setiap bagian memori dapat menampung banyak node. (Tentu saja, saya menyarankan agar Anda benar-benar mempelajari cara kerjanya .)

Jadi, dengan itu saja a dequeharus berkinerja lebih baik, karena tidak sering berurusan dengan memori. Dicampur dengan fakta Anda menangani data dengan ukuran konstan, mungkin tidak perlu mengalokasikan setelah melewati pertama melalui data, sedangkan daftar akan terus mengalokasikan dan membatalkan alokasi.

Hal kedua yang perlu dipahami adalah kinerja cache . Keluar ke RAM itu lambat, jadi ketika CPU benar-benar membutuhkannya, itu memanfaatkan yang terbaik dari waktu ini dengan mengambil sebagian memori bersamanya, ke dalam cache. Karena a dequemengalokasikan dalam potongan memori, kemungkinan mengakses elemen dalam penampung ini akan menyebabkan CPU mengembalikan sisa penampungnya juga. Sekarang akses lebih lanjut ke dequeakan lebih cepat, karena datanya ada dalam cache.

Ini tidak seperti daftar, di mana data dialokasikan satu per satu. Ini berarti bahwa data dapat tersebar di semua tempat di memori, dan kinerja cache akan menjadi buruk.

Jadi, mengingat itu, dequeseharusnya menjadi pilihan yang lebih baik. Inilah mengapa ini adalah penampung default saat menggunakan file queue. Meskipun demikian, ini masih hanya tebakan (sangat) terpelajar: Anda harus membuat profil kode ini, menggunakan dequetes dalam satu dan tes listlain untuk benar-benar mengetahui dengan pasti.

Tapi ingat: dapatkan kode yang berfungsi dengan antarmuka yang bersih, lalu khawatirkan performa.

John menimbulkan kekhawatiran bahwa membungkus listatau dequeakan menyebabkan penurunan kinerja. Sekali lagi, dia dan saya tidak dapat mengatakan dengan pasti tanpa membuat profilnya sendiri, tetapi kemungkinan besar kompilator akan menyebariskan panggilan yang queuedibuat. Artinya, ketika Anda mengatakan queue.push(), itu benar-benar hanya akan mengatakan queue.container.push_back(), melewatkan panggilan fungsi sepenuhnya.

Sekali lagi, ini hanya tebakan, tetapi menggunakan queuetidak akan menurunkan kinerja, jika dibandingkan dengan menggunakan wadah mentah yang mendasarinya. Seperti yang saya katakan sebelumnya, gunakan queue, karena bersih, mudah digunakan, dan aman, dan jika benar-benar menjadi profil masalah dan uji.

GManNickG
sumber
10
+1 - dan jika ternyata boost :: circular_buffer <> memiliki performa terbaik, maka gunakan saja itu sebagai container yang mendasarinya (ini juga menyediakan push_back (), pop_front (), front (), dan back () yang diperlukan ).
Michael Burr
2
Diterima karena menjelaskannya secara detail (yang saya butuhkan, terima kasih telah meluangkan waktu). Adapun kode yang baik, kinerja pertama terakhir, saya harus mengakui bahwa itu salah satu default terbesar saya, saya selalu mencoba melakukan sesuatu dengan sempurna saat pertama kali dijalankan ... Saya memang menulis kode menggunakan deque pertama, tapi karena hal itu tidak ' T berkinerja sebaik yang saya kira (seharusnya hampir real-time), saya rasa saya harus meningkatkannya sedikit. Seperti yang juga dikatakan Neil, saya seharusnya benar-benar menggunakan profiler ... Meskipun saya senang telah membuat kesalahan ini sekarang sementara itu tidak terlalu penting. Terima kasih banyak untuk kalian semua.
Gab Royer
4
-1 karena tidak memecahkan masalah dan jawaban tidak berguna yang membengkak. Jawaban yang benar di sini singkat dan ini adalah boost :: circular_buffer <>.
Dmitry Chichkov
1
"Kode bagus dulu, performa terakhir", itu kutipan yang luar biasa. Jika hanya semua orang yang memahami ini :)
thegreendroid
Saya menghargai tekanan pada pembuatan profil. Memberikan aturan praktis adalah satu hal dan kemudian membuktikannya dengan membuat profil adalah hal yang lebih baik
talekeDskobeDa
28

Lihat std::queue. Ini membungkus jenis penampung yang mendasari, dan penampung default adalah std::deque.

Mark Ransom
sumber
3
Setiap lapisan tambahan akan dihilangkan oleh kompiler. Menurut logika Anda, kita semua harus memprogram dalam assembly, karena bahasanya hanyalah shell yang menghalangi. Intinya adalah menggunakan jenis yang benar untuk pekerjaan itu. Dan queueapakah tipe itu. Kode bagus dulu, performa nanti. Sial, sebagian besar kinerja keluar dari penggunaan kode yang baik di tempat pertama.
GManNickG
2
Maaf tidak jelas - maksud saya adalah bahwa antrian persis seperti pertanyaan yang ditanyakan, dan perancang C ++ menganggap deque adalah wadah dasar yang baik untuk kasus penggunaan ini.
Mark Ransom
2
Tidak ada dalam pertanyaan ini yang menunjukkan bahwa dia menemukan kinerja yang kurang. Banyak pemula yang terus-menerus bertanya tentang solusi paling efektif untuk masalah apa pun, terlepas dari apakah solusi mereka saat ini bekerja dengan baik atau tidak.
jalf
1
@John, jika dia menemukan kinerjanya kurang, melepaskan cangkang pengaman queuetidak akan meningkatkan kinerja, seperti yang telah saya katakan. Anda menyarankan a list, yang mungkin akan berkinerja lebih buruk.
GManNickG
3
Hal tentang std :: queue <> adalah bahwa jika deque <> bukan yang Anda inginkan (untuk kinerja atau alasan apa pun), itu adalah satu-baris untuk mengubahnya untuk menggunakan std :: list sebagai penyimpanan pendukung - sebagai GMan berkata jauh. Dan jika Anda benar-benar ingin menggunakan buffer ring daripada daftar, boost :: circular_buffer <> akan masuk tepat di ... std :: queue <> hampir pasti merupakan 'antarmuka' yang harus digunakan. Penyimpanan pendukung untuk itu dapat diubah sesuka hati.
Michael Burr
7

Saya terus menerus push_backelemen baru sambil pop_fronting elemen tertua (sekitar satu juta kali).

Sejuta bukanlah angka yang besar dalam komputasi. Seperti yang disarankan orang lain, gunakan a std::queuesebagai solusi pertama Anda. Jika terjadi terlalu lambat, identifikasi hambatan menggunakan profiler (jangan tebak!) Dan implementasikan ulang menggunakan penampung berbeda dengan antarmuka yang sama.

burung phoenix
sumber
1
Masalahnya, ini adalah angka yang besar karena yang ingin saya lakukan seharusnya dalam waktu nyata. Meskipun Anda benar bahwa saya seharusnya menggunakan profiler untuk mengidentifikasi penyebabnya ...
Gab Royer
Masalahnya, saya tidak terlalu terbiasa menggunakan profiler (kami telah menggunakan sedikit gprof di salah satu kelas kami tetapi kami benar-benar tidak membahasnya secara mendalam ...). Jika Anda dapat mengarahkan saya ke beberapa sumber, saya akan sangat menghargai! PS. Saya menggunakan VS2008
Gab Royer
@ Gab: VS2008 mana yang Anda miliki (Express, Pro ...)? Beberapa datang dengan profiler.
sbi
@Gab Maaf, saya tidak menggunakan VS lagi jadi tidak bisa memberi saran
@Sbi, dari apa yang saya lihat, itu hanya dalam edisi sistem tim (yang dapat saya akses). Saya akan memeriksa ini.
Gab Royer
5

Mengapa tidak std::queue? Semua yang dimilikinya adalah push_backdan pop_front.

eduffy
sumber
3

Sebuah antrian mungkin antarmuka sederhana daripada deque tapi untuk seperti daftar kecil, perbedaan kinerja mungkin diabaikan.

Sama halnya dengan daftar . Ini tergantung pada pilihan API yang Anda inginkan.

lavinio
sumber
Tapi saya bertanya-tanya apakah push_back yang konstan membuat antrean atau membatalkan alokasi ulang sendiri
Gab Royer
std :: queue adalah pembungkus di sekitar penampung lain, jadi antrian yang membungkus deque akan kurang efisien daripada deque mentah.
John Millikin
1
Untuk 10 item, kinerja kemungkinan besar akan menjadi masalah kecil, sehingga "efisiensi" mungkin lebih baik diukur dalam waktu pemrogram daripada waktu kode. Dan panggilan dari antrian ke deque oleh pengoptimalan kompiler yang layak akan menjadi nol.
lavinio
2
@ John: Saya ingin Anda menunjukkan kepada saya seperangkat tolok ukur yang menunjukkan perbedaan kinerja seperti itu. Ini tidak kalah efisiennya dengan deque mentah. Compiler C ++ melakukan inline dengan sangat agresif.
jalf
3
Saya sudah mencobanya. : DA cepat & kotor 10 elemen kontainer dengan 100.000.000 pop_front () & push_back () rand () nomor int pada rilis build untuk kecepatan pada VC9 memberikan: daftar (27), antrian (6), deque (6), array (8) .
KTC
0

Gunakan a std::queue, tetapi perhatikan pengorbanan kinerja dari dua Containerkelas standar .

Secara default, std::queueadalah adaptor di atas std::deque. Biasanya, itu akan memberikan kinerja yang baik di mana Anda memiliki sejumlah kecil antrian yang berisi banyak entri, yang bisa dibilang kasus umum.

Namun, jangan buta terhadap implementasi std :: deque . Secara khusus:

"... deques biasanya memiliki biaya memori minimal yang besar; deque yang hanya menampung satu elemen harus mengalokasikan array internal penuhnya (misalnya 8 kali ukuran objek pada 64-bit libstdc ++; 16 kali ukuran objek atau 4096 byte, mana saja yang lebih besar , di 64-bit libc ++). "

Untuk menjernihkannya, anggaplah bahwa entri antrian adalah sesuatu yang Anda ingin antri, misalnya ukurannya cukup kecil, maka jika Anda memiliki 4 antrian, masing-masing berisi 30.000 entri, std::dequeimplementasi akan menjadi opsi pilihan. Sebaliknya, jika Anda memiliki 30.000 antrian, masing-masing berisi 4 entri, maka kemungkinan besar std::listpenerapannya akan optimal, karena Anda tidak akan pernah mengamortisasi std::dequebiaya overhead dalam skenario itu.

Anda akan membaca banyak opini tentang bagaimana cache adalah raja, bagaimana Stroustrup membenci daftar tertaut, dll., Dan semua itu benar, dalam kondisi tertentu. Hanya saja, jangan menerimanya dengan keyakinan buta, karena dalam skenario kedua kami di sana, sangat tidak mungkin std::dequeimplementasi default akan berfungsi. Evaluasi penggunaan dan ukuran Anda.

Allan Bazinet
sumber
-1

Kasus ini cukup sederhana sehingga Anda bisa menuliskannya sendiri. Ini adalah sesuatu yang bekerja dengan baik untuk situasi mikrokontroler di mana penggunaan STL memakan terlalu banyak ruang. Ini adalah cara yang bagus untuk melewatkan data dan sinyal dari penangan interupsi ke loop utama Anda.

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};
pengguna10658782
sumber
Tapi bagaimana / kapan itu akan terjadi?
pengguna10658782
Oh, saya pikir itu bisa karena suatu alasan. Lupakan!
Ry-