Tally

Tally

[Gilbert Gosseyn]

Before I make long tests with access Types, declarations or  containers, I would like to get an advice on how to program in a simple and fast way the following, or get a hint to an existing program.

Example_Input: (2, 3, 8, 2, 2, 2, 7, 2, 3, 4, 8) ; -- variable Length

Output by function or procedure : ((2, 5), (3, 2), (8, 2), (7, 1), (4, 1));  -- unknown Length

-- tallies the elements in Input, listing all distinct elements together with their multiplicities


Thank you

Re: Tally

[Niklas Holsti]

On 2020-01-14 17:27, Gilbert Gosseyn wrote:
> Before I make long tests with access Types, declarations or  containers, I would like to get an advice on how to program in a simple and fast way the following, or get a hint to an existing program.
> 
> Example_Input: (2, 3, 8, 2, 2, 2, 7, 2, 3, 4, 8) ; -- variable Length
> 
> Output by function or procedure : ((2, 5), (3, 2), (8, 2), (7, 1), (4, 1));  -- unknown Length
> 
> -- tallies the elements in Input, listing all distinct elements together with their multiplicities
> 
> 
> Thank you
> 

Put the input numbers in a map container, keyed on the input number and 
giving the multiplicity so far of that number.

When the input ends, output the map.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Tally

[Simon Wright]

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:

> On 2020-01-14 17:27, Gilbert Gosseyn wrote:
>> Before I make long tests with access Types, declarations or
>> containers, I would like to get an advice on how to program in a
>> simple and fast way the following, or get a hint to an existing
>> program.
>>
>> Example_Input: (2, 3, 8, 2, 2, 2, 7, 2, 3, 4, 8) ; -- variable Length
>>
>> Output by function or procedure : ((2, 5), (3, 2), (8, 2), (7, 1),
>> (4, 1)); -- unknown Length
>>
>> -- tallies the elements in Input, listing all distinct elements
>> together with their multiplicities
>>
>>
>> Thank you
>>
>
> Put the input numbers in a map container, keyed on the input number
> and giving the multiplicity so far of that number.
>
> When the input ends, output the map.

