Pertanyaan Cara tercepat untuk menghapus semua karakter yang tidak dapat dicetak dari Java String


Apa cara tercepat untuk menghapus semua karakter yang tidak dapat dicetak dari a String di Jawa?

Sejauh ini saya sudah mencoba dan mengukur String 138-byte, 131-karakter:

  • String replaceAll() - metode paling lambat
    • 517009 hasil / detik
  • Precompile a Pattern, lalu gunakan Matcher's replaceAll()
    • 637836 hasil / detik
  • Gunakan StringBuffer, dapatkan codepoint menggunakan codepointAt() satu-per-satu dan tambahkan ke StringBuffer
    • 711946 hasil / detik
  • Gunakan StringBuffer, gunakan chars charAt() satu-per-satu dan tambahkan ke StringBuffer
    • 1052964 hasil / detik
  • Preallocate a char[] penyangga, gunakan karakter charAt() satu per satu dan isi buffer ini, lalu konversikan kembali ke String
    • Hasil 2022653 / detik
  • Preallocate 2 char[] buffer - lama dan baru, dapatkan semua karakter untuk String yang ada sekaligus gunakan getChars(), ulangi buffer lama satu per satu dan isi buffer baru, lalu konversikan buffer baru ke String - versi tercepat saya sendiri
    • 2502502 hasil / detik
  • Barang yang sama dengan 2 buffer - hanya menggunakan byte[], getBytes() dan menentukan encoding sebagai "utf-8"
    • 857485 hasil / detik
  • Barang yang sama dengan 2 byte[] buffer, tetapi menentukan encoding sebagai konstanta Charset.forName("utf-8")
    • 791076 hasil / detik
  • Barang yang sama dengan 2 byte[] buffer, tetapi menentukan encoding sebagai pengkodean lokal 1-byte (hampir tidak hal yang bijaksana untuk dilakukan)
    • 370164 hasil / detik

Usaha terbaik saya adalah sebagai berikut:

    char[] oldChars = new char[s.length()];
    s.getChars(0, s.length(), oldChars, 0);
    char[] newChars = new char[s.length()];
    int newLen = 0;
    for (int j = 0; j < s.length(); j++) {
        char ch = oldChars[j];
        if (ch >= ' ') {
            newChars[newLen] = ch;
            newLen++;
        }
    }
    s = new String(newChars, 0, newLen);

Setiap pemikiran tentang cara membuatnya lebih cepat?

Poin bonus untuk menjawab pertanyaan yang sangat aneh: mengapa menggunakan nama charset "utf-8" secara langsung menghasilkan kinerja yang lebih baik daripada menggunakan konstanta statis pra-alokasi Charset.forName("utf-8")?

Memperbarui

  • Saran dari ratchet freak menghasilkan hasil yang luar biasa 3105590 / kinerja detik, peningkatan + 24%!
  • Saran dari Ed Staub menghasilkan peningkatan lain - 3471017 hasil / dtk, + 12% dari yang terbaik sebelumnya.

Perbarui 2

Saya sudah berusaha sebaik mungkin untuk mengumpulkan semua solusi yang diusulkan dan mutasi silangnya dan mempublikasikannya sebagai kerangka tolok ukur kecil di github. Saat ini olahraga 17 algoritma. Salah satunya adalah "khusus" - Voo1 algoritma (disediakan oleh pengguna SO Voo) menggunakan trik-trik refleksi yang rumit sehingga mencapai kecepatan bintang, tetapi mengacaukan status string JVM ', jadi itu secara terpisah.

Anda dipersilakan untuk memeriksanya dan menjalankannya untuk menentukan hasil di kotak Anda. Berikut ini ringkasan hasil yang saya miliki. Itu spesifikasi:

  • Sid Debian
  • Linux 2.6.39-2-amd64 (x86_64)
  • Java diinstal dari sebuah paket sun-java6-jdk-6.24-1, JVM mengidentifikasi dirinya sebagai
    • Java (TM) SE Runtime Environment (build 1.6.0_24-b07)
    • Java HotSpot (TM) Server 64-Bit VM (build 19.1-b02, mode campuran)

Algoritma yang berbeda menunjukkan hasil yang berbeda pada akhirnya dengan memberikan satu set data input yang berbeda. Saya telah menjalankan patokan dalam 3 mode:

String tunggal yang sama

Mode ini berfungsi pada string tunggal yang sama yang disediakan oleh StringSourcekelas sebagai konstanta. Pertarungannya adalah:

 Ops / s │ Algoritma
──────────┼──────────────────────────────
6 535 947 │ Voo1
──────────┼──────────────────────────────
5 350 454 │ RatchetFreak2EdStaub1GreyCat1
5 249 343 │ EdStaub1
5 002 501 │ EdStaub1GreyCat1
4 859 086 │ ArrayOfCharFromStringCharAt
4 295 532 │ RatchetFreak1
4 045 307 │ ArrayOfCharFromArrayOfChar
2 790 178 │ RatchetFreak2EdStaub1GreyCat2
2 583 311 │ RatchetFreak2
1 274 859 │ StringBuilderChar
1 138 174 │ StringBuilderCodePoint
  994 727 │ ArrayOfByteUTF8String
  918 611 │ ArrayOfByteUTF8Const
  756 086 │ MatcherReplace
  598 945 │ StringReplaceAll
  460 045 │ ArrayOfByteWindows1251

