Сравнение строк Java

Question

Я сравниваю подстроки в двух больших текстовых файлах.Очень просто, разбить токены на два контейнера токенов, сравнивая с 2 для циклов. Производительность катастрофическая! У кого-нибудь есть совет или идея, как улучшить производительность?

for (int s = 0; s < txtA.TokenContainer.size(); s++) {
    String strTxtA = txtA.getSubStr(s);
    strLengthA = txtA.getNumToken(s);

    if (strLengthA >= dp.getMinStrLength()) {
        int tokenFileB = 1;

        for (int t = 0; t < txtB.TokenContainer.size(); t++) {
            String strTxtB = txtB.getSubStr(t);
            strLengthB = txtB.getNumToken(t);

            if (strTxtA.equalsIgnoreCase(strTxtB)) {
                try {
                    subStrTemp = new SubStrTemp(
                        txtA.ID, txtB.ID, tokenFileA, tokenFileB,
                        (tokenFileA + strLengthA - 1), 
                        (tokenFileB + strLengthB - 1));

                    if (subStrContainer.contains(subStrTemp) == false) {
                        subStrContainer.addElement(subStrTemp);
                    }
                } catch (Exception ex) {
                    logger.error("error");
                }
            }
            tokenFileB += strLengthB;
        }
        tokenFileA += strLengthA;
    }
}

Обычно мой код читает две большие строки с помощью Java Tokonizer в контейнеры A и B. И затем пытаетсядля сравнения подстрок. Возможности подстрок, которые существуют в обеих строках для хранения в векторе.Но производительность ужасна, также не знаю, как ее решить с помощью HashMap.

Answer 1

Ваша основная проблема в том, что вы проходите все txtB для каждого токена в txtA.

Вы должны хранить информацию о токене из txtA (например, в HashMap ), а затем во втором цикле (но не во вложенном) вы сравниваете строки с существующей на карте.

---

По той же теме:

• частота с использованием java-программы
• Как считать слова в Java

Answer 2

Вы делаете соединение с вложенными циклами?Да, это O (n ^ 2).А как насчет создания хеш-соединения?То есть, создать карту из (в нижнем регистре) strText до t и выполнять поиск по этой карте, а не перебирать контейнер токенов?

Answer 3

A сказал, что это проблема сложности, и ваш алгоритм работает в O (n ^ 2) вместо O (n) с использованием хеша.

Для улучшений второго порядка попробуйте меньше вызывать функции, например, вы можете получить размер один раз

sizeB = txtB.TokenContainer.size ();

Зависит отразмер, вы можете вызвать контейнер один раз, чтобы получить массив строк для сохранения getStr ....

Roni

Answer 4

Поместите токены файла A в трехуровневую структуру данных.Затем при токенизации файла B вы можете довольно быстро проверить, есть ли эти токены в трие.Несколько комментариев кода помогут.