Câu hỏi Cách nhanh nhất để loại bỏ tất cả các ký tự không thể in từ một chuỗi Java


Cách nhanh nhất để loại bỏ tất cả các ký tự không thể in từ một String trong Java?

Cho đến nay tôi đã thử và đo trên chuỗi 138-byte, 131 ký tự:

  • Dây replaceAll() - - phương pháp chậm nhất
    • 517009 kết quả / giây
  • Biên dịch trước một Pattern, sau đó sử dụng Matcher replaceAll()
    • 637836 kết quả / giây
  • Sử dụng StringBuffer, lấy codepoints bằng cách sử dụng codepointAt() từng cái một và nối thêm vào StringBuffer
    • 711946 kết quả / giây
  • Sử dụng StringBuffer, lấy ký tự bằng cách sử dụng charAt() từng cái một và nối thêm vào StringBuffer
    • 1052964 kết quả / giây
  • Preallocate a char[] bộ đệm, lấy ký tự bằng cách sử dụng charAt() từng người một và điền vào bộ đệm này, sau đó chuyển đổi lại thành Chuỗi
    • 2022653 kết quả / giây
  • Preallocate 2 char[] bộ đệm - cũ và mới, nhận tất cả các ký tự cho Chuỗi hiện tại cùng một lúc bằng cách sử dụng getChars(), lặp qua bộ đệm cũ từng cái một và điền vào bộ đệm mới, sau đó chuyển đổi bộ đệm mới thành Chuỗi - phiên bản nhanh nhất của riêng tôi
    • 2502502 kết quả / giây
  • Nội dung tương tự với 2 bộ đệm - chỉ sử dụng byte[], getBytes() và chỉ định mã hóa là "utf-8"
    • 857485 kết quả / giây
  • Nội dung tương tự với 2 byte[] bộ đệm, nhưng chỉ định mã hóa làm hằng số Charset.forName("utf-8")
    • 791076 kết quả / giây
  • Nội dung tương tự với 2 byte[] bộ đệm, nhưng chỉ định mã hóa dưới dạng mã hóa cục bộ 1 byte (chỉ cần một điều lành mạnh để làm)
    • 370164 kết quả / giây

Thử tốt nhất của tôi là:

    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);

Bất kỳ suy nghĩ về làm thế nào để làm cho nó thậm chí còn nhanh hơn?

Điểm thưởng để trả lời câu hỏi rất lạ: tại sao sử dụng tên bộ ký tự "utf-8" trực tiếp mang lại hiệu suất tốt hơn so với sử dụng const tĩnh được phân bổ trước Charset.forName("utf-8")?

Cập nhật

  • Đề xuất từ ratchet freak mang lại ấn tượng 3105590 kết quả / giây hiệu suất, cải thiện + 24%!
  • Đề xuất từ Ed Staub sản lượng chưa được cải thiện - 3471017 kết quả / giây, tăng + 12% so với mức cao nhất trước đó.

Cập nhật 2

Tôi đã cố gắng hết mình để thu thập tất cả các giải pháp được đề xuất và các đột biến chéo của nó và xuất bản nó như là một khuôn khổ điểm chuẩn nhỏ tại github. Hiện tại nó có 17 thuật toán. Một trong số đó là "đặc biệt" - Voo1 thuật toán (được cung cấp bởi người dùng SO Voo) sử dụng các thủ thuật phản chiếu phức tạp, do đó đạt được tốc độ sao, nhưng nó làm rối loạn trạng thái của chuỗi JVM, do đó nó được đánh giá riêng biệt.

Bạn được quyền kiểm tra và chạy nó để xác định kết quả trên hộp của bạn. Đây là một bản tóm tắt các kết quả mà tôi có được. Đó là thông số kỹ thuật:

  • Sid Debian
  • Linux 2.6.39-2-amd64 (x86_64)
  • Java được cài đặt từ một gói sun-java6-jdk-6.24-1, JVM tự xác định là
    • Môi trường chạy thử Java (TM) SE (xây dựng 1.6.0_24-b07)
    • Java HotSpot (TM) Máy chủ 64-Bit VM (xây dựng 19.1-b02, chế độ hỗn hợp)

Các thuật toán khác nhau cho thấy kết quả cuối cùng khác nhau cho một tập hợp dữ liệu đầu vào khác nhau. Tôi đã chạy điểm chuẩn ở 3 chế độ:

Cùng một chuỗi

Chế độ này hoạt động trên cùng một chuỗi được cung cấp bởi StringSourcelớp như một hằng số. Cuộc thách là:

 Ops / s │ Thuật toán
───────────────────────────────
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 │ StringReplaceTất cả
  460 045 │ ArrayOfByteWindows1251

