Java Trie Optimization - PullRequest
Новая
       16

Java Trie Optimization

1 голос
/ 29 февраля 2012

Я играл с 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();
    }
}

1 Ответ

5 голосов
/ 29 февраля 2012

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

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

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

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

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

...