Was ist der effizienteste Weg, um die Länge des längsten Elements in einer Liste zu finden?

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

Frage

Wie können Sie angesichts einer Liste der Wörter mit verschiedenen Längen die maximale Länge von Wörtern am besten finden?

Zum Beispiel sollte Folgendes 6 zurückgeben 6

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


Natürlich ist es ziemlich trivial, dies zu tun ...

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


Oder etwas kürzer ...

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


Aber gibt es einen besseren Weg - etwas effizienteres?

Vielleicht eine Java -Methode? Konvertieren in Array und Sortieren nach Elementlänge? Die größte Lücke zwischen Kommas zählen?


In praktischer Hinsicht funktioniert eines der beiden oben genannten Beispiele für mein aktuelles Bedürfnis gut, und dies ist nicht für etwas, das leistungskritisch ist, also nicht brauchen Eine Antwort darauf, aber ich dachte, es wäre immer noch interessant zu sehen, was die Leute sich einfallen lassen könnten ...

War es hilfreich?

Lösung

Zählen Sie den Abstand zwischen Kommas.

Ich denke nichts könnte Sei schneller als das; es ist O(n), Und Sie haben Mindestens einmal jeden Charakter anschauen (um zu sehen, ob es sich um ein Komma handelt).

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

Oder ich nehme an, Sie könnten einfach sagen

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

Wenn wir Spiele spielen ...;

Andere Tipps

In Perl (vorausgesetzt, wir haben eine Variable $max in denen die Antwort gespeichert werden soll):

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

Oder:

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

Oder:

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

TMTOWTdi, schließlich.

EDIT: Ich habe die Kernmodule vergessen!

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

... was es irgendwie schafft, länger als die anderen zu sein. Nun ja!

EDIT 2: Ich habe mich gerade erinnert map():

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

Das ist eher wie das, wonach ich suche.

Bearbeiten 3: Und nur zur Vollständigkeit:

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

Da es eine gibt code-golf Tag, hier sind 52 Zeichen in C#

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

Und hier ist der "kurze" CFML -Weg - 72 Chars ...

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

Eine andere Version, 78 Chars, aber mit riesigen Saiten (siehe Kommentare) ...

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

Ich habe das Code -Golf -Tag gesehen - hier sind 54 Zeichen in Python:

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

In Java ohne Zeichenfolge zusätzliche Funktionen. (Nur eine pseudo verlinkte Liste: p) Geben Sie Max als 0 am Anfang an

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

Bearbeiten: Jetzt bemerkt jetzt eine Reihe von Wörtern, nicht eine Liste von Zeichenfolgen.

Wenn Sie sich keine Sorgen um die Lesbarkeit machen ...;)

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

Ich denke, es hängt davon ab, was effiziente Mittel haben. Wenn es die geringste Anzahl von Zeichen im geschriebenen Code bedeutet, ist das eine Sache. Wenn es bedeutet, die geringste Menge an Speicher oder die schnellste Ausführung, ist das eine andere.

Für die schnellste Ausführung werde ich die Schleife nehmen.

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

Im J

Nehmen Sie die Liste der Box -Zeichenfolgen (L) an:

{.\:~>#&.>L

Ein Beispiel unter Verwendung einer CSV -Datei:

{.\:~;>#&.>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))))

Lesbare Version:

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

Ich lerne immer noch die Sprache, also würde ich gerne eine Möglichkeit hören, sie zu verbessern.

Ich habe keine Python vor mir, also kann ich nicht überprüfen, ob dies funktioniert, aber ...

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

Sollte den Trick machen.

Wäre das nicht am einfachsten?

<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>
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top