DOI: https://doi.org/10.32515/2664-262X.2025.11(42).2.23-29
Особливості роботи складних обчислювальних алгоритмів на прикладі перевірки гіпотези Полокка
Про авторів
Недьошев Максим Владиславович , здобувач вищої освіти на третьому (освітньо-науковому) рівні за спеціальністю «Комп’ютерні науки», Національний університет біоресурсів і природокористування України, м. Київ, Україна, ORCID: https://orcid.org/0009-0000-9820-0649, email: m.nedoshev@nubip.edu.ua
Кириченко Віктор Вікторович , доцент, кандидат фізико-математичних наук, доцент кафедри комп`ютерних наук, Національний університет біоресурсів і природокористування України, м.Київ, Україна, ORCID: https://orcid.org/0009-0001-0575-8684, email: v.kyrychenko@nubip.edu.ua
Анотація
В роботі проведено аналіз алгоритмів пошуку представлення числа як суми тетраедричних чисел із використанням різних методів оптимізації, таких як жадібний алгоритм, апроксимація, двоє вказівників, мемоізація та багатопотоковість. Розглянуто різні техніки, що сприяють зменшенню часу обчислень, зокрема багатопотокова обробка та використання ефективних структур даних. Описано, як реалізувати ці методи в контексті різних мов програмування. Також проведено експерименти з оцінкою продуктивності різних підходів та порівняння результатів. Результати демонструють суттєве підвищення швидкості виконання алгоритму під час використання багатопотокових підходів та оптимізації коду.
Ключові слова
гіпотези Поллока, алгоритми пошуку, складність алгоритмів алгоритм, паралельні складні обчислення, багатопотоковість
Повний текст:
PDF
Посилання
1. Salzer, H., & Levine, N. (1958). Table of integers not exceeding 100000 that are not expressible as the sum of four tetrahedral numbers. Mathematics of Computation, 12, 141–144. https://doi.org/10.1090/S0025-5718-1958-0099756-3.
2. Dhalla, H. (2020). A performance analysis of native JSON parsers in Java, Python, MS.NET Core, JavaScript, and PHP. In Proceedings of the 16th International Conference on Network and Service Management (CNSM), 2–6 November 2020, Izmir, Turkey (pp. 1–5). https://doi.org/10.23919/CNSM50824.2020.9269101.
3. Lei, K., Ma, Y., & Tan, Z. (2014). Performance comparison and evaluation of web development technologies in PHP, Python, and Node.js. In Proceedings of the 17th IEEE International Conference on Computational Science and Engineering, 19–21 December 2014, Chengdu, China. https://doi.org/10.1109/CSE.2014.142.
4. Huang, Q., & Lu, N. (2021). Optimized real-time MUSIC algorithm with CPU-GPU architecture. IEEE Access, 9, 54067–54077. https://doi.org/10.1109/ACCESS.2021.3070980.
5. Sloane, N. J. A. (2024). Sequence A000797 [Electronic resource]. The On-Line Encyclopedia of Integer Sequences (OEIS). Retrieved April 6, 2025, from https://oeis.org/A000797.
6. Zinnia, N., & Hanada, E. (2024). Optimizing search strategies: A study of two-pointer linear search implementation. arXiv preprint. June. https://doi.org/10.48550/arXiv.2406.16729.
7. Performing Calculations on a GPU [Electronic resource]. Apple Developer Documentation. Retrieved April 10, 2025, from https://developer.apple.com/documentation/metal/performing-calculations-on-a-gpu.
8. The Computer Language 25.03 Benchmarks Game [Electronic resource]. Retrieved April 10, 2025, from https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html.
9. Bun — A fast all-in-one JavaScript runtime [Electronic resource]. Retrieved April 10, 2025, from https://bun.sh/.
10. Gebraad, L., & Andreas, F. (2023). Seamless GPU acceleration for C++ based physics with the Metal Shading Language on Apple’s M series unified chips. Seismological Research Letters, 94. https://doi.org/10.1785/0220220241.
Пристатейна бібліографія
1. Salzer H., Levine N. Table of Integers Not Exceeding 100000 That Are Not Expressible as the Sum of Four Tetrahedral Numbers // Mathematics of Computation. 1958. Т. 12. С. 141–144. DOI: 10.1090/S0025-5718-1958-0099756-3 (дата звернення: 02.04.2025).
2. Dhalla H. A performance analysis of native JSON parsers in Java, Python, MS.NET Core, JavaScript, and PHP // 2020 16th International Conference on Network and Service Management (CNSM), 2–6 листопада 2020 р., Ізмір, Туреччина. С. 1–5. DOI: 10.23919/CNSM50824.2020.9269101 (дата звернення: 04.04.2025).
3. Lei K., Ma Y., Tan Z. Performance Comparison and Evaluation of Web Development Technologies in PHP, Python, and Node.js // 2014 IEEE 17th International Conference on Computational Science and Engineering, 19–21 грудня 2014 р., Ченду, Китай. DOI: 10.1109/CSE.2014.142 (дата звернення: 08.04.2025).
4. Huang Q., Lu N. Optimized Real-Time MUSIC Algorithm With CPU-GPU Architecture // IEEE Access. 2021. Т. 9. С. 54067–54077. DOI: 10.1109/ACCESS.2021.3070980 (дата звернення: 08.04.2025).
5. Sloane N. J. A. Послідовність A000797 [Електрон. ресурс] // The On-Line Encyclopedia of Integer Sequences (OEIS). 2024. Режим доступу: https://oeis.org/A000797 (дата звернення: 06.04.2025).
6. Zinnia N., Hanada E. Optimizing Search Strategies: A Study of Two-Pointer Linear Search Implementation // arXiv preprint. 2024. June. DOI: 10.48550/arXiv.2406.16729 (дата звернення: 08.04.2025).
7. Performing Calculations on a GPU [Електрон. ресурс] // Apple Developer Documentation. Режим доступу: https://developer.apple.com/documentation/metal/performing-calculations-on-a-gpu (дата звернення: 10.04.2025).
8. The Computer Language 25.03 Benchmarks Game [Електрон. ресурс]. Режим доступу: https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html (дата звернення: 10.04.2025).
9. Bun — A fast all-in-one JavaScript runtime [Електрон. ресурс]. Режим доступу: https://bun.sh/ (дата звернення: 10.04.2025).
10. Gebraad L., Andreas F. Seamless GPU acceleration for C++ based physics with the Metal Shading Language on Apple’s M series unified chips // Seismological Research Letters. 2023. Т. 94. DOI: 10.1785/0220220241 (дата звернення: 10.04.2025).
Copyright (c) 2025 М. В. Недьошев, В. В. Кириченко
Особливості роботи складних обчислювальних алгоритмів на прикладі перевірки гіпотези Полокка
Про авторів
Недьошев Максим Владиславович , здобувач вищої освіти на третьому (освітньо-науковому) рівні за спеціальністю «Комп’ютерні науки», Національний університет біоресурсів і природокористування України, м. Київ, Україна, ORCID: https://orcid.org/0009-0000-9820-0649, email: m.nedoshev@nubip.edu.ua
Кириченко Віктор Вікторович , доцент, кандидат фізико-математичних наук, доцент кафедри комп`ютерних наук, Національний університет біоресурсів і природокористування України, м.Київ, Україна, ORCID: https://orcid.org/0009-0001-0575-8684, email: v.kyrychenko@nubip.edu.ua
Анотація
Ключові слова
Повний текст:
PDFПосилання
1. Salzer, H., & Levine, N. (1958). Table of integers not exceeding 100000 that are not expressible as the sum of four tetrahedral numbers. Mathematics of Computation, 12, 141–144. https://doi.org/10.1090/S0025-5718-1958-0099756-3.
2. Dhalla, H. (2020). A performance analysis of native JSON parsers in Java, Python, MS.NET Core, JavaScript, and PHP. In Proceedings of the 16th International Conference on Network and Service Management (CNSM), 2–6 November 2020, Izmir, Turkey (pp. 1–5). https://doi.org/10.23919/CNSM50824.2020.9269101.
3. Lei, K., Ma, Y., & Tan, Z. (2014). Performance comparison and evaluation of web development technologies in PHP, Python, and Node.js. In Proceedings of the 17th IEEE International Conference on Computational Science and Engineering, 19–21 December 2014, Chengdu, China. https://doi.org/10.1109/CSE.2014.142.
4. Huang, Q., & Lu, N. (2021). Optimized real-time MUSIC algorithm with CPU-GPU architecture. IEEE Access, 9, 54067–54077. https://doi.org/10.1109/ACCESS.2021.3070980.
5. Sloane, N. J. A. (2024). Sequence A000797 [Electronic resource]. The On-Line Encyclopedia of Integer Sequences (OEIS). Retrieved April 6, 2025, from https://oeis.org/A000797.
6. Zinnia, N., & Hanada, E. (2024). Optimizing search strategies: A study of two-pointer linear search implementation. arXiv preprint. June. https://doi.org/10.48550/arXiv.2406.16729.
7. Performing Calculations on a GPU [Electronic resource]. Apple Developer Documentation. Retrieved April 10, 2025, from https://developer.apple.com/documentation/metal/performing-calculations-on-a-gpu.
8. The Computer Language 25.03 Benchmarks Game [Electronic resource]. Retrieved April 10, 2025, from https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html.
9. Bun — A fast all-in-one JavaScript runtime [Electronic resource]. Retrieved April 10, 2025, from https://bun.sh/.
10. Gebraad, L., & Andreas, F. (2023). Seamless GPU acceleration for C++ based physics with the Metal Shading Language on Apple’s M series unified chips. Seismological Research Letters, 94. https://doi.org/10.1785/0220220241.
Пристатейна бібліографія
1. Salzer H., Levine N. Table of Integers Not Exceeding 100000 That Are Not Expressible as the Sum of Four Tetrahedral Numbers // Mathematics of Computation. 1958. Т. 12. С. 141–144. DOI: 10.1090/S0025-5718-1958-0099756-3 (дата звернення: 02.04.2025).
2. Dhalla H. A performance analysis of native JSON parsers in Java, Python, MS.NET Core, JavaScript, and PHP // 2020 16th International Conference on Network and Service Management (CNSM), 2–6 листопада 2020 р., Ізмір, Туреччина. С. 1–5. DOI: 10.23919/CNSM50824.2020.9269101 (дата звернення: 04.04.2025).
3. Lei K., Ma Y., Tan Z. Performance Comparison and Evaluation of Web Development Technologies in PHP, Python, and Node.js // 2014 IEEE 17th International Conference on Computational Science and Engineering, 19–21 грудня 2014 р., Ченду, Китай. DOI: 10.1109/CSE.2014.142 (дата звернення: 08.04.2025).
4. Huang Q., Lu N. Optimized Real-Time MUSIC Algorithm With CPU-GPU Architecture // IEEE Access. 2021. Т. 9. С. 54067–54077. DOI: 10.1109/ACCESS.2021.3070980 (дата звернення: 08.04.2025).
5. Sloane N. J. A. Послідовність A000797 [Електрон. ресурс] // The On-Line Encyclopedia of Integer Sequences (OEIS). 2024. Режим доступу: https://oeis.org/A000797 (дата звернення: 06.04.2025).
6. Zinnia N., Hanada E. Optimizing Search Strategies: A Study of Two-Pointer Linear Search Implementation // arXiv preprint. 2024. June. DOI: 10.48550/arXiv.2406.16729 (дата звернення: 08.04.2025).
7. Performing Calculations on a GPU [Електрон. ресурс] // Apple Developer Documentation. Режим доступу: https://developer.apple.com/documentation/metal/performing-calculations-on-a-gpu (дата звернення: 10.04.2025).
8. The Computer Language 25.03 Benchmarks Game [Електрон. ресурс]. Режим доступу: https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html (дата звернення: 10.04.2025).
9. Bun — A fast all-in-one JavaScript runtime [Електрон. ресурс]. Режим доступу: https://bun.sh/ (дата звернення: 10.04.2025).
10. Gebraad L., Andreas F. Seamless GPU acceleration for C++ based physics with the Metal Shading Language on Apple’s M series unified chips // Seismological Research Letters. 2023. Т. 94. DOI: 10.1785/0220220241 (дата звернення: 10.04.2025).
Copyright (c) 2025 М. В. Недьошев, В. В. Кириченко