Mengapa kelas String Java tidak mengimplementasikan indexOf () yang lebih efisien?

Mengikuti pertanyaan di bawah ini tentang Stack Overflow

/programming/5564610/fast-alernative-for-stringindexofstring-str

Saya bertanya-tanya mengapa java (setidaknya 6) tidak menggunakan implementasi yang lebih efisien?

Berikut ini adalah kode:

java.lang.String # indexOf (String str)

1762    static int indexOf(char[] source, int sourceOffset, int sourceCount,
1763                       char[] target, int targetOffset, int targetCount,
1764                       int fromIndex) {
1765        if (fromIndex >= sourceCount) {
1766            return (targetCount == 0 ? sourceCount : -1);
1767        }
1768        if (fromIndex < 0) {
1769            fromIndex = 0;
1770        }
1771        if (targetCount == 0) {
1772            return fromIndex;
1773        }
1774
1775        char first  = target[targetOffset];
1776        int max = sourceOffset + (sourceCount - targetCount);
1777
1778        for (int i = sourceOffset + fromIndex; i <= max; i++) {
1779            /* Look for first character. */
1780            if (source[i] != first) {
1781                while (++i <= max && source[i] != first);
1782            }
1783
1784            /* Found first character, now look at the rest of v2 */
1785            if (i <= max) {
1786                int j = i + 1;
1787                int end = j + targetCount - 1;
1788                for (int k = targetOffset + 1; j < end && source[j] ==
1789                         target[k]; j++, k++);
1790
1791                if (j == end) {
1792                    /* Found whole string. */
1793                    return i - sourceOffset;
1794                }
1795            }
1796        }
1797        return -1;
1798    }

"Efisiensi" adalah semua tentang pengorbanan, dan algoritma "terbaik" akan tergantung pada banyak faktor. Dalam kasus indexOf(), salah satu faktor tersebut adalah ukuran string yang diharapkan.

Algoritma JDK didasarkan pada referensi sederhana yang diindeks ke dalam array karakter yang ada. Knuth-Morris-Pratt yang Anda referensi perlu membuat yang baru int[]dengan ukuran yang sama dengan string input. Untuk Boyer-Moore , Anda memerlukan beberapa tabel eksternal, setidaknya satu di antaranya adalah dua dimensi (saya pikir; Saya tidak pernah menerapkan BM).

Jadi pertanyaannya menjadi: apakah mengalokasikan objek tambahan dan membangun tabel pencarian diimbangi dengan peningkatan kinerja algoritma? Ingat, kita tidak berbicara tentang perubahan dari O (N ² ) ke O (N), tetapi hanya pengurangan jumlah langkah yang diambil untuk setiap N.

Dan saya berharap bahwa desainer JDK mengatakan sesuatu seperti "untuk string kurang dari karakter X, pendekatan sederhana lebih cepat, kami tidak mengharapkan penggunaan string secara teratur lebih lama dari itu, dan orang-orang yang menggunakan string lebih lama akan tahu cara mengoptimalkan pencarian mereka. "

Algoritma pencarian string efisien standar yang diketahui semua orang adalah Boyer-Moore . Di antara hal-hal lain itu membutuhkan membangun tabel transisi yang ukurannya sama dengan set karakter Anda. Dalam kasus ASCII, itu adalah array dengan 256 entri, yang merupakan overhead konstan yang terbayar dengan string panjang, dan tidak memperlambat string kecil dengan cukup bagi siapa pun untuk peduli. Tapi Java menggunakan karakter 2-byte yang membuat tabel itu berukuran 64K. Dalam penggunaan normal, overhead ini melebihi kecepatan yang diharapkan dari Boyer-Moore, jadi Boyer-Moore tidak berharga.

Tentu saja sebagian besar tabel itu akan memiliki entri yang sama, jadi Anda mungkin berpikir bahwa Anda bisa menyimpan pengecualian dengan cara yang efisien, dan kemudian menyediakan default untuk apa pun yang tidak ada dalam pengecualian Anda. Sayangnya cara melakukan ini datang dengan biaya pencarian yang membuat mereka terlalu mahal untuk menjadi efisien. (Untuk satu masalah, ingat bahwa jika mengambil cabang yang tidak terduga menyebabkan warung pipa dan yang cenderung mahal.)

