Ускорить поиск строк в массиве с длиной меньше средней

#java #алгоритм

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

public List getLessMiddle(String[] src) {
    final List result = new ArrayList<>();

    int common = 0;

    for (String s : src) {
        common += s.length();
    }

    final int middle = common / src.length;

    for (String s : src) {
        if (s.length() < middle) {
            result.add(s);
        }
    }

    return result;
}


Можно ли сделать его быстрее?
    

Ответы

Ответ 1

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


Для того чтобы определить среднюю длину нужно хотя бы раз пройти по всем строкам
и сложить их длины.
Затем нужно вытащить строки с длиной меньше средней. В худшем случае (n-1 одинаковых
строк и одна чуть длиннее) таких строк будет n-1 и для того чтобы их вытащить нужна
будет хотя бы n-1 операция. 


Всего 2n-1, что немногим лучше. 

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

Т.к. по оптимизации алгоритма мне нечего сказать, перечислю проблематичные моменты
по алгоритму/коду.


Ошибка при делении. Используется целочисленное деление (common / src.length;) если
common не делится нацело на src.length, то произойдет округление книзу. Это округление
исключит при отборе строки, которые не должны быть исключены. Например: если на входе
массив {"a", "bb"}, то средняя длина — 1,5. При этом строка "a" должна попадать в результат.
Сейчас middle примет значение 1, и результат будет пуст. 

Чтобы исправить можно округлять кверху, либо использовать вещественный тип для middle
либо решить неравенство и обойтись без деления вообще (в этом случае может понадобится
long).
Никак не обрабатывается случай, когда входной массив пуст (произойдет деление на ноль).
Сумма длин строк может выходить за рамки int, что приведет к переполнению и некорректным
результатам.
Переменную result можно перенести ближе к использованию:

int common = 0;
for (String s : src) {
    common += s.length();
}  

final int middle = common / src.length;
final List result = new ArrayList<>();
for (String s : src) {
    if (s.length() < middle) {
        result.add(s);
    }
}
return result;