Какой самый эффективный способ найти длину самого длинного элемента в списке?
-
03-07-2019 - |
Вопрос
Учитывая список слов различной длины, как лучше всего найти максимальную длину любого слова?
Например, следующее должно вернуть 6
findMaxLen("a,set,of,random,words")
Конечно, это довольно тривиально сделать...
<cffunction name="findMaxLen" returntype="Numeric">
<cfset var CurMax = 0 />
<cfset var CurItem = 0 />
<cfloop index="CurItem" list="#Arguments[1]#">
<cfif Len(CurItem) GT CurMax >
<cfset CurMax = Len(CurItem)/>
</cfif>
</cfloop>
<cfreturn CurMax />
</cffunction>
Или немного короче...
<cffunction name="findMaxLen" returntype="Numeric">
<cfset var CurMax = 0 />
<cfset var CurItem = 0 />
<cfloop index="CurItem" list="#Arguments[1]#">
<cfset CurMax = Max( CurMax , Len(CurItem) ) />
</cfloop>
<cfreturn CurMax />
</cffunction>
Но есть ли лучший способ – что-то более эффективное?
Возможно, какой-то метод Java?Преобразование в массив и сортировка по длине элемента?Считаете самый большой разрыв между запятыми?
С практической точки зрения, любой из двух приведенных выше примеров будет отлично работать для моих текущих нужд, и это не для чего-то, что критично для производительности, поэтому я не буду нуждаться ответ на этот вопрос, но я подумал, что все равно будет интересно посмотреть, что люди могут придумать...
Решение
Посчитайте расстояние между запятыми.
я ничего не думаю мог быть быстрее этого;его O(n)
, а ты иметь в любом случае посмотреть на каждый символ хотя бы один раз (чтобы убедиться, что это запятая).
int FindLongestWord(char* str)
{
char* lastComma = str - 1;
int longest = 0;
int length;
char* pCheckChar;
for(pCheckChar = str; *pCheckChar; pCheckChar++)
{
if(*pCheckChar == ',')
{
length = pCheckChar - lastComma - 1;
if(length > longest)
{
longest = length;
}
lastComma = pCheckChar;
}
}
// Check to see if the last word is the longest
length = pCheckChar - lastComma - 1;
if(length > longest)
{
longest = length;
}
return longest;
}
или я полагаю, ты мог бы просто сказать
"a,set,of,random,words".Split(',').Max(w=>w.Length);
если мы играем в игры...;]
Другие советы
В Perl (при условии, что у нас есть переменная $max
в котором должен храниться ответ):
(length $1 > $max) && ($max = length $1) while "a,set,of,random,words" =~ /(\w+)/g;
Или:
(length $_ > $max) && ($max = length $_) foreach split /,/, "a,set,of,random,words";
Или:
$max = length((sort { length $b <=> length $a } split /,/, "a,set,of,random,words")[0]);
В конце концов, TMTOWTDI.
РЕДАКТИРОВАТЬ:Я забыл про основные модули!
use List::Util 'reduce';
$max = length reduce { length $a > length $b ? $a : $b } split /,/, "a,set,of,random,words";
...который каким-то образом оказывается длиннее остальных.Ну что ж!
РЕДАКТИРОВАТЬ 2:Я только что вспомнил map()
:
use List::Util 'max';
$max = max map length, split /,/, "a,set,of,random,words";
Это больше похоже на то, что я ищу.
РЕДАКТИРОВАТЬ 3:И просто для полноты:
($max) = sort { $b <=> $a } map length, split /,/, "a,set,of,random,words";
Видя, что есть code-golf
тег, вот 52 символа в C#
"a,set,of,random,words".Split(',').Max(w=>w.Length);
А вот «короткий» путь CFML — 72 символа...
Len(ArrayMax("a,set,of,random,words".replaceAll('[^,]','1').split(',')))
Другая версия, 78 символов, но обрабатывает огромные строки (см. комментарии)...
Len(ListLast(ListSort("a,set,of,random,words".replaceAll('[^,]','1'),'text')))
Я видел тег кода для гольфа — вот 54 символа на Python:
len(max("a,set,of,random,words".split(","), key=len))
В Java без строковых дополнительных функций.(просто псевдосвязный список: P) Вначале укажите max как 0
int find(LinkedList strings, int max) {
int i;
String s=(String)strings.element();
for(i=0;s.charAt(i)!='\0';i++);
if(strings.hasNext())
return find(strings.Next(),(i>max?i:max));
return max;
}
Редактировать:Только что заметил, что теперь дается строка слов, а не список строк, ну, неважно, остается здесь прежним :)
Если вас не беспокоит читабельность...;)
String longest(String...ss){String _="";for(String s:ss)if(_.length()<s.length())_=s;return _;}
Я думаю, это зависит от того, какие эффективные средства.если это означает наименьшее количество символов в написанном коде, это одно.если это означает наименьший объем памяти или самое быстрое выполнение, это другое.
для максимально быстрого выполнения я возьму цикл.
в vС++
int findMaxLen(const char *s)
{
const char c = ',';
int a = 0, b = 0;
while(*s)
{
while(*s && *s++ != c)b++;
if(b > a)a=b;
b = 0;
}
return a;
}
В Дж
Предположим, список упакованных строк (L):
{.\:~>#&.>L
Пример использования файла CSV:
{.\:~;>#&.>readcsv'test.csv'
В скале (55 символов):
",set,of,random,words".split(",").:\(0)(_.length max _)
Клююр:49 байт.
(def l #(reduce max(for[x(.split%%2)](count x))))
Разборчивая версия:
(defn longest [astr sep]
(reduce max
(for [word (.split astr sep)]
(count word))))
Я все еще изучаю язык, поэтому мне хотелось бы услышать о способах его улучшения.
У меня нет Python, поэтому я не могу проверить, работает ли это, но...
def maxlen(x):
return len(sorted(x.split(), key=lambda y: len(y))[1])
Должно сработать.
Разве это не было бы проще всего?
<cffunction name="findMaxLen" returntype="Numeric">
<cfset longest = 0>
<cfloop list="#Arguments[1]#" index="w">
<cfif len(w) gt longest>
<cfset longest = len(w)>
</cfif>
</cfloop>
<cfreturn longest>
</cffunction>