Какова временная сложность String#substring()
метода в Java?
источник
Какова временная сложность String#substring()
метода в Java?
Новый ответ
Начиная с обновления 6 в течение срока службы Java 7, поведение substring
изменилось, чтобы создать копию - поэтому каждый String
ссылается на объект, char[]
который не используется совместно с каким-либо другим объектом, насколько мне известно. Итак, в этот момент substring()
операция стала O (n), где n - числа в подстроке.
Старый ответ: до Java 7
Недокументировано - но на практике O (1), если вы предполагаете, что сборка мусора не требуется и т. Д.
Он просто создает новый String
объект, ссылающийся на тот же базовый объект, char[]
но с другими значениями смещения и счетчика. Таким образом, стоимость - это время, затрачиваемое на проверку и создание единственного нового (достаточно небольшого) объекта. Это O (1), поскольку разумно говорить о сложности операций, которые могут меняться во времени в зависимости от сборки мусора, кешей ЦП и т. Д. В частности, это напрямую не зависит от длины исходной строки или подстроки. .
В старых версиях Java это было O (1) - как заявил Джон, он просто создал новую строку с тем же базовым char [], и другим смещением и длиной.
Однако на самом деле все изменилось, начиная с версии 6 для Java 7.
Совместное использование char [] было удалено, а поля смещения и длины удалены. substring () теперь просто копирует все символы в новую строку.
Ergo, подстрока - O (n) в Java 7 (обновление 6)
источник
char[]
...Теперь это линейная сложность. Это после устранения проблемы с утечкой памяти для подстроки.
Итак, начиная с Java 1.7.0_06 помните, что String.substring теперь имеет линейную сложность вместо постоянной.
источник
Добавление доказательства к ответу Джона. У меня были такие же сомнения, и я хотел проверить, влияет ли длина строки на функцию подстроки. Написал следующий код, чтобы проверить, от какого параметра на самом деле зависит подстрока.
import org.apache.commons.lang.RandomStringUtils; public class Dummy { private static final String pool[] = new String[3]; private static int substringLength; public static void main(String args[]) { pool[0] = RandomStringUtils.random(2000); pool[1] = RandomStringUtils.random(10000); pool[2] = RandomStringUtils.random(100000); test(10); test(100); test(1000); } public static void test(int val) { substringLength = val; StatsCopy statsCopy[] = new StatsCopy[3]; for (int j = 0; j < 3; j++) { statsCopy[j] = new StatsCopy(); } long latency[] = new long[3]; for (int i = 0; i < 10000; i++) { for (int j = 0; j < 3; j++) { latency[j] = latency(pool[j]); statsCopy[j].send(latency[j]); } } for (int i = 0; i < 3; i++) { System.out.println( " Avg: " + (int) statsCopy[i].getAvg() + "\t String length: " + pool[i].length() + "\tSubstring Length: " + substringLength); } System.out.println(); } private static long latency(String a) { long startTime = System.nanoTime(); a.substring(0, substringLength); long endtime = System.nanoTime(); return endtime - startTime; } private static class StatsCopy { private long count = 0; private long min = Integer.MAX_VALUE; private long max = 0; private double avg = 0; public void send(long latency) { computeStats(latency); count++; } private void computeStats(long latency) { if (min > latency) min = latency; if (max < latency) max = latency; avg = ((float) count / (count + 1)) * avg + (float) latency / (count + 1); } public double getAvg() { return avg; } public long getMin() { return min; } public long getMax() { return max; } public long getCount() { return count; } } }
Результат выполнения в Java 8:
Avg: 128 String length: 2000 Substring Length: 10 Avg: 127 String length: 10000 Substring Length: 10 Avg: 124 String length: 100000 Substring Length: 10 Avg: 172 String length: 2000 Substring Length: 100 Avg: 175 String length: 10000 Substring Length: 100 Avg: 177 String length: 100000 Substring Length: 100 Avg: 1199 String length: 2000 Substring Length: 1000 Avg: 1186 String length: 10000 Substring Length: 1000 Avg: 1339 String length: 100000 Substring Length: 1000
Доказательство функции подстроки зависит от длины запрошенной подстроки, а не от длины строки.
источник
O (1), поскольку копирование исходной строки не выполняется, он просто создает новый объект-оболочку с другой информацией о смещении.
источник
Судите сами по следующему, но недостатки производительности Java кроются где-то еще, а не здесь, в подстроке строки. Код:
public static void main(String[] args) throws IOException { String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; int[] indices = new int[32 * 1024]; int[] lengths = new int[indices.length]; Random r = new Random(); final int minLength = 6; for (int i = 0; i < indices.length; ++i) { indices[i] = r.nextInt(longStr.length() - minLength); lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); } long start = System.nanoTime(); int avoidOptimization = 0; for (int i = 0; i < indices.length; ++i) //avoidOptimization += lengths[i]; //tested - this was cheap avoidOptimization += longStr.substring(indices[i], indices[i] + lengths[i]).length(); long end = System.nanoTime(); System.out.println("substring " + indices.length + " times"); System.out.println("Sum of lengths of splits = " + avoidOptimization); System.out.println("Elapsed " + (end - start) / 1.0e6 + " ms"); }
Выход:
Если это O (1) или нет, зависит. Если вы просто ссылаетесь на одну и ту же строку в памяти, а затем представьте очень длинную строку, вы создаете подстроку и перестаете ссылаться на длинную. Не было бы неплохо освободить память надолго?
источник
До Java 1.7.0_06: O (1).
После Java 1.7.0_06: O (n). Это было изменено из-за утечки памяти. После удаления полей
offset
иcount
из String реализация подстроки стала O (n).Для получения дополнительных сведений перейдите по ссылке : http://java-performance.info/changes-to-string-java-1-7-0_06/
источник