Повторить строку - Javascript

271

Каков наилучший или самый краткий метод для возврата строки, повторенной произвольное количество раз?

На данный момент мой лучший снимок:

function repeat(s, n){
    var a = [];
    while(a.length < n){
        a.push(s);
    }
    return a.join('');
}
штифтик
источник
5
Более 10 лет назад у меня было хорошо известное решение этой проблемы, которое я использовал в качестве примера в статье по оптимизации JavaScript за пару месяцев до того, как вы задали этот вопрос: webreference.com/programming/javascript/jkm3/3 .html Очевидно, что большинство людей забыли об этом коде, и я не вижу ни таких хороших решений, как моих. Лучший алгоритм выглядит так, как будто он взят из моего кода; кроме как из-за неправильного понимания того, как работает мой код, он делает один дополнительный шаг экспоненциальной конкатенации, который исключен в моем оригинале специальным циклом.
Джозеф Майерс
10
Никто не поднял решение Джозефа. Алгоритму 3700 лет. Стоимость дополнительного шага незначительна. И эта статья содержит ошибки и неправильные представления о конкатенации строк в Javascript. Для тех, кто интересуется, как Javascript действительно обрабатывает строки внутри, смотрите Rope .
artistoex
4
Кажется, никто не заметил, что повтор прототипа String определен и реализован, по крайней мере, в Firefox.
Кеннебек
3
@kennebec: Да, это функция EcmaScript 6, которой не было, когда задавался этот вопрос. Это довольно хорошо поддерживается сейчас.
rvighne
3
@rvighne - я только что проверил kangax.github.io/compat-table/es6/#String.prototype.repeat. Я не считаю поддержку исключительно из Firefox и Chrome "довольно хорошо поддерживаемой"
aaaaaa

Ответы:

406

Примечание для новых читателей: Этот ответ старый и не очень практичный - он просто «умный», потому что он использует Array для выполнения String. Когда я писал «меньше процессов», я определенно имел в виду «меньше кода», потому что, как другие отмечали в последующих ответах, он работает как свинья. Так что не используйте его, если скорость имеет значение для вас.

Я бы поставил эту функцию непосредственно на объект String. Вместо того, чтобы создавать массив, заполнять его и соединять с пустым символом, просто создайте массив правильной длины и соедините его с желаемой строкой. Тот же результат, меньше процесса!

String.prototype.repeat = function( num )
{
    return new Array( num + 1 ).join( this );
}

alert( "string to repeat\n".repeat( 4 ) );
Питер Бейли
источник
36
Я стараюсь не расширять нативные объекты, но в остальном это прекрасное решение. Спасибо!
Брэд
34
@ Брэд - почему бы и нет? Вы бы предпочли загрязнить глобальное пространство имен функцией, которая имеет довольно четко определенный дом (объект String)?
Питер Бейли
16
На самом деле, оба ваших аргумента применимы и к глобальному пространству имен. Если я собираюсь расширить пространство имен и иметь потенциальные коллизии, я бы предпочел сделать это 1) не в глобальном масштабе 2) в одном, который имеет отношение к делу и 3) легко реорганизовать. Это означает поместить его в прототип String, а не в глобальный.
Питер Бейли
11
одно изменение, которое я бы сделал в этой функции, заключалось бы в том, чтобы поместить parseInt () вокруг «num», поскольку, если у вас есть числовая строка, вы можете получить странное поведение из-за жонглирования типов в JS. например: "моя строка" .repeat ("6") == "61"
nickf
19
Если вы не хотите , чтобы расширить собственные объекты, вы могли бы поставить функцию на строковом объекте , а не, как это: String.repeat = function(string, num){ return new Array(parseInt(num) + 1).join(string); };. Назовите это так:String.repeat('/\', 20)
Знакурс
204

Я проверил производительность всех предложенных подходов.

Вот самый быстрый вариант, который у меня есть.

String.prototype.repeat = function(count) {
    if (count < 1) return '';
    var result = '', pattern = this.valueOf();
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    return result + pattern;
};

Или как отдельная функция:

function repeat(pattern, count) {
    if (count < 1) return '';
    var result = '';
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    return result + pattern;
}

Он основан на алгоритме artistoex . Это действительно быстро. И чем больше count, тем быстрее он идет по сравнению с традиционным new Array(count + 1).join(string)подходом.

Я только изменил 2 вещи:

  1. заменено pattern = thisна pattern = this.valueOf()(очищает одно очевидное преобразование типа);
  2. добавлена if (count < 1)проверка из prototypejs в начало функции, чтобы исключить ненужные действия в этом случае.
  3. прикладная оптимизация от ответа Дениса (ускорение на 5-7%)

UPD

Создана небольшая производительность тестирования площадки здесь для тех , кто заинтересован.

переменная count~ 0 .. 100:

Диаграмма производительности

постоянная count= 1024:

Диаграмма производительности

Используйте его и сделайте еще быстрее, если сможете :)