Dalam bentuk grafik: Tangga tali tunggal yang sama http://www.greycat.ru/img/os-chart-single.png

Beberapa string, 100% string mengandung karakter kontrol

Penyedia string sumber banyak dihasilkan string acak menggunakan (0,127) set karakter - sehingga hampir semua string mengandung setidaknya satu karakter kontrol. Algoritma menerima string dari array pra-hasil dalam mode round-robin.

 Ops / s │ Algoritma
──────────┼──────────────────────────────
2 123 142 │ Voo1
──────────┼──────────────────────────────
1 782 214 │ EdStaub1
1 776 199 │ EdStaub1GreyCat1
1 694 628 │ ArrayOfCharFromStringCharAt
1 481 481 │ ArrayOfCharFromArrayOfChar
1 460 067 │ RatchetFreak2EdStaub1GreyCat1
1 438 435 │ RatchetFreak2EdStaub1GreyCat2
1 366 494 │ RatchetFreak2
1 349 710 │ RatchetFreak1
  893 176 │ ArrayOfByteUTF8String
  817 127 │ ArrayOfByteUTF8Const
  778 089 │ StringBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceAll

Dalam bentuk grafik: Beberapa string, konsentrasi 100% http://www.greycat.ru/img/os-chart-multi100.png

Beberapa string, 1% string mengandung karakter kontrol

Sama seperti sebelumnya, tetapi hanya 1% string yang dihasilkan dengan karakter kontrol - 99% lainnya dihasilkan dengan menggunakan set karakter [32..127], sehingga tidak dapat memuat karakter kontrol sama sekali. Beban sintetis ini datang paling dekat ke aplikasi dunia nyata dari algoritma ini di tempat saya.

 Ops / s │ Algoritma
──────────┼──────────────────────────────
3 711 952 │ Voo1
──────────┼──────────────────────────────
2 851 440 │ EdStaub1GreyCat1
2 455 796 │ EdStaub1
2 426 007 │ ArrayOfCharFromStringCharAt
2 347 969 │ RatchetFreak2EdStaub1GreyCat2
2 242 152 │ RatchetFreak1
2 171 553 │ ArrayOfCharFromArrayOfChar
1 922 707 │ RatchetFreak2EdStaub1GreyCat1
1 857 010 │ RatchetFreak2
1 023 751 │ ArrayOfByteUTF8String
  939 055 │ StringBuilderChar
  907 194 │ ArrayOfByteUTF8Const
  841 963 │ StringBuilderCodePoint
  606 465 │ MatcherReplace
  501 555 │ StringReplaceAll
  381 185 │ ArrayOfByteWindows1251

Dalam bentuk grafik: Beberapa string, konsentrasi 1% http://www.greycat.ru/img/os-chart-multi1.png

Sangat sulit bagi saya untuk memutuskan siapa yang memberikan jawaban terbaik, tetapi mengingat solusi aplikasi dunia nyata diberikan / diinspirasi oleh Ed Staub, saya kira itu akan adil untuk menandai jawabannya. Terima kasih untuk semua yang ikut serta dalam hal ini, masukan Anda sangat membantu dan tak ternilai. Jangan ragu untuk menjalankan rangkaian uji coba di kotak Anda dan mengusulkan solusi yang lebih baik (bekerja dengan solusi JNI, siapa pun?).

Referensi


76
2017-08-23 13:10


asal


Jawaban:


Jika masuk akal untuk menanamkan metode ini di kelas yang tidak dibagikan antar-utas, Anda dapat menggunakan kembali buffer:

char [] oldChars = new char[5];

