CONSTRUCTIVE MODEL OF DATA STRUCTURES ADAPTATION IN RAM: PART I. PROGRAM TEXT CONSTRUCTING

V. I. Shynkarenko, H. V. Zabula

Abstract


Purpose. Rapidly growing volumes of information systems data being manipulated significantly reduce the temporary algorithms effeciency of their processing . Effective data layout in RAM is one of the directions of solving this problem. It is necessary to develop the model to solve problems of efficient automated data layout in RAM. Methodology. For processes simulation of data structures (DS) adaptation in RAM, the methodology of mathematical and algorithmic constructivism was applied. This approach involves the development of constructive and productive structures (CPS) with transformations of specialization, interpretation, specification and implementation. CPS development provides definition of expandable vector, signature of relations, transactions and constructive axioms. The most complex and essential part of the set of axioms is generated substitution rules that determine the output process of respective structures. Findings. CPS system was developed by the authors, consisting of the logical structure constructor of data, converters of logical structure in to a software interface and implementation in a programming language, constructors of scenarios and adaptation processes. The result of the adaptation process constructor is software text generations of the class library that implements the specified logical data structure with appropriate processing operations and its compilation in binary code. Originality. Structural model of development processes and data structures adaptation to different software and hardware environments was first proposed. It adapts date layout in the RAM and data processing algorithms. Application of constructivism in simulation allowed within a single approach and applied tools linking the data models and algorithms of their processing with performance criteria. Formation methodology of CPS system, mechanisms, and links between complementary CPS were improved. Modification of the constructor and converters allows changing and exploring the process of adaptation. Practical value. The developed model allows automating the data layout in RAM, which in turn increases the time efficiency of programs with significant processing of large and very large volumes of data.


Keywords


data structure; constructive and productive structure; adaptation; constructor; converter

References


Akulovskiy V.G. Algebra dlya opisaniya dannykh v kompozitsionnykh skhemakh algoritmov [Algebra for describing the data in the compositional schemes of algorithms]. Problemy prohramuvannia – Problems in Programming, 2012, no. 2-3, pp. 234-240.

Akulovskiy V.G. Osnovy algebry algoritmov, baziruyushcheysya na dannykh [Basic algebra algorithms based on data]. Problemy prohramuvannia – Problems in Programming, 2010, no. 2-3, pp. 89-96.

Kormen T., Leyzerson Ch., Rivest R., Shtayn K. Algoritmy: postroeniye i analiz [Algorithms: construction and analysis]. Saint-Petersburg, OOO «I. D. Vilyams» Publ., 2011. 1296 p.

Bosov A.A., Ilman V.M., Khalipova N.V. Strukturnaya slozhnost sistem [Structural complexity of systems]. Visnyk Dnipropetrovskoho natsionalnoho universytetu zaliznychnoho transportu imeni akademika V. Lazariana [Bulletin of Dnipropetrovsk National University of Railway Transport named after Academician V. Lazaryan], 2012, issue 40, pp. 173-179.

Doroshenko A.Ye., Akulovskiy V.G. Algebra algoritmov s dannymi i prognozirovaniye vychislitelnogo protsessa [Algebra of algorithms with data and prediction computational process]. Problemy prohramuvannia – Problems in Programming, 2011, no. 3, pp. 3-10.

Drozhzhin V.V., Volodin A.M. Preobrazovaniye struktur dannykh v pole struktur dannykh [Convert data structures in the field of data structures]. Izvestiya penzenskogo gosudarstvennogo pedagogicheskogo Universiteta im. V.G. Belinskogo [News of Penza State Pedagogical University named after V. G. Belinsky], 2011, no. 26, pp. 380-385.

Shinkarenko V.I., Ilman V.M., Zabula G.V. Konstruktsionno-produktsionnaya model struktur dannykh na logicheskom urovne [Construction-production model of the data structures at the logical level]. Problemy prohramuvannia – Problems in Programming, 2014, no. 2-3, pp. 10-16.

Ren J., Pan W., Zheng Y., Shi Z., Yan X. Array Based HV/VH Tree: an Effective Da-ta Structure for Layout Representation. Journal of Zhejiang University-SCIENCE C (Computers & Electronics), 2012, vol. 13, issue 3, pp. 232-237. doi: 10.1631/jzus.c1100193.

Attali D., Lieutier A., Salinas D. Efficient Data Structure for Repre-senting and Simplifying Simplicial Complexes in High Dimensions. Intern. Journal of Computational Geometry & Applications, 2012, vol. 22, issue 4, pp. 279-303. doi: 10.1142/S0218195912600060.

Bentley J.L. Writing Efficient Programs. New Jersey, Prentice-Hall in Englewood Cliffs Publ., 1982. 170 p.

Drepper U. What Every Programmer Should Know About Memory. Raleigh, RedHat, Inc. Publ., 2007. 114 p.

Shynkarenko V.I., Ilman V.M. Constructive-Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure. Cybernetics and Systems Analysis, 2014, vol. 50, issue 5, pp. 655-662. doi: 10.1007/s10559-014-9655-z.