disfated
источник
4
Хорошая работа! Я думаю, что count < 1дело действительно в ненужной оптимизации.
JayVee
Отличный алгоритм O (log N). Спасибо за отличную оптимизацию с помощью valueOf ()
vp_arth
2
Ссылки на изображения мертвы.
Бенджамин Грюнбаум
Ссылки в порядке. Может быть временная недоступность
разорена
Тест JSFiddle больше не работает правильно; кажется, что он просто продолжает запускать первую функцию снова и снова (
оставьте ее включенной
47

Эта проблема является хорошо известной / «классической» проблемой оптимизации для JavaScript, вызванной тем, что строки JavaScript являются «неизменяемыми», а добавление путем конкатенации даже одного символа в строку требует создания, включая выделение памяти и копирование в нее. , целая новая строка.

К сожалению, принятый ответ на этой странице неправильный, где «неправильный» означает с коэффициентом производительности 3x для простых односимвольных строк и 8x-97x для коротких строк, повторяемых несколько раз, до 300x для повторяющихся предложений и бесконечно неправильным, когда принимая предел отношений сложности алгоритмов, как nуходит в бесконечность. Кроме того, на этой странице есть еще один ответ, который является почти правильным (на основе одного из многих поколений и вариантов правильного решения, распространенного в Интернете за последние 13 лет). Однако в этом «почти правильном» решении отсутствует ключевой момент правильного алгоритма, что приводит к снижению производительности на 50%.

Результаты выполнения JS для принятого ответа, другого ответа с наибольшей эффективностью (на основе ухудшенной версии исходного алгоритма в этом ответе) и этого ответа с использованием моего алгоритма, созданного 13 лет назад

~ Октябрь 2000 г. Я опубликовал алгоритм для этой конкретной задачи, который был широко адаптирован, модифицирован, а затем, в конце концов, плохо понят и забыт. Чтобы исправить эту проблему, в августе 2008 года я опубликовал статью http://www.webreference.com/programming/javascript/jkm3/3.html, в которой объясняется алгоритм и используется его в качестве примера простой универсальной оптимизации JavaScript. К настоящему времени Web Reference удалил мою контактную информацию и даже мое имя из этой статьи. И снова, алгоритм был широко адаптирован, модифицирован, затем плохо понят и в значительной степени забыт.

Алгоритм JavaScript повторения / умножения исходных строк Джозефа Майерса, около Y2K, как функция умножения текста в Text.js; опубликовано в августе 2008 г. в этой форме посредством веб-ссылки: http://www.webreference.com/programming/javascript/jkm3/3.html (в статье используется функция в качестве примера оптимизации JavaScript, которая является единственной для странного имя "stringFill3.")

/*
 * Usage: stringFill3("abc", 2) == "abcabc"
 */

function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

В течение двух месяцев после публикации этой статьи этот же вопрос был опубликован в Stack Overflow и оставался у меня на радаре до сих пор, когда очевидно, что первоначальный алгоритм для этой проблемы был снова забыт. Лучшее решение, доступное на этой странице переполнения стека, - это модифицированная версия моего решения, возможно, разделенная на несколько поколений. К сожалению, модификации разрушили оптимальность решения. Фактически, изменяя структуру цикла по сравнению с моим оригиналом, модифицированное решение выполняет совершенно ненужный дополнительный шаг экспоненциального дублирования (таким образом, объединяя наибольшую строку, использованную в правильном ответе, с самим собой дополнительное время, а затем отбрасывая его).

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

Техника: избегайте ссылок на объекты или свойства объектов

Чтобы проиллюстрировать, как работает этот метод, мы используем реальную функцию JavaScript, которая создает строки любой необходимой длины. И, как мы увидим, можно добавить больше оптимизаций!

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

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

Оригинальный код для создания строк stringFill1()

function stringFill1(x, n) { 
    var s = ''; 
    while (s.length < n) s += x; 
    return s; 
} 
/* Example of output: stringFill1('x', 3) == 'xxx' */ 

Синтаксис здесь понятен. Как вы можете видеть, мы уже использовали локальные переменные функции, прежде чем перейти к дальнейшей оптимизации.

Имейте s.lengthв виду, что в коде есть одна невинная ссылка на свойство объекта, которое ухудшает его производительность. Еще хуже то, что использование этого свойства объекта уменьшает простоту программы, предполагая, что читатель знает о свойствах строковых объектов JavaScript.

Использование этого свойства объекта разрушает общность компьютерной программы. Программа предполагает, что это xдолжна быть строка длиной один. Это ограничивает применение stringFill1()функции чем-либо, кроме повторения отдельных символов. Даже отдельные символы не могут использоваться, если они содержат несколько байтов, таких как объект HTML &nbsp;.

Худшая проблема, вызванная этим ненужным использованием свойства объекта, заключается в том, что функция создает бесконечный цикл, если проверяется на пустой входной строке x. Чтобы проверить общность, примените программу к минимально возможному количеству ввода. У программы, которая аварийно завершает работу при запросе превышения объема доступной памяти, есть оправдание. Такая программа, которая вылетает, когда ее просят ничего не производить, недопустима. Иногда красивый код - это ядовитый код.

Простота может быть неоднозначной целью компьютерного программирования, но в целом это не так. Когда программе не хватает разумного уровня общности, нельзя сказать: «Программа достаточно хороша, насколько это возможно». Как видите, использование string.lengthсвойства не позволяет этой программе работать в общих настройках, и фактически неверная программа готова вызвать сбой браузера или системы.

Есть ли способ улучшить производительность этого JavaScript, а также решить эти две серьезные проблемы?

Конечно. Просто используйте целые числа.

Оптимизированный код для создания строк stringFill2()

function stringFill2(x, n) { 
    var s = ''; 
    while (n-- > 0) s += x; 
    return s; 
} 

Временной код для сравнения stringFill1()иstringFill2()

function testFill(functionToBeTested, outputSize) { 
    var i = 0, t0 = new Date(); 
    do { 
        functionToBeTested('x', outputSize); 
        t = new Date() - t0; 
        i++; 
    } while (t < 2000); 
    return t/i/1000; 
} 
seconds1 = testFill(stringFill1, 100); 
seconds2 = testFill(stringFill2, 100); 

Успех до сих пор stringFill2()

stringFill1()для заполнения 100-байтовой строки требуется 47,297 микросекунд (миллионные доли секунды) и stringFill2()27,68 микросекунд для того же. Это почти удваивает производительность, избегая ссылки на свойство объекта.

Техника: избегайте добавления коротких строк в длинные

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

Да, мы можем достичь этой цели. Прямо сейчас нам нужно объяснить, как мы не добавляем короткие строки в длинные.

Краткосрочное поведение представляется довольно хорошим по сравнению с нашей первоначальной функцией. Специалистам по информатике нравится анализировать «асимптотическое поведение» алгоритма функции или компьютерной программы, что означает изучение его долговременного поведения путем тестирования его с большими входными данными. Иногда, не проводя дальнейшие тесты, никогда не узнаешь, как можно улучшить компьютерную программу. Чтобы увидеть, что произойдет, мы собираемся создать 200-байтовую строку.

Проблема, которая обнаруживается с stringFill2()

Используя нашу функцию синхронизации, мы находим, что время увеличивается до 62,54 микросекунд для 200-байтовой строки по сравнению с 27,68 для 100-байтовой строки. Кажется, что нужно удвоить время, чтобы выполнить вдвое больше работы, но вместо этого оно утроится или увеличится в четыре раза. Из опыта программирования этот результат кажется странным, потому что, во всяком случае, функция должна быть немного быстрее, поскольку работа выполняется более эффективно (200 байт на вызов функции, а не 100 байт на вызов функции). Эта проблема связана с коварным свойством строк JavaScript: строки JavaScript являются «неизменяемыми».

Неизменяемый означает, что вы не можете изменить строку после ее создания. Добавляя по одному байту за раз, мы не тратим еще один байт на усилия. Мы фактически воссоздаем всю строку плюс еще один байт.

Фактически, чтобы добавить еще один байт к 100-байтовой строке, требуется работа в 101 байт. Давайте кратко проанализируем вычислительные затраты на создание строки Nбайтов. Стоимость добавления первого байта составляет 1 единицу вычислительного усилия. Стоимость добавления второго байта - не одна единица, а 2 единицы (копирование первого байта в новый строковый объект, а также добавление второго байта). Третий байт требует 3 единицы стоимости и т. Д.

C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2), Символ O(N^2)произносится как Big O из N в квадрате, и это означает, что вычислительные затраты в долгосрочной перспективе пропорциональны квадрату длины строки. Для создания 100 символов требуется 10000 единиц работы, а для создания 200 символов требуется 40000 единиц работы.

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

