www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Elegant way to test if members of array A are present in array B?

reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
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
Jun 11 2019
next sibling parent Alex <sascha.orlov gmail.com> writes:
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
Jun 11 2019
prev sibling next sibling parent reply Paul Backus <snarwin gmail.com> writes:
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.
Jun 11 2019
parent reply =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
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
Jun 11 2019
parent Paul Backus <snarwin gmail.com> writes:
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.
Jun 12 2019
prev sibling next sibling parent reply KnightMare <black80 bk.ru> writes:
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.
Jun 11 2019
parent KnightMare <black80 bk.ru> writes:
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
Jun 11 2019
prev sibling next sibling parent Murilo <murilomiranda92 hotmail.com> writes:
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`
Jun 11 2019
prev sibling parent reply Meta <jared771 gmail.com> writes:
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
Jun 12 2019
parent =?iso-8859-1?Q?Robert_M._M=FCnch?= <robert.muench saphirion.com> writes:
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
Jun 14 2019