Paradox Community
Search:

 Welcome |  What is Paradox |  Paradox Folk |  Paradox Solutions |
 Interactive Paradox |  Paradox Programming |  Internet/Intranet Development |
 Support Options |  Classified Ads |  Wish List |  Submissions 


Paradox Newsgroups  |  Paradox Web Sites  |  Paradox Book List  |  FAQs From The Corel FAQ Newsgroup  



Subject: FAQ:Concatenating Large Strings:2001.02.05

Version 1.0 (2001.02.05)
Written by gfk (gfk05@gmx.net)
Edited by Mike Irwin

====================
0. Introduction
====================

This FAQ deals about the rather special case when large
strings have to be constructed with the means of OPAL.
Now you are warned that this might become a little bit
boring....

-------------------------------
 0.1 Legal Info and Disclaimers
-------------------------------

Paradox is a trademark of Corel.
Borland Database Engine (BDE) is a trademark of Inprise.

The information provided in this FAQ is provided "as is"
and is not warranted in any way. The information provided
in this FAQ is not endorsed or authorized by Corel or
Inprise in any shape, form, or manner. The editors claim
NO responsibility for ANY illegal activity regarding
this file, or as a result of someone reading this file.

You may distribute this file, as long as the copies are
complete, unaltered, and are in electronic form only.

-------------
 0.2 Feedback
-------------

Please send feedback in a Corel Paradox newsgroup or the
news:comp.databases.Paradox newsgroup to any of the FAQ
Team mentioned in the "FAQ: FAQ FAQ" document.
Please specify the FAQ name and section number the
comment applies to, if any.

====================
0. Introduction
====================

This article deals about the rather special case that
large strings have to be constructed with the means of
OPAL. Now you are warned that this might become a
little bit boring...

====================
1. Task
====================
A string shall be computed by concatenation of a large
number (let's say: 1000) of very short strings. For
simplicity, we assume that these short strings consist
of a single character.

For this discussion, I call the length of the result N.
The operation which computes the i-th character is
called f(i). In practice, this may be any string
expression.

Practical example:
   Convert a string from one character set to another.
   f(i) computes the converted character at the i-th
   position.

====================
2. Simple approach
====================
r = ""
for i from 1 to N
    r = r + f(i)
endFor
return r

Cost of this algorithm:

Memory management:
   O(N) temporary result strings have to be allocated.

Copying:
   O(N*N) (roughly N*N/2) times a character is copied.

====================
3. Advanced approach
====================
r = ""
s = ""
for i from 1 to N
    s = s + f(i)
    if s.size()>r.size() then
       r = r + s
       s = ""
    endIf
endFor
return r + s

Cost of this algorithm:

I have failed to find a formula (maybe someone can who
is better at math than I), but I assume the following
for all N>k, where k is some positive constant:

Memory managment: MM(N) < O(N)

Copying: O(N*ld(N)) <= CP(N) < O(N*N)

In other words: For a sufficently large N, the cost of
the additional logic is lower than the saved cost of MM
and copying.

====================
4. Benchmark results
====================
For comparing the two algorithms, I have used a
single-character string (".") expression for f(i).
Thus the computed string simply consists of N dots.
There are overheads and a measurement inaccuracy
involved, but these are independent of N and the same
with both variants of the algorithm.

  N   |  T1  |  T2
-------------------
 2500 |   60 |   20
 5000 |  260 |   60
10000 | 1150 |  210
20000 | 5390 |  780

T1 is the time spent inside the simple algorithm, while
T2 is the time spent with the advanced approach. Both
times are in milliseconds. As one can see quiet easily,
the advanced algorithm is significantly faster, and its
cost grows much more slowly.

====================
5. Final remarks
====================
f(i) may return strings larger than 1 character, which
was the case with my application (converting a string
into HTML, where some characters have representations
like """).

The proposed algorithm increases the complexity of the
code. It helps to encapsulate the logic, for example
in a 'method put(const x String)' and a
'method get() String'.

====================
6. Disclaimer
====================
The basic ideas of the proposed algorithm are
well-known. I do *not* claim having invented it.
Thus everybody is free to use or modify it.


Paradox Community Newsgroups


 Feedback |  Paradox Day |  Who Uses Paradox |  I Use Paradox |  Downloads 


 The information provided on this Web site is not in any way sponsored or endorsed by Corel Corporation.
 Paradox is a registered trademark of Corel Corporation.


 Modified: 15 May 2003
 Terms of Use / Legal Disclaimer


 Copyright © 2001- 2003 Paradox Community. All rights reserved. 
 Company and product names are trademarks or registered trademarks of their respective companies. 
 Authors hold the copyrights to their own works. Please contact the author of any article for details.