![]() |
![]() |
|
![]() |
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. ![]() |
![]() |
|