(Историческая справка: этот анализ не обязательно применяется к строкам в исходном коде, например html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n', поскольку компилятор исходного кода JavaScript может объединять строки перед тем, как превратить их в строковый объект JavaScript. Всего несколько лет назад реализация KJS JavaScript зависал или зависал при загрузке длинных строк исходного кода, соединенных знаками плюса. Поскольку время вычислений было O(N^2)несложным, создавать веб-страницы, которые перегружали веб-браузер Konqueror или Safari, в которых использовалось ядро ​​движка JavaScript KJS. Сначала я столкнулся с этой проблемой, когда разрабатывал язык разметки и синтаксический анализатор языка разметки JavaScript, а затем обнаружил причину проблемы, когда написал свой сценарий для JavaScript Include.)

Очевидно, что это быстрое снижение производительности является огромной проблемой. Как мы можем справиться с этим, учитывая, что мы не можем изменить способ обработки строк в JavaScript как неизменных объектов в JavaScript? Решение состоит в том, чтобы использовать алгоритм, который воссоздает строку как можно меньше раз.

Чтобы уточнить, наша цель состоит в том, чтобы избежать добавления коротких строк в длинные строки, так как для добавления короткой строки вся длинная строка также должна дублироваться.

Как алгоритм работает, чтобы избежать добавления коротких строк в длинные строки

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

Например, чтобы сделать строку длины N = 9:

x = 'x'; 
s = ''; 
s += x; /* Now s = 'x' */ 
x += x; /* Now x = 'xx' */ 
x += x; /* Now x = 'xxxx' */ 
x += x; /* Now x = 'xxxxxxxx' */ 
s += x; /* Now s = 'xxxxxxxxx' as desired */

Для этого требовалось создать строку длины 1, создать строку длины 2, создать строку длины 4, создать строку длины 8 и, наконец, создать строку длины 9. Сколько затрат мы сэкономили?

Старая стоимость C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.

Новая стоимость C(9) = 1 + 2 + 4 + 8 + 9 = 24.

Обратите внимание, что мы должны были добавить строку длины 1 к строке длины 0, затем строку длины 1 к строке длины 1, затем строку длины 2 к строке длины 2, затем строку длины 4 до строки длины 4, затем строки длины 8 до строки длины 1, чтобы получить строку длины 9. То, что мы делаем, можно суммировать, избегая добавления коротких строк в длинные строки, или в других слова, пытающиеся объединить строки, которые имеют одинаковую или почти равную длину.

Для старой вычислительной стоимости мы нашли формулу N(N+1)/2. Есть ли формула для новой стоимости? Да, но это сложно. Важно то, что это так O(N), и удвоение длины строки приблизительно удвоит объем работы, а не увеличит ее в четыре раза.

Код, который реализует эту новую идею, почти так же сложен, как и формула для вычислительных затрат. Когда вы читаете это, помните, что это >>= 1означает сдвиг вправо на 1 байт. Так что, если n = 10011это двоичное число, то n >>= 1приводит к значению n = 1001.

Другая часть кода, которую вы можете не распознать - это побитовый оператор и написано &. Выражение n & 1оценивается как истина, если последняя двоичная цифра nравна 1, и ложь, если последняя двоичная цифра nравна 0.

Новая высокоэффективная stringFill3()функция

function stringFill3(x, n) { 
    var s = ''; 
    for (;;) { 
        if (n & 1) s += x; 
        n >>= 1; 
        if (n) x += x; 
        else break; 
    } 
    return s; 
} 

Это выглядит некрасиво для неопытного глаза, но его производительность не что иное, как прекрасный.

Давайте посмотрим, насколько хорошо эта функция выполняет. После просмотра результатов, скорее всего, вы никогда не забудете разницу между O(N^2)алгоритмом и O(N)алгоритмом.

stringFill1()для создания 200-байтовой строки требуется 88,7 микросекунды (миллионные доли секунды), stringFill2()62,54 и stringFill3()4,608. Что сделало этот алгоритм намного лучше? Все функции воспользовались преимуществами использования локальных переменных функций, но использование второго и третьего методов оптимизации добавило в двадцать раз улучшение производительности stringFill3().

Более глубокий анализ

Что заставляет эту особую функцию вырывать конкуренцию из воды?

Как я уже упоминал, причина того, что обе эти функции, stringFill1()и stringFill2()работают так медленно, состоит в том, что строки JavaScript являются неизменяемыми. Память не может быть перераспределена, чтобы допускать добавление еще одного байта за раз к строковым данным, хранящимся в JavaScript. Каждый раз, когда в конец строки добавляется еще один байт, вся строка восстанавливается от начала до конца.

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

Например, чтобы создать 16-буквенную байтовую строку, сначала будет предварительно вычислена двухбайтовая строка. Затем двухбайтовая строка будет использоваться повторно для предварительного вычисления четырехбайтовой строки. Затем четырехбайтовая строка будет повторно использована для предварительного вычисления восьмибайтовой строки. Наконец, две восьмибайтовые строки будут повторно использованы для создания желаемой новой строки из 16 байтов. Всего нужно было создать четыре новые строки, одну из длины 2, одну из длины 4, одну из длины 8 и одну из длины 16. Общая стоимость составляет 2 + 4 + 8 + 16 = 30.

В долгосрочной перспективе эта эффективность может быть вычислена путем сложения в обратном порядке и использования геометрического ряда, начинающегося с первого члена a1 = N и имеющего общее отношение r = 1/2. Сумма геометрического ряда определяется как a_1 / (1-r) = 2N.

Это более эффективно, чем добавление одного символа для создания новой строки длиной 2, создания новой строки длиной 3, 4, 5 и т. Д. До 16. Предыдущий алгоритм использовал этот процесс добавления одного байта за раз и общая стоимость этого будет n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.

Очевидно, что 136 - это намного большее число, чем 30, и поэтому предыдущий алгоритм требует гораздо, гораздо больше времени для построения строки.

Чтобы сравнить два метода, вы можете увидеть, насколько быстрее рекурсивный алгоритм (также называемый «разделяй и властвуй») на строке длиной 123 457. На моем компьютере с FreeBSD этот алгоритм, реализованный в stringFill3()функции, создает строку за 0,001058 секунд, тогда как исходная stringFill1()функция создает строку за 0,0808 секунды. Новая функция в 76 раз быстрее.

Разница в производительности увеличивается по мере увеличения длины строки. В пределе, когда создаются все большие и большие строки, исходная функция ведет себя примерно как C1(постоянное) время N^2, а новая функция ведет себя как C2(постоянное) время N.

Из нашего эксперимента мы можем определить значение C1быть C1 = 0.0808 / (123457)2 = .00000000000530126997и значение C2быть C2 = 0.001058 / 123457 = .00000000856978543136. За 10 секунд новая функция может создать строку, содержащую 1 166 890 359 символов. Чтобы создать эту же строку, старой функции потребуется 7,218,384 секунды.

Это почти три месяца по сравнению с десятью секундами!

Я отвечаю только (с опозданием на несколько лет), потому что мое первоначальное решение этой проблемы распространялось по Интернету уже более 10 лет, и, видимо, все еще плохо понимают те немногие, кто его помнит. Я думал, что, написав статью об этом здесь, я помогу:

Оптимизация производительности для высокоскоростного JavaScript / Page 3

К сожалению, некоторые другие решения, представленные здесь, все еще являются некоторыми из тех, которые потребовали бы три месяца, чтобы произвести то же самое количество продукции, которое правильное решение создает за 10 секунд.

Я хочу потратить время на то, чтобы воспроизвести часть статьи здесь в качестве канонического ответа о переполнении стека.

Обратите внимание, что наиболее эффективный алгоритм здесь явно основан на моем алгоритме и, вероятно, унаследован от чужой адаптации 3-го или 4-го поколения. К сожалению, модификации привели к снижению его производительности. Вариант моего решения, представленный здесь, возможно, не понимал моего запутанного for (;;)выражения, которое выглядит как основной бесконечный цикл сервера, написанного на C, и которое было просто разработано, чтобы позволить аккуратно расположить оператор останова для управления циклом, самый компактный способ Избегайте экспоненциальной репликации строки еще один лишний раз.

Джозеф Майерс
источник
4
Этот ответ не должен был получить столько голосов. Прежде всего, претензии Иосифа на собственность являются насмешкой. Основному алгоритму 3700 лет.
artistoex
2
Во-вторых, он содержит много дезинформации. Современные реализации Javascript даже не касаются содержимого строки при выполнении конкатенации (v8 представляет конкатенированные строки как объект типа ConsString). Все остальные улучшения незначительны (с точки зрения асимптотической сложности).
artistoex
3
Ваша идея о том, как соединяются строки, неверна. Чтобы объединить две строки, Javascript вообще не читает байты составляющих строк. Вместо этого он просто создает объект, который ссылается на левую и правую части. Вот почему последняя конкатенация в цикле не дороже, чем первые.
artistoex
3
Разумеется, это приводит к затратам на индексирование строки, превышающим O (1), поэтому последующая конкатенация может быть сглажена, что действительно требует дальнейшей оценки.
artistoex
1
Это было отличное чтение. Вы должны написать книгу об эффективности и все такое!
39

Этот довольно эффективный

String.prototype.repeat = function(times){
    var result="";
    var pattern=this;
    while (times > 0) {
        if (times&1)
            result+=pattern;
        times>>=1;
        pattern+=pattern;
    }
    return result;
};
artistoex
источник
11
@Olegs, я думаю, что идея голосования меньше, чем голосование за человека или за творческий потенциал человека (что действительно достойно одобрения), но идея состоит в том, чтобы проголосовать за наиболее полное решение, чтобы его можно было легко найти на верхней части списка, без необходимости читать все ответы в поиске идеального. (Потому что, к сожалению, у всех нас есть ограниченное время ...)
Сорин Постельнику
38

Хорошие новости! String.prototype.repeatв настоящее время является частью JavaScript .

"yo".repeat(2);
// returns: "yoyo"

Этот метод поддерживается всеми основными браузерами, кроме Internet Explorer и Android Webview. Обновленный список см. В разделе MDN: String.prototype.repeat> Совместимость браузера .

MDN имеет полифилл для браузеров без поддержки.

Андре Ласло
источник
Спасибо, что сообщили о текущем положении дел, хотя я думаю, что полизаполнение в Mozilla является сложным для большинства нужд (я предполагаю, что они пытаются имитировать поведение своей эффективной реализации на C) - поэтому не будет действительно отвечать требованию OP о краткости. Любой из других подходов, настроенных как полифилы, должен быть более лаконичным ;-)
Guss
2
Определенно! Но использование встроенного должно быть самой краткой версией. Поскольку полифиллы в основном являются бэк-портами, они могут быть немного сложными для обеспечения совместимости со спецификациями (или предлагаемыми спецификациями, в данном случае). Я добавил это для полноты, это зависит от ОП, чтобы решить, какой метод использовать, я думаю.
Андре Ласло
19