The Booch Components included Bags, which would solve this directly!
(not that I'd recommend anyone to use the BCs for a new project)

Re: Tally

[Jeffrey R. Carter]

On 1/14/20 4:27 PM, Gilbert Gosseyn wrote:
> Before I make long tests with access Types, declarations or  containers, I would like to get an advice on how to program in a simple and fast way the following, or get a hint to an existing program.
> 
> Example_Input: (2, 3, 8, 2, 2, 2, 7, 2, 3, 4, 8) ; -- variable Length
> 
> Output by function or procedure : ((2, 5), (3, 2), (8, 2), (7, 1), (4, 1));  -- unknown Length

A lot depends on what restraints the problem domain puts on the input values. If 
you can define something like

type Input_Number is range 1 .. 10;

then you can do something straightforward like

type Count_Map is array (Input_Number) of Natural;

Count  : Count_Map := (others => 0);
Number : Input_Number;
...
loop
    exit when No_More_Numbers;

    Number := Next_Number;
    Count (Number) := Count (Number) + 1;
end loop;

If you can't limit the input numbers to a sufficiently small range that an 
object like Count can be declared, then you'll need to use a map, as Holsti 
suggested, which is only a little more complicated.

-- 
Jeff Carter
Just as Khan was hindered by two-dimensional thinking in a
three-dimensional situation, so many developers are hindered
by sequential thinking in concurrent situations.
118

Re: Tally

[Brad Moore]

On Tuesday, January 14, 2020 at 2:08:16 PM UTC-7, Jeffrey R. Carter wrote:

> A lot depends on what restraints the problem domain puts on the input values. If 
> you can define something like
> 
> type Input_Number is range 1 .. 10;
> 
> then you can do something straightforward like
> 
> type Count_Map is array (Input_Number) of Natural;
> 
> Count  : Count_Map := (others => 0);
> Number : Input_Number;
> ...
> loop
>     exit when No_More_Numbers;
> 
>     Number := Next_Number;
>     Count (Number) := Count (Number) + 1;
> end loop;
> 
> If you can't limit the input numbers to a sufficiently small range that an 
> object like Count can be declared, then you'll need to use a map, as Holsti 
> suggested, which is only a little more complicated.
> 

Just to clarify, I'd say using a Map is more complex (quite a bit actually) in terms of what is happening semantically when the program executes, but I think it is worth noting that there is not necessarily much difference in complexity in terms of what the user has to write. As Jeff notes, using a map does has the advantage of flexibility, for example in handling sparsely populated data where there is a large range of input values.

e.g.

with Ada.Containers.Ordered_Maps; use Ada;

procedure Main
is
   package Count_Maps is new
     Containers.Ordered_Maps (Key_Type     => Natural,
                              Element_Type => Natural);
   
   type Input_Data is array (Natural range <>) of Natural;
   
   Input : Input_Data := (2, 3, 8, 2, 2, 2, 7, 2, 3, 4, 8);
   
   Counts : Count_Maps.Map;
      
begin
   for Number of Input loop
      Counts (Number) := Counts (Number) + 1;
   end loop;
end Main;

Brad

Re: Tally

[Simon Wright]

Brad Moore <bmoore.ada@gmail.com> writes:

>    for Number of Input loop
>       Counts (Number) := Counts (Number) + 1;
>    end loop;

   for Number of Input loop
      if Counts.Contains (Number) then
         Counts (Number) := Counts (Number) + 1;
      else
         Counts.Insert (Number, 1);
      end if;
   end loop;

and then of course

   for C in Counts.Iterate loop
      Put_Line (Count_Maps.Key (C)'Image
                  & " -> "
                  & Count_Maps.Element (C)'Image);
   end loop;

Re: Tally

[Simon Wright]

Simon Wright <simon@pushface.org> writes:

> The Booch Components included Bags, which would solve this directly!
> (not that I'd recommend anyone to use the BCs for a new project)

This is what it'd look like (it's a lot uglier in Ada 95, because the
containers and iterators, while tagged, can't use dotted notation).
Sorry about the silly Hash function.

with BC.Containers.Bags.Unmanaged;
with Ada.Text_IO; use Ada.Text_IO;

procedure Main
is
   package Abstract_Containers is new BC.Containers (Natural);
   package Abstract_Bags is new Abstract_Containers.Bags;
   function Hash (N : Natural) return Natural is (N);
   package Bags is new Abstract_Bags.Unmanaged
     (Buckets => 43,
      Hash => Hash);

   type Input_Data is array (Natural range <>) of Natural;

   Input : Input_Data := (2, 3, 8, 2, 2, 2, 7, 2, 3, 4, 8);

   Counts : Bags.Bag;

begin
   for Number of Input loop
      Counts.Add (Number);
   end loop;
   declare
      It : Abstract_Containers.Iterator'Class := Counts.New_Iterator;
   begin
      while not It.Is_Done loop
         Put_Line (It.Current_Item'Image
                     & " -> "
                     & Counts.Count (It.Current_Item)'Image);
         It.Next;
      end loop;
   end;
end Main;

Re: Tally

[Jere]

On Wednesday, January 15, 2020 at 4:03:14 AM UTC-5, Simon Wright wrote:
> Brad Moore  writes:
> 
> >    for Number of Input loop
> >       Counts (Number) := Counts (Number) + 1;
> >    end loop;
> 
>    for Number of Input loop
>       if Counts.Contains (Number) then
>          Counts (Number) := Counts (Number) + 1;
>       else
>          Counts.Insert (Number, 1);
>       end if;
>    end loop;
> 
> and then of course
> 
>    for C in Counts.Iterate loop
>       Put_Line (Count_Maps.Key (C)'Image
>                   & " -> "
>                   & Count_Maps.Element (C)'Image);
>    end loop;

I might recommend using insert every iteration and seeing if
it fails or succeeds.  Since it gives a cursor regardless of
success, you can use that get the element and avoid doing
all the searches each time:

    for Number of Input loop
    
        -- Try to insert a new element.  This will 
        -- fail if the element already exists
        Counts.Insert
            (Key => Number,
             New_Item => 1,
             Position => Position,
             Inserted => Inserted);
    
        -- Since the element already exists, simply
        -- increment the count
        if not inserted then
            Counts(Position) := Counts(Position) + 1;
        end if;

    end loop;

Re: Tally

[Simon Wright]

Jere <jhb.chat@gmail.com> writes:

> I might recommend using insert every iteration and seeing if
> it fails or succeeds.  Since it gives a cursor regardless of
> success, you can use that get the element and avoid doing
> all the searches each time:
>
>     for Number of Input loop
>     
>         -- Try to insert a new element.  This will 
>         -- fail if the element already exists
>         Counts.Insert
>             (Key => Number,
>              New_Item => 1,
>              Position => Position,
>              Inserted => Inserted);
>     
>         -- Since the element already exists, simply
>         -- increment the count
>         if not inserted then
>             Counts(Position) := Counts(Position) + 1;
>         end if;
>
>     end loop;

Yes, I thought about that. More LoC/less clarity without the comments
are the only objections I can see (though fairly compelling for toy
examples!)

Re: Tally

[Brad Moore]

On Thursday, January 16, 2020 at 4:34:57 AM UTC-7, Simon Wright wrote:
> Jere writes:
> 
> > I might recommend using insert every iteration and seeing if
> > it fails or succeeds.  Since it gives a cursor regardless of
> > success, you can use that get the element and avoid doing
> > all the searches each time:
> >
> >     for Number of Input loop
> >     
> >         -- Try to insert a new element.  This will 
> >         -- fail if the element already exists
> >         Counts.Insert
> >             (Key => Number,
> >              New_Item => 1,
> >              Position => Position,
> >              Inserted => Inserted);
> >     
> >         -- Since the element already exists, simply
> >         -- increment the count
> >         if not inserted then
> >             Counts(Position) := Counts(Position) + 1;
> >         end if;
> >
> >     end loop;
> 
> Yes, I thought about that. More LoC/less clarity without the comments
> are the only objections I can see (though fairly compelling for toy
> examples!)

Thanks Simon for catching my failure to insert the initial value.

In Ada 2020, I think one could use a container aggregate to initialize the map
to contain the initial objects:

e.g.
   Counts : Count_Maps.Map 
     := [for I in Input'Range
           when (for all J in Input'First .. I - 1 => Input (I) /= Input (J))
              use I => 0];

The "when" clause should filter the input to just the unique values.
The "use" clause creates the mapping between key value and count value (Initially 0).

Then you could just write:

   for Number of Input loop
      Counts (Number) := Counts (Number) + 1;
   end loop;

To update the counts.

I leave it to the reader to decide whether this is clearer than what you had,
as I think many would prefer what you had.

For that matter, you could do it all in one shot and even make the map a constant.

   Counts : constant Count_Maps.Map
     := [for I in Input'Range
           when (for all J in Input'First .. I - 1 => Input (I) /= Input (J))
              use I =>
                 [for K in Input'Range when Input (K) = Input (I)) => 1]
                   'Reduce("+", 0)];

Using a reduction expression to count the values. 
But this is definitely quite a mouthful.

I think if one wanted a constant object, it would be clearer to write a
function that returns the map container object using a simpler form of expression to create the return object.

It would be nice however, if one could test membership of an array or container using "in" or "not in" to see if a particular element value can be found.

Then one could write;

Counts : Count_Maps.Map :=  
  [for I in Input'Range when (Input (I) not in Input (1 .. I - 1)) use I => 0];

To create the initial map objects, which is easier to read.

Similarly, it would be nice to apply 'Max or 'Min to an array or container object, which could be shorthand forms for reduction expressions using Ada 2020 syntax to return the largest or smallest element in the array or container.

e.g.
  Put_Line ("Biggest=>" & Natural'Image(Input'Max));

But if these ideas have any merit, you'd have to look past Ada 2020 to a future version of the language.

Brad

Re: Tally

[Randy Brukardt]

"Brad Moore" <bmoore.ada@gmail.com> wrote in message 
news:4967a95b-3d79-4a5b-a30d-0f04f00ebbc4@googlegroups.com...
...
> For that matter, you could do it all in one shot and even make the map a 
> constant.
>
>   Counts : constant Count_Maps.Map
>     := [for I in Input'Range
>           when (for all J in Input'First .. I - 1 => Input (I) /= Input 
> (J))
>              use I =>
>                 [for K in Input'Range when Input (K) = Input (I)) => 1]
>                   'Reduce("+", 0)];
>
> Using a reduction expression to count the values.
> But this is definitely quite a mouthful.

So Ada 202x will allow us to catch up to C++ and many other "expressive" 
languages by allowing us to have "guess what this code does" contests!! :-)

Compared to Jere's loop, the above is impentrable. And it's hard to guess 
the performance of that (I'd have to expand the aggregate into its 
underlying operations to figure out whether it is more or less expensive 
than the simple loop would be).

                            Randy.

Re: Tally

[Jeffrey R. Carter]

On 1/16/20 4:35 PM, Brad Moore wrote:
> 
>     Counts : Count_Maps.Map
>       := [for I in Input'Range
>             when (for all J in Input'First .. I - 1 => Input (I) /= Input (J))
>                use I => 0];

I think you want

    use Input (I) => 0

here (and further on). I can figure out what this does, but I wouldn't call it 
clear.

>     Counts : constant Count_Maps.Map
>       := [for I in Input'Range
>             when (for all J in Input'First .. I - 1 => Input (I) /= Input (J))
>                use I =>
>                   [for K in Input'Range when Input (K) = Input (I)) => 1]
>                     'Reduce("+", 0)];

This is getting close to write-only code.

-- 
Jeff Carter
"I'm a lumberjack and I'm OK."
Monty Python's Flying Circus
54

Re: Tally

[Jeffrey R. Carter]

On 1/16/20 9:20 PM, Randy Brukardt wrote:
> 
> So Ada 202x will allow us to catch up to C++ and many other "expressive"
> languages by allowing us to have "guess what this code does" contests!! :-)

Don't worry. No doubt in Ada 3X we'll be able to write

    C<-,I!\{+0

-- 
Jeff Carter
"I'm a lumberjack and I'm OK."
Monty Python's Flying Circus
54

Re: Tally

[Simon Wright]

"Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org> writes:

>>     Counts : constant Count_Maps.Map
>>       := [for I in Input'Range
>>             when (for all J in Input'First .. I - 1 => Input (I) /= Input (J))
>>                use I =>
>>                   [for K in Input'Range when Input (K) = Input (I)) => 1]
>>                     'Reduce("+", 0)];
>
> This is getting close to write-only code.

Already there.

Re: Tally

[Brad Moore]

On Thursday, January 16, 2020 at 3:25:50 PM UTC-7, Simon Wright wrote:
> "Jeffrey R. Carter"  writes:
> 
> >>     Counts : constant Count_Maps.Map
> >>       := [for I in Input'Range
> >>             when (for all J in Input'First .. I - 1 => Input (I) /= Input (J))
> >>                use I =>
> >>                   [for K in Input'Range when Input (K) = Input (I)) => 1]
> >>                     'Reduce("+", 0)];
> >
> > This is getting close to write-only code.
> 
> Already there.

That'll be the challenge, I think. With more tools (and new ones) to work with, one hopes people will end up choosing the right tool for the job.
Some of the new tools are powerful, and there might be a tendency to want to use them, but a simpler tool can get the job done faster sometimes.

This example feels like using a big new table saw to slice bread, when a good 'ol bread knife can get it done faster and better.

Note that the simple loop accomplishes the task with a single pass through the date. The monster expression has 3 levels of nested loops, so hard to imagine it would beat the simple loop.

Brad

Re: Tally

[Brad Moore]

On Wednesday, January 15, 2020 at 2:03:14 AM UTC-7, Simon Wright wrote:

> 
> and then of course
> 
>    for C in Counts.Iterate loop
>       Put_Line (Count_Maps.Key (C)'Image
>                   & " -> "
>                   & Count_Maps.Element (C)'Image);
>    end loop;

This is interesting, in AI12-0189-1/07 (Loop body as anonymous procedure), there is an example given in the AI showing how the feature could be used
to similarly iterate through a map container.

   for (C : Cursor) of My_Map.Iterate loop
      Put_Line (My_Key_Type'Image (Key (C)) & " => " &
         My_Element_Type'Image (Element (C)));
   end loop;

   -- The above is equivalent to:

   declare
      procedure P (C : Cursor) is
      begin
         Put_Line (My_Key_Type'Image (Key (c)) & " => " &
            My_Element_Type'Image (Element (C)));
      end P;
   begin
      My_Map.Iterator (P'Access);
   end;

Here is another example where new Ada 2020 machinery is used to do something, which ends up looking more complicated than doing it the gool ol' Ada 2012 way ;-). The only real difference is that "(C: Cursor)" is replacing "C", and its an "of" loop, rather than an "in" loop.

While the example is illustrative, I think a better example is needed at least, 
as we shouldn't be showing an example if it is ultimately not the recommended way to tackle the problem. I would recommend Simon's loop over this.

Brad