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

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

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

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

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

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);
}

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

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

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

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

Если вам нужно как «буквальное», так и «числовое» сравнение, какие данные содержат эти строки? Всегда ли они представляют собой числа?

Если они содержат только числа, то, вероятно, намного быстрее хранить их как числа (помимо того, что это более чистая вещь).

И если вам нужно «буквальное» сравнение (которое я интерпретирую как сортировку «100» перед «20»), то вы можете легко реализовать это на int s или long s с некоторой математикой, которая, вероятно, все еще намного быстрее, чем сравнение строк.

Как уже сказали Ренье и Гийом, String.compareTo () не виноват. Это должно быть медленнее, чем числовое сравнение, но на самом деле это не так уж важно.

Даже если ваш список состоит из миллионов элементов, это не займет больше секунды.

Если это вариант, я бы выполнил поиск в фоновом режиме, то есть прикрепить к строкам какую-то индексацию.

Вам действительно следует проанализировать, какие операции будут происходить чаще всего: одиночные вставки, массовые несортированные вставки, массовые частично отсортированные вставки, сортировка, удаление и т. Д.

В зависимости от наиболее распространенной операции вы можете выбрать более подходящую структуру данных.

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

На основании вашего недавнего разъяснения вот второй ответ: Создайте класс: Элемент , который может использоваться для представления числового или буквенно-цифрового значения, и может определить, случай авансом . Таким образом вы избегаете накладных расходов на синтаксический анализ значения и обработку любых исключений во время вызова метода 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;
    }
}

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

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

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

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

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

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