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

StackOverflow https://stackoverflow.com/questions/603877

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

Was it helpful?

Solution

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... ;]

OTHER TIPS

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

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

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

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

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

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

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

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

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

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.

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

In J

Assume list of boxed strings(L):

{.\:~>#&.>L

An example using a CSV file:

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

In scala (55 chars):

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

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.

I don't have Python in front of me so I can't check this works, but...

def maxlen(x):
    return len(sorted(x.split(), key=lambda y: len(y))[1])

Should do the trick.

Wouldn't this be simplest?

<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>
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top