Tom de Neef

And I correct the timings. As someone wrote, they vary a lot with circumstances. But the relativities are a reasonable indication.

SEARCH:

REPLACE:

Thanks for the report - I've corrected.

The functions are meant for repeated searches:

var t : TstrPosRec; k : integer;

begin

  t:=SetupStrPos(target,source,ignoreCase);

  repeat

     k:=NextStrPos(t);

     if k=0 then break;

     // user code, based on k

  until false;

Thus the initialization overhead is outside the loop.

When you code like this:

  k:=1-target.length;

  repeat

     k:=StrPos(target,source,k+target.length);

     if k=0 then break;

     // user code, based on k

  until false;

you bring all the initialization within the loop. The StrPos function is provided only as a replacement for system.pos (and does not offer ignoreCase for that reason).

I have taken up two suggestions: change the license (to MIT) and use SSE4.2 (both 32 and 64 bit Windows platforms). Timing over 10M trials are as follows:

SEARCH:

REPLACE:

Pls explain your comment about the license. I have no wish to limit use in any way. What license condition should I use then ?

I've seen several queries about 64 bit equivalents for the fast string routines in Win32. And I needed them myself as well.

I have published (assembly based) functions that mimic system.Pos and sysUtils.StringReplace for 32 & 64 bit compiling (both String and AnsiString). Extra feature: searching can be case sensitive or case insensitive.

Timing for string search (1k substrings in 1M string, microsec, see documentation; NextStrPos is new):

Timing for String replace (1k substrings in 1M string, microsec, see documentation; StrReplace is new):

Files and documentation on https://sourceforge.net/projects/delphi-fast-pos-stringreplace/

Added a zip for convenience

(This is a re-start of another thread)

I have published Delphi sorting routines that ought to be similar in speed to TIMsort, for arrays of simple types, strings and objects.

The focus has been on large (10M+) real-world situations, where there is already some order in the data.

The documentation explains how to use in case you do not want generics.

The software is free: https://sourceforge.net/projects/fast-stable-sorting-in-delphi/   It includes a test suite.

Stable sorting of objects with QuickSort is possible by adding to the object a tag that can serve as stability key. In that way I compare sorting speeds of my procedures with Tarray.sort<Tobject>. For (semi-)random data the difference is 5-10 times. When there is already order in the data, the improvement may go up to a factor of 20.

I chose some optimization parameters on the basis of the test arrays that I generated. It would be nice to know if attractive results are obtained when applied to real-world data.

You have a point. But we're talking here about arrays with millions of elements. Who cares about speed when the array is just a few thousand elements long?

My interest comes from server code where the data involves 5 million records and where, together with all the other processing, the target response time is 300 msec.

Anyway, I hope that my contribution to the community is of some value.

Sorting a reversed sorted array is more from the academic world than from the real world. But I have taken the hint and modified the code so that reversed input will be treated well. 

For real-world data (like sorted arrays that have been modified and need re-sorting) and for stable sorting of objects, the speed gain over Delphi's default sorting is immense. It would be nice to see some practical tests.

I have no Timsort with my Delphi's. I responded because I notice that others are seeking fast stable sort routines without generics. If they have Timsort, they can asses the relative performance.

Read the documentation. In the core, it is merge. The selection of sub-arrays is not via a pivot but step-forward as long as ordered, from position 0 onward.

When the source is random, simple types will be sorted with QuickSort.

I have just published Delphi sorting routines that ought to be similar in speed to TIMsort, for arrays of simple types, strings and objects.

The focus has been on large (10M+) real-world situations, where there is already some order in the data.

The documentation explains how to use in case you do not want generics.

The software is free: https://sourceforge.net/projects/fast-stable-sorting-in-delphi/

Hope it is of use.