Сложность алгоритма, содержащего рандомную операцию

#алгоритм #сложность #асимптотика

Для всякого ли алгоритма можно оценить сложность при помощи О нотации?

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

Ответы

Ответ 1

Да, можно. Следует оценивать с учётом вероятности.

Например, сложность bogosort оценивается как



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


Если в массиве около половины чисел чётные, то O(1).
Если только одно число чётное, то O(n) с жирненькой константой.
Если ни одного, то алгоритм вообще не завершится.

Если рассматривать случайный (равномерный) массив, то, вероятно, будет сводиться
к O(1) - как доступ по ключу хэш-таблицы.

PS: Провёл эксперимент для случая с единственным искомым числом (результат смотреть
в реальной консоли, открытой до запуска сниппета; при запуске браузер может зависнуть
на несколько секунд):



function go(n) {
  while (Math.random() * n | 0);
}

var res = [];

function check(n) {
  var t = performance.now();
  go(1< x+y)
  }
}

console.table(res.map(stat));






При удвоении длины время увеличивается вдвое, т. е. действительно O(n).

Что означает O(n^{2}). в описании сложности алгоритма?

#алгоритм #любой_язык #асимптотика

Что означает O(n2) в описании сложности алгоритма?

Что значит О, что значит n?
    

Ответы

Ответ 1

O - ничего не означает. Просто буква :) Вообще это из теории эквивалентных функций 

n - параметр размерности входных данных (обычно из контекста понятно о чём речь,
пример: размер массива). Или иной параметр, от значения которого зависит время работы. 

Теперь о вопросе что это значит в сумме, это значит что с ростом объёма входных данных
в 10 раз, ваша функция будет работать не более чем в 100 раз дольше. Учтите, оценки
асимптотические, работают при больших n. Поэтому иногда квадрат быстрее чем линия из-за
скрытых констант.

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



Следует помнить, что нотация обычно амортизирована и не всегда показывает время на
1 операцию. Пример - любой динамический массив вроде как и O(1) добавить, но регулярно
он может быть полностью скопирован (максимальное время единичной операции растёт, и
это не противоречит О - нотации).

Наглядный пример роста числа операций от О-нотации



При этом при О - нотации принято не указывать константы. Т.е. O(n) == O(2*n), так
же все младшие степени "поглощаются" старшими O(n2 + n) == O(n2). Исключение может
быть только при смешивании полиномиальной и экспоненциальной части (для малых n полином
может быть больше). 

Ссылки:


английский связанный ответ 
цикл статей о О нотации, хабр
примеры сложностей алгоритмов, хабр

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:

function test(n) {
  for (i=1; i<100000/n; i++) {
    dosomething();
  }
}

    

Ответы

Ответ 1

Их даже в теории не существует. Потому что это ограничение сверху.

O(C + 1/n) = O(C) = O(1)


Где C - некоторая константа, отличная от 0.

А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.

Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависи
и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.



Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоени
n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно.



Даже в коде из вопроса


