How to determine if all characters in a string are equal

Question

I need to know if all characters in a string are equal (formed by the same character). the function must return true or false depending if all the elements of the string are equal to an particular char.

I wrote this function that works well, but I'm looking for a more optimal (fastest) solution, the strings can have thousands of chars.

function AllElementsAreEqual(Element:Char;Str:String):Boolean;
var
  i : Integer;
begin
Result:=True;
 if Str<>'' then
  for i:=1 to Length(Str) do
   if  Str[i]<>Element then
   begin
      Result:= False;
      exit;
   end;
end;

UPDATE finally using the Barry Kelly Suggestion and adding the inline directive, the performance was significantly improved.

function AllElementsAreEqual(Const Element:Char;Str:String):Boolean;inline;
type
ArrayInt = Array of Integer;
var
  i    : Integer;
  Delta: Integer;
  List : ArrayInt;
  Test : Integer;
begin
  Result:=True;
  Delta:=(Length(Str) mod  4);
  if Delta<>0 then
  Str:=Str+StringOfChar(Element,4-Delta);
  Test:=Ord(Element) + Ord(Element) shl 8 + Ord(Element) shl 16 + Ord(Element) shl 24;
  List:=ArrayInt(@(Str[1]));

  for i:=0 to ((Length(Str) div 4)-1) do
   if List[i]<>Test  then
    begin
     Result:=False;
     exit;
    end;
end;

UPDATE 2

i'm sorry but i posted an old implementation of the solution (with a bug), now is fixed. Thanks to The_Fox for create a better implementation of the Barry suggestion.

Ukase

why not use the "===" triple equal thats what its used for. compares if that is absolutely = to. Checks data type as well as the chars – Cutlerr

@Val, since when does Delphi have "==="? Are you confusing Delphi with JavaScript? – Platus

my bad I was thinking of something else... – Cutlerr

Answer 1

You could consider creating an Integer value with the Element repeated 4 times (since this is AnsiChar in Delphi 7), shifted like Ord(Element) + Ord(Element) shl 8 + Ord(Element) shl 16 + Ord(Element) shl 24, then typecast the string to a PIntegerArray (^array[0..MaxInt div 4 - 1] of Integer) and loop over it Length(Str) div 4 times, comparing as integers instead of characters. You'll need to compare the last few Length(str) mod 4 characters manually though.

Dedie

Is this the kind of trick the Delphi compiler uses to be so fast? ;) – Carduaceous

It is one of the tricks it uses for string hashing and comparisons, yes. – Dedie

Answer 2

You implemented the suggestion of Barry Kelly wrong. When I test it on Delphi 7, it is even slower than your first implementation and it gives wrong results if your stringlength is not divisible by 4.

I tested it with this string: StringOfChar('c', 100000) + 'x'; and your new function returns True AllElementsAreEqual('c', StringOfChar('c', 100000) + 'x') while it should return False.

Your implementation is slower because you are trying to make your string divisable by four (in which you fail, but you can figure out by yourself why it fails) and thus creating a new string which needs memory allocations which are costly.

Another dangerous thing you do is letting a dynamic array (array of integer) point to a string. Both are refcounted and this can lead to strange results. Please follow Barry Kelly's advise and use a PIntegerArray!

I think Barry Kelly meant this:

function AllElementsAreEqual(const aElement: Char; const aStr: string): Boolean;
var
  lIntArray: PIntegerArray;
  i: Integer;
  lTest: Integer;
begin
  Result := True;
  lTest := Ord(aElement) + Ord(aElement) shl 8 + Ord(aElement) shl 16 + Ord(aElement) shl 24;

  lIntArray := @aStr[1];
  for i := 0 to Length(aStr) div 4 - 1 do
    if lIntArray[i] <> lTest then
    begin
      Result := False;
      Exit;
    end;

  for i := Length(aStr) - (Length(aStr) mod 4) + 1 to Length(aStr) do
    if aStr[i] <> aElement then
    begin
      Result := False;
      Exit;
    end;
end;

NB: Your function returns True for empty strings, is that OK?

NB2: Please award points to Barry Kelly's answer and not mine, because this is really an oversized comment and not an answer.

Skiba

+1 i'm sorry but last night I did many tests with different implementations and i posted an old implementation of the proposed solution (with a bug), now is fixed. Thanks very much for create a better implementation of the Barry suggestion. – Ukase

Answer 3

Maybe use StringOfChar to generate a string with the target char repeated N times, then do a string comparison instead of comparing char-by-char.

(Don't know if this is actually faster; measure & see).

Febrifugal

Answer 4

You could implement a Select algorithm to faster find char out of place, this will not increase the speed it the string is "True", but it should make it somewhat faster.

Pangermanism

Answer 5

Get the string length, use GetMem to allocate memory the size of the string. FillChar the memory with the desired char. Then use CompareMem to compare the string and the memory

Lemuel

Answer 6

From what i understood from your code

Result:= False;

":=" is used to assign value to a variable. how do you compare 2 values in delphi?

Tempt

Operators in Delphi: library.thinkquest.org/C006657/delphi/operators_in_delphi.htm – Platus

In a logical way, with an equals sign, rather than equals equals or === or other oddity. := is usually read as "is assigned to" or "becomes". == comes from "C" (and originally "B"). However BCPL used :=, which came from Algol. Because of this odd decision (presumably by Thompson and/or Ritchie) thousands of bugs have been created by misuse of = rather than == – Sherrer

genius, how can I never think about that. Frankly, I've never been seeing such a brilliant answer, but you missed something, that is, the : mark is called a colon in English. I hope many people here keep voting your answer up. >-( – Vaish

The sarcasm is uncalled for, @Vantomex. – Clingstone

@Rob, Don't you see he just want to play intentionally with his answer? This bad attitudes might tend to be repeat again and again if there is no consequence of doing so. Why did you say that to me, Gerry did as I did too? And why didn't you warn @Tempt absolutely? – Vaish