Thread overview | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
|
June 11, 2019 Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
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
|
June 11, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | 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 |
June 11, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | 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. |
June 11, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | 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. |
June 11, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to KnightMare | 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 |
June 12, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | 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`
|
June 12, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Paul Backus | 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 |
June 12, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | 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 |
June 13, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Robert M. Münch | 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.
|
June 14, 2019 Re: Elegant way to test if members of array A are present in array B? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Meta | 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 |
Copyright © 1999-2021 by the D Language Foundation