www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Reflections on isPalindrome

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
I would appreciate comments on my palindrome predicate function

bool isPalindrome(R)(in R range)  safe pure
     if (isBidirectionalRange!(R))
{
     import std.range: retro, take;
     import std.algorithm: equal;
     static if (hasLength!R)
     {
         const mid = range.length/2; // too long for string
         return equal(range.retro.take(mid),
                      range.take(mid));
     }
     else
     {
         return range.retro.equal(range);
     }
}
unittest
{
     assert("dallassallad".isPalindrome);
     assert(!"ab".isPalindrome);
     assert("a".isPalindrome);
     assert("åäå".isPalindrome);
     assert("".isPalindrome);
     assert([1, 2, 2, 1].isPalindrome);
}
alias isSymmetrical = isPalindrome;

also defined here

https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L773

Specifically I wonder what to do with

     const mid = range.length/2; // TODO too long for string

when R is a string.

Further, I would like to extend isPalindrome() with a minimum 
length argument minLength that for string and wstring does

import std.uni: byDchar;
range.byDchar.array.length >= minLength.

AFAIK this will however prevent my algorithm from being 
single-pass right?
Oct 24 2014
next sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Fri, Oct 24, 2014 at 09:56:18PM +0000, "Nordlöw" via Digitalmars-d-learn
wrote:

 I would appreciate comments on my palindrome predicate function
 
 bool isPalindrome(R)(in R range)  safe pure
     if (isBidirectionalRange!(R))
 {
     import std.range: retro, take;
     import std.algorithm: equal;
     static if (hasLength!R)
     {
         const mid = range.length/2; // too long for string
         return equal(range.retro.take(mid),
                      range.take(mid));
     }
     else
     {
         return range.retro.equal(range);
     }
 }


[...]

I'd just do it the simple way using range primitives:

	bool isPalindrome(R)(in R range)
		if (isBidirectionalRange!R)
	{
		auto r = range.save;
		while (!r.empty)
		{
			if (r.front != r.back)
				return false;
			r.popFront();
			r.popBack();
		}
		return true;
	}

This is guaranteed to work on all bidirectional ranges in single-pass,
handles odd/even lengths correctly, and doesn't depend on .length.

Offhand remark: in general you shouldn't annotate template functions
with  safe or pure. Instead, let the compiler infer those attributes,
and use  safe/pure unittests with known  safe/pure ranges to ensure your
code itself doesn't introduce any un- safe or impure operations.
Otherwise, your function cannot be used with a range that has un- safe
or impure range methods.


T

-- 
Государство делает вид, что платит нам
зарплату, а мы делаем вид, что работаем.
Oct 24 2014
prev sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Friday, 24 October 2014 at 21:56:20 UTC, Nordlöw wrote:

 bool isPalindrome(R)(in R range)  safe pure


Aside: for templates, just let the compiler infer  safe and pure. 
You don't know whether the range operations on R are pure or not.

As for the actual algorithm, there's no need for the random 
access version, and you bidirectional version does twice as much 
as necessary:

Just do:

while (!range.empty)
{
   if (range.front != range.back) return false;
   range.popFront();
   if (range.empty) break;
   range.popBack();
}
return true;

This automatically handles narrow strings.



 Further, I would like to extend isPalindrome() with a minimum 
 length argument minLength that for string and wstring does

 import std.uni: byDchar;
 range.byDchar.array.length >= minLength.

 AFAIK this will however prevent my algorithm from being 
 single-pass right?


I'm not sure what you are saying here, but hopefully the above 
code obviates this anyway.
Oct 24 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Friday, 24 October 2014 at 22:29:12 UTC, Peter Alexander wrote:

 On Friday, 24 October 2014 at 21:56:20 UTC, Nordlöw wrote:

 bool isPalindrome(R)(in R range)  safe pure


 Aside: for templates, just let the compiler infer  safe and 
 pure. You don't know whether the range operations on R are pure 
 or not.

 As for the actual algorithm, there's no need for the random 
 access version, and you bidirectional version does twice as 
 much as necessary:

 Just do:

 while (!range.empty)
 {
   if (range.front != range.back) return false;
   range.popFront();
   if (range.empty) break;
   range.popBack();
 }
 return true;

 This automatically handles narrow strings.



 Further, I would like to extend isPalindrome() with a minimum 
 length argument minLength that for string and wstring does

 import std.uni: byDchar;
 range.byDchar.array.length >= minLength.

 AFAIK this will however prevent my algorithm from being 
 single-pass right?


 I'm not sure what you are saying here, but hopefully the above 
 code obviates this anyway.


Clever. Thx!
Oct 24 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Friday, 24 October 2014 at 22:29:12 UTC, Peter Alexander wrote:

 Further, I would like to extend isPalindrome() with a minimum 
 length argument minLength that for string and wstring does




I extended my algorithm with a minLength argument 
https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L774
Oct 26 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 26 October 2014 at 20:38:29 UTC, Nordlöw wrote:

 On Friday, 24 October 2014 at 22:29:12 UTC, Peter Alexander 
 wrote:

 Further, I would like to extend isPalindrome() with a minimum 
 length argument minLength that for string and wstring does




 I extended my algorithm with a minLength argument 
 https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L774


You could add an early `return false;` if the range has length 
and it is less than minLength.
Oct 27 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 27 October 2014 at 12:10:59 UTC, Marc Schütz wrote:

 You could add an early `return false;` if the range has length 
 and it is less than minLength.


See update :)

