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:




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:








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.

Kemahiran: Algoritma, Delphi

Lihat lagi: partial match string, delphi tstringlist find partial, up string, to string, to find a solution, string the, string searching in c, string searching algorithm, string searching, string search in c, string search algorithm c, string search algorithm, string matching in c, string matching algorithm, string match algorithm, string match, string i, string find c, string algorithm, solution algorithm, simple search algorithm, simple performance tester, simple algorithm example, search string in c, search string c

Tentang Majikan:
( 591 ulasan ) Turku, Thailand

ID Projek: #4080528

Dianugerahkan kepada:


I am good at algorithms, I will make your program 30% faster. I will make it the best i.e an O(log n) algorithm that would take the least time. I will build a red-black tree to solve it which will take the least possib Lagi

$90 USD dalam sehari
(2 Ulasan)

2 pekerja bebas membida secara purata $155 untuk pekerjaan ini


Hello, here is my bid

$220 USD dalam 2 hari
(4 Ulasan)