Wie wollen Sie Sortieren und effizient zu finden, Elemente in einem cell-array (Zeichenfolgen) in die Oktave?

Gibt es integrierte Funktionen für das?

  • Gegeben eine lexikographisch sortiert cell array, können Sie die Funktion 'lookup' in octave ausführen der binären Suche. Alles, was jetzt bleibt, ist die Sortierung 😉
InformationsquelleAutor B Seven | 2011-11-22
  1. 11

    Ja prüfen: http://www.obihiro.ac.jp/~suzukim/masuda/Oktave/html3/octave_36.html#SEC75

    a = ["hello"; "world"];
c = cellstr (a)
     ⇒ c =
         {
           [1,1] = hello
           [2,1] = world
         }
>>> cellidx(c, 'hello')
ans =  1

>>> cellidx(c, 'world')
ans =  2
    • Funktioniert Super. Keine Notwendigkeit zu Sortieren. Zurück 0 wenn Sie Sie nicht finden. Ich wundere mich über die Effizienz...Ist es ein brute-force-Suche?
    • Es scheint, dass es ist. Wenn Sie verwenden die 'die' - Funktion und übergeben Sie eine Funktion, wird es Sie auf die Quellcode-Datei. In diesem Fall ist die cellidx'. Wenn Sie einen Blick auf die Quelle, du wirst sehen, dass es macht eine brute-force-Suche.
    • Siehe meine Antwort (Hinzugefügt lange nach der Frage gefragt wurde) für nicht-brute-force-Optionen.
    • Schade, aber cellidx war veraltet (warum?) und entfernt in Octave 3.8
    • cellidx funktioniert nicht in Octave 4.0.2
    InformationsquelleAutor Peter Rudenko
  2. 31

    GNU Octave Suche ein cell-array von Zeichenketten in linearer Zeit O(n):

    Die andere Antwort hat cellidx ist abgeschrieben von octave, er läuft immer noch, aber Sie sagen, zu verwenden ismember statt, wie diese:

    %linear time string index search.
a = ["hello"; "unsorted"; "world"; "moobar"]
b = cellstr(a)
%b =
%{
%  [1,1] = hello
%  [2,1] = unsorted
%  [3,1] = world
%  [4,1] = moobar
%}
find(ismember(b, 'world'))   %returns 3

    'Welt' ist in der index-3-Steckplatz. Dies ist eine teure die lineare Zeit O(n) operation, weil es zum iterieren durch alle Elemente, ob oder nicht es ist gefunden.

    Zu erreichen logarathmic Zeit O(log n) Lösung, dann ist deine Liste kommen muss, vorsortiert und dann Sie können verwenden Sie die binäre Suche:

    , Wenn Sie Ihre cell-array ist schon sortiert, Sie können tun O(log-n) schlimmsten Fall:

    function i = binsearch(array, val, low, high)
  %binary search algorithm for numerics, Usage:
  %myarray = [ 30, 40, 50.15 ];        %already sorted list
  %binsearch(myarray, 30,    1, 3)     %item 30 is in slot 1
  if ( high < low )
    i = 0;
  else
    mid = floor((low + high) / 2);
    if ( array(mid) > val )
      i = binsearch(array, val, low, mid-1);
    elseif ( array(mid) < val )
      i = binsearch(array, val, mid+1, high);
    else
      i = mid;
    endif
  endif
endfunction

function i = binsearch_str(array, val, low, high)
  % binary search for strings, usage:
  %myarray2 = [ "abc"; "def"; "ghi"];       #already sorted list
  %binsearch_str(myarray2, "abc", 1, 3)     #item abc is in slot 1
  if ( high < low )
    i = 0;
  else
    mid = floor((low + high) / 2);
    if ( mystrcmp(array(mid, [1:end]), val) == 1 )
      i = binsearch(array, val, low, mid-1);
    elseif ( mystrcmp(array(mid, [1:end]), val) == -1 )
      i = binsearch_str(array, val, mid+1, high);
    else
      i = mid;
    endif
  endif
endfunction
function ret = mystrcmp(a, b)
    %this function is just an octave string compare, it's exactly like 
    %strcmp(str1,str2) in C, or java.lang.String.compareTo(...) in Java.
    %returns 1 if string a > b
    %returns 0 if string a == b
    %return -1 if string a < b
    letters_gt = gt(a, b);      %list of boolean a > b
    letters_lt = lt(a, b);      %list of boolean a < b
    ret = 0;
    %octave makes us roll our own string compare because 
    %strings are arrays of numerics
    len = length(letters_gt);
    for i = 1:len
        if letters_gt(i) > letters_lt(i)
            ret = 1;
            return
        elseif letters_gt(i) < letters_lt(i)
            ret = -1;
            return
        endif
    end;
