Qual é a maneira mais eficiente de encontrar a duração do item mais longo de uma lista?

Question

Dada uma lista de palavras variadas de comprimento, qual é a melhor maneira de encontrar o comprimento máximo de alguma palavra?

Por exemplo, o seguinte deve retornar 6

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

Claro, é bastante trivial fazer isso ...

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

Ou, um pouco mais curto ...

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

Mas existe uma maneira melhor - algo mais eficiente?

Talvez algum método Java? Convertendo em matriz e classificação por comprimento do item? Contando a maior lacuna entre vírgulas?

Em termos práticos, qualquer um dos dois exemplos acima funcionará bem para minha necessidade atual, e isso não é para algo que é crítico, então eu não precisar Uma resposta para isso, mas eu pensei que ainda seria interessante ver o que as pessoas poderiam criar ...

Answer 1

Conte a distância entre vírgulas.

Eu não acho nada poderia ser mais rápido que isso; Está O(n), e você tenho Olhar para cada personagem pelo menos uma vez de qualquer maneira (para ver se é uma vírgula).

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

Ou suponho que você poderia apenas dizer

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

Se estamos jogando ...;

Answer 2

Em Perl (assumindo que temos uma variável $max em que a resposta deve ser armazenada):

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

Ou:

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

Ou:

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

Tmtowtdi, afinal.

EDIT: Eu esqueci os módulos principais!

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

... que de alguma forma consegue ser mais longo que os outros. Ah bem!

Edit 2: Acabei de me lembrar map():

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

Isso é mais como o que estou procurando.

EDIT 3: E apenas para completar:

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

Answer 3

Vendo como há um code-golf Tag, aqui estão 52 caracteres em C#

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

Answer 4

E aqui está o caminho "curto" da CFML - 72 chars ...

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

Outra versão, 78 chars, mas lida com cordas enormes (veja comentários) ...

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

Answer 5

Eu vi a etiqueta de golfe de código - aqui estão 54 caracteres no Python:

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

Answer 6

Em java sem funções extras de string. (apenas uma lista de pseudo vinculada: P) Dê Max como 0 no começo

   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: Acabei de notar agora que recebe uma série de palavras, não uma lista de strings, bem, não importa, permanece aqui da mesma forma :)

Answer 7

Se você não está preocupado com a legibilidade ...;)

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

Answer 8

Eu acho que depende do que eficiente significa. Se isso significa a menor quantidade de caracteres no código escrito, isso é uma coisa. Se isso significa, pelo menos quantidade de memória ou execução mais rápida, isso é outra.

Para a execução mais rápida, vou dar o loop.

Answer 9

em 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

Dentro J

Assuma a lista de strings em caixa (L):

{.\:~>#&.>L

Um exemplo usando um arquivo CSV:

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

Answer 11

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

Versão legível:

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

Ainda estou aprendendo o idioma, então adoraria ouvir alguma maneira de melhorá -lo.

Answer 13

Eu não tenho python na minha frente, então não posso verificar isso funciona, mas ...

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

Deve fazer o truque.

Answer 14

Isso não seria mais simples?

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