Harap dicatat bahwa dengan Unicode masalah ini sangat tergantung pada penyandian Anda. Ketika Java ditulis, Unicode muat dalam 64 K, jadi Java hanya menggunakan 2 byte per karakter dan panjang string hanyalah jumlah byte yang dibagi dengan 2. (Pengkodean ini disebut UCS-2.) Ini membuatnya cepat untuk lompat ke karakter tertentu atau ekstrak substring tertentu, dan inefisiensi untukindexOf()adalah masalah. Sayangnya Unicode telah berkembang, jadi karakter Unicode tidak selalu cocok dengan karakter Java. Ini membawa Java ke masalah ukuran yang mereka coba hindari. (Encoding mereka sekarang UTF-16.) Untuk kompatibilitas mundur mereka tidak dapat mengubah ukuran karakter Java, tetapi sekarang ada meme bahwa karakter Unicode dan karakter Java adalah hal yang sama. Mereka tidak, tetapi hanya sedikit programmer Java yang mengetahuinya, dan bahkan lebih sedikit yang akan menemukannya dalam kehidupan sehari-hari. (Perhatikan bahwa Windows dan .NET mengikuti jalur yang sama, untuk alasan yang sama.)

Dalam beberapa bahasa dan lingkungan lain, UTF-8 digunakan sebagai gantinya. Ini memiliki sifat yang bagus bahwa ASCII adalah Unicode yang valid dan Boyer-Moore efisien. Imbalannya adalah bahwa kegagalan untuk memperhatikan isu-isu byte variabel lebih banyak memukul Anda daripada di UTF-16.

Sebagian besar turun ke ini: perbaikan yang paling jelas adalah dari Boyer-Moore, atau varian dari itu. BM dan varian, bagaimanapun, benar-benar menginginkan antarmuka yang sama sekali berbeda.

Secara khusus, Boyer-Moore dan turunannya benar-benar berfungsi dalam dua langkah: pertama Anda melakukan inisialisasi. Ini membangun tabel berdasarkan murni pada string yang Anda cari untuk . Itu menciptakan tabel yang kemudian dapat Anda gunakan untuk mencari string itu sesering yang Anda inginkan.

Anda tentu bisa memasukkan ini ke antarmuka yang ada dengan memoisasi tabel dan menggunakannya untuk pencarian selanjutnya dari string target yang sama. Saya tidak berpikir itu akan cocok dengan maksud asli Sun untuk fungsi ini: bahwa itu adalah blok bangunan tingkat rendah yang tidak akan bergantung pada banyak hal lain. Menjadikannya fungsi level yang lebih tinggi yang bergantung pada sedikit infrastruktur lain akan berarti (antara lain) bahwa Anda harus memastikan bahwa tidak ada infrastruktur memoizing yang digunakannya yang dapat menggunakan pencarian substring.

Saya pikir hasil yang paling mungkin dari itu akan hanya menerapkan kembali sesuatu seperti ini (yaitu, rutin pencarian mandiri) dengan nama yang berbeda, dengan rutin tingkat yang lebih tinggi dengan nama yang ada. Semua hal dipertimbangkan, saya pikir mungkin akan lebih masuk akal untuk hanya menulis rutin tingkat tinggi baru dengan nama baru.

Alternatif yang jelas untuk itu adalah dengan menggunakan semacam versi memoizing yang dipreteli, yang (misalnya) menyimpan hanya satu tabel secara statis, dan menggunakannya kembali jika string target identik dengan yang digunakan untuk membuat tabel. . Itu tentu saja mungkin, tetapi akan jauh dari optimal untuk banyak kasus penggunaan. Menjadikannya thread-safe juga tidak akan sepele.

Kemungkinan lain adalah untuk mengekspos sifat dua langkah dari pencarian BM secara eksplisit. Saya ragu ada orang yang benar-benar akan menyukai ide itu - ia membawa biaya yang cukup tinggi (kecanggungan, kurangnya keakraban) dan sedikit atau tidak ada manfaat untuk banyak kasus penggunaan (sebagian besar studi pada subjek menunjukkan bahwa panjang tali rata-rata adalah sesuatu seperti 20 karakter).