The Negative Effect of Traditional Loops Style on the Performance of Algorithms

Authors: Mahmoud Moh'd Mhashi

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

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329280

References:

[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.