Shynkarenko V.I., Ilman V.M., Skalozub V.V. Structural Models of Algorithms in Problems of Applied Programming. I. Formal Algorithmic Structures. Cybernetics and Systems Analysis, 2009, vol. 45, issue 3, pp. 329-339. doi: 10.1007/s10559-009-9118-0.

Weiss M.A. Data Structures and Algorithm Analysis in C++. New Jersey, Pearson Education Inc., Addison-Wesley Publ., 2014. 656 p.

Ziegler C.A. Programming System methodologies. New Jersey, Prentice-Hall, Englewood Cliffs Publ., 1983. 260 p.


GOST Style Citations


  1. Акуловский, В. Г. Алгебра для описания данных в композиционных схемах алгоритмов / В. Г. Акуловский // Проблеми програмування. – 2012 – № 2-3. – C. 234–240.
  2. Акуловский, В. Г. Основы алгебры алгоритмов, базирующейся на данных / В. Г. Акуловский // Проблеми програмування. – 2010. – № 2-3. – C. 89–96.
  3. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – Санкт-Петербург : ООО «И. Д. Вильямс», 2011. – 1296 с.
  4. Босов, А. А. Структурная сложность систем / А. А. Босов, В. М. Ильман, Н. В. Халипова // Вісн. Дніпропетр. нац. ун-ту залізн. трансп ім. акад. В. Лазаряна. – Дніпропетровськ, 2012. – Вип. 40. – C. 173–179.
  5. Дорошенко, А. Е. Алгебра алгоритмов с данными и прогнозирование вычислительного процесса / А. Е. Дорошенко, В. Г. Акуловский // Проблеми програмування. – 2011. – № 3. – С. 3–10.
  6. Дрожжин, В. В. Преобразование структур данных в поле структур данных / В. В. Дрожжин, А. М. Володин // Изв. Пензен. гос. пед. ун-та им. В. Г. Белинского. – Пенза, 2011. – № 26. – С. 380–385.
  7. Шинкаренко, В. И. Конструкционно-продукционная модель структур данных на логическом уровне / В. И. Шинкаренко, В. М. Ильман, Г. В. Забула // Проблеми програмування. – 2014. – № 2-3. – С. 10–16.
  8. Array Based HV/VH Tree: an Effective Data Structure for Layout Representation / J. Ren, W. Pan, Y. Zheng [et al.] // J. of Zhejiang University-SCIENCE C (Computers & Electronics). – 2012. – Vol. 13. – Iss. 3. – P. 232–237. doi: 10.1631/jzus.c1100193.
  9. Attali, D. Efficient Data Structure for Representing and Simplifying Simplicial Complexes in High Dimensions / D. Attali, A. Lieutier, D. Salinas // Intern. J. of Computational Geometry & Applications. – 2012. – Vol. 22. – Iss. 4. – P. 279–303. doi: 10.1142/S0218195912600060.
  10. Bentley, J. L. Writing Efficient Programs / J. L. Bentley. – New Jersey: Prentice-Hall in Englewood Cliffs, 1982. – 170 p.
  11. Drepper, U. What Every Programmer Should Know About Memory / U. Drepper. –Raleigh: RedHat, Inc., 2007. – 114 p.
  12. Shynkarenko, V. I. Constructive-Synthesizing Structures and Their Grammatical Interpretations. I. Generalized Formal Constructive-Synthesizing Structure / V. I. Shynkarenko, V. M. Ilman // Cybernetics and Systems Analysis. – 2014. – Vol. 50. – Iss. 5. – P. 655–662. doi: 10.1007/s10559-014-9655-z.
  13. Shynkarenko, V. I. Structural Models of Algorithms in Problems of Applied Programming. I. Formal Algorithmic Structures / V. I. Shynkarenko, V. M. Ilman, V. V. Skalozub // Cybernetics and Systems Analysis. – 2009. – Vol. 45. – Iss. 3. – P. 329–339. doi: 10.1007/s10559-009-9118-0.
  14. Weiss, M. A. Data Structures and Algorithm Analysis in C++ / M. A. Weiss. –New Jersey: Pearson Education Inc., Addison-Wesley, 2014. – 656 p.
  15. Ziegler, C. A. Programming System methodologies / C. A. Ziegler. –New Jersey: Prentice-Hall,EnglewoodCliffs, 1983. – 260 p.


DOI: https://doi.org/10.15802/stp2016/60998

 

Cited-by:

1. MODELLING THE MODIFIED METHOD OF ANALYTIC HIERARCHY PROCESS BY MEANS OF CONSTRUCTIVE AND PRODUCTIVE STRUCTURES
T. М. Vasetska
Science and Transport Progress. Bulletin of Dnipropetrovsk National University of Railway Transport  Issue: 4(64)  First page: 81  Year: 2016  
doi: 10.15802/stp2016/77926



Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

 

ISSN 2307–3489 (Print)
ІSSN 2307–6666 (Online)