Array sequence algorithm efficiency

Question

I am looking for suggestions for a more efficient algorithm to determine if an array contains all the values from 1 through the length of the array. The solution I have devised works correctly using 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;

The output of my program is

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

Example: you are at the index i check if a[ abs(a[i]) - 1 ] > 0 if no return false else a[ abs(a[i]) - 1 ] *= -1 and continue iteration. Complexity is O(n) — Rasul Kerimov
– Rasul Kerimov, Commented Feb 6, 2017 at 15:08
The requirement is to determine if an array contains all the values from 1 to the length of the array. The values can be in any order, but every value must be represented. For instance, a 6 element array must contain the values 1..6. — Jim Rogers
– Jim Rogers, Commented Feb 6, 2017 at 15:08

trashgod · Accepted Answer · 2017-02-06 18:26:03Z

3

You could use some of the built-in set support. I don't think its guaranteed to execute quicker, but if you turn on full optimization and your compiler's optimizer is good, it might execute quicker. I say this because it could pack your array and compare it 32 bools at a time, rather than needing a loop iteration for each. Likewise it also could create your comparison array 32 bools at a time.

Of course, if your optimizer is really good it might figure out how to do the same thing with the code you had.

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;

The other suggestion I have for you is to replace that exit statement with a return False; You know at that point it doesn't match, so there's no point hanging out in the routine and doing more work.

edited Feb 6, 2017 at 18:26

trashgod

206k33 gold badges264 silver badges1.1k bronze badges

answered Feb 6, 2017 at 15:24

T.E.D.

44.9k10 gold badges79 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Jim Rogers Over a year ago

Using the actual range of the passed-in array is an error. The value sequence must start at 1, so the Flags array must start at 1, no matter how long the passed-in array is. The use of a Flags array fails when the length of the passed-in array is greater than Integer'Last, for instance when the range of the passed-in array is Integer'First..Integer'Last.

T.E.D. Over a year ago

@JimRogers - I was wondering about that (refer back to my note about not quite understanding the requirements). So in that case, I'll put those back, but consider this a strong suggestion to think about what happens to your algorithm in the case where a slice is passed in.

Jim Rogers Over a year ago

One could simply change the requirements such that the passed-in array was defined as array(Positive range <>) of Integer

T.E.D. Over a year ago

@JimRogers Wouldn't that still allow someone to pass a (5..10) array?

Jim Rogers Over a year ago

Yes it will. Try it. The for loop testing the values is agnostic about the index range of the passed-in array. It uses whatever range is passed in. That range will be the range of the slice, not the range of the base type of the array.

|

egilhh · Accepted Answer · 2017-02-06 16:59:16Z

2

On my computer, I get a slightly better result with

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

And more surprisingly, a named subtype seems to give even better result:

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

Tested with:

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;

edited Feb 6, 2017 at 16:59

answered Feb 6, 2017 at 16:43

egilhh

6,4401 gold badge21 silver badges20 bronze badges

Collectives™ on Stack Overflow

Array sequence algorithm efficiency

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related