Описание задания:
Напишите функцию commonPrefix
, который принимает в качестве параметра две строки и возвращает общий префикс.
Пример: параметры abcdef
и abc1gv
вернется abc
.
Моя реализация:
fun commonPrefix(str1: String, str2: String): String {
var sRet = ""
var i = 0
val length = if (str1.length >= str2.length)
str1.length else str2.length
while (i < length) {
if (str1.take(i + 1) != str2.take(i + 1)) {
return sRet
}
sRet += str1[i++]
}
return sRet
}
val first = "abcdef"
val sec = "abc1ef"
println(commonPrefix(first, sec))
Моя реализация сделана хорошо? Где это можно было оптимизировать?
1 ответ
Первое, что мне бросается в глаза, это то, что обычно лучше использовать стандартные функции, чем использовать собственные даже для тривиальных вещей. Например
val length = if (str1.length >= str2.length)
str1.length else str2.length
можно было бы лучше написать как
val length = maxOf(str1.length, str2.length)
Люди часто говорят об этом, думая об эффективности, но обычно это отвлекающий маневр. Современные компиляторы довольно хороши в оптимизации, и различия, вероятно, будут минимальными, если они вообще существуют.
Вместо этого главная причина использования именованной функции — удобочитаемость. В первом примере я должен остановиться и собрать воедино то, что он на самом деле делает. В последнем я могу сразу увидеть и продолжить бегло читать код.
Исходя из этого, теперь я вижу, что это неправильный чек. По логике, общий префикс не может быть длиннее, чем короче из двух строк. Итак, теперь, когда я ясно вижу, что существующий код эквивалентен maxOf
звоните, я понимаю, что это, вероятно, должно быть minOf
вызов.
Второе, что бросается в глаза, — это эффективность вашего цикла. Каждый раз, когда вы проходите цикл, вы (1) сравниваете весь префикс и (2) обновляете возвращаемое значение. То есть в первый раз вы сравниваете «а» с «а», и это нормально. К третьему раунду вы сравниваете «abc» с «abc» и, таким образом, переделываете работу по сравнению «a» и «b». Затем вы берете свой предыдущий sRet
объект «ab», копируя его и «c» в новый строковый объект и присваивая его обратно sRet
. Если вы знакомы с большой нотацией O, это означает, что ваша общая функция становится O (n2) в длине префикса. Это также означает, что вы создаете и выбрасываете множество маленьких временных объектов.
Тебе тоже не нужно этого делать. К тому времени, когда вы дойдете до третьего шага в цикле, вы уже знаете, что «ab» соответствует «ab», поэтому вам не нужно проверять снова. Вместо того, чтобы использовать take
чтобы получить префикс, используйте get
чтобы получить собственно письмо. Тогда вы можете просто проверить «c» против «c».
Что касается проблемы множества одноразовых отходов sRet
объекты, обычно советуют использовать StringBuilder. В отличие от строки, StringBuilder специально создан с мыслью, что вы будете изменять его по мере продвижения. Для этого он намного эффективнее. тем не мение, в этом случае вам не нужно этого делать, потому что вам не нужно sRet
вообще! В конце концов, оба str1
и str2
содержат префикс, который вам нужен. У вас уже есть (и вы использовали!) Функцию для вывода префикса. Так что просто считайте по двум строкам, сравнивая по одному символу за раз. Как только вы узнаете количество одинаковых символов, take
Это.
Последнее, что я хотел бы упомянуть, — это тестирование. Вы указали одну пару входных данных для своей функции. Это хорошо и помогает проиллюстрировать проблему. Также стоит подумать, какие еще примеры стоит проверить. В общем, для такой функции я бы посоветовал протестировать как минимум следующее:
str1 | ул2 | причина |
---|---|---|
abc | xyz | Легко получить ошибку, которая не работает, когда префикс пуст. |
а | б | Легко получить ошибку, которая портит ввод одиночных символов |
а | а | То же, что и выше |
abc | abc | Легко получить ошибку, которая порождает идентичные строки |
abxyz | abc | Вы пытаетесь поддерживать вводы разной длины, поэтому это следует протестировать. |
abc | abxyz | То же, что и выше |
abcde | abc | Одна строка является префиксом другой |
Пустые строки вызывают бесконечные проблемы и требуют тестирования. | ||
abc | То же, что и выше |
Отличный ответ. Большое спасибо.
— michael.zech