Ở dạng biểu đồ: Cùng một biểu đồ chuỗi đơn http://www.greycat.ru/img/os-chart-single.png

Nhiều chuỗi, 100% chuỗi chứa ký tự điều khiển

Nhà cung cấp chuỗi nguồn được tạo trước nhiều chuỗi ngẫu nhiên bằng cách sử dụng bộ ký tự (0..127) - do đó gần như tất cả các chuỗi chứa ít nhất một ký tự điều khiển. Các thuật toán nhận được chuỗi từ mảng được tạo trước này theo kiểu vòng tròn.

 Ops / s │ Thuật toán
───────────────────────────────
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 │ ChuỗiBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceTất cả

Ở dạng biểu đồ: Nhiều chuỗi, tập trung 100% http://www.greycat.ru/img/os-chart-multi100.png

Nhiều chuỗi, 1% chuỗi chứa ký tự điều khiển

Tương tự như trước, nhưng chỉ 1% chuỗi được tạo bằng ký tự điều khiển - 99% khác được tạo bằng cách sử dụng bộ ký tự [32..127], vì vậy chúng không thể chứa các ký tự điều khiển. Tải tổng hợp này đến gần nhất với ứng dụng thế giới thực của thuật toán này tại vị trí của tôi.

 Ops / s │ Thuật toán
───────────────────────────────
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 │ StringReplaceTất cả
  381 185 │ ArrayOfByteWindows1251

Ở dạng biểu đồ: Nhiều chuỗi, tập trung 1% http://www.greycat.ru/img/os-chart-multi1.png

Rất khó để tôi quyết định ai là người đưa ra câu trả lời hay nhất, nhưng với giải pháp tốt nhất thế giới thực được đưa ra / lấy cảm hứng từ Ed Staub, tôi đoán sẽ là công bằng khi đánh dấu câu trả lời của anh ấy. Cảm ơn tất cả những người đã tham gia vào việc này, đầu vào của bạn rất hữu ích và vô giá. Cảm thấy tự do để chạy bộ thử nghiệm trên hộp của bạn và đề xuất các giải pháp tốt hơn nữa (giải pháp làm việc JNI, bất kỳ ai?).

Tài liệu tham khảo


76
2017-08-23 13:10


gốc


"Câu hỏi này cho thấy nỗ lực nghiên cứu" - hmm ... vâng, vượt qua. +1 - Gustav Barkefors
StringBuilder sẽ nhanh hơn một chút so với StringBuffer vì nó không được đồng bộ hóa, tôi chỉ đề cập đến điều này vì bạn đã gắn thẻ mục này micro-optimization - feeling unwelcome
@ Jarrod Roberson: ok, vậy hãy làm cho tất cả các trường chỉ đọc cuối cùng và trích xuất s.length() ra khỏi for vòng lặp là tốt :-) - home
Một số ký tự bên dưới khoảng trắng có thể in được, ví dụ: \t và \n. Nhiều ký tự trên 127 không thể in được trong bộ ký tự của bạn. - Peter Lawrey
bạn đã bắt đầu bộ đệm chuỗi với khả năng s.length()? - ratchet freak


Các câu trả lời:


Nếu nó là hợp lý để nhúng phương pháp này trong một lớp học mà không được chia sẻ trên các chủ đề, sau đó bạn có thể tái sử dụng bộ đệm:

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);

v.v ...

Đây là một chiến thắng lớn - 20% hoặc hơn, khi tôi hiểu trường hợp tốt nhất hiện tại.

Nếu điều này là để được sử dụng trên các chuỗi có khả năng lớn và bộ nhớ "rò rỉ" là một mối quan tâm, một tài liệu tham khảo yếu có thể được sử dụng.


9
2017-08-23 19:32



Ý tưởng tuyệt vời! Cho đến nay, số lượng này lên tới 3471017 chuỗi mỗi giây - tức là cải thiện + 12% so với phiên bản tốt nhất trước đó. - GreyCat


sử dụng 1 mảng char có thể hoạt động tốt hơn một chút

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);

và tôi tránh các cuộc gọi lặp lại s.length();

một tối ưu hóa vi mô khác có thể hoạt động là

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



