Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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;imid;++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.
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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 :)
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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!
Re: Reflections on isPalindrome
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?
Re: Reflections on isPalindrome
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
Re: Reflections on isPalindrome
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
Re: Reflections on isPalindrome
On Fri, Oct 24, 2014 at 09:56:18PM +, 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
--
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.
Re: Reflections on isPalindrome
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.
Re: Reflections on isPalindrome
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!
