配列の配列アルゴリズムの効率

Question

配列が1から配列の長さまでのすべての値を含んでいるかどうかを判断する、より効率的なアルゴリズムの提案を探しています。私が考案した解決策は、Ada2012を使って正しく動作します。

------------------------------------------------------------------ 
-- Build a function to determine whether an array contains -- 
-- all the values from 1 through the length of the array. -- 
------------------------------------------------------------------ 
with Ada.Text_IO; use Ada.Text_IO; 

procedure Sequence_test is 
    type Sequence_Array is array(Positive range <>) of Integer; 

    function Is_Sequence(Item : Sequence_Array) return Boolean is 
     Flags : Array(Positive range 1..Item'Length) of Boolean := (Others => False); 
    begin 
     for Num of Item loop 
     if Num in Flags'Range then 
      Flags(Num) := True; 
     else 
      exit; 
     end if; 
     end loop; 
     return (for all P of Flags => P = True); 
    end Is_Sequence; 
    A : Sequence_Array := (1,2,3,4,5,6); 
    B : Sequence_Array := (6,5,4,3,2,1); 
    C : Sequence_Array := (1,1,1,6,6,6); 
    D : Sequence_Array := (1,2,3,4,6); 
    E : Sequence_Array := (6,1,5,2,4,3); 
    F : Sequence_Array := (1,1,1,2,3,4,5,9,10,11); 
begin 
    Put_Line("A is " & Boolean'Image(Is_Sequence(A))); 
    Put_Line("B is " & Boolean'Image(Is_Sequence(B))); 
    Put_Line("C is " & Boolean'Image(Is_Sequence(C))); 
    Put_Line("D is " & Boolean'Image(Is_Sequence(D))); 
    Put_Line("E is " & Boolean'Image(Is_Sequence(E))); 
    Put_Line("F slice is " & Boolean'Image(Is_Sequence(F(3..7)))); 
end Sequence_test; 

私のプログラムの出力は

A is TRUE 
B is TRUE 
C is FALSE 
D is FALSE 
E is TRUE 
F slice is TRUE 

Answer 1

ありますはビルトインset supportの一部を使用することができます。私は、より速く実行することが保証されているとは思わないが、完全な最適化をオンにしてコンパイラのオプティマイザが良い場合は、がより速く実行される可能性があります。私はこれをアレイをパックし、それぞれをループ反復を必要とするのではなく、一度に32個のboolと比較することができるからです。同様に、もの比較配列を32個作成できます。

もちろん、オプティマイザがの場合、実際にはというコードを使って同じことをする方法がわかります。

function Is_Sequence(Item : Sequence_Array) return Boolean is 
    All_There constant : Array(Positive range 1..Item'Length) of Boolean 
    := (Others => True); 
    Flags : Array(Positive range 1..Item'Length) of Boolean := not All_There; 

begin 
    for Num of Item loop 
    if Num in Flags'Range then 
     Flags(Num) := True; 
    else 
     exit; 
    end if; 
    end loop; 
    return Flags = All_There; 
end Is_Sequence; 

あなたのために私が持っている他の提案は、あなたがその時点でそれが一致していない知っているので、日常的にたむろし、より多くの仕事をしてない点はありませんreturn False;とそのexit文を交換することです。私のコンピュータ上で

Answer 2

は、私が

for Num of Item loop 
    exit when Num not in Flags'Range; 
    Flags(Num) := True; 
    end loop; 
    return (for all P of Flags => P); 

で若干良い結果を得るそして、もっと驚くべきことには、名前のサブタイプはさらに良い結果を与えるようだ：

でテスト

type Item_Length_Array is array(Positive range 1..Item'Length) of Boolean; 
Flags : Item_Length_Array := (others => False); 

：

Start_Time := Ada.Real_Time.Clock; 
for I in 1..10_000_000 loop 
    Ignore := Is_Sequence(A); 
    Ignore := Is_Sequence(B); 
    Ignore := Is_Sequence(C); 
    Ignore := Is_Sequence(D); 
    Ignore := Is_Sequence(E); 
    Ignore := Is_Sequence(F(3..7)); 
end loop; 
End_Time := Ada.Real_Time.Clock;