Есть ли способ перевернуть строку быстрее, чем O (n)?

Question

У меня есть следующий код, который выполняется более 5 секунд с аргументом -Xmx<1024M>.

Я знаю, что for l oop занимает время O(q), а также reverse() и toString() занимают O(n) время каждый.

Есть ли способ перевернуть строку менее чем за O(n) время? Или что-то еще замедляет код? Любая помощь будет приветствоваться!

class Main {
  public static void main(String[] args){
    String s = "a";
    String qa = "200000";
    int q = Integer.parseInt(qa);
    String[] t = new String[q];
    for(int i = 0; i < q; i++) {
      if(i%2==0) {t[i] = "2 1 x";}
      if(i%2==1) {t[i] = "1";}
      if(t[i].toCharArray()[0] == '1') {
        StringBuilder rev = new StringBuilder(s).reverse();
        s = rev.toString();
      } else {
        char letter = t[i].toCharArray()[4];
        if(t[i].toCharArray()[2] == '1') {
          s = letter + s;
        } else {
          s = s + letter;
        }
      }
    }
    System.out.println(s);
  }
}

Answer 1

Независимо от того, что он должен делать (я понятия не имею), я обнаружил следующие проблемы:

• Несколько мгновений StringBuilder в каждой итерации.
• Строка объединение с использованием оператора +.
• Повторное использование Sring::toCharArray (см. 2-е решение)

Вы достигнете более быстрого результата, используя непосредственно только один экземпляр StringBuilder:

String s = "a";
String qa = "200000";
int q = Integer.parseInt(qa);
String[] t = new String[q];
StringBuilder sb = new StringBuilder(s);       // Instantiate before the loop
for (int i = 0; i < q; i++) {
    if(i%2==0) {t[i] = "2 1 x";}
    if(i%2==1) {t[i] = "1";}
    if(t[i].toCharArray()[0] == '1') {
        sb.reverse();                          // all you did here is just reversing 's'
    } else {
        char letter = t[i].toCharArray()[4];
        if(t[i].toCharArray()[2] == '1') {
            sb.insert(0, letter);              // prepend a letter
        } else {
            sb.append(letter);                 // append a letter
        }
    }
}

Другое дело, что вы несколько раз определяете строку, такую ​​как t[i] = "2 1 x";, а затем сравниваете с t[i].toCharArray()[0]. Предопределение этих неизменяемых значений и использование char[][] также должно помочь:

String s = "a";
String qa = "200000";
int q = Integer.parseInt(qa);
char[][] t = new char[q][];                    // char[][] instead of String[]
char[] char21x = new char[]{'2', '1', 'x'};    // predefined array
char[] char1 = new char[]{'1'};                // another predefined array
StringBuilder sb = new StringBuilder(s);       // Instantiate before the loop
for (int i = 0; i < q; i++) {
    if(i%2==0) {t[i] = char21x;}     // first reuse
    if(i%2==1) {t[i] = char1;}       // second reuse
    if(t[i][0] == '1') {             // instead of String::toCharArray, mind the indices
        sb.reverse();                // all you did here is just reversing 's'
    } else {
        char letter = t[i][2];       // instead of String::toCharArray, mind the indices
        if(t[i][1] == '1') {
            sb.insert(0, letter);    // prepend a letter
        } else {
            sb.append(letter);       // append a letter
        }
    }
}

Редактировать: Я протестировал решение самым простым способом, используя разницу System.currentTimeMillis() на Мой ноутбук:

• Исходное решение: 7.658, 6.899 и 7.046 секунд
• 2-е решение: 3.288, 3.691 и 3.158 секунд
• 3-е решение: 2.717, 2.966 и 2.717 секунд

Вывод: Я не вижу способа улучшить сам алгоритм с точки зрения вычислений сложность, однако, использование правильных способов обработки строк помогает сократить временную сложность в 2-3 раза (в моем случае).

Общие рекомендации : что вы можете создать и определить до l oop, сделайте это до l oop.

Answer 2

Множество ненужных операций замедляют эту программу. Вот намного более быстрая (и более простая для понимания) реализация той же программы.

class Faster {
    public static void main(String[] args) {

        String hundredXs = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";

        for (int i = 0; i < 500; i++)
            System.out.print(hundredXs);

        System.out.print("a");

        for (int i = 0; i < 500; i++)
            System.out.print(hundredXs);

        System.out.println();
    }
}