for (i=1; i<100000/n; i++) {



что произойдёт, когда n превысит 100000?

У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n.


Ответ 2

Нет, не существует.

Сначала вспомним, что такое асимптота:

Пусть у нас есть некая кривая y = A(x). Тогда асимптота y = B(x) — это такая кривая, к которой A как бы «прижимается» при движении в бесконечность вдоль оси x.

Графически это выглядит так:



Источник: https://en.wikipedia.org/wiki/File:1-over-x-plus-x.svg

В данном примере прямая y = x является асимптотой для y = 1 / x + x, так как пр
достаточно больших x обе линии практически сливаются.

Асимптотатическая сложность ведёт себя аналогичным образом, только вместо графиков у нас зависимость вычислительной сложности от количества элементов.

Соответственно, чтобы утверждать, что алгоритм имеет сложность O(1 / N), надо, чтоб
график сложности алгоритма совпадал с графиком 1 / n при очень больших n. Но в этом случае 1 / n вырождается в константу ноль. А раз у нас константа, значит и алгоритм имеет константную сложность, обозначаемую как O(1).


Ответ 3

А вообще, есть интересный случай. В большинстве случаев говоря об асимптотике м
предполагаем возрастание аргумента. Но, строго говоря, это может быть не так. Например, если мы знаем, что область определения некоторой функции ограничена. Возьмём и реализуем деление int(1/x) через вычитание:



function f(x) {
  for (var i=0, v=1; v>0; ++i, v-=x);
  return i;
}

console.log(f(1));
console.log(f(.5));
console.log(f(.25));
console.log(f(.125));
console.log(f(.0625));
console.log(f(.0000001));




В принципе можно сказать, что у этой функции асимптотика O(1/x), т. е. при маленьки
значениях x она будет работать очень медленно (кстати, ещё и неточно из-за накопления погрешноти). Разумеется, в случае с целым аргументом такой вариант будет невозможен.

String & StringBuilder

В таких языках как Java и C# для конкатенации большого числа строк принято использовать StringBuilder, чтобы получить линейную асимптотику вместо квадратичной.

Однако, JavaScript каким-то образом справляется имея лишь один тип String. Асимптотик
конкатенации там линейная, по крайней мере при циклах до 131072 итераций. Но, что странно, время не зависит от длины складываемых строк. По крайней мере, так происходит в Хроме.

Как так вышло?

И бонусный вопрос знатокам JS: а что собственно случилось при 262144?

http://ideone.com/gtm5iy

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
  private static string Test(int n, string s)
  {
    var res = "";

    for (var q=0; q[10];
    const int N = 1024;
    var sw = new Stopwatch();

    for (var n=0; n();

      foreach (var s in new string[] {"!", "!2", "!234", "!2345678"})
      {
        res[n][s] = 0;

        for (var q=0; qC:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe StringConcat.cs && StringConcat.exe
Microsoft (R) Visual C# Compiler version 4.7.2046.0
for C# 5
Copyright (C) Microsoft Corporation. All rights reserved.

This compiler is provided as part of the Microsoft (R) .NET Framework, but only support
language versions up to C# 5, which is no longer the latest version. For compilers that support newer versions of the C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240

 0       1      0.000      0.000      0.000      0.000
 1       2      0.000      0.000      0.000      0.000
 2       4      0.000      0.000      0.000      0.000
 3       8      0.001      0.001      0.001      0.001
 4      16      0.002      0.001      0.001      0.002
 5      32      0.002      0.004      0.004      0.004
 6      64      0.005      0.006      0.009      0.014
 7     128      0.013      0.019      0.028      0.043
 8     256      0.042      0.057      0.087      0.148
 9     512      0.118      0.174      0.302      0.559
10    1024      0.354      0.606      1.124      2.279
11    2048      1.220      2.242      4.545     10.041
12    4096      4.517      8.982     19.706     41.568
13    8192     17.864     39.063     82.814    169.274
14   16384     78.454    165.893    337.830    718.843




function test(n, s) {
  var res = '';

  for (var q=0; q

Ответы
Ответ 1

Почему так происходит?

Судя по сорцам V8, строки оптимизированы для конкатенации. При конкатенации вмест
создания новой строки создаётся экземпляр, который ссылается на конкатенируемые куски. Каждый кусок тоже может ссылаться на подкуски. Таким образом строится бинарное дерево.

// The ConsString class describes string values built by using the
// addition operator on strings.  A ConsString is a pair where the
// first and second components are pointers to other string values.
// One or both components of a ConsString can be pointers to other
// ConsStrings, creating a binary tree of ConsStrings where the leaves
// are non-ConsString string values.  The string value represented by
// a ConsString can be obtained by concatenating the leaf string
// values in a left-to-right depth-first traversal of the tree.
class ConsString : public String {
 public:
  // First string of the cons cell.
  inline String* first();
  inline void set_first(String* first,
    WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  // Second string of the cons cell.
  inline String* second();
  inline void set_second(String* second,
    WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  // Minimum length for a cons string.
  static const int kMinLength = 13;
  // ...
}


Также есть подклассы строк для подстрок, явно разделяются однобайтовые и двубайтовые строки, и так далее.

// The Sliced String class describes strings that are substrings of another
// sequential string.  The motivation is to save time and memory when creating
// a substring.  A Sliced String is described as a pointer to the parent,
// the offset from the start of the parent string and the length.  Using
// a Sliced String therefore requires unpacking of the parent string and
// adding the offset to the start address.  A substring of a Sliced String
// are not nested since the double indirection is simplified when creating
// such a substring.
// Currently missing features are:
//  - handling externalized parent strings
//  - external strings as parent
//  - truncating sliced string to enable otherwise unneeded parent to be GC'ed.
class SlicedString : public String {
 public:
  inline String* parent();
  inline void set_parent(String* parent,
                         WriteBarrierMode mode = UPDATE_WRITE_BARRIER);
  inline int offset() const;
  inline void set_offset(int offset);
  // Minimum length for a sliced string.
  static const int kMinLength = 13;
  // ...
}


В результате такая простая операция как конкатенация превращается в подобное:

MaybeHandle Factory::NewConsString(Handle left,
                                           Handle right) {
  if (left->IsThinString()) {
    left = handle(Handle::cast(left)->actual(), isolate());
  }
  if (right->IsThinString()) {
    right = handle(Handle::cast(right)->actual(), isolate());
  }
  int left_length = left->length();
  if (left_length == 0) return right;
  int right_length = right->length();
  if (right_length == 0) return left;

  int length = left_length + right_length;

  if (length == 2) {
    uint16_t c1 = left->Get(0);
    uint16_t c2 = right->Get(0);
    return MakeOrFindTwoCharacterString(isolate(), c1, c2);
  }

  // Make sure that an out of memory exception is thrown if the length
  // of the new cons string is too large.
  if (length > String::kMaxLength || length < 0) {
    THROW_NEW_ERROR(isolate(), NewInvalidStringLengthError(), String);
  }

  bool left_is_one_byte = left->IsOneByteRepresentation();
  bool right_is_one_byte = right->IsOneByteRepresentation();
  bool is_one_byte = left_is_one_byte && right_is_one_byte;
  bool is_one_byte_data_in_two_byte_string = false;
  if (!is_one_byte) {
    // At least one of the strings uses two-byte representation so we
    // can't use the fast case code for short one-byte strings below, but
    // we can try to save memory if all chars actually fit in one-byte.
    is_one_byte_data_in_two_byte_string =
        left->HasOnlyOneByteChars() && right->HasOnlyOneByteChars();
    if (is_one_byte_data_in_two_byte_string) {
      isolate()->counters()->string_add_runtime_ext_to_one_byte()->Increment();
    }
  }

  // If the resulting string is small make a flat string.
  if (length < ConsString::kMinLength) {
    // Note that neither of the two inputs can be a slice because:
    STATIC_ASSERT(ConsString::kMinLength <= SlicedString::kMinLength);
    DCHECK(left->IsFlat());
    DCHECK(right->IsFlat());

    STATIC_ASSERT(ConsString::kMinLength <= String::kMaxLength);
    if (is_one_byte) {
      Handle result =
          NewRawOneByteString(length).ToHandleChecked();
      DisallowHeapAllocation no_gc;
      uint8_t* dest = result->GetChars();
      // Copy left part.
      const uint8_t* src =
          left->IsExternalString()
              ? Handle::cast(left)->GetChars()
              : Handle::cast(left)->GetChars();
      for (int i = 0; i < left_length; i++) *dest++ = src[i];
      // Copy right part.
      src = right->IsExternalString()
                ? Handle::cast(right)->GetChars()
                : Handle::cast(right)->GetChars();
      for (int i = 0; i < right_length; i++) *dest++ = src[i];
      return result;
    }

    return (is_one_byte_data_in_two_byte_string)
        ? ConcatStringContent(
            NewRawOneByteString(length).ToHandleChecked(), left, right)
        : ConcatStringContent(
            NewRawTwoByteString(length).ToHandleChecked(), left, right);
  }

  bool one_byte = (is_one_byte || is_one_byte_data_in_two_byte_string);
  return NewConsString(left, right, length, one_byte);
}


Всякие подобные премудрости — всегда компромисс, обложенный эвристиками. Движок JavaScrip
пытается угадать, когда выгоднее использовать какой способ: когда создавать полноценную строку, когда строить бинарное дерево строк; когда важнее скорость конкатенации, когда важнее скорость итерации; и так далее.

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

Почему так сделано в JavaScript?

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

Кроме того, когда язык создавался, скорость выполнения вовсе не имела значения, потом
что сложных программ на языке никто не писал. Сложные программы появились намного позже. Если вы запустите эту программу не в Chrome последней версии, а в любом браузере 20-летней давности, вы обнаружите совсем другую производительность.

Почему так не сделано в других языках?

Это зависит от языка и его предназначения. Например, строки в C++ простые и топорные
от программиста требуется указывать каждое движение, появляется разница в производительност
между объявлением строки в теле цикла или вне, между передачей строки в функцию по ссылке и по значению, от программиста ожидается указание заранее ожидаемой длины строки и так далее.

С другой стороны, в PHP массивы находятся в роли строк в JS и дадут фору по сложности
Массивы могут быть векторами, словарями, множествами и так далее. Они обладают сложной структурой, которая оптимизирована под каждый случай.

В целом, подход к стандартным классам меняется от языка к языку и даже между версиям
одного компилятора языка. Сегодня в JavaScript и PHP появляются типизированные массивы, завтра может появиться StringBuilder.

Сложность алгоритма, содержащего рандомную операцию

Для всякого ли алгоритма можно оценить сложность при помощи О нотации?
Допустим, я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное. Конечно, это очень кривой подход (в плане доступа к кэшам, например), но можно ли оценить его алгоритмическую сложность?

Ответ

Да, можно. Следует оценивать с учётом вероятности.
Например, сложность bogosort оценивается как
я имею массив чисел и хочу вытащить оттуда любое, условно, четное. Но перебирать их буду не по-порядку, а рандомно, в бесконечном цикле, пока не найду нужное.
Если в массиве около половины чисел чётные, то O(1). Если только одно число чётное, то O(n) с жирненькой константой. Если ни одного, то алгоритм вообще не завершится.
Если рассматривать случайный (равномерный) массив, то, вероятно, будет сводиться к O(1) - как доступ по ключу хэш-таблицы.
PS: Провёл эксперимент для случая с единственным искомым числом (результат смотреть в реальной консоли, открытой до запуска сниппета; при запуске браузер может зависнуть на несколько секунд):
function go(n) { while (Math.random() * n | 0); } var res = []; function check(n) { var t = performance.now(); go(1< x+y) } } console.table(res.map(stat));

При удвоении длины время увеличивается вдвое, т. е. действительно O(n).

Программно определить вычислительную сложность неизвестного алгоритма JS

Есть функция f : неизвестный алгоритм принимающий на вход одномерный массив . Есть коллекция массивов различной длины data каждый из которых передаю в f. Необходимо написать функцию результатом которой будет строка оценивающая вычислительную сложность алгоритма в f. Функция должна различать O(n), O(n2), O(n3), O(ln(n))
Есть ли пример как программно вычисляется вычислительная сложность алгоритма? Буду благодарен любым ссылкам и материалам, желательно с простейшими примерами.

Ответ

Грубо - если данные достаточно разных размеров - отличающиеся на порядки - можно пытаться построить зависимость времени работы от размера и посмотреть, для какого из вариантов корреляция будет выше.
Но обычно вмешивается столько других факторов, что сказать абсолютно точно абсолютно уверенно практически нереально. Например, при T=N + 0.00000001*N^2 при том, что алгоритм - O(N2), эксперимент при реальных N даст O(N)...

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:
function test(n) { for (i=1; i<100000/n; i++) { dosomething(); } }

Ответ

Их даже в теории не существует. Потому что это ограничение сверху.
O(C + 1/n) = O(C) = O(1)
Где C - некоторая константа, отличная от 0.
А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.
Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависит и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.

Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоении n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно.

Даже в коде из вопроса
for (i=1; i<100000/n; i++) {
что произойдёт, когда n превысит 100000?
У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n

String & StringBuilder

В таких языках как Java и C# для конкатенации большого числа строк принято использовать StringBuilder, чтобы получить линейную асимптотику вместо квадратичной.
Однако, JavaScript каким-то образом справляется имея лишь один тип String. Асимптотика конкатенации там линейная, по крайней мере при циклах до 131072 итераций. Но, что странно, время не зависит от длины складываемых строк. По крайней мере, так происходит в Хроме.
Как так вышло?
И бонусный вопрос знатокам JS: а что собственно случилось при 262144?
http://ideone.com/gtm5iy
using System; using System.Collections.Generic; using System.Diagnostics;
public class Program { private static string Test(int n, string s) { var res = "";
for (var q=0; q return res; }
public static void Main() { var res = new Dictionary[10]; const int N = 1024; var sw = new Stopwatch();
for (var n=0; n();
foreach (var s in new string[] {"!", "!2", "!234", "!2345678"}) { res[n][s] = 0;
for (var q=0; q res[n][s] /= N; } }
for (var n=0; n foreach (var kvp in res[n]) Console.Write("{0,10:0.000} ", kvp.Value / 1000);
Console.WriteLine(); } } }

0 1 0.001 0.000 0.000 0.000 1 2 0.002 0.001 0.001 0.001 2 4 0.003 0.003 0.005 0.003 3 8 0.006 0.006 0.007 0.007 4 16 0.013 0.015 0.013 0.014 5 32 0.025 0.025 0.032 0.034 6 64 0.050 0.059 0.070 0.097 7 128 0.120 0.142 0.220 0.303 8 256 0.337 0.417 0.630 0.972 9 512 0.897 1.256 1.964 4.087
К сожалению, при увеличении числа итераций программа не укладывается в 5 секунд, отведённые на выполнение на ideone. Вот результаты с домашнего компа:
D:\Temp\Supertemp>C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe StringConcat.cs && StringConcat.exe Microsoft (R) Visual C# Compiler version 4.7.2046.0 for C# 5 Copyright (C) Microsoft Corporation. All rights reserved.
This compiler is provided as part of the Microsoft (R) .NET Framework, but only supports language versions up to C# 5, which is no longer the latest version. For compilers that support newer versions of the C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240
0 1 0.000 0.000 0.000 0.000 1 2 0.000 0.000 0.000 0.000 2 4 0.000 0.000 0.000 0.000 3 8 0.001 0.001 0.001 0.001 4 16 0.002 0.001 0.001 0.002 5 32 0.002 0.004 0.004 0.004 6 64 0.005 0.006 0.009 0.014 7 128 0.013 0.019 0.028 0.043 8 256 0.042 0.057 0.087 0.148 9 512 0.118 0.174 0.302 0.559 10 1024 0.354 0.606 1.124 2.279 11 2048 1.220 2.242 4.545 10.041 12 4096 4.517 8.982 19.706 41.568 13 8192 17.864 39.063 82.814 169.274 14 16384 78.454 165.893 337.830 718.843
function test(n, s) { var res = ''; for (var q=0; q

Ответ

Почему так происходит?
Судя по сорцам V8, строки оптимизированы для конкатенации. При конкатенации вместо создания новой строки создаётся экземпляр, который ссылается на конкатенируемые куски. Каждый кусок тоже может ссылаться на подкуски. Таким образом строится бинарное дерево.
// The ConsString class describes string values built by using the // addition operator on strings. A ConsString is a pair where the // first and second components are pointers to other string values. // One or both components of a ConsString can be pointers to other // ConsStrings, creating a binary tree of ConsStrings where the leaves // are non-ConsString string values. The string value represented by // a ConsString can be obtained by concatenating the leaf string // values in a left-to-right depth-first traversal of the tree. class ConsString : public String { public: // First string of the cons cell. inline String* first(); inline void set_first(String* first, WriteBarrierMode mode = UPDATE_WRITE_BARRIER); // Second string of the cons cell. inline String* second(); inline void set_second(String* second, WriteBarrierMode mode = UPDATE_WRITE_BARRIER); // Minimum length for a cons string. static const int kMinLength = 13; // ... }
Также есть подклассы строк для подстрок, явно разделяются однобайтовые и двубайтовые строки, и так далее.
// The Sliced String class describes strings that are substrings of another // sequential string. The motivation is to save time and memory when creating // a substring. A Sliced String is described as a pointer to the parent, // the offset from the start of the parent string and the length. Using // a Sliced String therefore requires unpacking of the parent string and // adding the offset to the start address. A substring of a Sliced String // are not nested since the double indirection is simplified when creating // such a substring. // Currently missing features are: // - handling externalized parent strings // - external strings as parent // - truncating sliced string to enable otherwise unneeded parent to be GC'ed. class SlicedString : public String { public: inline String* parent(); inline void set_parent(String* parent, WriteBarrierMode mode = UPDATE_WRITE_BARRIER); inline int offset() const; inline void set_offset(int offset); // Minimum length for a sliced string. static const int kMinLength = 13; // ... }
В результате такая простая операция как конкатенация превращается в подобное
MaybeHandle Factory::NewConsString(Handle left, Handle right) { if (left->IsThinString()) { left = handle(Handle::cast(left)->actual(), isolate()); } if (right->IsThinString()) { right = handle(Handle::cast(right)->actual(), isolate()); } int left_length = left->length(); if (left_length == 0) return right; int right_length = right->length(); if (right_length == 0) return left;
int length = left_length + right_length;
if (length == 2) { uint16_t c1 = left->Get(0); uint16_t c2 = right->Get(0); return MakeOrFindTwoCharacterString(isolate(), c1, c2); }
// Make sure that an out of memory exception is thrown if the length // of the new cons string is too large. if (length > String::kMaxLength || length < 0) { THROW_NEW_ERROR(isolate(), NewInvalidStringLengthError(), String); }
bool left_is_one_byte = left->IsOneByteRepresentation(); bool right_is_one_byte = right->IsOneByteRepresentation(); bool is_one_byte = left_is_one_byte && right_is_one_byte; bool is_one_byte_data_in_two_byte_string = false; if (!is_one_byte) { // At least one of the strings uses two-byte representation so we // can't use the fast case code for short one-byte strings below, but // we can try to save memory if all chars actually fit in one-byte. is_one_byte_data_in_two_byte_string = left->HasOnlyOneByteChars() && right->HasOnlyOneByteChars(); if (is_one_byte_data_in_two_byte_string) { isolate()->counters()->string_add_runtime_ext_to_one_byte()->Increment(); } }
// If the resulting string is small make a flat string. if (length < ConsString::kMinLength) { // Note that neither of the two inputs can be a slice because: STATIC_ASSERT(ConsString::kMinLength <= SlicedString::kMinLength); DCHECK(left->IsFlat()); DCHECK(right->IsFlat());
STATIC_ASSERT(ConsString::kMinLength <= String::kMaxLength); if (is_one_byte) { Handle result = NewRawOneByteString(length).ToHandleChecked(); DisallowHeapAllocation no_gc; uint8_t* dest = result->GetChars(); // Copy left part. const uint8_t* src = left->IsExternalString() ? Handle::cast(left)->GetChars() : Handle::cast(left)->GetChars(); for (int i = 0; i < left_length; i++) *dest++ = src[i]; // Copy right part. src = right->IsExternalString() ? Handle::cast(right)->GetChars() : Handle::cast(right)->GetChars(); for (int i = 0; i < right_length; i++) *dest++ = src[i]; return result; }
return (is_one_byte_data_in_two_byte_string) ? ConcatStringContent( NewRawOneByteString(length).ToHandleChecked(), left, right) : ConcatStringContent( NewRawTwoByteString(length).ToHandleChecked(), left, right); }
bool one_byte = (is_one_byte || is_one_byte_data_in_two_byte_string); return NewConsString(left, right, length, one_byte); }
Всякие подобные премудрости — всегда компромисс, обложенный эвристиками. Движок JavaScript пытается угадать, когда выгоднее использовать какой способ: когда создавать полноценную строку, когда строить бинарное дерево строк; когда важнее скорость конкатенации, когда важнее скорость итерации; и так далее.
Очевиден плюс: потенциально очень медленные операции становятся более быстрыми. Особенно важно это для случаев, когда некоторые паттерны использования классов часто используются программистами, например, конкатенация строк. Но очевиден и минус: другие операции становятся медленнее, кроме того движок не всегда угадывает намерения программиста и выбирает самый оптимальный способ.
Почему так сделано в JavaScript?
Потому что язык сделан намеренно простым для понимания и использования. Чем больше магии, чем меньше нужно думать о внутреннем представлении, тем проще писать программы.
Кроме того, когда язык создавался, скорость выполнения вовсе не имела значения, потому что сложных программ на языке никто не писал. Сложные программы появились намного позже. Если вы запустите эту программу не в Chrome последней версии, а в любом браузере 20-летней давности, вы обнаружите совсем другую производительность.
Почему так не сделано в других языках?
Это зависит от языка и его предназначения. Например, строки в C++ простые и топорные, от программиста требуется указывать каждое движение, появляется разница в производительности между объявлением строки в теле цикла или вне, между передачей строки в функцию по ссылке и по значению, от программиста ожидается указание заранее ожидаемой длины строки и так далее.
С другой стороны, в PHP массивы находятся в роли строк в JS и дадут фору по сложности. Массивы могут быть векторами, словарями, множествами и так далее. Они обладают сложной структурой, которая оптимизирована под каждый случай.
В целом, подход к стандартным классам меняется от языка к языку и даже между версиями одного компилятора языка. Сегодня в JavaScript и PHP появляются типизированные массивы, завтра может появиться StringBuilder.

Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:
function test(n) { for (i=1; i<100000/n; i++) { dosomething(); } }

Ответ

Их даже в теории не существует. Потому что это ограничение сверху.
O(C + 1/n) = O(C) = O(1)
Где C - некоторая константа, отличная от 0.
А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.
Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависит и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.

Альтернативное обоснование: представим, что такой алгоритм есть, но тогда при удвоении n время его исполнения уменьшается вдвое и при достаточно большом n должно будет стать менее одной процессорной инструкции, что невозможно.

Даже в коде из вопроса
for (i=1; i<100000/n; i++) {
что произойдёт, когда n превысит 100000?
У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n

String & StringBuilder

В таких языках как Java и C# для конкатенации большого числа строк принято использовать StringBuilder, чтобы получить линейную асимптотику вместо квадратичной.
Однако, JavaScript каким-то образом справляется имея лишь один тип String. Асимптотика конкатенации там линейная, по крайней мере при циклах до 131072 итераций. Но, что странно, время не зависит от длины складываемых строк. По крайней мере, так происходит в Хроме.
Как так вышло?
И бонусный вопрос знатокам JS: а что собственно случилось при 262144?
http://ideone.com/gtm5iy
using System; using System.Collections.Generic; using System.Diagnostics;
public class Program { private static string Test(int n, string s) { var res = "";
for (var q=0; q return res; }
public static void Main() { var res = new Dictionary[10]; const int N = 1024; var sw = new Stopwatch();
for (var n=0; n();
foreach (var s in new string[] {"!", "!2", "!234", "!2345678"}) { res[n][s] = 0;
for (var q=0; q res[n][s] /= N; } }
for (var n=0; n foreach (var kvp in res[n]) Console.Write("{0,10:0.000} ", kvp.Value / 1000);
Console.WriteLine(); } } }

0 1 0.001 0.000 0.000 0.000 1 2 0.002 0.001 0.001 0.001 2 4 0.003 0.003 0.005 0.003 3 8 0.006 0.006 0.007 0.007 4 16 0.013 0.015 0.013 0.014 5 32 0.025 0.025 0.032 0.034 6 64 0.050 0.059 0.070 0.097 7 128 0.120 0.142 0.220 0.303 8 256 0.337 0.417 0.630 0.972 9 512 0.897 1.256 1.964 4.087
К сожалению, при увеличении числа итераций программа не укладывается в 5 секунд, отведённые на выполнение на ideone. Вот результаты с домашнего компа:
D:\Temp\Supertemp>C:\Windows\Microsoft.NET\Framework64\v4.0.30319\csc.exe StringConcat.cs && StringConcat.exe Microsoft (R) Visual C# Compiler version 4.7.2046.0 for C# 5 Copyright (C) Microsoft Corporation. All rights reserved.
This compiler is provided as part of the Microsoft (R) .NET Framework, but only supports language versions up to C# 5, which is no longer the latest version. For compilers that support newer versions of the C# programming language, see http://go.microsoft.com/fwlink/?LinkID=533240
0 1 0.000 0.000 0.000 0.000 1 2 0.000 0.000 0.000 0.000 2 4 0.000 0.000 0.000 0.000 3 8 0.001 0.001 0.001 0.001 4 16 0.002 0.001 0.001 0.002 5 32 0.002 0.004 0.004 0.004 6 64 0.005 0.006 0.009 0.014 7 128 0.013 0.019 0.028 0.043 8 256 0.042 0.057 0.087 0.148 9 512 0.118 0.174 0.302 0.559 10 1024 0.354 0.606 1.124 2.279 11 2048 1.220 2.242 4.545 10.041 12 4096 4.517 8.982 19.706 41.568 13 8192 17.864 39.063 82.814 169.274 14 16384 78.454 165.893 337.830 718.843
function test(n, s) { var res = ''; for (var q=0; q

Ответ

Почему так происходит?
Судя по сорцам V8, строки оптимизированы для конкатенации. При конкатенации вместо создания новой строки создаётся экземпляр, который ссылается на конкатенируемые куски. Каждый кусок тоже может ссылаться на подкуски. Таким образом строится бинарное дерево.
// The ConsString class describes string values built by using the // addition operator on strings. A ConsString is a pair where the // first and second components are pointers to other string values. // One or both components of a ConsString can be pointers to other // ConsStrings, creating a binary tree of ConsStrings where the leaves // are non-ConsString string values. The string value represented by // a ConsString can be obtained by concatenating the leaf string // values in a left-to-right depth-first traversal of the tree. class ConsString : public String { public: // First string of the cons cell. inline String* first(); inline void set_first(String* first, WriteBarrierMode mode = UPDATE_WRITE_BARRIER); // Second string of the cons cell. inline String* second(); inline void set_second(String* second, WriteBarrierMode mode = UPDATE_WRITE_BARRIER); // Minimum length for a cons string. static const int kMinLength = 13; // ... }
Также есть подклассы строк для подстрок, явно разделяются однобайтовые и двубайтовые строки, и так далее.
// The Sliced String class describes strings that are substrings of another // sequential string. The motivation is to save time and memory when creating // a substring. A Sliced String is described as a pointer to the parent, // the offset from the start of the parent string and the length. Using // a Sliced String therefore requires unpacking of the parent string and // adding the offset to the start address. A substring of a Sliced String // are not nested since the double indirection is simplified when creating // such a substring. // Currently missing features are: // - handling externalized parent strings // - external strings as parent // - truncating sliced string to enable otherwise unneeded parent to be GC'ed. class SlicedString : public String { public: inline String* parent(); inline void set_parent(String* parent, WriteBarrierMode mode = UPDATE_WRITE_BARRIER); inline int offset() const; inline void set_offset(int offset); // Minimum length for a sliced string. static const int kMinLength = 13; // ... }
В результате такая простая операция как конкатенация превращается в подобное
MaybeHandle Factory::NewConsString(Handle left, Handle right) { if (left->IsThinString()) { left = handle(Handle::cast(left)->actual(), isolate()); } if (right->IsThinString()) { right = handle(Handle::cast(right)->actual(), isolate()); } int left_length = left->length(); if (left_length == 0) return right; int right_length = right->length(); if (right_length == 0) return left;
int length = left_length + right_length;
if (length == 2) { uint16_t c1 = left->Get(0); uint16_t c2 = right->Get(0); return MakeOrFindTwoCharacterString(isolate(), c1, c2); }
// Make sure that an out of memory exception is thrown if the length // of the new cons string is too large. if (length > String::kMaxLength || length < 0) { THROW_NEW_ERROR(isolate(), NewInvalidStringLengthError(), String); }
bool left_is_one_byte = left->IsOneByteRepresentation(); bool right_is_one_byte = right->IsOneByteRepresentation(); bool is_one_byte = left_is_one_byte && right_is_one_byte; bool is_one_byte_data_in_two_byte_string = false; if (!is_one_byte) { // At least one of the strings uses two-byte representation so we // can't use the fast case code for short one-byte strings below, but // we can try to save memory if all chars actually fit in one-byte. is_one_byte_data_in_two_byte_string = left->HasOnlyOneByteChars() && right->HasOnlyOneByteChars(); if (is_one_byte_data_in_two_byte_string) { isolate()->counters()->string_add_runtime_ext_to_one_byte()->Increment(); } }
// If the resulting string is small make a flat string. if (length < ConsString::kMinLength) { // Note that neither of the two inputs can be a slice because: STATIC_ASSERT(ConsString::kMinLength <= SlicedString::kMinLength); DCHECK(left->IsFlat()); DCHECK(right->IsFlat());
STATIC_ASSERT(ConsString::kMinLength <= String::kMaxLength); if (is_one_byte) { Handle result = NewRawOneByteString(length).ToHandleChecked(); DisallowHeapAllocation no_gc; uint8_t* dest = result->GetChars(); // Copy left part. const uint8_t* src = left->IsExternalString() ? Handle::cast(left)->GetChars() : Handle::cast(left)->GetChars(); for (int i = 0; i < left_length; i++) *dest++ = src[i]; // Copy right part. src = right->IsExternalString() ? Handle::cast(right)->GetChars() : Handle::cast(right)->GetChars(); for (int i = 0; i < right_length; i++) *dest++ = src[i]; return result; }
return (is_one_byte_data_in_two_byte_string) ? ConcatStringContent( NewRawOneByteString(length).ToHandleChecked(), left, right) : ConcatStringContent( NewRawTwoByteString(length).ToHandleChecked(), left, right); }
bool one_byte = (is_one_byte || is_one_byte_data_in_two_byte_string); return NewConsString(left, right, length, one_byte); }
Всякие подобные премудрости — всегда компромисс, обложенный эвристиками. Движок JavaScript пытается угадать, когда выгоднее использовать какой способ: когда создавать полноценную строку, когда строить бинарное дерево строк; когда важнее скорость конкатенации, когда важнее скорость итерации; и так далее.
Очевиден плюс: потенциально очень медленные операции становятся более быстрыми. Особенно важно это для случаев, когда некоторые паттерны использования классов часто используются программистами, например, конкатенация строк. Но очевиден и минус: другие операции становятся медленнее, кроме того движок не всегда угадывает намерения программиста и выбирает самый оптимальный способ.
Почему так сделано в JavaScript?
Потому что язык сделан намеренно простым для понимания и использования. Чем больше магии, чем меньше нужно думать о внутреннем представлении, тем проще писать программы.
Кроме того, когда язык создавался, скорость выполнения вовсе не имела значения, потому что сложных программ на языке никто не писал. Сложные программы появились намного позже. Если вы запустите эту программу не в Chrome последней версии, а в любом браузере 20-летней давности, вы обнаружите совсем другую производительность.
Почему так не сделано в других языках?
Это зависит от языка и его предназначения. Например, строки в C++ простые и топорные, от программиста требуется указывать каждое движение, появляется разница в производительности между объявлением строки в теле цикла или вне, между передачей строки в функцию по ссылке и по значению, от программиста ожидается указание заранее ожидаемой длины строки и так далее.
С другой стороны, в PHP массивы находятся в роли строк в JS и дадут фору по сложности. Массивы могут быть векторами, словарями, множествами и так далее. Они обладают сложной структурой, которая оптимизирована под каждый случай.
В целом, подход к стандартным классам меняется от языка к языку и даже между версиями одного компилятора языка. Сегодня в JavaScript и PHP появляются типизированные массивы, завтра может появиться StringBuilder.