Самый быстрый способ сравнения строк (буквенный и числовой)

Question

У меня проблема с производительностью, связанная со сравнением строк (в Java).

Я работаю над проектом, который должен отсортировать огромный список (TableViewer в Eclipse). В любом случае, я определил узкое место в вызове compareTo () для сравниваемой строки.

Есть ли способ оптимизировать производительность сравнения строк? Я искал и гуглил безрезультатно ...

Поскольку проект строго ограничен средой Win32, я подумал, что, возможно, можно будет воспользоваться этим ...

Любые предложения будут с благодарностью.

РЕДАКТИРОВАТЬ: Я забыл упомянуть, что мне нужно как числовое сравнение, так и буквальное сравнение строк.

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

EDIT3: Я знаю, что многие из вас были обеспокоены попыткой try () - catch (). На самом деле это не так важно, потому что даже если я удаляю этот код и выполняю только блок catch (одиночный compareTo ()), он все равно выполняется практически с той же скоростью, что и исходный код. Однако, если я закомментирую CompareTo () также; оставляя мне только накладные расходы на функцию сравнения (получение меток и т. д.), это молниеносно. Поэтому мне все еще нужен лучший способ сравнения строк. Либо с помощью кеширования, либо с помощью какой-то другой магии.

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

РАЗЪЯСНЕНИЯ:

Функция сравнения реализована как часть платформы TableViewer для выполнения операций сортировки, что означает, что я не реализую конкретный алгоритм сортировки, а реализован SWT / JFace. Я только реализую функцию сравнения.

Еще более интересным является тот факт, что код для сортировки парных чисел на быстрее , чем сравнение строк. Сортировать столбцы только с числами быстрее, чем с реальными буквенными строками ... Что приводит меня к выводу, что в методе compareTo () происходит что-то подозрительное ...

Вот ядро ​​функции:

// e1Label and e2Label is Strings to be compared
//

// Be smart about the comparison and use non-lexical comparison if
// possible (i.e. if both strings are actually numbers...)
//
// Warning: This is only "semi-smart" as the sorting might get "a bit"
// messed up if some of the values in a column can be parsed as
// doubles while others can not...
//
try {
    // Try using numeric (double) comparison of label values
    //
    double e1_double = Double.parseDouble(e1Label);
    double e2_double = Double.parseDouble(e2Label);
    rc = Double.compare(e1_double, e2_double);
} catch (NumberFormatException e) {
    // Use lexical comparison if double comparison is not possible
    //
    rc = e1Label.compareToIgnoreCase(e2Label);
}

Answer 1

Если у вас есть знания о вашем String контенте, вы можете предварительно рассчитать и сохранить дополнительную информацию, чтобы ускорить сравнение. Например, предположим, что ваши String s содержат только заглавные буквы A-Z. Вы можете присвоить звание String на основе, скажем, первых 3 букв; например,

• AAA: = 1
• AAB: = 2
• ...
• ABA: = 27

Тогда вы могли бы ускорить ваш compareTo, сначала сравнив каждый ранг String (быстрое сравнение на основе int), а затем выполнив полное String сравнение, если ранги были равны.

Answer 2

Несмотря на то, что узким местом является функция compareTo (), оно, вероятно, выделяется в профилировщике, поскольку именно эта функция вызывается чаще всего в цикле.

Может быть также полезно знать, как именно работает ваша процедура сортировки. Возможно, вам лучше изменить алгоритм сортировки, так как там будет гораздо больше скорости.

Answer 3

Это почти наверняка исключения, которые замедляют сравнение. Создание и перехват исключения является дорогостоящей операцией, и вы получаете исключение с каждым нечисловым значением ячейки.

Попробуйте сначала использовать регулярное выражение, чтобы проверить, является ли значение числовым, а если нет, не пытаться его проанализировать.

private static final Pattern numberPattern = Pattern.compile("[-+0-9.e]+");

// ...

// e1Label and e2Label is Strings to be compared
//

// Be smart about the comparison and use non-lexical comparison if
// possible (i.e. if both strings are actually numbers...)
//
// Warning: This is only "semi-smart" as the sorting might get "a bit"
// messed up if some of the values in a column can be parsed as
// doubles while others can not...
//
if (numberPattern.matches(e1Label) && numberPattern.matches(e2Label)) {
    try {
        // Try using numeric (double) comparison of label values
        //
        double e1_double = Double.parseDouble(e1Label);
        double e2_double = Double.parseDouble(e2Label);
        rc = Double.compare(e1_double, e2_double);
    } catch (NumberFormatException e) {
        // Use lexical comparison if double comparison is not possible
        //
        rc = e1Label.compareToIgnoreCase(e2Label);
    }
} else {
    rc = e1Label.compareToIgnoreCase(e2Label);
}

Answer 4

Не храните значения как объекты String. Создайте свою собственную обертку, которая вызывает Double.parseDouble только один раз для каждой строки. Кэшируйте ответ (либо значение, либо исключение). Вероятно, он также может кэшировать нечувствительную к регистру версию строки.

