Java Trie Optimization

Question

Я тренировался с помощью структуры данных для практики (нет связанной с курсом работы) структуры данных trie. Этот класс используется для хранения подстрок строки. Для строки длиной n есть n(n+1)/2 подстроки. В частности, эта реализация trie сохраняет естественное упорядочение и более эффективна, чем TreeMap или TreeSet на случайных строках. Сохранение в памяти одного символа, а не всей строки сохраняется.

Я думаю, что для хранения подстрок суффикс-массив может быть лучшим способом, но я хотел убедиться, что этот класс trie достаточно оптимизирован для скорости, прежде чем запускать новый проект.

class Trie 
{ 
    final Trie my_parent; 
    final Trie[] my_children; 
    final char my_value; 

    public Trie(final Trie the_parent, final char the_value) 
    { 
     my_parent = the_parent; 
     my_value = the_value; 
     my_children = new Trie[26]; 
    } 

    public int insertIterative(final char[] the_text) 
    { 
     int number = 0; 
     Trie parent = this; 

     for(int ator = 0; ator < the_text.length; ator++) 
     { 
      final int key = the_text[ator] - 97; 
      Trie child = parent.my_children[key]; 

      if(child == null) 
      { 
       child = new Trie(parent, the_text[ator]); 
       parent.my_children[key] = child; 
       number++; 
      } 

      parent = child; 
     } 

     return number; 
    } 

    public String getString() 
    { 
     final StringBuilder builder = new StringBuilder(); 
     Trie parent = this; 

     while(parent.my_parent != null) 
     { 
      builder.append(parent.my_value); 
      parent = parent.my_parent; 
     } 

     return builder.reverse().toString(); 
    } 
} 

Answer 1

Смотрите мой комментарий выше, но несколько замечаний в любом случае:

Вы выделяете 26 ребенок пытается сразу же, независимо от того, используются ли они. Вы могли бы создать эти лениво (т. Е. Только при встрече с конкретной буквой).

Ваш код будет работать только для простых букв ASCII и не обрабатывает чужие символы, дефисы, апострофы или смешанный футляр. Это может помочь и ленивое распределение.

В вашей реализации используется объект Trie за char, а также некоторые пустые запасные части, поэтому, вероятно, будет довольно тяжело использовать память.

Это может лучше собирать результат в getString() в правильном порядке, а не добавлять, а затем реверсировать, но вам нужно сравнить это. Если вы отслеживаете глубину Trie, тогда вы можете выделить массив правильной длины, а не StringBuilder, но отслеживание глубины имеет свою собственную стоимость памяти.