Существуют несколько классических описанных в разных книгах и статьях алгоритмов, задача которых — это поиск некоторой строки в тексте (ещё говорят поиск подстроки в строке или же образца в строке). Я написал на Джава 17 реализации 4 разных алгоритмов, о которых рассказываю на лекциях, и посмотрел, как они работают на макбуке с процессором М1. Сразу скажу, что эти реализации не являются эталонными и наверняка их можно улучшить. Так, Бойер-Мур достаточно легко ускоряется за счёт замены самописаного OpenTable на что-то вроде Int2IntOpenHashMap Но, тем не менее, почему бы не посравнивать хоть что-то?
Итак, перед тем, как представить 4 алгоритма, участвующих в сравнении, и для всех них будет использоваться этот интерфейс:
public interface StringSearch {
int find(String pattern, String string);
default boolean equals(String pattern, String text, int from, int to) {
for (int i = from; i < to; i++) {
if (pattern.charAt(i - from) != text.charAt(i)) {
return false;
}
}
return true;
}
}
А сами алгоритмы реализуем так:
public class NaiveSearch implements StringSearch {
@Override
public int find(String p, String s) {
for (int i = 0; i <= s.length() - p.length(); i++) {
if (equals(p, s, i, i + p.length())) {
return i;
}
}
return -1;
}
}
public class RabinKarpSearch implements StringSearch {
@Override
public int find(String pattern, String string) {
int patternLength = pattern.length();
int hs = stringHashCode(pattern, 0, patternLength);
int stringLength = string.length();
int st = stringHashCode(string, 0, patternLength);
for (int i = 0; i <= stringLength - patternLength; i++) {
if (hs == st && equals(pattern, string, i, i + patternLength)) {
return i;
}
st = st - string.charAt(i) + string.charAt(i + patternLength);
}
return -1;
}
private int stringHashCode(String string, int start, int end) {
int result = 0;
for (int i = start; i < end; i++) {
result += string.charAt(i);
}
return result;
}
}
public class BoyerMooreSearch implements StringSearch {
@Override
public int find(String p, String s) {
OpenTable table = new OpenTable<>(p.length());
for (int i = 0; i < p.length() - 1; i++) {
table.put(p.charAt(i), i);
}
loop: for (int i = 0; i < s.length() - p.length() + 1;) {
for (int j = p.length() - 1; j > -1; j--) {
if (p.charAt(j) != s.charAt(i + j)) {
Integer move = table.get(s.charAt(i + j));
i += Math.max(1, j - (move == null ? p.length() : move));
continue loop;
}
}
return i;
}
return -1;
}
}
public class KnuthMorrisPrattSearch implements StringSearch {
@Override
public int find(String p, String s) {
var pi = computePrefixFunction(p);
var q = 0;
for (int i = 0; i < s.length(); i++) {
while (q > 0 && p.charAt(q) != s.charAt(i)) {
q = pi[q];
}
if (p.charAt(q) == s.charAt(i)) {
q = q + 1;
}
if (q == p.length()) {
return i - p.length() + 1;
}
}
return -1;
}
private int[] computePrefixFunction(String p) {
int[] pi = new int[p.length() + 1];
int k = 0;
for (int q = 1; q < p.length(); q++) {
while (k > 0 && p.charAt(k) != p.charAt(q)) {
k = pi[k];
}
if (p.charAt(k) == p.charAt(q)) {
k = k + 1;
}
pi[q + 1] = k;
}
return pi;
}
}
Каждый текст я прогоню несколько раз и замерю время работы поиска в наносекундах. Подстрока генерируется случайным образом из строки текста. Длина подстроки и текста определяются в зависимости от эксперимента.
Эксперимент 1: Влияние длины подстроки на время работы
В этом эксперименте длина строки не меняется, а длина подстроки изменяется от 1 до 1 000 (в случае с текстом Lorem до 445). Теоретически, поскольку каждый алгоритм работает за линейное время (кроме наивной реализации) влияние n будет тем больше, чем ближе длина подстроки к длине самой строки. Запуск на MacBook Air M1 2020 дал следующие результаты:
Эксперимент 2: Влияние длины текста на время работы
Теперь будет менять длину текста. От 0 + длина образца до 5000 + длина образца (кроме Lorem), тогда как длина подстроки будет зафиксирована на значения 10, 256 и 1000.
Длина подстроки 10, текста от 10 до 5010:
Длина подстроки 256, текста от 256 до 5256:
Длина подстроки 1000, текста от 1000 до 6000:
Интересно то, что во всех случаях лучше всего работает самые простые алгоритмы: наивный и его улучшение в виде Рабина-Карпа. Причём последний работает лучше всего. Ещё лучше работает базовая реализация в самой Джаве (String::indexOf). Хотя и тут не без интересного: в эксперименте 1 можно увидеть, как на нескольких графиках время работы резко меняется тогда, когда длина паттерна становится равной 256. О причинах такого я могу догадываться, но попробую изучить вопрос внимательней и прийти с ответом в следующий раз.
Что касается эксперимента 2, то на коротких паттернах хуже всего работает алгоритм Бойера-Мура, но достаточно быстро он начинает реабилитироваться на паттернах в 256 и 1000 символах, за исключением текста с последовательностью ДНК. Это в общем-то согласуется с утверждением о том, что алгоритм Бойера-Мура не так эффективен на текстах с небольшим алфавитом.
public class Quiz_2 {
public void func(Integer i) {
System.out.println("integer"); }
public void func(Double i) {
System.out.println("double"); }
public void func(Object i) {
System.out.println("object"); }
public static void main(String[] args) {
List nums = Arrays.asList(1/2);
new Quiz_2().func(nums.get(0));
}
}
… из-за того, что список List<?> nums типизирован <?>. Такой вайлдкард вернёт Object в любой ситуации, а компилятор заранее скомпилирует представленный код с вызовом правильной функции, а именно public void func(Object i) {.
Задача 3
public class Quiz_3 {
public static void main(String[] args) {
System.out.println(
true?false:true == true?false:true
);
}
}
public class Quiz_4 {
public static void main(String[] args) {
int n = 1;
int result = Optional.of(n++)
.map(i -> i + n)
.orElse(-1);
System.out.println(result);
}
}
Переменная n должна быть финальной, чтобы использоваться в лямбда-выражении i -> i + n. С другой стороны, n не может быть финальной из-за унарного оператора ++ в выражении Optional.of(n++).
Задача 5
public class Quiz_5 {
public static void main(String[] args) {
int n = Integer.MAX_VALUE;
n++;
System.out.println(n + n);
}
}
Начнём с того, что Integer.MAX_VALUE + 1 = Integer.MIN_VALUE. В бинарном представлении значение Integer.MAX_VALUE (01111111111111111111111111111111) при добавлении к нему единицы получится Integer.MIN_VALUE (10000000000000000000000000000000). При сложении 2-х этих чисел сумма старших битов даст 102, что приведёт к переполнению в памяти. Поскольку 1 будет некуда записать в 32-х битном представлении, то останутся только нули.
At run time, the result of the instanceof operator is true if the value of the RelationalExpression is not null and the reference could be cast (§15.16) to the ReferenceType without raising a ClassCastException.
Задача 2
public class Quiz_2 {
public static void main(String[] args) {
String[] strings = {"1", "1"};
Object[] objects = strings;
objects[0] = 0;
System.out.println(
Arrays.toString(objects)
);
}
}
Выражение "t" + "r" + "u" + "e" является строковым литералом и согласно спецификации 3.10.5. String Literals:
A long string literal can always be broken up into shorter pieces and written as a (possibly parenthesized) expression using the string concatenation operator +
[...]
Moreover, a string literal always refers to the same instance of class String.
Strings computed by constant expressions (§15.28) are computed at compile time and then treated as if they were literals.
Strings computed by concatenation at run-time are newly created and therefore distinct.
Более того, компилятор самостоятельно вычислить выражение и в байт-код запишет следующее:
Метод StringBuilder.toString() возвращает новый экземпляр типа String с новой ссылкой:
@Override
public String toString() {
// Create a copy, don't share the array
return new String(value, 0, count);
}
Именно поэтому сравнение через == вернёт значение false.
В соответствии с javadoc метода replace():
If the character {@code oldChar} does not occur in the character sequence represented by this {@code String} object, then a reference to this {@code String} object is returned.
Поскольку 'T' отсутствует в исходной строке, то вернётся исходный объект.
Задача 4
public class Quiz_4 {
public static void main(String[] args) {
Stream stream =
Stream.of("A", "B");
System.out.print(1);
stream.peek(System.out::print);
System.out.print(2);
stream.forEach(System.out::print);
}
}
Exception in thread "main" java.lang.IllegalStateException: stream has already been operated upon or closed
at java.util.stream.AbstractPipeline.sourceStageSpliterator(AbstractPipeline.java:279)
at java.util.stream.ReferencePipeline$Head.forEach(ReferencePipeline.java:580)
at me.markoutte.sandbox.conferences.jpoint2018.luxoft.day1.Quiz_4.main(Quiz_4.java:21)
Происходит это всё из-за того, что peek является промежуточной операцией, возвращающей новый стрим, который в данном примере отсутствует, а вызов forEach обнаруживает проблему чтения из того же стрима, что читает peek.
Задача 5
public class Quiz_5 {
public static void main(String[] args) {
HashSet set = new HashSet<>();
for (short i = 0; i < 100; i++) {
set.add(i);
set.remove(i - 1);
}
System.out.println(set.size());
}
}
Ни одно из значений не будет удалено из сета, поскольку для операции (i - 1) будет автоматически выполнено сначала расширения типа до integer, а потом боксинг в тип Integer. Поскольку в сете хранится тип Short, а не Integer, то ни одна из операций по удалению не сможет найти нужных значений и величина массива будет равна количеству операции по добавлению. В данном случае таковых 100.
Решите, например, сегодняшнее задание на codewars:
Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.
You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?
The parameter of the function findNb (find_nb, find-nb, findNb) will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + … + 1^3 = m if such a n exists or -1 if there is no such n.
Переведу в кратце: необходимо вычислить количество кубиков для здания заданного объёма. Объём здания считается как сумма объёмов состовляющих его кубиков. Каждый кубик, начиная с нижнего, имеет объём , где i — порядковый номер куба (от 1 до n) снизу.
Решение в лоб с использованием циклов:
public static long findNb(long m) {
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : -1;
}
Но в университете мне что-то рассказывали про ряды и их суммы, поэтому захотелось решить задачу математически. Как считать ряды я давно забыл, но ответ вы найдёте, перейдя на Wolfram Alpha и введя sum n^3, n = 1 to k в поле поиска. Узнаем, что:
Приравняем правую часть к m, извлечём корень и упростим выражение:
Теперь можно решить квадратное уравнение:
Пишем код:
public static long findNb(long m) {
double res = Math.sqrt(m);
double d = 1 + 8 * res;
double n = (Math.sqrt(d) - 1) / 2;
return n - Math.floor(n) == 0 ? (long) n : -1;
}
Оказывается, что для некоторого числа тестовых данных, код даёт неверный ответ. Например, для значения 1646842954019151682L. В джаве корень из этого числа даёт:
Более правильное (и, наверняка, быстрое) решение не всегда даёт правильные результаты. Этим не удивишь опытного разработчика, но начинающие программисты долго могут гадать о природе ошибки.
Посчитать правильно предыдущий пример всё-таки можно, если использовать более подходищие типы для таких задач. Речь про BigDecimal:
public static long findNb(long m) {
MathContext mc = new MathContext(64);
BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}
, где i — порядковый номер куба (от 1 до n) снизу.
