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

- =?iso-8859-1?Q?Robert_M._M=FCnch?= (6/6) Jun 11 2019 Is there a simple and elegant way to do this? Or is just using a
- Alex (4/6) Jun 11 2019 There is also find_among, but the performance is the same, I
- Paul Backus (7/9) Jun 11 2019 It's a space/time tradeoff. foreach with canFind is O(n^2) time
- =?iso-8859-1?Q?Robert_M._M=FCnch?= (10/15) Jun 11 2019 Yes, that's why I asekd. They haystack is most likely >10 times larger
- Paul Backus (4/9) Jun 12 2019 Hash table insertion and lookup lookup both have amortized O(1)
- KnightMare (8/10) Jun 11 2019 not elegant, not simple. for byte/short/ubye/ushort only
- KnightMare (4/8) Jun 11 2019 *FIX*
- Murilo (19/21) Jun 11 2019 I made it this way, I consider it elegant. I don't know if others
- Meta (5/7) Jun 12 2019 There are two versions of find that can find a range within
- =?iso-8859-1?Q?Robert_M._M=FCnch?= (7/11) Jun 14 2019 Thanks, that looks good. I read the find docs, but somehow didn't

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

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

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

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

On Wednesday, 12 June 2019 at 06:57:55 UTC, Robert M. MÃ¼nch wrote:Hash table insertion and lookup lookup both have amortized O(1) complexity, and D's associative arrays are implemented using hash tables.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.

Jun 12 2019

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

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

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. MÃ¼nch wrote:

Jun 11 2019

On Tuesday, 11 June 2019 at 17:12:17 UTC, Robert M. MÃ¼nch wrote:

Jun 12 2019

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.3Thanks, 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