Cảm ơn! Phiên bản của bạn mang lại 3105590 chuỗi / giây - một cải tiến lớn! - GreyCat
newLen++;: những gì về việc sử dụng preincrement ++newLen;? - (++j trong vòng lặp là tốt). Có một cái nhìn ở đây: stackoverflow.com/questions/1546981/… - Thomas
Đang thêm final với thuật toán này và sử dụng oldChars[newLen++] (++newLen là lỗi - toàn bộ chuỗi sẽ bị tắt bởi 1!) mang lại hiệu suất không thể đo lường được (tức là tôi nhận được chênh lệch ± 2..3%, có thể so sánh với sự khác biệt của các lần chạy khác nhau) - GreyCat
@ xám Tôi đã thực hiện một phiên bản khác với một số tối ưu hóa khác - ratchet freak
Hmm! Đó là một ý tưởng tuyệt vời! 99,9% các chuỗi trong môi trường sản xuất của tôi sẽ không thực sự yêu cầu tước - tôi có thể cải thiện nó hơn nữa để loại bỏ ngay cả trước tiên char[] phân bổ và trả về String như là, nếu không có tước bỏ xảy ra. - GreyCat


Tôi đã đánh bại phương pháp tốt nhất hiện tại (giải pháp của freak với mảng preallocated) khoảng 30% theo các biện pháp của tôi. Làm sao? Bằng cách bán linh hồn của tôi.

Như tôi chắc chắn rằng tất cả mọi người đã theo dõi các cuộc thảo luận cho đến nay biết điều này vi phạm khá nhiều bất kỳ nguyên tắc lập trình cơ bản, nhưng oh tốt. Dù sao sau đây chỉ hoạt động nếu mảng ký tự được sử dụng của chuỗi không được chia sẻ giữa các chuỗi khác - nếu nó có bất kỳ ai phải gỡ lỗi, bạn sẽ có quyền quyết định giết bạn (không gọi đến chuỗi con) và sử dụng chuỗi ký tự này điều này sẽ làm việc như tôi không thấy lý do tại sao JVM sẽ thực hiện các chuỗi duy nhất đọc từ một nguồn bên ngoài). Mặc dù đừng quên đảm bảo rằng mã điểm chuẩn không làm điều đó - điều đó rất có thể và sẽ giúp giải pháp phản chiếu rõ ràng.

Dù sao ở đây chúng tôi đi:

    // 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;
    }

Đối với chuỗi thử nghiệm của tôi 3477148.18ops/s so với 2616120.89ops/s cho biến thể cũ. Tôi khá chắc chắn cách duy nhất để đánh bại đó có thể là viết nó trong C (có lẽ không phải) hoặc một số cách tiếp cận hoàn toàn khác nhau không ai đã nghĩ đến cho đến nay. Mặc dù tôi hoàn toàn không chắc liệu thời gian có ổn định trên các nền tảng khác nhau hay không - tạo ra kết quả đáng tin cậy trên hộp của tôi (Java7, Win7 x64) ít nhất.


9
2017-08-24 12:55