endfunction

%Assuming that myarray is already sorted, (it must be for binary 
%search to finish in logarithmic time `O(log-n))` worst case, then do

myarray = [ 30, 40, 50.15 ];        %already sorted list
binsearch(myarray, 30,    1, 3)     %item 30 is in slot 1
binsearch(myarray, 40,    1, 3)     %item 40 is in slot 2
binsearch(myarray, 50,    1, 3)     %50 does not exist so return 0
binsearch(myarray, 50.15, 1, 3)     %50.15 is in slot 3

%same but for strings:
myarray2 = [ "abc"; "def"; "ghi"];       %already sorted list
binsearch_str(myarray2, "abc", 1, 3)     %item abc is in slot 1
binsearch_str(myarray2, "def", 1, 3)     %item def is in slot 2
binsearch_str(myarray2, "zzz", 1, 3)     %zzz does not exist so return 0
binsearch_str(myarray2, "ghi", 1, 3)     %item ghi is in slot 3

    Zu Sortieren das array, wenn es nicht bereits:

    Komplexität der Sortierung hängt von der Art der Daten, die Sie haben, und was auch immer Sortieren Algorithmus GNU octave Sprache-Autoren ausgewählt, es ist irgendwo zwischen O(n*log(n)) und O(n*n). 

    myarray = [ 9, 40, -3, 3.14, 20 ];        %not sorted list 
myarray = sort(myarray) 

myarray2 = [ "the"; "cat"; "sat"; "on"; "the"; "mat"];       %not sorted list 
myarray2 = sortrows(myarray2)

    Scheuen Sie sich nicht, auf das Klebeband, mit dem das Geburtsdatum, es ist die einzige halten die Einheit zusammen.

    InformationsquelleAutor Eric Leschinski
  3. 3

    Den cellidx Lösung erfüllt nicht die OP-Effizienz-Anforderung, und ist veraltet (wie bereits von help cellidx).

    Håvard Geithus in einem Kommentar vorgeschlagen, die lookup () - Funktion auf ein sortiert cell array von strings, das ist deutlich effizienter als cellidx. Es ist immer noch eine binäre Suche wenn, in der Erwägung, dass die meisten modernen Sprachen (und auch viele 20 Jahre alten) geben Sie uns einfach Zugriff auf assoziative arrays, das wäre ein deutlich besserer Ansatz.

    Während Oktave nicht offensichtlich verknüpft haben, arrays, das ist effektiv das, was der interpreter für ocatve-Variablen, einschließlich Strukturen, so können Sie uns, die, wie hier beschrieben:
    http://math-blog.com/2011/05/09/associative-arrays-and-cellular-automata-in-octave/

    Built-in Function: struct ("field", value, "field", value,...)
Built-in Function: isstruct (expr)
Built-in Function: rmfield (s, f)
Function File: [k1,..., v1] = setfield (s, k1, v1,...)
Function File: [t, p] = orderfields (s1, s2)
Built-in Function: fieldnames (struct)
Built-in Function: isfield (expr, name)
Function File: [v1,...] = getfield (s, key,...)
Function File: substruct (type, subs,...)

    Konvertieren von Matlab Octave gibt es einen Container.Anzeigen-äquivalent? schlägt vor, javaObject("java.util.Hashtable"). Das wäre zu kommen mit einigen setup-Aufwand, aber wäre ein performance-Gewinn, wenn Sie es eine Menge. Vielleicht ist es sogar sinnvoll Glied in einer Bibliothek, geschrieben in C oder C++? Überlegen Sie, ob dies ein vertretbares option, obwohl.

    Caveat: ich bin relativ neu in der Oktave, und schreiben das auf, als ich die Forschung selbst (die, wie ich aufgewickelt hier). Ich habe noch keine tests über die Effizienz dieser Techniken, und zwar habe ich eine faire Kenntnis der zugrunde liegenden algorithmen, ich kann machen unvernünftigen Annahmen über das, was tatsächlich effizienter in die Oktave.

    InformationsquelleAutor mc0e
Schreibe einen Kommentar