What's the most efficient way to find the length of the longest item in a list?

Question

Given a list of assorted length words, what is the best way to find the maximum length of any words?

For example, the following should return 6

findMaxLen("a,set,of,random,words")

Of course, it's fairly trivial to do this...

<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>

Or, a little shorter...

<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>

But is there a better way - something more efficient?

Perhaps some Java method? Converting to array and sorting by item length? Counting the biggest gap between commas?

In practical terms, either of the above two examples will work fine for my current need, and this isn't for something that is performance critical, so I don't need an answer to this, but I thought it would still be interesting to see what people might come up with...

Answer 1

Count the distance between commas.

I don't think anything could be faster than that; it's O(n), and you have to look at each character at least once anyway (to see if it's a comma).

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;
}

or I suppose you could just say

"a,set,of,random,words".Split(',').Max(w=>w.Length);

if we're playing games... ;]

Answer 2

I did see the code golf tag - here is 54 characters in Python:

len(max("a,set,of,random,words".split(","), key=len))

Answer 3

Seeing as there's a code-golf tag, here's 52 characters in C#

"a,set,of,random,words".Split(',').Max(w=>w.Length);

Answer 4

And here's the 'short' CFML way - 72 chars...

Len(ArrayMax("a,set,of,random,words".replaceAll('[^,]','1').split(',')))

Another version, 78 chars but handles huge strings (see comments)...

Len(ListLast(ListSort("a,set,of,random,words".replaceAll('[^,]','1'),'text')))

Answer 5

In java without string extra functions. (just a pseudo linked list :P) Give max as 0 in the begining

   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;
    }

Edit: Just noticed now it's given a String of words not a list of strings, well never mind stays here the same :)

Answer 6

In Perl (assuming we have a variable $max in which the answer is to be stored):

(length $1 > $max) && ($max = length $1) while "a,set,of,random,words" =~ /(\w+)/g;

Or:

(length $_ > $max) && ($max = length $_) foreach split /,/, "a,set,of,random,words";

Or:

$max = length((sort { length $b <=> length $a } split /,/, "a,set,of,random,words")[0]);

TMTOWTDI, after all.

EDIT: I forgot about the Core Modules!

use List::Util 'reduce';
$max = length reduce { length $a > length $b ? $a : $b } split /,/, "a,set,of,random,words";

...which somehow manages to be longer than the other ones. Oh well!

EDIT 2: I just remembered map():

use List::Util 'max';
$max = max map length, split /,/, "a,set,of,random,words";

That's more like what I'm looking for.

EDIT 3: And just for completeness:

($max) = sort { $b <=> $a } map length, split /,/, "a,set,of,random,words";

Answer 7

If you are not worried about readability... ;)

String longest(String...ss){String _="";for(String s:ss)if(_.length()<s.length())_=s;return _;}

Answer 8

i guess it depends on what efficient means. if it means the least amount of characters in the code written, that is one thing. if it means, least amount of memory or fastest executing, that is another.

for fastest executing i'll take the loop.

Answer 9

in 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;
}

Answer 10

In J

Assume list of boxed strings(L):

{.\:~>#&.>L

An example using a CSV file:

{.\:~;>#&.>readcsv'test.csv'

Answer 11

In scala (55 chars):

",set,of,random,words".split(",").:\(0)(_.length max _)

Answer 12

Clojure: 49 bytes.

(def l #(reduce max(for[x(.split%%2)](count x))))

Legible version:

(defn longest [astr sep]
  (reduce max
    (for [word (.split astr sep)]
      (count word))))

I'm still learning the language, so I'd love to hear any ways to improve it.