Jika Anda membuat asumsi ringan tentang jumlah tumpang tindih dalam rentang awalan Anda, Anda dapat melakukan apa yang Anda inginkan secara optimal menggunakan MongoDB atau MySQL. Dalam jawaban saya di bawah ini, saya akan mengilustrasikannya dengan MongoDB, tetapi seharusnya cukup mudah untuk mem-porting jawaban ini ke MySQL.
Pertama, mari kita ulangi masalahnya sedikit. Saat Anda berbicara tentang pencocokan "rentang awalan", saya yakin apa yang sebenarnya Anda bicarakan adalah menemukan rentang yang benar berdasarkan pengurutan leksikografis (secara intuitif, ini hanyalah pengurutan string berdasarkan abjad alami). Misalnya, himpunan bilangan yang awalannya cocok dengan 54661601 hingga 54661679 adalah himpunan bilangan yang, jika ditulis sebagai string, secara leksikografis lebih besar atau sama dengan "54661601", tetapi secara leksikografis lebih kecil dari "54661680". Jadi, hal pertama yang harus Anda lakukan adalah menambahkan 1 ke semua batas tinggi Anda, sehingga Anda bisa mengungkapkan pertanyaan Anda dengan cara ini. Di mongo, dokumen Anda akan terlihat seperti ini
{low: "54661601", high: "54661680", bin: "a"}
{low: "526219100", high: "526219200", bin: "b"}
{low: "4305870404", high: "4305870405", bin: "c"}
Sekarang masalahnya menjadi: jika diberikan himpunan interval satu dimensi dalam bentuk [rendah, tinggi), bagaimana kita dapat dengan cepat menemukan interval mana yang memuat suatu titik tertentu ? Cara termudah untuk melakukan hal ini adalah dengan indeks pada bidang rendah atau tinggi. Mari kita gunakan bidang tinggi. Di cangkang mongo:
db.coll.ensureIndex({high : 1})
Untuk saat ini, anggap saja intervalnya tidak tumpang tindih sama sekali. Jika hal ini terjadi, maka untuk titik kueri "x" tertentu, satu-satunya interval yang mungkin berisi "x" adalah interval dengan nilai tinggi terkecil yang lebih besar dari "x". Jadi kita bisa menanyakan dokumen itu dan memeriksa apakah nilainya rendah juga kurang dari "x". Misalnya, ini akan mencetak interval yang cocok, jika ada:
db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(1).forEach(
function(doc){ if (doc.low <= "5466160179125211") printjson(doc) }
)
Misalkan sekarang, alih-alih mengasumsikan interval tidak tumpang tindih sama sekali, Anda berasumsi bahwa setiap interval tumpang tindih dengan interval tetangga yang kurang dari k (saya tidak tahu berapa nilai k akan menjadikan hal ini benar bagi Anda, namun mudah-mudahan ini hanya masalah kecil). Dalam hal ini, Anda cukup mengganti 1 dengan k pada "batas" di atas, yaitu.
db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(k).forEach(
function(doc){ if (doc.low <= "5466160179125211") printjson(doc) }
)
Berapa waktu berjalan algoritma ini? Indeks disimpan menggunakan pohon-B, jadi jika ada interval n dalam kumpulan data Anda, diperlukan waktu O(log n) untuk mencari dokumen pertama yang cocok dengan < nilai kuat>tinggi, lalu O(k) waktu untuk melakukan iterasi pada dokumen k berikutnya, dengan total O(log n + k) kali. Jika k konstan, atau bahkan kurang dari O(log n), maka ini optimal secara asimtotik (ini ada dalam model komputasi standar; saya tidak menghitung jumlah transfer memori eksternal atau apa pun yang mewah).
Satu-satunya kasus di mana hal ini gagal adalah ketika k besar, misalnya jika suatu interval besar memuat hampir semua interval lainnya. Dalam hal ini, waktu berjalannya adalah O(n). Jika data Anda terstruktur seperti ini, Anda mungkin ingin menggunakan metode lain. Salah satu pendekatannya adalah dengan menggunakan pengindeksan "2d" mongo, dengan nilai rendah dan tinggi yang mengkodekan koordinat x dan y . Maka kueri Anda akan berhubungan dengan kueri titik di wilayah tertentu pada bidang x - y. Hal ini mungkin berhasil dalam praktiknya, meskipun dengan penerapan pengindeksan 2d saat ini, kasus terburuknya masih O(n).
Ada sejumlah hasil teoritis yang mencapai kinerja O(log n) untuk semua nilai k. Mereka diberi nama seperti Pohon Pencarian Prioritas, Pohon Segmen, Pohon Interval, dll. Namun, ini adalah struktur data tujuan khusus yang harus Anda terapkan sendiri. Sejauh yang saya tahu, saat ini tidak ada database populer yang mengimplementasikannya.
person
matulef
schedule
16.06.2012