String stripControlChars(String s)
{
    final int inputLen = s.length();
    if ( oldChars.length < inputLen )
    {
        oldChars = new char[inputLen];
    }
    s.getChars(0, inputLen, oldChars, 0);

dll ...

Ini adalah kemenangan besar - 20% atau lebih, karena saya memahami kasus terbaik saat ini.

Jika ini digunakan pada string besar yang berpotensi dan "kebocoran" memori menjadi perhatian, referensi lemah dapat digunakan.


9
2017-08-23 19:32



menggunakan 1 array char bisa bekerja sedikit lebih baik

int length = s.length();
char[] oldChars = new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

dan saya menghindari panggilan berulang s.length();

pengoptimalan mikro lain yang mungkin berhasil

int length = s.length();
char[] oldChars = new char[length+1];
s.getChars(0, length, oldChars, 0);
oldChars[length]='\0';//avoiding explicit bound check in while
int newLen=-1;
while(oldChars[++newLen]>=' ');//find first non-printable,
                       // if there are none it ends on the null char I appended
for (int  j = newLen; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;//the while avoids repeated overwriting here when newLen==j
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

24
2017-08-23 13:20



Yah saya telah mengalahkan metode terbaik saat ini (solusi aneh dengan array yang telah dialokasikan sebelumnya) sekitar 30% menurut ukuran saya. Bagaimana? Dengan menjual jiwaku.

Seperti yang saya yakin semua orang yang telah mengikuti diskusi sejauh ini tahu ini melanggar hampir semua prinsip pemrograman dasar, tapi oh well. Anyways berikut hanya berfungsi jika karakter yang digunakan array string tidak dibagi antara string lain - jika tidak siapa pun yang harus debug ini akan memiliki hak setiap memutuskan untuk membunuh Anda (tanpa panggilan ke substring () dan menggunakan ini pada string literal ini harus bekerja karena saya tidak melihat mengapa JVM akan magang string unik yang dibaca dari sumber luar). Meskipun jangan lupa untuk memastikan kode patokan tidak melakukannya - itu sangat mungkin dan akan membantu solusi refleksi jelas.

Ngomong-ngomong di sini kita pergi:

    // Has to be done only once - so cache those! Prohibitively expensive otherwise
    private Field value;
    private Field offset;
    private Field count;
    private Field hash;
    {
        try {
            value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            offset = String.class.getDeclaredField("offset");
            offset.setAccessible(true);
            count = String.class.getDeclaredField("count");
            count.setAccessible(true);
            hash = String.class.getDeclaredField("hash");
            hash.setAccessible(true);               
        }
        catch (NoSuchFieldException e) {
            throw new RuntimeException();
        }

    }

    @Override
    public String strip(final String old) {
        final int length = old.length();
        char[] chars = null;
        int off = 0;
        try {
            chars = (char[]) value.get(old);
            off = offset.getInt(old);
        }
        catch(IllegalArgumentException e) {
            throw new RuntimeException(e);
        }
        catch(IllegalAccessException e) {
            throw new RuntimeException(e);
        }
        int newLen = off;
        for(int j = off; j < off + length; j++) {
            final char ch = chars[j];
            if (ch >= ' ') {
                chars[newLen] = ch;
                newLen++;
            }
        }
        if (newLen - off != length) {
            // We changed the internal state of the string, so at least
            // be friendly enough to correct it.
            try {
                count.setInt(old, newLen - off);
                // Have to recompute hash later on
                hash.setInt(old, 0);
            }
            catch(IllegalArgumentException e) {
                e.printStackTrace();
            }
            catch(IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        // Well we have to return something
        return old;
    }

Untuk teststring saya yang didapat 3477148.18ops/s vs. 2616120.89ops/s untuk varian lama. Saya yakin satu-satunya cara untuk mengalahkan itu adalah dengan menuliskannya di C (mungkin tidak juga) atau pendekatan yang sama sekali berbeda yang belum pernah dipikirkan oleh banyak orang. Meskipun saya benar-benar tidak yakin jika waktu stabil di berbagai platform - menghasilkan hasil yang dapat diandalkan di kotak saya (Java7, Win7 x64) setidaknya.


9
2017-08-24 12:55



Anda dapat membagi tugas menjadi beberapa sub-tugas paralel, tergantung dari kuantitas prosesor.


2
2017-08-23 13:37



IANA tingkat rendah junkie kinerja java, tetapi apakah Anda sudah mencoba membuka gulungan lingkaran utama Anda? Tampaknya itu bisa memungkinkan beberapa CPU untuk melakukan pemeriksaan secara paralel.

Juga, ini memiliki beberapa ide menyenangkan untuk pengoptimalan.


1
2017-08-23 13:24



Saya sangat bebas dan menulis patokan kecil untuk algoritme yang berbeda. Ini tidak sempurna, tapi saya mengambil minimal 1000 berjalan dari algoritma yang diberikan 10.000 kali melalui string acak (dengan sekitar 32/200% non printables secara default). Yang harus mengurus hal-hal seperti GC, inisialisasi dan sebagainya - tidak ada begitu banyak overhead sehingga algoritma apa pun seharusnya tidak memiliki setidaknya satu run tanpa banyak halangan.

Tidak terdokumentasi dengan baik, tapi oh well. Kita mulai - Saya memasukkan kedua algoritma ratchet freak dan versi dasar. Saat ini saya secara acak menginisialisasi string panjang 200 chars dengan karakter seragam didistribusikan dalam kisaran [0, 200).


1
2017-08-23 14:52



mengapa menggunakan "utf-8" nama charset secara langsung menghasilkan kinerja yang lebih baik daripada menggunakan konstanta statis pra-dialokasikan Charset.forName ("utf-8")?

Jika yang kamu maksud String#getBytes("utf-8") dll. Ini seharusnya tidak lebih cepat - kecuali untuk beberapa caching yang lebih baik - sejak Charset.forName("utf-8")digunakan secara internal, jika charset tidak di-cache.

Satu hal yang mungkin adalah Anda menggunakan charset yang berbeda (atau mungkin beberapa kode Anda tidak transparan) tetapi charset di-cache dalam StringCoding tidak berubah.


0
2017-08-23 13:22