Is there a simple and elegant way to do this? Or is just using a foreach(...) with canFind() the best way?

-- 
Robert M. Münch
http://www.saphirion.com
smarter | better | faster

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. Münch wrote:
> Is there a simple and elegant way to do this? Or is just using a foreach(...) with canFind() the best way?

There is also find_among, but the performance is the same, I assume.
https://dlang.org/library/std/algorithm/searching/find_among.html

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. Münch wrote:
> Is there a simple and elegant way to do this? Or is just using a foreach(...) with canFind() the best way?

It's a space/time tradeoff. foreach with canFind is O(n^2) time and O(1) space. If you use an associative array or a set, it's O(n) time and O(n) space. If you sort the arrays and use std.algorithm.setops.setDifference it's O(n*log(n)) time and either O(1) or O(n) space, depending on whether you use an in-place sorting algorithm.

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. Münch wrote:
> Is there a simple and elegant way to do this? Or is just using a foreach(...) with canFind() the best way?

not elegant, not simple. for byte/short/ubye/ushort only
https://www.strchr.com/strcmp_and_strlen_using_sse_4.2
https://dlang.org/spec/iasm.html

probably strstr https://dlang.org/library/core/stdc/string/strstr.html implemented over it. there is a tendency to remove dependency from C-runtime.

On Tuesday, 11 June 2019 at 18:39:38 UTC, KnightMare wrote:
> probably strstr https://dlang.org/library/core/stdc/string/strstr.html implemented over it. there is a tendency to remove dependency from C-runtime.

*FIX*
strpbrk
https://dlang.org/phobos/core_stdc_string.html#.strpbrk

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. Münch wrote:
> Is there a simple and elegant way to do this? Or is just using a foreach(...) with canFind() the best way?

I made it this way, I consider it elegant. I don't know if others will like it.
Here it is:
import std.stdio : writeln;
import std.algorithm.searching;
import std.algorithm.sorting;

void main()
{
    int[] a = [3, 9, 1, 4, 7, 6, 5, 8, 2];
    int[] b = [5, 4, 6];
    //first we sort both of them
    sort(a);
    sort(b);
    //now we check them using slices
    writeln(b == a[a.countUntil(b[0]) .. a.countUntil(b[$ - 1]) + 1]);
}

It should output `true`

On 2019-06-11 17:34:00 +0000, Paul Backus said:

> It's a space/time tradeoff. foreach with canFind is O(n^2) time and O(1) space.

Yes, that's why I asekd. They haystack is most likely >10 times larger than the needles. Speed has priority.

> If you use an associative array or a set, it's O(n) time and O(n) space.

I don't see how this is the case. The AA itself has some overhead too. So, the checking loop is O(n) but the AA lookups not.

> If you sort the arrays and use std.algorithm.setops.setDifference it's O(n*log(n)) time and either O(1) or O(n) space, depending on whether you use an in-place sorting algorithm.

I think I will need some testing to see the effect of different approaches...

-- 
Robert M. Münch
http://www.saphirion.com
smarter | better | faster

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. Münch wrote:
> Is there a simple and elegant way to do this? Or is just using a foreach(...) with canFind() the best way?

There are two versions of find that can find a range within another:

https://dlang.org/phobos/std_algorithm_searching.html#.find
https://dlang.org/phobos/std_algorithm_searching.html#.find.3

On Wednesday, 12 June 2019 at 06:57:55 UTC, Robert M. Münch wrote:
>> If you use an associative array or a set, it's O(n) time and O(n) space.
>
> I don't see how this is the case. The AA itself has some overhead too. So, the checking loop is O(n) but the AA lookups not.

Hash table insertion and lookup lookup both have amortized O(1) complexity, and D's associative arrays are implemented using hash tables.

On 2019-06-12 13:58:49 +0000, Meta said:

> There are two versions of find that can find a range within another:
> 
> https://dlang.org/phobos/std_algorithm_searching.html#.find
> https://dlang.org/phobos/std_algorithm_searching.html#.find.3

Thanks, that looks good. I read the find docs, but somehow didn't see/understand the forwardRange part. Not so easy to get...

-- 
Robert M. Münch
http://www.saphirion.com
smarter | better | faster