🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of rpottsoh

rpottsoh's solution

to Parallel Letter Frequency in the Delphi Pascal Track

Published at Mar 07 2019 · 2 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Count the frequency of letters in texts using parallel computation.

Parallelism is about doing things in parallel that can also be done sequentially. A common example is counting the frequency of letters. Create a function that returns the total frequency of each letter in a list of texts and that employs parallelism.

Testing

In order to run the tests for this track, you will need to install DUnitX. Please see the installation instructions for more information.

Loading Exercises into Delphi

If Delphi is properly installed, and *.dpr file types have been associated with Delphi, then double clicking the supplied *.dpr file will start Delphi and load the exercise/project. control + F9 is the keyboard shortcut to compile the project or pressing F9 will compile and run the project.

Alternatively you may opt to start Delphi and load your project via. the File drop down menu.

When Questions Come Up

We monitor the Pascal-Delphi support room on gitter.im to help you with any questions that might arise.

Submitting Exercises

Note that, when trying to submit an exercise, make sure the exercise file you're submitting is in the exercism/delphi/<exerciseName> directory.

For example, if you're submitting ubob.pas for the Bob exercise, the submit command would be something like exercism submit <path_to_exercism_dir>/delphi/bob/ubob.pas.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you may receive assistance from a mentor.

uParallelLetterFrequencyTest.pas

unit uParallelLetterFrequencyTest;

interface
uses
  DUnitX.TestFramework;

const
  CanonicalVersion = '1.0.0';

type

  [TestFixture]
  ParallelLetterFrequencyTests = class(TObject)
  private
    // Poem by Friedrich Schiller. The corresponding music is the European Anthem.
    const OdeAnDieFreude =
        'Freude schöner Götterfunken' + sLineBreak +
        'Tochter aus Elysium,' + sLineBreak +
        'Wir betreten feuertrunken,' + sLineBreak +
        'Himmlische, dein Heiligtum!' + sLineBreak +
        'Deine Zauber binden wieder' + sLineBreak +
        'Was die Mode streng geteilt;' + sLineBreak +
        'Alle Menschen werden Brüder,' + sLineBreak +
        'Wo dein sanfter Flügel weilt.';

    // Dutch national anthem
    const Wilhelmus =
        'Wilhelmus van Nassouwe' + sLineBreak +
        'ben ik, van Duitsen bloed,' + sLineBreak +
        'den vaderland getrouwe' + sLineBreak +
        'blijf ik tot in den dood.' + sLineBreak +
        'Een Prinse van Oranje' + sLineBreak +
        'ben ik, vrij, onverveerd,' + sLineBreak +
        'den Koning van Hispanje' + sLineBreak +
        'heb ik altijd geëerd.';

    // American national anthem
    const StarSpangledBanner =
        'O say can you see by the dawn''s early light,' + sLineBreak +
        'What so proudly we hailed at the twilight''s last gleaming,' + sLineBreak +
        'Whose broad stripes and bright stars through the perilous fight,' + sLineBreak +
        'O''er the ramparts we watched, were so gallantly streaming?' + sLineBreak +
        'And the rockets'' red glare, the bombs bursting in air,' + sLineBreak +
        'Gave proof through the night that our flag was still there;' + sLineBreak +
        'O say does that star-spangled banner yet wave,' + sLineBreak +
        'O''er the land of the free and the home of the brave?'+ sLineBreak;
  public
    [Test]
//    [Ignore('Comment the "[Ignore]" statement to run the test')]
    procedure No_texts_mean_no_letters;

    [Test]
    [Ignore]
    procedure One_letter;

    [Test]
    [Ignore]
    procedure Case_insensitivity;

    [Test]
    [Ignore]
    procedure Many_empty_texts_still_mean_no_letters;

    [Test]
    [Ignore]
    procedure Many_times_the_same_text_gives_a_predictable_result;

    [Test]
    [Ignore]
    procedure Punctuation_doesnt_count;

    [Test]
    [Ignore]
    procedure Numbers_dont_count;

    [Test]
    [Ignore]
    procedure All_three_anthems_together;
  end;

implementation
uses
  System.Generics.Collections,
  uParallelLetterFrequency;

type
  Assert = class(DUnitX.TestFramework.Assert)
    class procedure AreEqual(const expected,
      actual: TDictionary<char, integer>); overload;
  end;

{ ParallelLetterFrequencyTests }

procedure ParallelLetterFrequencyTests.All_three_anthems_together;
var
  Input: string;
  Actual: TDictionary<char, integer>;
begin
  Input := OdeAnDieFreude + Wilhelmus + StarSpangledBanner;
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.AreEqual(49, Actual['a']);
  Assert.AreEqual(56, Actual['t']);
  Assert.AreEqual(2, Actual['ü']);
end;

procedure ParallelLetterFrequencyTests.Case_insensitivity;
var
  Input: string;
  Actual: TDictionary<char, integer>;
  Expected: TDictionary<char, integer>;
begin
  Input := 'aA';
  Expected := TDictionary<char, integer>.Create;
  Expected.AddOrSetValue('a', 2);
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.AreEqual(Expected, Actual);
end;

