Apakah implementasi `std::make_heap` libc++ tidak sesuai

Sunting: ini bukan menanyakan bagaimana melakukan std::make_heap dengan cara O(n), melainkan apakah implementasi khusus ini memang O(n)

Cara buku teks untuk membuat heap dalam waktu O(n) adalah dengan membangun heap secara berturut-turut dari bawah ke atas. Tetapi implementasi std::make_heap pada mesin Mac saya di libc++ adalah

template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_INLINE_VISIBILITY
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
#ifdef _LIBCPP_DEBUG
    typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref;
    __debug_less<_Compare> __c(__comp);
    __make_heap<_Comp_ref>(__first, __last, __c);
#else  // _LIBCPP_DEBUG
    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
    __make_heap<_Comp_ref>(__first, __last, __comp);
#endif  // _LIBCPP_DEBUG
}

di mana __make_heap didefinisikan sebagai

template <class _Compare, class _RandomAccessIterator>
void
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
{
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
    difference_type __n = __last - __first;
    if (__n > 1)
    {
        __last = __first;
        ++__last;
        for (difference_type __i = 1; __i < __n;)
            __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i);
    }
}

template <class _Compare, class _RandomAccessIterator>
void
__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
                 typename iterator_traits<_RandomAccessIterator>::difference_type __len)
{
    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
    if (__len > 1)
    {
        __len = (__len - 2) / 2;
        _RandomAccessIterator __ptr = __first + __len;
        if (__comp(*__ptr, *--__last))
        {
            value_type __t(_VSTD::move(*__last));
            do
            {
                *__last = _VSTD::move(*__ptr);
                __last = __ptr;
                if (__len == 0)
                    break;
                __len = (__len - 1) / 2;
                __ptr = __first + __len;
            } while (__comp(*__ptr, __t));
            *__last = _VSTD::move(__t);
        }
    }
}

Bukankah ini hanya memasukkan secara iteratif ke dalam heap, sehingga dengan kompleksitas waktu O(n log n)? Apakah saya benar bahwa ini adalah bug?


c++ clang llvm stl libc++
person Siyuan Ren    schedule 29.06.2014    source sumber
comment
Lihat jawaban ini. Singkatnya, algoritmanya tidak sesederhana kelihatannya.   -  person WhozCraig    schedule 29.06.2014
comment
@WhozCraig: Saya tahu algoritma O(n). Saya bertanya apakah implementasi khusus ini (libc++) gagal menggunakan yang benar.   -  person Siyuan Ren    schedule 29.06.2014
comment
@WhozCraig: Ini sama sekali bukan pertanyaan duplikat. Saya tidak bertanya bagaimana melakukannya dengan cara O(n). Sebaliknya, saya bertanya apakah implementasi ini memang O(n).   -  person Siyuan Ren    schedule 29.06.2014
comment
@Matthieu M.: Lihat hasil edit baru saya tentang ini bukan duplikat.   -  person Siyuan Ren    schedule 29.06.2014
comment
Saya tidak menandainya sebagai duplikat. Saya menghubungkan jawaban itu hanya untuk analisis algoritma (yang akurat). Pertanyaan Anda adalah mengenai implementasi spesifik dari algoritme tersebut, yang meskipun terkait, bukan merupakan duplikat (imho) dan seharusnya tidak ditandai seperti itu (itulah sebabnya saya tidak melakukannya). Pemungutan suara untuk dibuka kembali.   -  person WhozCraig    schedule 29.06.2014
comment
@C.R.: Saya ragu untuk menandainya sebagai duplikat juga; dan sejujurnya aku masih ragu. Faktanya adalah, algoritme di sini tampak sangat mirip dengan algoritme lainnya, dan analisis membuktikan bahwa algoritme tersebut adalah O(n). Memang ada beberapa perbedaan, tetapi menurut saya perbedaan tersebut tidak mengubah keadaan.   -  person Matthieu M.    schedule 29.06.2014
comment
@MatthieuM. Saya setuju juga, saya benar-benar ingin menipu hal ini, tetapi memilih untuk tidak melakukannya karena penerapannya, meskipun serupa, tidak sama dengan pertanyaan ini. Jawaban yang saya tautkan (dari pertanyaan itu, dan yang saya yakini adalah jawaban yang benar untuk kata-kata yang sama meskipun OP di sana sepertinya memilih yang berbeda) adalah analisis algoritma yang indah. Saya percaya bahwa analisis juga cocok dengan implementasi ini, dan mungkin hanya itu yang ingin divalidasi oleh C.R.   -  person WhozCraig    schedule 29.06.2014
comment
Ini memang terlihat seperti versi algoritme yang salah, dan saya telah mengukur jumlah operasinya untuk berbagai ukuran masukan dan sepertinya sesuai dengan kurva n log n.   -  person n. 1.8e9-where's-my-share m.    schedule 29.06.2014
comment
Saya memiliki Xcode 5.1.1 yang menjalankan implementasi libc++ yang sama dengan Anda, dan analisis dari jawaban tertaut mengenai algoritme tampak akurat. Saya menulis test-jig sederhana untuk membuat tumpukan dari urutan yang dihasilkan secara acak dengan panjang 1024 hingga 102400, versi gcc dapat dilihat di sini. Output rilis dari Mac saya dapat dilihat di sini. Outputnya mencakup N, NlogN, 3*N, dan perbandingan aktual yang dilakukan. Tidak pernah ada waktu yang melebihi 3N (atau bahkan terpenuhi). Semoga ini bisa membantu.   -  person WhozCraig    schedule 30.06.2014
comment
Sunting: Setelah membaca komentar n.m di bawah, saya terus maju dan menguji kompleksitas kasus terburuk daripada kompleksitas kasus rata-rata, dan memang dia benar. Lihat komentar saya untuk info lebih lanjut.   -  person WhozCraig    schedule 30.06.2014

