Re: passing a string to a dll

Part of the reason I wasn't certain about the cost of std::map is that it is a balanced
tree system. However, since I used to worry about all this sort of thing, you have to
look at insertion cost, organization cost, and search cost. There is no one simple answer
except that array is almost always wrong for something that has "thousands" (undefined?
2,000? 200,000?) in its name. Given how easy it is to use std::map or a hash table (I
think it's std::hash, but I haven't used one yet, since what I've needed is sorted sets),
there seems to be little reason to worry about these costs, which can be rendered very
low. Even when using an array, a CArray::SetSize(0, HUGE_ESTIMATED_NUMBER_HERE) will do
wonders for construction. Sorting is less an issue. But given the lookup happens just
once, at startup time, there's a question as to where these values come from. One
approach would be to make them a resource. Then you can create them, sort them, and write
out a resource file that can hold them, and you can use bsearch to search the resource.
I've done this for precanned databases and it works very well indeed. Then the insertion
cost is 0, the sorting cost is 0 (it's all been done beforehand), and we are left only
with lookup cost, and even for reasonable thousands, bsearch works better. The problem
with the original description is that it provides absolutely nothing to go on, just some
vague handwave about "thousands" of items. Quantities matter, certainly quantities to
within an order of magnitude should be provided; details of how the values are created
matters; details of whether or not the values need to be secured matters; key here is that
without a lot more detail than the vague description, no solid answer can be made. But
within the vague parameters given, array sounds suspect as a strategy.
joe

On Wed, 19 Sep 2007 15:16:50 +0200, "Giovanni Dicanio" <giovanni.dicanio@xxxxxxxxxx>
wrote:


"Joseph M. Newcomer" <newcomer@xxxxxxxxxxxx> ha scritto nel messaggio
news:3qc1f39uj6cqkg3j0tr041d67saln7l5h0@xxxxxxxxxx

The real purpose of this particular DLL is to store thousands of
alphanumeric codes. Presently, I do this in a function in the exe,
building
a large CStringArray to which each constant is added, e.g.,
array.Add(_T("K34TU79456T1") ); When a string (code) is passed to this
function, an iteration searches for that string in the array and returns a
bool value accordingly. The call occurs only once during the running of
the
exe. This has been working very effectively, but perhaps not so
efficiently; I am not sure how to evaluate the performance other than that
the results are instantaneous and accurate.
****
This is probably a bad design. Use CMap or std::map, at the very least.
An array is just
about the worst possible choice when thousands of keys are involved, since
the time to
search is O(n/2), whereas for hash tables it can be O(k) for some small
integer k;
std::map is fairly fast, although I'm not sure what its complexity is (I
haven't checked),
but it going to be faster than O(n/2).

My understanding of the OP's problem is the following:

o He stores strings into an array; these strings represent valid codes.

o This array is initialized only once in program life-cycle, at startup.

o He has a function like so:

bool IsValidCode( string codeToCheck )

that searches the input string in the valid-codes array; if the string
is found, then it represents a valid code, and the function returns true;
else the function returns false.

If my understand is correct, I don't very much agree with what Joe suggests
(maybe I have not understood Joe well).

In fact, I think that using the array is just fine in that context.
The array is initialized only once to store the strings representing valid
codes.

The trick here IMHO is to be sure that the array is *sorted*.
In fact, if the array is sorted, then a simple *binary search* with a
O(log(n)) asymptotic complexity would be just fine.
And I think it would be even better than a map, which I think has worse
performance than binary-search's O(log(n)).

Moreover - IIRC, but take it with a grain of salt - I think that std::map is
actually *not* a hash-map, but a BST (binary search *tree*).
I think that the real hash-map is std::hash_map.

But, again, I think that sorted array + binary search would be just fine...


You would need to say more about this list of codes. Are they some
attempt to do license
keys? If so, it would take most 14-year-olds under ten minutes to crack
it.

I completely agree with Joe on this point.


If I move these strings into the DLL function, I will be happy to get them
out of the exe; but what impact does this have on performance, memory
consumption or anything else? Am I gaining or losing anything?
****
Zero. Putting them in a DLL has effectly zero impact. Well, there's a
small cost to load

Maybe the effect would be to make it easier for the cracker to break the
protection: the DLL substitution with a cracked DLL that just returns OK
when codes are checked would be just fine :(


Otherwise, you would use LPCTSTR in the usual (old-fashioned, error-prone,
possibly-storage-leaking) way it has always been used.

There are contexts where LPCTSTR (or better const wchar_t * or even BSTR
IMHO, as COM does) are OK.
For example: if the DLL has a C *interface* (it's OK to use a string class
*inside* the DLL, of course).

BTW: BSTR is even better than wchar_t *, because with wchar_t* it requires
O(n) to find the string length, while with BSTR is is just optimal O(1),
being the BSTR length-prefixed.

Giovanni

Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Relevant Pages

  • Re: passing a string to a dll
    ... I might handle the array. ... I actually have been wondering if I could use a second string ... look at insertion cost, organization cost, and search cost. ...
    (microsoft.public.vc.mfc)
  • Re: passing a string to a dll
    ... you can put a STRINGTABLE in a DLL. ... downward, if> estimate upward, etc., but there is a LoadString to load the string. ... I might handle the array. ... look at insertion cost, organization cost, and search cost. ...
    (microsoft.public.vc.mfc)
  • Re: passing a string to a dll
    ... I might handle the array. ... I actually have been wondering if I could use a second string ... look at insertion cost, organization cost, and search cost. ... Putting them in a DLL has effectly zero impact. ...
    (microsoft.public.vc.mfc)
  • Re: deques, deques, and dequeues
    ... insertions into the array. ... 17 is devoted to amortized analysis. ... Re-allocation strategy 1, double the array size when re- ... number of items inserted approaches infinity, the mean cost of each ...
    (rec.games.roguelike.development)
  • Re: Did SF predict the Internet?
    ... Though if someone wants to front me, say, $250,000, I can finish the development of one that WOULD cost you about that and have many uses at close range. ... If you want long range/high resolution, you'll need to come up with a market which will allow the production demand equal to, say, your current demand for digital cameras. ... Development of high-res IR camera imaging arrays has lagged visible light array development because there isn't nearly the demand for it that will offset development costs; I can get a 320x240 LWIR array unit for about $2,000. ...
    (rec.arts.sf.written)
Loading