I need a case-insensitive check to see if a string contains another string for a "quick filter" feature. It should preferrably be perceived as instant by the user, and needs to check a few thousand strings in typical cases. Is a regex the best option, or what would you suggest?

On 10/5/22 12:59 PM, torhu wrote:

https://dlang.org/phobos/std_uni.html#asLowerCase

bool isearch(S1, S2)(S1 haystack, S2 needle)
{
    import std.uni;
    import std.algorithm;
    return haystack.asLowerCase.canFind(needle.asLowerCase);
}

untested.

-Steve

On Wednesday, 5 October 2022 at 17:29:25 UTC, Steven Schveighoffer wrote:
[...]

I wanted to do some quick benchmarking to figure out what works.

When I run this:

import std.stdio;
import std.datetime.stopwatch;

void main()
{
	auto sw = StopWatch();	
	sw.stop();
	writeln(sw.peek().toString());
}

It prints this:

Am I doing something wrong here?

On Wednesday, 5 October 2022 at 20:40:46 UTC, torhu wrote:

Right, you can instantiate structs without arguments. It's been ten years since I last used D, I was thinking of structs like if they were classes.

On Wednesday, 5 October 2022 at 20:45:55 UTC, torhu wrote:

I think there should be sensible default here, seems like an easy trap to remove.

On Wednesday, 5 October 2022 at 17:29:25 UTC, Steven Schveighoffer wrote:

bool isearch(S1, S2)(S1 haystack, S2 needle)
{
    import std.uni;
    import std.algorithm;
    return haystack.asLowerCase.canFind(needle.asLowerCase);
}

I did some basic testing, and regex was two orders of magnitude faster. So now I know, I guess.

On Wednesday, 5 October 2022 at 21:50:32 UTC, torhu wrote:

Substring search functionality is currently in a very bad shape in Phobos. I discovered this myself a few weeks ago when I was trying to solve the https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/A2 puzzle using D language. A part of the solution requires a fast substring search (actually a subarray search) and Phobos doesn't offer anything with even remotely acceptable performance.

Phobos does have a Boyer-Moore implementation. This algorithm is historically famous in computer science as one of the first attempts to optimize substring search, but it also has pathologically bad performance on certain input data and probably shouldn't be recommended for any practical use nowadays. The users of old versions of Python discovered this too: https://codeforces.com/blog/entry/106849?#comment-952483

The standard 'find' function from the following simple example also becomes awfully slow when arrays 'a' and 'b' are large and/or are adversarially constructed:

import std;
void main() {
  auto a = [1, 2, 3, 4];
  auto b = [2, 3];
  writefln("Is %s a subarray of %s? The answer is %s.",
           b, a, a.find(b).empty ? "no" : "yes");
}

I think that the best fit for your use case is the https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm and there's an old issue in bugzilla about this: https://issues.dlang.org/show_bug.cgi?id=16066

BTW, if anyone is curious, one of the possible solutions for the hacker-cup/2022/round-1/problems/A2 puzzle in D language can be found here: https://codeforces.com/blog/entry/106768?#comment-952808

On Thursday, 6 October 2022 at 08:15:10 UTC, Siarhei Siamashka wrote:

Please don’t tell us that D will be slower than Python again?)