tries

mencoba

Kelas ini memberikan dasar untuk membangun wadah berbasis trie.

Pada bentuk dasarnya, kelas TTRIE dapat digunakan untuk menyimpan elemen data berbasis 16, 32 dan 64 bit.

Struktur menyediakan implementasi trie kedalaman tetap, yang pada gilirannya membuat waktu yang sama untuk menemukan, menghapus, dan menambahkan node.

Urutan struktur adalah O (d) di mana d adalah kedalaman trie, yang tergantung jika dibangun untuk menyimpan nilai 16, 32 atau 64 bit. Untuk 16 bit d = 4 untuk 32 bit d = 8 dan untuk 64 bit d = 16

Untuk menjaga ukuran simpul kecil, hanya 16 cabang per node yang akan digunakan dan bendera indikator dan indeks pointer internal dikodekan dalam kata 16 bit dan dalam bilangan bulat 64 bit.

Pointer ke cabang dikelola secara dinamis sehingga hanya pointer yang dialokasikan pada array pointer ketika cabang baru perlu ditambahkan, ini meminimalkan limbah array pointer yang dialokasikan sebelumnya ke cabang tingkat bawah. Ini akan memperlambat penambahan.

Leafs dialokasikan di tempat daripada sebagai node individu yang ditunjuk oleh simpul cabang terakhir.

Akhirnya, node daun dapat dikendalikan secara dinamis oleh kelas turunan dari ttrie yang memungkinkan untuk mengimplementasikan kamus yang mudah menggunakan Ttrie sebagai basis.

Secara keseluruhan, melakukan beberapa tes yang menyimpan memori yang dialokasikan oleh alokasi Lazarus (Freepascal) dalam MAC membuat sekitar 40% efisiensi penyimpanan sebanding dengan ukuran objek yang disimpan, yang tidak buruk mengingat kinerja untuk menambah, menemukan, dan menghapus operasi.

Kelas juga menyediakan metode paket yang digunakan untuk menjaga penyimpanan di cek ketika banyak yang dilepas telah dikeluarkan.

Tintegerhashtrie dan Tstringhashtrie disediakan sebagai keturunan kelas generik Thashtrie. Thashtrie memiliki dua mode operasi:

• Gunakan tabel hash untuk simpul root, dengan struktur trie dengan 16 node per ember untuk level berikutnya
• Struktur hashtrie penuh dari node root

Hash Table memberikan kinerja yang lebih baik tentu saja, tetapi Hashtrie memiliki jejak memori yang lebih efisien saat menyimpan sejumlah kecil elemen.

Diuji tstringhashtrie melawan delphi's tDictionary <> dan c# dictionary <> kelas.

Tstringhashtrie mengalahkan keduanya, implementasi C# dan Delphi. Perbedaan lebih besar saat menggunakan tabel hash untuk node root.

Jejak memori secara keseluruhan untuk beban besar juga lebih baik, mulai dari 30% -40% lebih baik. Untuk sejumlah kecil elemen secara definitif menggunakan hashtrie murni daripada node root tabel hash akan menggunakan memori secara dramatis lebih sedikit.

Tes yang dikumpulkan dalam Delphi 2007 menghasilkan hasil yang lebih baik karena string tidak harus menjalani konversi dari UTF16 ke ANSI sebelum dimasukkan ke dalam struktur.

TStringHashtrie mendukung unicode dalam bentuk UTF8.