String.prototype.repeat теперь является стандартом ES6.

'abc'.repeat(3); //abcabcabc
Льюис
источник
отлично! ... но не для меня (это не поддерживается на ios <9): kangax.github.io/compat-table/es6
Бенджамин
@ Benjamin Используйте полифилл по ссылке.
Льюис
Я думаю, что должен быть закрепленный ответ.
test30
17

Расширяя решение П.Бейли :

String.prototype.repeat = function(num) {
    return new Array(isNaN(num)? 1 : ++num).join(this);
    }

Таким образом, вы должны быть защищены от неожиданных типов аргументов:

var foo = 'bar';
alert(foo.repeat(3));              // Will work, "barbarbar"
alert(foo.repeat('3'));            // Same as above
alert(foo.repeat(true));           // Same as foo.repeat(1)

alert(foo.repeat(0));              // This and all the following return an empty
alert(foo.repeat(false));          // string while not causing an exception
alert(foo.repeat(null));
alert(foo.repeat(undefined));
alert(foo.repeat({}));             // Object
alert(foo.repeat(function () {})); // Function

РЕДАКТИРОВАТЬ: Кредиты Джероне за его элегантную ++numидею!

antichris
источник
2
Немного String.prototype.repeat = function(n){return new Array(isNaN(n) ? 1 : ++n).join(this);}
поменял
В любом случае, согласно этому тесту ( jsperf.com/string-repeat/2 ), выполнение простого цикла for с конкатенацией строк в Chrome выглядит намного быстрее по сравнению с использованием Array.join. Разве это не смешно ?!
Марко Демайо
8

