5
\$\begingroup\$

I have a huge file (1Gb) with English sentences and I need to filter only those containing the Alice word.

Actual tests could be more complex, e.g. matching a verb by its wordforms (go, goes, gone, went, going).

To solve the task I have designed a method, which feeds English word as it is ready to a consumer and if test returns back positive the method returns immediately.

I have improved performance twice in comparison with storing words in a list first and matching them afterwards. Still I have the following benchmarks:

  • read: 1.6s / 100MB;
  • process: 1.5s / 100MB.

Could this code be improved further:

import java.util.function.Function;

public class ExtractEnglishWordsAndTest {
    public static boolean extractEnglishWordsAndTest(String text, Function<String, Boolean> consumer) {
        if (text == null || text.isEmpty()) {
            return false;
        }

        char[] buf = new char[text.length()];
        int bufIndex = -1;

        boolean isEnglishPiece = isEnglishLetterOrHyphen(text.charAt(0));

        for (char ch : text.toCharArray()) {
            boolean isEnglishLetter = isEnglishLetterOrHyphen(ch);

            if (isEnglishPiece && !isEnglishLetter || !isEnglishPiece && isEnglishLetter) {
                if (isEnglishPiece) {
                    if (consumer.apply(new String(buf, 0, bufIndex + 1))) {
                        return true;
                    }
                }

                isEnglishPiece = !isEnglishPiece;

                bufIndex = -1;
            }

            bufIndex++;
            buf[bufIndex] = ch;
        }

        if (isEnglishPiece) {
            if (consumer.apply(new String(buf, 0, bufIndex + 1))) {
                return true;
            }
        }

        return false;
    }

    public static boolean isEnglishLetterOrHyphen(char ch) {
        return ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch == '-';
    }

    public static void main(String[] args) {
        // could be used for just splitting
        ExtractEnglishWordsAndTest.extractEnglishWordsAndTest("Some key-phrases that may hint to you " +
                "that the question is better suited for Code-Review " +
                "are like the following:", (word) -> {
            System.out.print(word + " ");
            return false;
        });

        System.out.println();

        System.out.println("test: " + ExtractEnglishWordsAndTest.extractEnglishWordsAndTest("In another moment down went Alice after it, " +
                "never once considering how in the world " +
                "she was to get out again.", (word) -> word.equals("Alice")));

        System.out.println("test: " + ExtractEnglishWordsAndTest.extractEnglishWordsAndTest("Presently she began again.",
                (word) -> word.equals("Alice")));
    }
}

Output:

Some key-phrases that may hint to you that the question is better suited for Code-Review are like the following

test: true

test: false

\$\endgroup\$
3
\$\begingroup\$

The logic of word extraction seems convoluted. Consider two loops instead, along the lines of

    int text_length = text.length();
    int i = 0;
    while (true) {
        while ((i < text_length) && !isEnglishLetterOrHyphen(text.charAt(i))) {
            i++;
        }

        int wordStart = i;
        while ((i < text_length) && isEnglishLetterOrHyphen(text.charAt(i))) {
            i++;
        }

        if (consumer.apply(text.substring(wordStart, i))) {
            return true;
        }
    }

BTW,

    isEnglishPiece && !isEnglishLetter || !isEnglishPiece && isEnglishLetter

is a long (and unclear) way to say

    isEnglishPiece != isEnglishLetter
\$\endgroup\$
0
2
\$\begingroup\$

The algorithm might be improved in two directions.

  1. If there are character repetitions in the keyword, it may be faster to jump by the length of the keyword and check the read text under that index for all the characters in the current set. Thus there's a chance a percentage of text will be skipped.

KEYWORD: Alice -> 5 different chars -> normal search

KEYWORD: monochrome -> length: 10, charSet: [m, o, n, c, h, r, e] 7 chars

In the latter the ration is 7/10, so you can expect a rough gain in speed of 30% if you jump the searched text by 10 positions and first check it before checking for the whole word. If the word appears separated by space, that's another direction to expand. The effective algorithm switch ratio is a matter of calculation and/or testing.

  1. If the search will be repeated for a text, you may think of an index or a few of them. It might include characters not present in the sentence. Checking against it/them first might bring gain.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.