Jawaban (2)


arrow_upward
9
arrow_downward

Ini memang implementasi O(n log n) yang tidak sesuai.

Membandingkannya dengan versi "saring" heapify dari artikel Wikipedia tentang heapsort menunjukkan bahwa pada dasarnya algoritmanya sama . Mengujinya pada urutan bilangan bulat yang meningkat (kasus terburuk) menghasilkan waktu berjalan yang sesuai dengan kurva n log n, dan jumlah perbandingan yang diperlukan melebihi angka 3n yang diamanatkan standar bahkan untuk n kecil.

Meskipun secara rata-rata algoritme bekerja dengan baik dalam batas 3n, standar ini mewajibkan performa dalam kasus terburuk, bukan performa rata-rata.

person n. 1.8e9-where's-my-share m.    schedule 30.06.2014
comment
@C.R. Terima kasih telah melaporkan bug tersebut. - person Marshall Clow; 30.06.2014
comment
+1 terima kasih telah menyelesaikan ini. Saya selalu lupa kelas algoritme dan pemodelan data terburuk saya masuk ke algoritme bertentangan dengan ekspektasi standar. Biaya rata-rata pada distribusi acak seragam tampaknya cocok, namun tentu saja hal ini merupakan masalah dalam penerapannya untuk kasus terburuk. Terima kasih lagi. - person WhozCraig; 30.06.2014
comment
Diperbaiki dalam revisi 213615 oleh David Majnemer - person Marshall Clow; 24.07.2014

arrow_upward
0
arrow_downward

Saya yakin diskusi di sini tampaknya menyimpang.

Jawaban atas pertanyaan tersebut adalah: Tidak; Implementasi std::make_heap libc++ memenuhi persyaratan yang diamanatkan standar C++ untuk rutinitas tersebut.

Mengutip dari standar C++11 (standar C++14 yang akan datang tampaknya tidak berubah untuk ini)

template<class RandomAccessIterator>
  void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
  void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

* Effects: Constructs a heap out of the range [first,last).
* Requires: The type of *first shall satisfy the MoveConstructible requirements (Table 20) and the MoveAssignable requirements (Table 22).
* Complexity: At most 3 * (last - first) comparisons.

Satu-satunya persyaratan kompleksitas adalah jumlah panggilan ke operator pembanding. Saya telah menjalankan beberapa tes, dan menyimpulkan bahwa implementasi libc++ memenuhi persyaratan ini. Saya mendapatkan sekitar 2.3*N perbandingan untuk operasi tersebut. Saya menggunakan pengujian di https://llvm.org/svn/llvm-project/libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp. @n.m, Anda mengklaim sebaliknya; Saya akan sangat menghargai melihat kasus uji Anda. Pengujian saya dilakukan dengan berbagai ukuran array int yang telah diacak menggunakan std::random_shuffle.

Pertanyaan yang ditautkan oleh @WhozCraig menunjukkan bahwa algoritma ini dapat diimplementasikan dengan menggunakan kurang dari 3N perbandingan. Saya telah menambahkan artikel itu ke daftar bacaan saya (sayangnya, panjang) untuk studi lebih lanjut dan kemungkinan peningkatan implementasi make_heap libc++. (Terima kasih!)

person Marshall Clow    schedule 30.06.2014
comment
Tolong tunjukkan pengujian Anda juga sehingga saya dapat memverifikasinya sendiri. - person Siyuan Ren; 30.06.2014
comment
yang telah diacak menggunakan std::random_shuffle. Itulah masalahnya. Algoritmenya (mungkin) rata-rata O(n), tetapi O(n log n) kasus terburuk. Coba urutan menaik (itulah kasus pengujian saya). - person n. 1.8e9-where's-my-share m.; 30.06.2014
comment
@n.m. kamu benar. Kode pengujian yang sama yang saya tunjukkan di komentar umum memiliki keluaran yang sangat berbeda dalam kasus terburuk vs rata-rata. Gcc yang dibangun di atas ideone (terlihat di sini) menampilkan angka-angka yang Anda harapkan. Bangunan lokal saya menggunakan rantai alat dan lib yang sama dengan OP (output terlihat di sini) menghasilkan angka yang sangat berbeda, dengan mudah melebihi 3N dan dengan cepat mendekati O(NlogN). Anda benar-benar harus mengirimkan jawaban sehingga saya dapat memperbaruinya. Terima kasih telah membuatku tetap jujur. Dengan ini saya setuju bahwa ini adalah implementasi yang disadap. - person WhozCraig; 30.06.2014
comment
@n.m. Saya selanjutnya menguji rantai alat yang sama, hanya mengalihkan perpustakaan standar yang digunakan dari libc++ ke libstdc++ dari gnu, dan jumlahnya sekali lagi dapat diterima dan setara dengan yang ada di postingan ideone. Sekali lagi, terima kasih telah menjaga ini tetap di atas air. - person WhozCraig; 30.06.2014
comment
@n.m. Saya melihatnya sekarang. Terima kasih. - person Marshall Clow; 30.06.2014
comment
Jawaban ini bertentangan dengan jawaban yang diterima. Apakah Anda setuju dengan penilaian di sana, atau Anda masih mengklaim bahwa libc++ memenuhi batasan kompleksitas yang ditentukan oleh standar? - person user4815162342; 10.07.2014