использование Array(N+1).join("string_to_repeat")

Калпеш Патель
источник
Мне это нравится. ИДК, почему это не там.
Джо Томас
любить это. так просто и чисто
ekkis
5
/**  
@desc: repeat string  
@param: n - times  
@param: d - delimiter  
*/

String.prototype.repeat = function (n, d) {
    return --n ? this + (d || '') + this.repeat(n, d) : '' + this
};

это как повторить строку несколько раз с помощью делитера.

BitOfUniverse
источник
4

Вот улучшение на 5-7% по ответу обезумевшего.

Разверните цикл, остановившись на нем, count > 1и выполните дополнительный result += pattnernконкат после цикла. Это позволит избежать финальных циклов, ранее не использованных, pattern += patternбез необходимости использования дорогой проверки if. Конечный результат будет выглядеть так:

String.prototype.repeat = function(count) {
    if (count < 1) return '';
    var result = '', pattern = this.valueOf();
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    result += pattern;
    return result;
};

И вот скрипучая скрипка раздвоена для развернутой версии: http://jsfiddle.net/wsdfg/

Деннис
источник
2
function repeat(s, n) { var r=""; for (var a=0;a<n;a++) r+=s; return r;}
Джоэл Коухорн
источник
2
Разве это не дорогая конкатенация строк? По крайней мере, в случае с Java.
Виджей Дев
Почему да, они есть. Тем не менее, он не может быть оптимизирован в javarscript. :(
McTrafik
Что об этом спектакле improvent: var r=s; for (var a=1;...:)))) В любом случае , согласно этому тесту ( jsperf.com/string-repeat/2 ) делая простой цикл с струнной concatanation как то , что вы предложили , кажется, намного быстрее по сравнению с Chrome с использованием массива .присоединиться.
Марко Демайо
@VijayDev - не в соответствии с этим тестом: jsperf.com/ultimate-concat-vs-join
jbyrd
2

