Я ранее ошибочно попросил str.count, когда я действительно имел в виду str.length. Спасибо ответчикам за то, что вы вернулись ко мнеВ рубине, какая временная стоимость str.length?
Является ли это постоянной операцией времени или линейным временем? Я знаю, что в Java это постоянное время, а C - линейное время, согласно In Java, for a string x, what is the runtime cost of s.length()? Is it O(1) or O(n)?, но не уверен, что происходит в Ruby.
String#count подсчитывает количество вхождений (набора) подстрок в строке. Для этого должен сравнить каждый символ с набором предикатов, другого выхода нет.
Он не может быть быстрее, чем O (n). Тривиальная реализация - O (n), поэтому для того, чтобы сделать медленнее, чем O (n), вы должны быть лишними глупостями и выполнять дополнительную работу. Таким образом, поскольку он не может быть быстрее, чем O (n), и мы можем предположить, что никто не был бы глуп или злонамерен, чтобы сделать его медленнее, чем O (n), мы можем с уверенностью заключить, что это O (n).
Однако это только вывод. Это не гарантия. Спецификация языка Ruby не гарантирует производительность. Но вы можете быть уверены, что реализация Ruby, где она не O (n), будет высмеиваться и просто не использоваться и не умирать.
Не совсем, он не учитывает подстроки, а вхождения символов из пересечения всех параметров. Странно, я знаю. – akuhn
@akuhn Это очень похоже на ['String # tr'] (https://ruby-doc.org/core-2.4.0/String.html#method-i-tr) таким образом с помощью этой нотации, основанной на Perl. – tadman
Он фактически использует 'tr_find' и' tr_setup_table' внутренне. – akuhn
Сложность O(n + m)
Где n является размером строки и m этого числа параметров набора символов.
O(m) для создания справочной таблицы/хэш из аргументовO(n) * O(1) для сравнения входной строки с таблицы поиска/хэшn или m может быть доминирующим фактором.Если же вы имеете в виду String#length то O(1)
Почему бы не проверить их источник? – Li357
Источник сообщает только, что делает конкретная версия одной конкретной реализации. Он ничего не говорит о гарантиях, связанных с языковой спецификацией. Я считаю, что сейчас около 5 реализаций Ruby в дикой природе. (Ну, есть еще много, но 5, которые являются промышленно-прочными, готовыми к производству, все еще поддерживаются и развиваются и в реальном реальном использовании.) –
Вы действительно имеете в виду 'String # count', поскольку ваше название спрашивает, или вы имеете в виду 'String # length', как указывает связанный вопрос? – pilcrow