procedure ParallelLetterFrequencyTests.Many_empty_texts_still_mean_no_letters;
var
  Input: string;
  Actual: TDictionary<char, integer>;
  i: integer;
begin
  Input := '';
  for i := 1 to 10000 do
    Input := Input + ' ';
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.AreEqual(0, Actual.Count);
end;

procedure ParallelLetterFrequencyTests.Many_times_the_same_text_gives_a_predictable_result;
var
  Input: string;
  Actual: TDictionary<char, integer>;
  Expected: TDictionary<char, integer>;
  i: integer;
begin
  Input := '';
  for i := 1 to 1000 do
    Input := Input + 'abc';
  Expected := TDictionary<char, integer>.Create;
  Expected.AddOrSetValue('a', 1000);
  Expected.AddOrSetValue('b', 1000);
  Expected.AddOrSetValue('c', 1000);
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.AreEqual(Expected, Actual);
end;

procedure ParallelLetterFrequencyTests.No_texts_mean_no_letters;
var
  Input: string;
  Actual: TDictionary<char, integer>;
  Expected: TDictionary<char, integer>;
begin
  Input := '';
  Expected := TDictionary<char, integer>.Create;
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.AreEqual(Expected, Actual);
end;

procedure ParallelLetterFrequencyTests.Numbers_dont_count;
var
  Input: string;
  Actual: TDictionary<char, integer>;
begin
  Input := 'Testing, 1, 2, 3';
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.IsFalse(Actual.ContainsKey('1'));
end;

procedure ParallelLetterFrequencyTests.One_letter;
var
  Input: string;
  Actual: TDictionary<char, integer>;
  Expected: TDictionary<char, integer>;
begin
  Input := 'a';
  Expected := TDictionary<char, integer>.Create;
  Expected.AddOrSetValue('a', 1);
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.AreEqual(Expected, Actual);
end;

procedure ParallelLetterFrequencyTests.Punctuation_doesnt_count;
var
  Input: string;
  Actual: TDictionary<char, integer>;
begin
  Input := OdeAnDieFreude;
  Actual := TParallelLetterFrequency.Calculate(Input);
  Assert.IsFalse(Actual.ContainsKey(','));
end;

{ Assert }

class procedure Assert.AreEqual(const expected,
  actual: TDictionary<char, integer>);
var
  ExpectedItem: TPair<char, integer>;
begin
  Assert.AreEqual(expected.Count, actual.Count);
  for ExpectedItem in expected do
  begin
    Assert.IsTrue(actual.ContainsKey(ExpectedItem.Key));
    Assert.AreEqual(ExpectedItem.Value, actual[ExpectedItem.Key]);
  end;
end;

initialization
  TDUnitX.RegisterTestFixture(ParallelLetterFrequencyTests);
end.
unit uParallelLetterFrequency;
{$define ParallelOperation}
interface
uses
  System.Generics.Collections;

type
  TParallelLetterFrequency = class
    class function Calculate(const aInputLetters: string): TDictionary<char, integer>;
  end;

implementation
uses
  System.SysUtils,
  System.Character,
  System.Threading;

{ ParallelLetterFrequency }

{$ifdef ParallelOperation}
class function TParallelLetterFrequency.Calculate(
  const aInputLetters: string): TDictionary<char, integer>;
begin
  var LowerCased := aInputLetters.ToLowerInvariant;
  var LetterTallies := TDictionary<char, integer>.Create;
  TParallel.For(low(LowerCased), High(LowerCased), procedure(i: Int64)
  begin
    var c := LowerCased[i];
    if c.IsLetter then
    begin
      TMonitor.Enter(LetterTallies);
      try
        if not LetterTallies.ContainsKey(c) then
          LetterTallies.AddOrSetValue(c, 0);
        var x := LetterTallies[c];
        inc(x);
        LetterTallies[c] := x;
      finally
        TMonitor.Exit(LetterTallies);
      end;
    end;
  end);
  result := LetterTallies;
end;

{$else}

class function TParallelLetterFrequency.Calculate(
  const aInputLetters: string): TDictionary<char, integer>;
begin
  var LowerCased := aInputLetters.ToLowerInvariant;
  var LetterTallies := TDictionary<char, integer>.Create;
  For var i := low(LowerCased) to High(LowerCased) do
  begin
    var c := LowerCased[i];
    if c.IsLetter then
    begin
      if not LetterTallies.ContainsKey(c) then
        LetterTallies.AddOrSetValue(c, 0);
      var x := LetterTallies[c];
      inc(x);
      LetterTallies[c] := x;
    end;
  end;
  result := LetterTallies;
end;
{$endif}

end.

Community comments

Find this solution interesting? Ask the author a question to learn more.
Avatar of Selticq

Hello, in order to test the real time saving of parallel calculation, I created an algorithm that runs the string (aInputLetters) for each character allowed. I don't see any difference between parallel calculation and calculation with a normal loop. For more comprehension, you can see my solution.

Regards.

Selticq.

Avatar of rpottsoh

This doesn't really surprise me. TDictionary is not threadsafe. Having to use TMonitor removes any possible advantage and essentially turns the process into a single thread operation since only one thread is active at a time. The solution is more of an exercise in using TParallel. The advantage to using TParallel maybe could be realized if the solution didn't utilize TDictionary.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?