Bootstrap pada Struktur Pohon Jari

Setelah bekerja dengan 2-3 pohon jari cukup lama saya terkesan dengan kecepatan mereka di sebagian besar operasi. Namun, satu masalah yang saya temui adalah overhead besar yang terkait dengan penciptaan awal pohon jari besar. Karena bangunan didefinisikan sebagai urutan operasi rangkaian Anda akhirnya membangun sejumlah besar struktur pohon jari yang tidak dibutuhkan.

Karena sifat kompleks pohon 2-3 jari saya tidak melihat metode intuitif untuk bootstrap mereka, dan semua pencarian saya sudah kosong. Jadi pertanyaannya adalah, bagaimana Anda bisa melakukan bootstrap pada pohon 2-3 jari dengan overhead yang minimal?

Secara eksplisit: diberi urutan dengan panjang yang diketahui n menghasilkan representasi pohon jari S dengan operasi minimal.$S$$n$$S$

Cara naif untuk mencapainya adalah panggilan berturut-turut ke operasi kontra (dalam literatur operator ' '). Namun, ini akan membuat n struktur pohon jari yang berbeda yang mewakili semua irisan S untuk [ 1 .. i ] .$\triangleleft$$n$$S$$[1..i]$

GHC ini Data.Sequence's replicatefungsi membangun fingertree di ruang dan waktu, tetapi ini diaktifkan dengan mengetahui unsur-unsur yang pergi pada tulang belakang kanan pohon jari dari get-go. Perpustakaan ini ditulis oleh penulis makalah asli pada pohon 2-3 jari.$O(\lg n)$

Jika Anda ingin membangun pohon jari dengan rangkaian berulang, Anda mungkin dapat mengurangi penggunaan ruang sementara sambil membangun dengan mengubah representasi duri. Duri pada pohon 2-3 jari disimpan dengan cerdas sebagai daftar yang terhubung secara tunggal yang disinkronkan. Sebaliknya, jika Anda menyimpan duri sebagai deques, dimungkinkan untuk menghemat ruang saat menggabungkan pohon. Idenya adalah bahwa menggabungkan dua pohon dengan ketinggian yang sama membutuhkan ruang dengan menggunakan kembali duri pohon. Ketika menggabungkan 2-3 pohon jari seperti yang dijelaskan sebelumnya, duri-duri yang ada di dalam pohon baru tidak dapat lagi digunakan apa adanya.$O(1)$

"Representasi Murni Berfungsi dari Daftar Berurut Catenable" dari Kaplan dan Tarjan menggambarkan struktur pohon jari yang lebih rumit. Makalah ini (dalam bagian 4) juga membahas konstruksi yang mirip dengan saran deque yang saya buat di atas. Saya percaya struktur yang mereka gambarkan dapat menggabungkan dua pohon dengan ketinggian yang sama dalam waktu dan ruang. Untuk membangun pohon jari, apakah ini cukup ruang untuk Anda?$O(1)$

NB: Penggunaan kata "bootstrap" mereka berarti sesuatu yang sedikit berbeda dari penggunaan Anda di atas. Mereka berarti menyimpan bagian dari struktur data menggunakan versi sederhana dari struktur yang sama.

Mengetahui jawaban jbapple yang sangat baik tentang replicate, tetapi menggunakan replicateA(yang replicatedibangun di atas), saya datang dengan yang berikut:

--Unlike fromList, one needs the length explicitly. 
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
    where go = do
           (y:ys) <- get
            put ys
            return y

myFromList(dalam versi yang sedikit lebih efisien) sudah didefinisikan dan digunakan secara internal dalam Data.Sequenceuntuk membangun pohon jari yang hasil macam.

Secara umum, intuisi untuk replicateAsederhana. replicateAdibangun di atas fungsi applicativeTree . applicativeTreemengambil sepotong pohon ukuran m, dan menghasilkan pohon seimbang yang mengandung nsalinan ini. Kasing nhingga 8 (satu Deepjari) dikodekan dengan keras. Apa pun di atas ini, dan itu memanggil dirinya sendiri secara rekursif. Unsur "aplikatif" hanyalah bahwa ia menyisipkan konstruksi pohon dengan efek threading melalui, seperti, dalam kasus kode di atas, menyatakan.

