Thread overview | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
October 24, 2014 Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
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? |
October 24, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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 -- Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем. |
October 24, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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. |
October 24, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Peter Alexander | 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!
|
October 26, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Peter Alexander | 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 |
October 27, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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.
|
October 27, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Marc Schütz | 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!
|
October 27, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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?
|
October 27, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrea Fontana | 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 |
October 28, 2014 Re: Reflections on isPalindrome | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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. |
Copyright © 1999-2021 by the D Language Foundation