Что я должен изменить для оптимизации метода замены?

Question

Я создаю метод, чтобы узнать, сколько раз 'RAV' находится внутри строки.Моя программа работает, но она должна быть быстрее, если строка содержит +10 000 символов.

Сначала я использовал String, затем StringBuilder, и это быстрее, но не достаточно.

public class E{

    private static int replace(String cad){
        StringBuilder sb = new StringBuilder(cad);
        int cont = 0;
        while (sb.indexOf("RAV") > -1 && cont < 50000) {
            sb.replace(sb.indexOf("RAV"), sb.indexOf("RAV") + 3, "");
            cont++;
        }
        return cont;
    }
    public static void main(String[] args) {
        String[] arr = new String[]{"RARAVV", "VAR", "RAVV"};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(replace(arr[i]));
        }
    }
}

Ожидаемый вывод

2
0
1

Answer 1

Вот мой взгляд на линейный алгоритм.Не самый общий или красивый код, но он показывает идею.Через строку выполняется только одно сканирование, и мы не смотрим назад или вперед, что дает линейное усилие по длине строки.

Для более длинных строк это должно быть значительно быстрее, чем «заменить»основанные алгоритмы.

public class Main {

    private static class StateFrame {
        int matched;
        StateFrame previous;
    }

    private static int count(String cad) {
        StateFrame state = new StateFrame();
        final int len = cad.length();
        int result = 0;
        for (int i = 0; i < len; i++) {
            final char ch = cad.charAt(i);
            if (ch == 'R') {
                if (state.matched == 0) {
                    state.matched = 1;
                } else {
                    StateFrame next = new StateFrame();
                    next.previous = state;
                    state = next;
                    state.matched = 1;
                }
            } else if (ch == 'A') {
                if (state.matched == 1) {
                    state.matched = 2;
                } else {
                    state.previous = null;
                    state.matched = 0;
                }
            } else if (ch == 'V') {
                if (state.matched == 2) {
                    result++;
                    if (state.previous == null) {
                        state.matched = 0;
                    } else {
                        state = state.previous;
                    }
                } else {
                    state.previous = null;
                    state.matched = 0;
                }
            } else {
                state.previous = null;
                state.matched = 0;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String[] arr = new String[] { "RARAVV", "VAR", "RAVV", "RRAVRXXXAV", "RARRAVAVV", "RRAVARAVV", "RRARAVVARAVV" };
        for (String anArr : arr) {
            System.out.printf("%s %d%n", anArr, count(anArr));
        }
    }
}

Это дает вывод

RARAVV 2
VAR 0
RAVV 1
RRAVRXXXAV 1
RARRAVAVV 3
RRAVARAVV 3
RRARAVVARAVV 4

Answer 2

private static int replace(String cad) {
    int originalLength = cad.length();
    for (;;) {
        String cad2 = cad.replace("RAV", "");
        if (cad2.length() == cad.length()) {
            break;
        }
        cad = cad2;
    }
    return (originalLength - cad.length()) / "RAV".length();
}

Прежде всего indexOf следует поместить в переменную, как три раза.String.replace может сделать несколько замен.Тогда сокращение выражения имеет другой порядок, но для «RAV» это не приведет к другому результату.

В приведенном выше примере вы можете проверить результат замены для cad2 == cad, но некоторые контролеры стиля предпочтут равно.Достаточно равенство длины.

И, конечно, число замен - это уменьшение длины / 3.

---

Поскольку фактическое измерение показало String.replace(String, String) медленным:

private static int replace(String cad) {
    // Could try to shorten string: cad = cad.replaceAll("[^RAV]+", "e");
    StringBuilder sb = new StringBuilder(cad);
    int pos0 = 0;
    for (;;) {
        int pos = sb.indexOf("RAV", pos0);
        if (pos == -1) {
            break;
        }
        sb.delete(pos, pos + 3);
        // Continue searching 2 chars before.
        pos0 = Math.max(0, pos - 2); // RA[RAV]V
    }
    return (cad.length() - sb.length()) / 3;
}

Спасибо @GPI за сравнительный анализ.

Answer 3

Сначала я использовал String, затем StringBuilder и он стал быстрее

Вы уверены?Какие тестовые случаи вы использовали?Для этого:

RAVRAVRAVRAVRAVRAVRAVRAVRAVRAV

Как вы думаете, StringBuilder быстрее String?Рассмотрим этот метод:

public static int replace(String cad, String pattern){
    String str = cad;
    do {
        str = str.replace(pattern, "");
    } while (str.contains(pattern));
    return (cad.length() - str.length()) / pattern.length();
}

Эта версия replace(), безусловно, намного быстрее , чем ваша в тестовых случаях, таких как вышеупомянутый String, и для большинства случайных тестовых случаев какон может сделать более 1 замены за 1 итерацию и не использовать счетчик.StringBuilder будет более эффективным и быстрым, когда вы будете иметь дело с такими случаями, как:

RARARARARARARARARARAVVVVVVVVVV

Answer 4

Если вы сделаете это с recursion, это будет намного быстрее.

public class E{

    private int cont;

    private static int replace(String cad){
        StringBuilder sb = new StringBuilder(cad);

        if(sb.indexOf("RAV") > -1){
            sb.replace(sb.indexOf("RAV"), sb.indexOf("RAV") + 3, "");
            cont++;
            return replace(sb.toString())}
        else{
            return cont; 
        }
    }

    public static void main(String[] args) {
        cont = 0;
        String[] arr = new String[]{"RARAVV", "VAR", "RAVV"};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(replace(arr[i]));
        }
    }
}