Испытания различных методов:

var repeatMethods = {
    control: function (n,s) {
        /* all of these lines are common to all methods */
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return '';
    },
    divideAndConquer:   function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        with(Math) { return arguments.callee(floor(n/2), s)+arguments.callee(ceil(n/2), s); }
    },
    linearRecurse: function (n,s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return s+arguments.callee(--n, s);
    },
    newArray: function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return (new Array(isNaN(n) ? 1 : ++n)).join(s);
    },
    fillAndJoin: function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        var ret = [];
        for (var i=0; i<n; i++)
            ret.push(s);
        return ret.join('');
    },
    concat: function (n,s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        var ret = '';
        for (var i=0; i<n; i++)
            ret+=s;
        return ret;
    },
    artistoex: function (n,s) {
        var result = '';
        while (n>0) {
            if (n&1) result+=s;
            n>>=1, s+=s;
        };
        return result;
    }
};
function testNum(len, dev) {
    with(Math) { return round(len+1+dev*(random()-0.5)); }
}
function testString(len, dev) {
    return (new Array(testNum(len, dev))).join(' ');
}
var testTime = 1000,
    tests = {
        biggie: { str: { len: 25, dev: 12 }, rep: {len: 200, dev: 50 } },
        smalls: { str: { len: 5, dev: 5}, rep: { len: 5, dev: 5 } }
    };
var testCount = 0;
var winnar = null;
var inflight = 0;
for (var methodName in repeatMethods) {
    var method = repeatMethods[methodName];
    for (var testName in tests) {
        testCount++;
        var test = tests[testName];
        var testId = methodName+':'+testName;
        var result = {
            id: testId,
            testParams: test
        }
        result.count=0;

        (function (result) {
            inflight++;
            setTimeout(function () {
                result.start = +new Date();
                while ((new Date() - result.start) < testTime) {
                    method(testNum(test.rep.len, test.rep.dev), testString(test.str.len, test.str.dev));
                    result.count++;
                }
                result.end = +new Date();
                result.rate = 1000*result.count/(result.end-result.start)
                console.log(result);
                if (winnar === null || winnar.rate < result.rate) winnar = result;
                inflight--;
                if (inflight==0) {
                    console.log('The winner: ');
                    console.log(winnar);
                }
            }, (100+testTime)*testCount);
        }(result));
    }
}
Fordi
источник
2

Вот безопасная версия JSLint

String.prototype.repeat = function (num) {
  var a = [];
  a.length = num << 0 + 1;
  return a.join(this);
};
Эрик Айгнер
источник
2

Для всех браузеров

Это примерно так кратко:

function repeat(s, n) { return new Array(n+1).join(s); }

Если вы также заботитесь о производительности, это гораздо лучший подход:

function repeat(s, n) { var a=[],i=0;for(;i<n;)a[i++]=s;return a.join(''); }

Если вы хотите сравнить производительность обоих вариантов, посмотрите эту Fiddle и эту Fiddle для тестов производительности. Во время моих собственных тестов второй вариант был примерно в 2 раза быстрее в Firefox и примерно в 4 раза быстрее в Chrome!

Только для современных браузеров:

В современных браузерах вы также можете сделать это:

function repeat(s,n) { return s.repeat(n) };

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

