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