The gofungsi, yang direplikasi, hanyalah sebuah tindakan yang mendapat kondisi saat ini, muncul sebuah elemen dari atas, dan menggantikan sisanya. Pada setiap doa, itu dengan demikian melangkah lebih jauh ke bawah daftar yang disediakan sebagai input.

Beberapa catatan lebih konkret

main = print (length (show (Seq.fromList [1..10000000::Int])))

Pada beberapa tes sederhana, ini menghasilkan tradeoff kinerja yang menarik. Fungsi utama di atas berjalan hampir 1/3 lebih rendah dengan myFromList daripada dengan fromList. Di sisi lain, myFromListdigunakan tumpukan konstan 2MB, sedangkan standar fromListdigunakan hingga 926MB. 926MB itu muncul dari keharusan untuk menahan seluruh daftar di memori sekaligus. Sementara itu, solusi dengan myFromListmampu mengkonsumsi struktur dengan cara streaming malas. Masalah dengan kecepatan hasil dari fakta yang myFromListharus melakukan alokasi kira-kira dua kali lebih banyak (sebagai akibat dari pembangunan pasangan / penghancuran monad negara) sebagaifromList. Kita dapat menghilangkan alokasi tersebut dengan pindah ke state monad yang diubah CPS, tetapi hal itu menghasilkan memori yang jauh lebih banyak pada waktu tertentu, karena kehilangan kemalasan mengharuskan untuk melintasi daftar secara non-streaming.

Di sisi lain, jika alih-alih memaksa seluruh urutan dengan sebuah pertunjukan, saya pindah ke hanya mengekstraksi kepala atau elemen terakhir, myFromListsegera menyajikan kemenangan yang lebih besar - mengekstraksi elemen kepala hampir instan, dan mengekstraksi elemen terakhir adalah 0,8 detik. . Sementara itu, dengan standar fromList, mengekstraksi kepala atau elemen terakhir membutuhkan biaya ~ 2,3 detik.

Ini semua detail, dan merupakan konsekuensi dari kemurnian dan kemalasan. Dalam situasi dengan mutasi dan akses acak, saya akan membayangkan replicatesolusinya benar-benar lebih baik.

Namun, hal itu menimbulkan pertanyaan apakah ada cara untuk menulis ulang applicativeTreesedemikian rupa sehingga myFromListlebih efisien. Masalahnya adalah, saya pikir, bahwa tindakan aplikatif dijalankan dalam urutan yang berbeda dari pohon secara alami dilalui, tetapi saya belum sepenuhnya bekerja melalui bagaimana ini bekerja, atau jika ada cara untuk menyelesaikan ini.

Sementara Anda berakhir dengan sejumlah besar struktur jari tengah, mereka berbagi sebagian besar struktur mereka satu sama lain. Pada akhirnya Anda mengalokasikan paling banyak dua kali lebih banyak memori daripada dalam kasus ideal, dan sisanya dibebaskan dengan koleksi pertama. Asimptotik ini sama baiknya dengan yang didapat, karena Anda memerlukan jari yang diisi dengan n nilai pada akhirnya.

Anda dapat membangun ujung jari dengan menggunakan Data.FingerTree.replicatedan menggunakannya FingerTree.fmapWithPosuntuk mencari nilai-nilai Anda dalam array yang memainkan peran urutan terbatas Anda, atau menggunakan traverseWithPosuntuk mengupasnya dari daftar atau wadah berukuran diketahui lainnya.

$O(\log n)$$O(n)$$O(\log n)$

$O(\log n)$replicateAmapAccumL

TL; DR Jika saya harus melakukan ini, saya mungkin akan menggunakan:

rep :: (Int -> a) -> Int -> Seq a 
rep f n = mapWithIndex (const . f) $ replicate n () 

dan untuk mengindeks ke array berukuran tetap saya hanya akan menyediakan (arr !)untuk di fatas.