Optimize a function to find a string from sorted TStringList (partial match)

Please find attached a simple Delphi function:

Function StringListPos(const SubStr : String; const List : TStringList; const SkipLine : Integer = -1) : Integer;

Also included in the zip is a Tester application for it. StringListPos is a simple function that searches whether the given sorted TStringList contains the given SubStr and if it does, a line index to the matching line is returned. If no match is found, -1 is returned. The search must be with partial matching and case insensitive, that is, if SubStr = "foo" and List is:

123

Foobar

qwerty

The function call must return 1 (as SubStr "foo" matches to line 1's data "Foobar").

Your job is to make StringListPos as fast as possible. List usually contains partially duplicate data. That is, if we are searching with SubStr = "foobar123" and List is:

0000

123456

foo

foobar

foobar000

foobar123567890

foobarqwrt

You should be able to locate the correct line (i.e. line number 5) by taking benefit from the fact that you know the list is sorted.

I will pay you according to your performance. With your bid, you must give me an estimate of how much you can speed up the Tester app in per cent. I will pay you accordingly, after the job is complete. For example, if you make a bid of $100 and say you can improve the speed by 50%, I will pay you $100 if, after your modifications, the Tester app runs in my computer 50 % faster. If you only manage to improve the speed by 20 %, I will only pay you 20 % of your bid (0.2 x $100 = $20). However, if you manage to improve the speed more than you estimated, for example 70% instead of promised 50%, I will pay you $100 + (70%-50%) = $120. In other words, the faster you get the code, the more you'll earn. Also included in the zip is Profile_REF.txt. It contains the runtime data of the Tester app in my computer, it contains the numbers for you to beat.

Here are the rules: The only thing you can modify in the code is StringListPos function. You cannot assume anything about the contents of SubStr or List, other than List is sorted. You cannot use any proprietary code or assemply code. You must not increase the memory footprint (amount of memory used) of the code by more than 4 fold. That is, running your code must not use over 4 times of memory compared to the original code. If you want to be able to store data between function calls, you are free to do so (either use global variables or convert the function into a class. Latter preferred.)

The solution must be compatible with Delphi 2010 and compatible with unicode strings (as is the current, reference implementation).

With your bid, give me your estimate of how much faster you can make the code, as it will be used to calculate your final pay.

Algoritmi Delphi

Projektin tunnus: #4080528

Tietoa projektista