Сложность времени подстроки Java()

Question

Какова временная сложность метода String#substring() в Java?

Answer 1

Нового ответ

Как обновления 6 в течение жизни Java 7, в поведении substring изменилось, чтобы создать копию - так что каждый String относится к char[], который не совместно с любым другим объектом, как и насколько я знаю. Таким образом, в этот момент substring() стал операцией O (n), где n - числа в подстроке.

Старый ответ: до Java 7

Незарегистрированные - но на практике O (1), если не берут на себя мусор требуется сбор и т.д.

Он просто создает новый объект String со ссылкой на те же базовые char[], но с разными значениями смещения и количества. Таким образом, стоимость - это время, затраченное на выполнение проверки и построение одного нового (достаточно малого) объекта. Это O (1), насколько это разумно говорить о сложности операций, которые могут меняться во времени на основе сбора мусора, кэшей CPU и т. Д. В частности, это не зависит напрямую от длины исходной строки или подстроки ,

Answer 2

O (1), поскольку копирование исходной строки не выполняется, оно просто создает новый объект-обертку с различной информацией о смещении.

Answer 3

Судите сами за собой, но недостатки производительности 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"); 
    } 

Выход:

substring 32768 times 
Sum of lengths of splits = 1494414 
Elapsed 2.446679 ms

Если это O (1) или нет, зависит от многого. Если вы просто ссылаетесь на одну и ту же строку в памяти, тогда представьте себе очень длинную строчку, вы делаете подстроку и перестаете ссылаться на длинную. Было бы неплохо выпустить память на долгий срок?

Answer 4

Это было O (1) в более старых версиях Java - как сказал Джон, он просто создал новую строку с тем же основным char [] и другим смещением и длиной.

Однако, это на самом деле изменилось начал с Java 7 обновлений 6.

полукокса [] разделение было устранено, и смещение и поля длины были удалены. Подстрока() теперь просто копирует все символы в новую строку.

Ergo, подстрока O (п) в Java 7 обновлений 6

Answer 5

Это теперь линейная сложность. Это происходит после исправления проблемы утечки памяти для подстроки.

Итак, из Java 1.7.0_06 помните, что String.substring теперь имеет линейную сложность вместо константной.