21

このための組み込み機能はありますか?

4

3 に答える 3

43

GNU Octave は、文字列のセル配列を線形時間で検索しますO(n)。

もう1つの答えにはcellidx、オクターブごとに減価償却されたものがありますが、それでも実行されますが、ismember代わりに次のように使用するように言われています:

%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

'world' はインデックス スロット 3 にあります。これは、見つかったかどうかに関係なくすべての要素を反復処理する必要があるため、コストのかかる線形時間 O(n) 操作です。

対数時間 O(log n) ソリューションを実現するには、リストを事前に並べ替える必要があり、バイナリ検索を使用できます。

O(log-n)セル配列が既に並べ替えられている場合は、最悪の場合を実行できます。

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

まだ並べ替えていない場合に配列を並べ替えるには、次のようにします。

O(n*log(n))並べ替えの複雑さは、持っているデータの種類と、GNU オクターブ言語の作成者が選択した並べ替えアルゴリズムに依存します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)

このドブでダクトテープを恥ずかしがらないでください。それはユニットを一緒に保持する唯一のものです.

于 2012-12-01T21:16:42.927 に答える
11

はい、これを確認してください: http://www.obihiro.ac.jp/~suzukim/masuda/octave/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
于 2011-11-24T20:39:36.640 に答える
3

cellidx ソリューションは、OP の効率要件を満たしていないため、推奨されていません ( に記載されているとおりhelp cellidx)。

コメントの Håvard Geithus は、 cellidx よりもはるかに効率的な、並べ替えられた文字列のセル配列で lookup() 関数を使用することを提案しました。ただし、これは依然として二分探索ですが、最近のほとんどの言語 (および多くの 20 年前の言語でさえも) では、連想配列に簡単にアクセスできます。これは、はるかに優れたアプローチです。

Octave は明らかに関連する配列を持っていませんが、構造体を含む ocatve の変数に対してインタープリターが実際に使用しているものなので、ここで説明されているように、それを使用できます: http://math-blog.com/2011/05/ 09/連想配列とセルラー オートマトン イン オクターブ/

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

Matlab を Octave に変換すると、containers.Map に相当するものはありますか? javaObject("java.util.Hashtable") を使用することをお勧めします。これにはセットアップのオーバーヘッドが伴いますが、頻繁に使用している場合はパフォーマンスが向上します。C や C++ で書かれたライブラリをリンクすることも可能でしょうか? ただし、これが保守可能なオプションであるかどうかを考えてください。

警告: 私は Octave に比較的慣れていないので、自分で調べながらこれを書いています (これが私がここにたどり着いた方法です)。私はこれらの手法の効率性についてまだテストを行っていません。基礎となるアルゴリズムについてかなりの知識を持っていますが、Octave で実際に何が効率的であるかについて不合理な仮定をしている可能性があります。

于 2013-12-15T19:44:31.550 に答える