Answer 5

Я действительно сомневаюсь, что вы сможете ускорить String.compareTo (). Решение, вероятно, заключается в том, чтобы реже вызывать CompareTo (). Но невозможно сказать вам, как это сделать, не зная больше о вашем алгоритме.

Answer 6

Даже если вы можете выжать немного больше производительности из вашего CompareTo (), я думаю, что главная проблема - это размер списка. Даже если, гипотетически, сегодня вы можете уменьшить задержку сортировки до приемлемого уровня (1 секунда?), Что если в следующем году приложению потребуется отобразить список, который в два раза больше? Алгоритмы сортировки O (n log n), поэтому удвоение размера списка сделает сортировку значительно медленнее.

Для надежного решения посмотрите виртуальные таблицы (используя атрибут SWT.VIRTUAL). Затем вы можете реализовать базовый поставщик данных, который не должен выполнять полную сортировку заранее. Как именно вы это реализуете, будет зависеть от того, откуда поступают ваши данные. Если это происходит из базы данных, вы можете рассмотреть возможность размещения индексов для всех сортируемых полей. Если нет способа сделать это, есть другие стратегии, которые вы можете использовать, например, если у вас есть какой-то быстрый метод для разделения таблицы на куски (например, строки, начинающиеся с «A», строки, начинающиеся с «B» и т. Д.), То вы можно начать с простого извлечения строк в первом чанке, их сортировки и отображения, поскольку пользователь всегда начинается с верхней части таблицы. Сортировка последующих кусков может продолжаться в фоновом потоке.

Answer 7

Почему бы не попробовать три?

http://algs4.cs.princeton.edu/52trie/

http://en.wikipedia.org/wiki/Radix_tree

Как пишет Роберт Седжвик: «Предложение H. Среднее число узлов, проверенных на предмет отсутствия поиска в дереве, построенном из N случайных ключей в алфавите с размером R, равно ~ logR N.» [Седжвик, Роберт; Уэйн, Кевин (2011-02-21). Алгоритмы (4-е издание) (Kindle Locations 12674-12676). Пирсон Образование (США). Kindle Edition.]

Answer 8

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

public class Item implements Comparable<Item> {
    private final String s;
    private final double d;
    private final boolean numeric;

    public Item(String s) {
        double tmpD;
        boolean tmpNumeric;

        try {
            // Do the work of parsing / catching exceptions *upfront*.
            tmpD = Double.parseDouble(s);
            tmpNumeric = true;
        } catch(NumberFormatException ex) {
            // Parse failed so must be a String.
            tmpD = 0.0;
            tmpNumeric = false;
        }

        this.s = s;
        this.d = tmpD;
        this.numeric = tmpNumeric;
    }

    public String asString() {
        return s;
    }

    public double asDouble() {
        if (!numeric) {
            throw new IllegalStateException("Not a numeric value: " + s);
        }

        return d;
    }

    public boolean isNumeric() {
        return numeric;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Item)) return false;

        Item item = (Item) o;

        return Double.compare(item.d, d) == 0 && s.equals(item.s);
    }

    @Override
    public int hashCode() {
        int result;
        long temp;
        result = s.hashCode();
        temp = d != +0.0d ? Double.doubleToLongBits(d) : 0L;
        result = 31 * result + (int) (temp ^ (temp >>> 32));
        return result;
    }

    public int compareTo(Item item) {
        int ret;

        if (numeric && item.isNumeric()) {
            // Both items are numeric so do fast comparison.
            double diff = d - item.asDouble();
            if (diff > 0.0) {
                ret = 1;
            } else if (diff < 0.0) {
                ret = -1;
            } else {
                ret = 0;
            }
        } else {
            ret = s.compareTo(item.asString());
        }

        return ret;
    }
}

Answer 9

Мне кажется, что вам нужно избегать вызова String.compareTo () так часто, как вы. Есть два основных способа сделать это.

1) Реализовать некоторую форму сортировки сегментов , чтобы избежать выполнения всех этих сравнений.

В зависимости от количества сортируемых строк (тысячи? Миллионы?), Использование полной сортировки сегментов может потребовать слишком много накладных расходов с точки зрения пространства и сборок мусора.

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

2) Создайте хэш для каждой строки и отсортируйте хеши (убедитесь, что обрабатывает коллизии). После этого вы можете просто изменить порядок строк. Это, наверное, самое простое решение.

Использование любого из этих решений позволит вам отсортировать миллионы строк менее чем за секунду.

Answer 10

Почему бы не отсортировать список один раз в начале, обновляя его с помощью сортировки вставкой? Затем, когда вы хотите изменить порядок с восходящего на нисходящий, информация уже есть. Если вы хотите отсортировать по другому столбцу, то просто держать список рядом, если вы переключитесь обратно на этот столбец? Или это не выполнимо в SWT? (Прошло много времени с тех пор, как я его использовал)