Cảm ơn các giải pháp, xin vui lòng kiểm tra cập nhật câu hỏi - Tôi đã xuất bản khuôn khổ thử nghiệm của tôi và thêm 3 kết quả chạy thử nghiệm cho 17 thuật toán. Thuật toán của bạn luôn ở trên cùng, nhưng nó thay đổi trạng thái bên trong của chuỗi Java, do đó phá vỡ hợp đồng "chuỗi bất biến" => nó sẽ khá khó để sử dụng nó trong ứng dụng thế giới thực. Kiểm tra khôn ngoan, vâng, đó là kết quả tốt nhất, nhưng tôi đoán tôi sẽ công bố nó như là một đề cử riêng biệt :) - GreyCat
@ GreyCat Yeah nó chắc chắn có một số dây lớn đính kèm và thành thật mà nói, tôi khá nhiều chỉ viết nó lên bởi vì tôi khá chắc chắn không có cách nào đáng chú ý để cải thiện giải pháp tốt nhất hiện tại của bạn hơn nữa. Có những tình huống mà tôi chắc chắn rằng nó sẽ hoạt động tốt (không có xâu chuỗi hoặc cuộc gọi thực tập trước khi tước nó), nhưng đó là vì kiến ​​thức về một phiên bản Hotspot hiện tại (tức là afaik nó sẽ không thực hiện chuỗi đọc từ IO - wouldn ' t đặc biệt hữu ích). Nó có thể hữu ích nếu người ta thực sự cần thêm x% đó, nhưng nếu không thì đường cơ sở để xem bạn có thể cải thiện bao nhiêu;) - Voo
Mặc dù tôi đã cố gắng thử một phiên bản JNI nếu tôi tìm thấy thời gian - không bao giờ sử dụng nó cho đến nay để có thể trở nên thú vị. Nhưng tôi khá chắc chắn nó sẽ chậm hơn vì các chi phí gọi cao hơn (dây là quá nhỏ) và thực tế là JIT không nên có một thời gian khó tối ưu hóa các chức năng. Chỉ cần không sử dụng new String()trong trường hợp chuỗi của bạn không bị thay đổi, nhưng tôi nghĩ bạn đã có nó. - Voo
Tôi đã cố gắng làm chính xác điều tương tự trong tinh khiết C - và, tốt, nó không thực sự hiển thị nhiều cải tiến so với phiên bản dựa trên sự phản chiếu của bạn. Phiên bản C chạy một cái gì đó như + 5..10% nhanh hơn, không thực sự tuyệt vời - Tôi nghĩ rằng nó sẽ có ít nhất là 1.5x-1.7x ... - GreyCat


Bạn có thể chia nhiệm vụ thành một số nhiệm vụ song song, tùy thuộc vào số lượng bộ xử lý.


2
2017-08-23 13:37



Yeah, tôi nghĩ về nó quá, nhưng nó sẽ không mang lại bất kỳ lợi ích hiệu suất trong tình hình của tôi - thuật toán tước này sẽ được gọi là trong hệ thống song song đã ồ ạt. - GreyCat
Và, bên cạnh đó, tôi có thể đoán rằng forking off một vài chủ đề để xử lý cho mỗi chuỗi 50-100 byte sẽ là một overkill rất lớn. - GreyCat
Có, đề đề cho mỗi chuỗi nhỏ không phải là ý tưởng tốt. Nhưng cân bằng tải có thể cải thiện hiệu suất. BTW, bạn đã thử nghiệm hiệu suất với StringBuilder thay vì StringBuffer có hiệu suất thiếu vì nó đã đồng bộ hóa. - umbr
Thiết lập sản xuất của tôi chạy một số quy trình riêng biệt và sử dụng càng nhiều CPU và lõi song song càng tốt, vì vậy tôi có thể tự do sử dụng StringBuilder ở khắp mọi nơi mà không có bất kỳ vấn đề gì cả. - GreyCat


IANA cấp thấp junkie hiệu suất java, nhưng có bạn đã thử unrolling vòng lặp chính của bạn? Dường như nó có thể cho phép một số CPU thực hiện kiểm tra song song.

Cũng thế, điều này có một số ý tưởng thú vị để tối ưu hóa.


1
2017-08-23 13:24



Tôi nghi ngờ rằng có thể thực hiện unrolling ở đây, vì có (a) phụ thuộc vào các bước sau của thuật toán trên các bước trước đó, (b) Tôi thậm chí chưa từng nghe thấy ai đang thực hiện việc bỏ vòng lặp thủ công trong Java để tạo ra bất kỳ kết quả xuất sắc nào; JIT thường làm một công việc tốt khi bỏ mọi thứ mà nó thấy phù hợp với nhiệm vụ. Cảm ơn gợi ý và liên kết, mặc dù :) - GreyCat


Tôi rất tự do và đã viết một chuẩn mực nhỏ cho các thuật toán khác nhau. Nó không hoàn hảo, nhưng tôi lấy tối thiểu 1000 lần chạy của một thuật toán đã cho 10000 lần so với một chuỗi ngẫu nhiên (mặc định là khoảng 32/200% không in được). Điều đó sẽ chăm sóc các công cụ như GC, khởi tạo và như vậy - không có quá nhiều chi phí mà bất kỳ thuật toán nào không nên có ít nhất một lần chạy mà không có nhiều trở ngại.

Không đặc biệt là tài liệu tốt, nhưng oh tốt. Ở đây chúng ta đi - Tôi bao gồm cả thuật toán của ratchet freak và phiên bản cơ bản. Tại thời điểm này, tôi ngẫu nhiên khởi tạo một chuỗi dài 200 ký tự với các ký tự phân bố đồng nhất trong phạm vi [0, 200).


1
2017-08-23 14:52



+1 cho nỗ lực này - nhưng bạn nên hỏi tôi - tôi đã có một bộ điểm chuẩn tương tự - đó là nơi tôi đã thử nghiệm các thuật toán của mình;) - GreyCat
@ GreyCat Vâng tôi có thể, nhưng chỉ cần ném rằng với nhau (ra khỏi anyways mã hiện có) có lẽ là nhanh hơn;) - Voo


tại sao sử dụng tên bộ ký tự "utf-8" trực tiếp mang lại hiệu suất tốt hơn so với sử dụng charset.forName tĩnh được phân bổ trước ("utf-8")?

Nếu bạn muốn nói String#getBytes("utf-8") v.v. Điều này không nên nhanh hơn - ngoại trừ một số bộ nhớ đệm tốt hơn - kể từ Charset.forName("utf-8")được sử dụng trong nội bộ, nếu bộ ký tự không được lưu trong bộ nhớ cache.

Một điều có thể là bạn đang sử dụng các bộ ký tự khác nhau (hoặc có thể một số mã của bạn không minh bạch) nhưng bộ ký tự được lưu trong bộ nhớ cache StringCoding không thay đổi.


0
2017-08-23 13:22