Thanks!
Oct 27 2014
parent reply "Andrea Fontana" <nospam example.com> writes:
On Monday, 27 October 2014 at 16:59:19 UTC, Nordlöw wrote:

 On Monday, 27 October 2014 at 12:10:59 UTC, Marc Schütz wrote:

 You could add an early `return false;` if the range has length 
 and it is less than minLength.


 See update :)

 Thanks!


And you can return true if length <= 1

Why bidirectional range only?
Oct 27 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Monday, 27 October 2014 at 21:28:17 UTC, Andrea Fontana wrote:

 And you can return true if length <= 1


Thanks.


 Why bidirectional range only?


popBack() only for

http://dlang.org/phobos/std_range.html#isBidirectionalRange
Oct 27 2014
next sibling parent reply "MattCoder" <stopthespam mail.com> writes:
Hi,

I don't know if I'm missing something but I did some tests with 
the popFront and popBack version:

bool isPalindrome(R)(R range)
if (isBidirectionalRange!(R))
{
	while (!range.empty){
		if (range.front != range.back) return false;
   		range.popFront();
   	if (range.empty) break;
   	range.popBack();
	}
	return true;
}

Against the older known version (or implementation):

bool isPalindrome2(R)(R r){
     auto len = r.length;
     auto mid = len/2;
     --len;
     for(auto i=0;i<mid;++i){
         if(r[i]!=r[len-i]){
             return false;
	}
     }
     return true;
}

And in my benchmark test, the first version is 3x "slower" than 
the second one.

Matheus.
Oct 28 2014
parent reply "MattCoder" <stopthespam mail.com> writes:
On Tuesday, 28 October 2014 at 11:48:37 UTC, MattCoder wrote:

 And in my benchmark test, the first version is 3x "slower" than 
 the second one.


I forgot to say that I'm compiling with DMD without any compiler 
hints/optimizations.

Matheus.
Oct 28 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 28 October 2014 at 11:51:42 UTC, MattCoder wrote:

 I forgot to say that I'm compiling with DMD without any 
 compiler hints/optimizations.


Try compiling with DMD flag

-release

and perhaps also

-release -noboundscheck

to get relevant results.

DMD is currently not that good at inlining range primitives.
Oct 28 2014
parent reply "MattCoder" <stopthespam mail.com> writes:
On Tuesday, 28 October 2014 at 13:30:05 UTC, Nordlöw wrote:

 On Tuesday, 28 October 2014 at 11:51:42 UTC, MattCoder wrote:

 I forgot to say that I'm compiling with DMD without any 
 compiler hints/optimizations.


 Try compiling with DMD flag

 -release

 and perhaps also

 -release -noboundscheck

 to get relevant results.

 DMD is currently not that good at inlining range primitives.


Interesting!

With -release the second version still faster but only by 10%.

Now with: -release -noboundscheck they are equal and sometimes 
your version is slightly faster by ~3 milliseconds.

Matheus.
Oct 28 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Tuesday, 28 October 2014 at 14:09:50 UTC, MattCoder wrote:

 Now with: -release -noboundscheck they are equal and sometimes 
 your version is slightly faster by ~3 milliseconds.


That is great to hear!

You should try profiling with ldc aswell.
Oct 28 2014
prev sibling parent reply "MachineCode" <netorib94 gmail.com> writes:
On Tuesday, 28 October 2014 at 14:09:50 UTC, MattCoder wrote:

 On Tuesday, 28 October 2014 at 13:30:05 UTC, Nordlöw wrote:

 On Tuesday, 28 October 2014 at 11:51:42 UTC, MattCoder wrote:

 I forgot to say that I'm compiling with DMD without any 
 compiler hints/optimizations.


 Try compiling with DMD flag

 -release

 and perhaps also

 -release -noboundscheck

 to get relevant results.

 DMD is currently not that good at inlining range primitives.


 Interesting!

 With -release the second version still faster but only by 10%.

 Now with: -release -noboundscheck they are equal and sometimes 
 your version is slightly faster by ~3 milliseconds.

 Matheus.


I'm very surprise. If they either equal or fast sometimes the 
compiler did great optizations or it's just a multicore processor 
that's helping or what else? the first version (from your post, 
the one using ranges) change in each iteration two pointers (in 
pop*() calls) and request r's length 3 times (in .empty calls) 
while the second doesn't, just run until an already know index 
(when enter in the loop) and access two index in each iteration. 
This without consider the amount of ifs.

I don't know, maybe I just thinking in the C-way as that code 
would run.
Oct 28 2014
parent "MattCoder" <stopthespam mail.com> writes:
On Tuesday, 28 October 2014 at 16:07:38 UTC, MachineCode wrote:

 I'm very surprise. If they either equal or fast sometimes the 
 compiler did great optizations or it's just a multicore 
 processor that's helping or what else? the first version (from 
 your post, the one using ranges) change in each iteration two 
 pointers (in pop*() calls) and request r's length 3 times (in 
 .empty calls) while the second doesn't, just run until an 
 already know index (when enter in the loop) and access two 
 index in each iteration. This without consider the amount of 
 ifs.

 I don't know, maybe I just thinking in the C-way as that code 
 would run.


Yes, I'm curious about this too. I will check the assembly output 
later (When I have free time) to understand what is happening and 
why popFront/Back are faster than a loop.

Matheus.
Oct 29 2014
prev sibling parent "Andrea Fontana" <nospam example.com> writes:
On Monday, 27 October 2014 at 22:53:57 UTC, Nordlöw wrote:

 Why bidirectional range only?


 popBack() only for


I mean: you should write a different version for 
non-bidirectional ranges too :)
Oct 28 2014