Как эффективно формировать массив суффиксов?

Question

Я искал подход сделать массив суффиксов на Java.
Я нашел два варианта возможностей. Более того, я хочу гораздо глубже понять различия между этими вариантами.
Включает running time & space.

Код (суффиксы):

public static String[] suffixes(String s) 
{ 
int N = s.length(); 
String[] suffixes = new String[N]; 
for (int i = 0; i < N; i++) 
suffixes[i] = s.substring(i, N); 
return suffixes; 
} 

Код (StringBuilder суффиксы):

public static String[] suffixes(String s) 
{ 
int N = s.length(); 
StringBuilder sb = new StringBuilder(s); 
String[] suffixes = new String[N]; 
for (int i = 0; i < N; i++) 
suffixes[i] = sb.substring(i, N); 
return suffixes; 
} 

Вопрос:

• Как эффективно формировать А.Р. луч суффиксов?

Answer 1

Там не будет никакой заметной разницы между этими двумя способами это делать, что вы описываете: так String s в Java являются непреложный, новый объект будет создан для каждого суффикса. Создание подстроки из String против StringBuilder не даст вам большой разницы в производительности по сравнению с распределениями и копированием, необходимыми для создания новых строковых объектов.

Когда вы ищете суффикс, передавая конечный индекс не является необходимым: использовать перегрузку, которая принимает один int вместо:

for (int i = 0; i < N; i++) 
    suffixes[i] = s.substring(i); 

Answer 2

Единственное различие между вашими фрагментами кода использует строку или StringBuilder, также вы используете его только для извлечения подстроки.
subString() из StringBuilder делает

new String(offset + beginIndex, endIndex - beginIndex, value); 

и subString() из строки делает

new String(offset + beginIndex, endIndex - beginIndex, value); 

оба же и создает новую строку, так что привычка быть какая-то разница в производительности

Answer 3

Наиболее эффективным способом было бы для использования массива char. Однако это не будет столь значительным, как самая дорогостоящая операция по созданию объектов String.

String s = "foobarbaz"; 
char[] cha = s.toCharArray(); 
int length = cha.length; 
String[] suffixes = new String[length]; 
for (int i = 0; i < length; ++i) 
    suffixes[i] = new String(cha, i, length-i); 

Answer 4

Вы можете сделать это, что позволяет избежать метод подстроки,

public String[] suffix(String s) 
{ 
    String[] suffixes = new String[s.length()]; 
    String suffix = null; 
    for (int i = 0 ; i < s.length() ; i++) 
    { 
     suffix = suffix == null ? "" + s.charAt(i) : suffix + s.charAt(i); 
     suffixes[i] = suffix; 
    } 

    return suffixes; 
} 

не уверен, если это быстрее, хотя.

Answer 5

В конце вам всегда требуется строка n + 1 для выполнения этой задачи. Единственное, что можно оптимизировать, - это время создания этих объектов.

Вы можете создать строковое представление в виде массива символов и ленивый (по запросу) возврат суффиксов.

Вы можете использовать интерфейсы итерации и Iterator, чтобы сделать это:

public class StringSufixies implements Iterable<String> { 

    private final String input; 

    public StringSufixies(String input) { 
     this.input = input; 
    } 

    @Override 
    public Iterator<String> iterator() { 
     return new SuffixStringIterator(input); 
    } 

    private static class SuffixStringIterator implements Iterator<String> { 

     private final String input; 
     private final int size; 
     private int suffixId; 

     private SuffixStringIterator(String input) { 
      this.input = input; 
      this.size = input.length(); 
      this.suffixId = 1; 
     } 

     @Override 
     public boolean hasNext() { 
      return suffixId <= size; 
     } 

     @Override 
     public String next() { 
      return input.substring(0, suffixId++); //At this point we create new String 
     } 

     @Override 
     public void remove() { 
      //Add throw or other impl 
     } 

    } 

} 

Вы могли бы реализовать ключевые функции над массивом символов.

private static class SuffixCharIterator implements Iterator<String> { 

private final char[] charSequence; 
private final int size; 
private int suffixId = 0; 

private SuffixCharIterator(char[] charSequence) { 
    this.charSequence = charSequence; 
    this.size = charSequence.length; 
} 

@Override 
public boolean hasNext() { 
    return suffixId <= size; 
} 

@Override 
public String next() { 
    return new String(charSequence, 0, suffixId++); //At this point we create a new String 
} 

@Override 
public void remove() { 

} 

} 

Но ИМХО сложнее, и мы ничего не получаем.

Преимущество этого решения в том, что вы можете работать над результатами и решать, чтобы остановить, прежде чем все префиксы создаются.