К сожалению, это не работает ни в одной версии Internet Explorer. Числа в таблице указывают первую версию браузера, которая полностью поддерживает метод:

введите описание изображения здесь

Джон Слегерс
источник
2
function repeat(pattern, count) {
  for (var result = '';;) {
    if (count & 1) {
      result += pattern;
    }
    if (count >>= 1) {
      pattern += pattern;
    } else {
      return result;
    }
  }
}

Вы можете проверить это в JSFiddle . Сравнение с хакерами Array.joinи моим, грубо говоря, от 10 (Chrome) до 100 (Safari) до 200 (Firefox) раз быстрее (в зависимости от браузера).

николай
источник
2

Просто еще одна функция повтора:

function repeat(s, n) {
  var str = '';
  for (var i = 0; i < n; i++) {
    str += s;
  }
  return str;
}
oboshto
источник
2

ES2015 было понято это repeat() метод!

http://www.ecma-international.org/ecma-262/6.0/#sec-string.prototype.repeat
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/ Строка / повтор
http://www.w3schools.com/jsref/jsref_repeat.asp

/** 
 * str: String
 * count: Number
 */
const str = `hello repeat!\n`, count = 3;

let resultString = str.repeat(count);

console.log(`resultString = \n${resultString}`);
/*
resultString = 
hello repeat!
hello repeat!
hello repeat!
*/

({ toString: () => 'abc', repeat: String.prototype.repeat }).repeat(2);
// 'abcabc' (repeat() is a generic method)

// Examples

'abc'.repeat(0);    // ''
'abc'.repeat(1);    // 'abc'
'abc'.repeat(2);    // 'abcabc'
'abc'.repeat(3.5);  // 'abcabcabc' (count will be converted to integer)
// 'abc'.repeat(1/0);  // RangeError
// 'abc'.repeat(-1);   // RangeError

xgqfrms
источник
1

Это может быть самый маленький рекурсивный: -

String.prototype.repeat = function(n,s) {
s = s || ""
if(n>0) {
   s += this
   s = this.repeat(--n,s)
}
return s}
Джон
источник
1

Простая рекурсивная конкатенация

Я просто хотел дать ему удар, и сделал это:

function ditto( s, r, c ) {
    return c-- ? ditto( s, r += s, c ) : r;
}

ditto( "foo", "", 128 );

Я не могу сказать, что много думал об этом, и это, вероятно, показывает :-)

Это возможно лучше

String.prototype.ditto = function( c ) {
    return --c ? this + this.ditto( c ) : this;
};

"foo".ditto( 128 );

И это очень похоже на уже опубликованный ответ - я знаю это.

Но зачем вообще быть рекурсивным?

А как насчет небольшого поведения по умолчанию тоже?

String.prototype.ditto = function() {
    var c = Number( arguments[ 0 ] ) || 2,
        r = this.valueOf();
    while ( --c ) {
        r += this;
    }
    return r;
}

"foo".ditto();

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

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

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

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

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

«Так что, если я не знаю, как это работает ?!»

Шутки в сторону?

JavaScript страдает одной из своих сильных сторон; он очень терпим к плохому поведению и настолько гибок, что будет наклоняться назад, чтобы возвращать результаты, когда это могло бы быть лучше для всех, если бы оно сломалось!

"С большой властью приходит большая ответственность" ;-)

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

Эти «идеальные» алгоритмы забавны и все, но «один размер подходит всем» редко, если вообще когда-либо, будет лучше, чем сделанный на заказ.

Эта проповедь была принесена вам из-за недостатка сна и преходящего интереса. Иди и код!

Фред Гандт
источник
1

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

Во-вторых, как отметил Андре Ласло, String.repeat является частью ECMAScript 6 и уже доступен в нескольких популярных реализациях, поэтому самая краткая реализация String.repeat- не реализовывать его ;-)

Наконец, если вам нужно поддерживать хосты, которые не предлагают реализацию ECMAScript 6, полифил MDN, упомянутый Андре Ласло, совсем не лаконичен.

Итак, без лишних слов - вот мой краткий polyfill:

String.prototype.repeat = String.prototype.repeat || function(n){
    return n<=1 ? this : this.concat(this.repeat(n-1));
}

Да, это рекурсия. Мне нравятся рекурсии - они просты, и если все сделано правильно, их легко понять. Что касается эффективности, если язык поддерживает ее, они могут быть очень эффективными, если написаны правильно.

Из моих тестов этот метод на ~ 60% быстрее, чем Array.joinподход. Хотя, очевидно, это нигде не соответствует реализации disfated, это гораздо проще, чем оба.

Моя тестовая установка - это узел v0.10, использующий «строгий режим» (я думаю, что он разрешает какую-то TCO ), вызывая repeat(1000)строку из 10 символов миллион раз.

Guss
источник
1

Если вы считаете, что все эти определения прототипов, создание массивов и операции соединения излишни, просто используйте однострочный код там, где вам это нужно. Строка S, повторяющаяся N раз:

for (var i = 0, result = ''; i < N; i++) result += S;
Semra
источник
3
Код должен быть читабельным. Если вы буквально только каждый собираетесь использовать его один раз, то отформатируйте его правильно (или используйте Array(N + 1).join(str)метод, если это не является узким местом производительности). Если есть малейший шанс, что вы собираетесь использовать его дважды, переместите его в функцию с соответствующим именем.
cloudfeet
1

