On Tuesday, 26 January 2021 at 21:55:47 UTC, mw wrote:
On Tuesday, 26 January 2021 at 17:40:36 UTC, methonash wrote:
foreach( i, ref pStr; sortedArr )
{
foreach( j, ref cStr; sortedArr[ i + 1 .. $ ] )
{
if( indexOf( pStr, cStr ) > -1 )
{
// ... yourInnerOp
}
}
}
Before adding the code excerpt above, the Dlang program was
taking ~1 second on an input file containing approx. 64,000
strings.
What's the typical length of your strings?
Actually, I think it's reasonable given your algo:
Your algo (double-loop) is O(n^2), n = 64,000
so the loop will run n^2 = 4,096,000,000 i.e 4G
Suppose your CPU is 2GHz, and suppose each loop operation take
just 1 machine cycle (very unlikely), this algo will take 2
seconds.
However, string searching i.e `indexOf`, or `yourInnerLoop` can
easily take hundreds of cycles, let's suppose it's 100 machine
cycles (still a very low estimate), then the algo will take ~200
seconds = ~3.3 minutes.
If you want, you can try to rewrite your algo in Java or Python,
and compare the run time with the Dlang version.
