リスト内の最も長いアイテムの長さを見つける最も効率的な方法は何ですか?
-
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メソッド?配列に変換し、アイテムの長さで並べ替えますか?コンマ間の最大のギャップを数えますか?
実用面では、上記の2つの例のいずれかが現在のニーズに対してうまく機能しますが、これはパフォーマンスに重大な影響を与えるものではないため、これに対する回答は必要ありません 、しかし、人々が何を思い付くのかを見るのはまだ面白いと思いました...
解決
カンマ間の距離をカウントします。
これより高速なものは何もありません 。それは O(n)
であり、とにかく少なくとも1回は各文字を確認する必要があります(コンマかどうかを確認するため)。
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 Perlで(答えが保存される変数 $ max
があると仮定して):
(length $1 > $max) && ($max = length $1) while "a,set,of,random,words" =~ /(\w+)/g;
または:
$max = length((sort { length $b <=> length $a } split /,/, "a,set,of,random,words")[0]);
または:
use List::Util 'reduce';
$max = length reduce { length $a > length $b ? $a : $b } split /,/, "a,set,of,random,words";
TMTOWTDI、結局のところ。
編集:コアモジュールを忘れました!
use List::Util 'max';
$max = max map length, split /,/, "a,set,of,random,words";
...どういうわけか他のものよりも長くなります。まあ!
編集2: map()
を思い出した:
($max) = sort { $b <=> $a } map length, split /,/, "a,set,of,random,words";
それは私が探しているものに似ています。
編集3:そして完全を期すために:
<*> > $max) && ($max = length Perlで(答えが保存される変数 $ max
があると仮定して):
(length $1 > $max) && ($max = length $1) while "a,set,of,random,words" =~ /(\w+)/g;
または:
<*>
または:
<*>
TMTOWTDI、結局のところ。
編集:コアモジュールを忘れました!
<*>
...どういうわけか他のものよりも長くなります。まあ!
編集2: map()
を思い出した:
<*>
それは私が探しているものに似ています。
編集3:そして完全を期すために:
<*>) foreach split /,/, "a,set,of,random,words";
または:
<*>TMTOWTDI、結局のところ。
編集:コアモジュールを忘れました!
<*>...どういうわけか他のものよりも長くなります。まあ!
編集2: map()
を思い出した:
それは私が探しているものに似ています。
編集3:そして完全を期すために:
<*> code-golf
タグがあるので、C#では52文字です
"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')))
ゴルフタグのコードが表示されました-Pythonでは54文字です:
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 _;}
私はそれが効率的な意味に依存すると推測します。記述されたコードで文字の最小量を意味する場合、それは1つのことです。最小メモリ量または最速実行を意味する場合、それは別のものです。
最速で実行するにはループを使用します。
vc ++
で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;
}
スカラ(55文字):
",set,of,random,words".split(",").:\(0)(_.length max _)
Clojure: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>