Используйте функциональность утилиты Lodash для Javascript, например, повторяющиеся строки.

Lodash обеспечивает хорошую производительность и совместимость с ECMAScript.

Я настоятельно рекомендую его для разработки пользовательского интерфейса, и он хорошо работает и на стороне сервера.

Вот как повторить строку "yo" 2 раза, используя Lodash:

> _.repeat('yo', 2)
"yoyo"
L3x
источник
0

Рекурсивное решение с использованием разделяй и властвуй:

function repeat(n, s) {
    if (n==0) return '';
    if (n==1 || isNaN(n)) return s;
    with(Math) { return repeat(floor(n/2), s)+repeat(ceil(n/2), s); }
}
Fordi
источник
0

Я пришел сюда случайно, и у меня никогда не было причин повторять символ в javascript раньше.

Я был впечатлен тем, как artistoex сделал это, и разочаровал результаты. Я заметил, что последний конкат строки не нужен, как также указал Деннис.

Я заметил еще несколько вещей, когда играл с разбитым семплом.

Результаты варьировались изрядное количество, часто в пользу последнего запуска, и подобные алгоритмы часто жокей для позиции. Одна из вещей, которые я изменил, была вместо того, чтобы использовать сгенерированный JSLitmus счет в качестве начального числа для вызовов; так как счетчик был сгенерирован по-разному для различных методов, я поместил в индекс. Это сделало вещь намного более надежной. Затем я посмотрел, чтобы в функции передавались строки различного размера. Это предотвратило некоторые изменения, которые я видел, когда некоторые алгоритмы работали лучше на одиночных символах или меньших строках. Тем не менее, лучшие 3 метода все хорошо, независимо от размера строки.

Вилочный тестовый набор

http://jsfiddle.net/schmide/fCqp3/134/

// repeated string
var string = '0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789';
// count paremeter is changed on every test iteration, limit it's maximum value here
var maxCount = 200;

var n = 0;
$.each(tests, function (name) {
    var fn = tests[name];
    JSLitmus.test(++n + '. ' + name, function (count) {
        var index = 0;
        while (count--) {
            fn.call(string.slice(0, index % string.length), index % maxCount);
            index++;
        }
    });
    if (fn.call('>', 10).length !== 10) $('body').prepend('<h1>Error in "' + name + '"</h1>');
});

JSLitmus.runAll();

Затем я включил исправление Денниса и решил посмотреть, смогу ли я найти способ получить больше.

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

// final: growing pattern + prototypejs check (count < 1)
'final avoid': function (count) {
    if (!count) return '';
    if (count == 1) return this.valueOf();
    var pattern = this.valueOf();
    if (count == 2) return pattern + pattern;
    if (count == 3) return pattern + pattern + pattern;
    var result;
    if (count & 1) result = pattern;
    else result = '';
    count >>= 1;
    do {
        pattern += pattern;
        if (count & 1) result += pattern;
        count >>= 1;
    } while (count > 1);
    return result + pattern + pattern;
}

Это привело к улучшению на 1-2% по сравнению с исправлением Денниса. Тем не менее, различные прогоны и разные браузеры будут демонстрировать достаточно справедливую дисперсию, что этот дополнительный код, вероятно, не стоит усилий по сравнению с двумя предыдущими алгоритмами.

График

Изменить: я сделал это в основном под Chrome. Firefox и IE часто отдают предпочтение Деннису на пару%.

Эндрю Халлендорф
источник
0

Простой метод:

String.prototype.repeat = function(num) {
    num = parseInt(num);
    if (num < 0) return '';
    return new Array(num + 1).join(this);
}
Эдуардо Куомо
источник
0

Люди слишком усложняют это до смешного или бесполезно. Массивы? Рекурсия? Ты меня разыгрываешь.

function repeat (string, times) {
  var result = ''
  while (times-- > 0) result += string
  return result
}

Редактировать. Я провел несколько простых тестов, чтобы сравнить их с побитовой версией, опубликованной artistoex / disfated и другими людьми. Последний был лишь незначительно быстрее, но на несколько порядков эффективнее с точки зрения памяти. Для 1000000 повторений слова «бла» процесс Node увеличился до 46 мегабайт с простым алгоритмом конкатенации (см. Выше), но только с 5,5 мегабайтами с логарифмическим алгоритмом. Последний, безусловно, путь. Переписываю это ради ясности:

function repeat (string, times) {
  var result = ''
  while (times > 0) {
    if (times & 1) result += string
    times >>= 1
    string += string
  }
  return result
}
Нело Митраним
источник
У вас есть лишняя string += stringполовина времени.
Николай
0

Конкатенация строк на основе числа.

function concatStr(str, num) {
   var arr = [];

   //Construct an array
   for (var i = 0; i < num; i++)
      arr[i] = str;

   //Join all elements
   str = arr.join('');

   return str;
}

console.log(concatStr("abc", 3));

Надеюсь, это поможет!

loxsat
источник
0

С ES8 вы также можете использовать padStartили padEndдля этого. например.

var str = 'cat';
var num = 23;
var size = str.length * num;
"".padStart(size, str) // outputs: 'catcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcat'
wizzfizz94
источник