The Negative Effect of Traditional Loops Style on the Performance of Algorithms
A new algorithm called Character-Comparison to Character-Access (CCCA) is developed to test the effect of both: 1) converting character-comparison and number-comparison into character-access and 2) the starting point of checking on the performance of the checking operation in string searching. An experiment is performed using both English text and DNA text with different sizes. The results are compared with five algorithms, namely, Naive, BM, Inf_Suf_Pref, Raita, and Cycle. With the CCCA algorithm, the results suggest that the evaluation criteria of the average number of total comparisons are improved up to 35%. Furthermore, the results suggest that the clock time required by the other algorithms is improved in range from 22.13% to 42.33% by the new CCCA algorithm.
[1] M.S. Ager, O. Danvy, and H.K. Rohde. Fast partial evaluation of pattern
matching in strings. ACM/SIGPLAN Workshop Partial Evaluation and
Semantic-Based Program Manipulation, San Diego, California, USA,
pp. 3 - 9, 2003.W.-K. Chen, Linear Networks and Systems (Book style).
Belmont, CA: Wadsworth, 1993, pp. 123-135.
[2] K. Fredriksson and S. Grabowski: Practical and Optimal String
Matching. Proceedings of SPIRE'2005, Lecture Notes in Computer
Science 3772, pp. 374-385, Springer Verlag, 2005.
[3] M. Hernandez, and D. Rosenblueth. Disjunctive partial deduction of a
right-to-left string-matching algorithm. Information Processing Letters,
Vol 87, pp. 235-241, 2003.
[4] A. Apostolico, and R. R.Giancarlo, "The Boyer-Moore-Galil string
searching strategies revisited", SIAM J. Comput. Vol. 15, no. 1, pp. 98-
105, 1986.
[5] M. Crochemore, Transducers and repetitions, Theoret. Comput. Sci.,
Vol. 45, pp. 63-86, 1986.
[6] M. Crochemore, D. Perrin, Two-way string-matching, J. ACM, Vol. 38,
pp. 651-675, 1991.
[7] Z. Galil, R. Giancarlo, On the exact complexity of string matching:
upper bounds, SIAM J. Comput. Vol. 21, pp. 407-437, 1992.
[8] P. D. Smith, Experiments with a very fast substring search algorithm,
SP&E Vol. 21, no. 10, pp. 1065-1074, 1991.
[9] D. M. Sunday, A very fast substring search algorithm, Communications
of the ACM Vol. 33, no. 8, pp. 132-142, 1990.
[10] Z. Liu, X. Du, N. Ishii, An improved adaptive string searching
algorithm, Software-Practice and Experience Vol. 28, no. 2, pp. 191-
198, 1998.
[11] P. Fenwick, Fast string matching for multiple searches, Software-
Practice and Experience Vol. 31, no. 9, pp. 815-833, 2001.
[12] M. Mhashi, A Fast String Matching Algorithm using Double-Length
Skip Distances. Dirasat Journal, University of Jordan, Jordan Vol. 30,
no. 1, pp. 84-92, 2003.
[13] P. Fenwick, Some perils of performance prediction: a case study on
pattern matching. Software-Practice and Experience Vol. 31, no. 9, pp.
835-843, 2001.
[14] A. Al-jaber, M. Mhashi, A modified double skip algorithm in string
searching, AMSE(Association for the advancement of modelling &
Simulation Techniques in Enterprises) Periodicals Vol.8, no. 4, pp. 1-16,
2003.
[15] F. Franek, C. Jennings, W.F. Smyth: A Simple Fast Hybrid Pattern-
Matching Algorithm. In A. Apostolico, M. Crochemore, K. Park (Eds.):
Combinatorial Pattern Matching, Lecture Notes in Computer Science
3537. Springer, pp. 288-297, 2005.
[16] M. Mhashi, The effect of multiple reference characters on detecting
matches in string searching algorithms, Software Practice & Experience
Vol. 35, no. 13, pp. 1299-1315, 2005.M. Young, The Techincal Writers
Handbook. Mill Valley, CA: University Science, 1989.
[1] M.S. Ager, O. Danvy, and H.K. Rohde. Fast partial evaluation of pattern
matching in strings. ACM/SIGPLAN Workshop Partial Evaluation and
Semantic-Based Program Manipulation, San Diego, California, USA,
pp. 3 - 9, 2003.W.-K. Chen, Linear Networks and Systems (Book style).
Belmont, CA: Wadsworth, 1993, pp. 123-135.
[2] K. Fredriksson and S. Grabowski: Practical and Optimal String
Matching. Proceedings of SPIRE'2005, Lecture Notes in Computer
Science 3772, pp. 374-385, Springer Verlag, 2005.
[3] M. Hernandez, and D. Rosenblueth. Disjunctive partial deduction of a
right-to-left string-matching algorithm. Information Processing Letters,
Vol 87, pp. 235-241, 2003.
[4] A. Apostolico, and R. R.Giancarlo, "The Boyer-Moore-Galil string
searching strategies revisited", SIAM J. Comput. Vol. 15, no. 1, pp. 98-
105, 1986.
[5] M. Crochemore, Transducers and repetitions, Theoret. Comput. Sci.,
Vol. 45, pp. 63-86, 1986.
[6] M. Crochemore, D. Perrin, Two-way string-matching, J. ACM, Vol. 38,
pp. 651-675, 1991.
[7] Z. Galil, R. Giancarlo, On the exact complexity of string matching:
upper bounds, SIAM J. Comput. Vol. 21, pp. 407-437, 1992.
[8] P. D. Smith, Experiments with a very fast substring search algorithm,
SP&E Vol. 21, no. 10, pp. 1065-1074, 1991.
[9] D. M. Sunday, A very fast substring search algorithm, Communications
of the ACM Vol. 33, no. 8, pp. 132-142, 1990.
[10] Z. Liu, X. Du, N. Ishii, An improved adaptive string searching
algorithm, Software-Practice and Experience Vol. 28, no. 2, pp. 191-
198, 1998.
[11] P. Fenwick, Fast string matching for multiple searches, Software-
Practice and Experience Vol. 31, no. 9, pp. 815-833, 2001.
[12] M. Mhashi, A Fast String Matching Algorithm using Double-Length
Skip Distances. Dirasat Journal, University of Jordan, Jordan Vol. 30,
no. 1, pp. 84-92, 2003.
[13] P. Fenwick, Some perils of performance prediction: a case study on
pattern matching. Software-Practice and Experience Vol. 31, no. 9, pp.
835-843, 2001.
[14] A. Al-jaber, M. Mhashi, A modified double skip algorithm in string
searching, AMSE(Association for the advancement of modelling &
Simulation Techniques in Enterprises) Periodicals Vol.8, no. 4, pp. 1-16,
2003.
[15] F. Franek, C. Jennings, W.F. Smyth: A Simple Fast Hybrid Pattern-
Matching Algorithm. In A. Apostolico, M. Crochemore, K. Park (Eds.):
Combinatorial Pattern Matching, Lecture Notes in Computer Science
3537. Springer, pp. 288-297, 2005.
[16] M. Mhashi, The effect of multiple reference characters on detecting
matches in string searching algorithms, Software Practice & Experience
Vol. 35, no. 13, pp. 1299-1315, 2005.M. Young, The Techincal Writers
Handbook. Mill Valley, CA: University Science, 1989.
@article{"International Journal of Information, Control and Computer Sciences:50048", author = "Mahmoud Moh'd Mhashi", title = "The Negative Effect of Traditional Loops Style on the Performance of Algorithms", abstract = "A new algorithm called Character-Comparison to Character-Access (CCCA) is developed to test the effect of both: 1) converting character-comparison and number-comparison into character-access and 2) the starting point of checking on the performance of the checking operation in string searching. An experiment is performed using both English text and DNA text with different sizes. The results are compared with five algorithms, namely, Naive, BM, Inf_Suf_Pref, Raita, and Cycle. With the CCCA algorithm, the results suggest that the evaluation criteria of the average number of total comparisons are improved up to 35%. Furthermore, the results suggest that the clock time required by the other algorithms is improved in range from 22.13% to 42.33% by the new CCCA algorithm.
", keywords = "Pattern matching, string searching, charactercomparison,character-access, text type, and checking", volume = "1", number = "8", pages = "2306-8", }
