在8位AVR Arduino微控制器上对未经优化的排序算法的实证评估
1Faculty of Computer Science and Mathematics, Cracow University of Technology, 31-155 Kraków, Poland.
Sensors (Basel, Switzerland)
|January 10, 2026
概括
堆排序为资源有限的微控制器提供了最佳性能,平衡速度和内存使用. 这项研究评估了Arduino板上的六个排序算法,发现堆排序是嵌入式传感应用的最佳选择.
科学领域:
- 嵌入式系统工程 嵌入式系统工程
- 计算机科学 计算机科学
- 算法分析 算法分析
背景情况:
- 物联网 (IoT) 中资源受限的微控制器和嵌入式传感器需要高效的算法.
- 算法选择对低成本设备的延迟,能源消耗和内存足迹产生重大影响.
- 现有的研究往往忽视了微控制器 (如Arduino板) 的特定局限性.
研究的目的:
- 评估微控制器上六种常见的排序算法 (泡,插入,选择,合并,快速,堆排序) 的性能.
- 在现实的嵌入式传感条件下分析执行时间,写作操作和内存使用情况.
- 为在资源有限的环境中选择算法提供实用指南.
主要方法:
- 在Arduino Uno,Leonardo和Mega 2560板上实现了六个未经优化的排序算法.
- 用越来越大的数据集测试算法,模拟缓冲时间序列传感器数据 (随机,上升,下降).
- 测量执行时间,写作操作和静态随机存取内存 (SRAM) 的使用情况.
主要成果:
- O(n log n) 算法 (快速排序,堆排序) 显著超过了O(n^2) 算法 (泡,插入,选择排序).
- 快速排序和合并排序显示高速,但过度使用SRAM (2023字节的合并排序) 或递归问题.
- 堆排序证明了最佳的权衡,在SRAM限制内执行所有测试的大小 (约. 12-13字节额外的SRAM) 并实现快速运行时间 (<100,000μs对于n=1000).
结论:
- 堆排序是资源受限的8位AVR微控制器在传感应用中推的算法.
- 算法选择必须考虑RAM,程序内存和能量的特定约束.
- 本研究提供经验数据,以指导嵌入式系统的实际实施选择.
相关概念视频
Multiple Comparison Tests
4.4K
Multiple comparison test, abbreviated as MCT, is a post hoc analysis generally performed after comparing multiple samples with one or more tests. An MCT will help identify a significantly different sample among multiple samples or a factor among multiple factors.
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...
4.4K
Optimization Problems
8
Optimization problems often involve identifying maximum or minimum values under specific constraints. A well-known example is determining the longest horizontal pipe that can be moved around a right-angled corner, where a 3-meter-wide hallway meets a 2-meter-wide hallway. This scenario, common in architectural design and industrial transport, can be understood conceptually through geometric and trigonometric reasoning.To visualize the problem, consider the pipe as a straight line that touches...
8
Serial Position Effect
501
The serial position effect is a cognitive phenomenon where individuals are more likely to recall the first and last items in a list compared to those in the middle. This effect is divided into the primacy effect and the recency effect. The primacy effect is observed when the initial items in a list are remembered better. This occurs because these items are rehearsed more frequently or receive more elaborative processing, allowing them to be encoded into long-term memory more effectively. For...
501
Voltage Dividers
1.2K
In electrical circuits, resistors can be connected in series, sequentially linked one after the other. In a series configuration, the same current flows through each resistor. Ohm's law is a fundamental principle to understand the behavior of resistors in series. It expresses the voltage across these resistors in terms of the current and resistance.
Kirchhoff's voltage law implies that the sum of the voltages across the resistors in series equals the source voltage. This means that the current...
Kirchhoff's voltage law implies that the sum of the voltages across the resistors in series equals the source voltage. This means that the current...
1.2K
Non-ohmic Devices
1.5K
In most substances, the current flow is proportional to the voltage applied to it. A simple relationship between the values of current, voltage, and resistance is known as Ohm's law. Nonohmic devices do not exhibit a linear relationship between voltage and current. One such device is the semiconducting circuit element known as a diode. A diode is a circuit device that allows current flow in only one direction.
Consider a simple circuit consisting of a battery, a diode, and a resistor. A...
Consider a simple circuit consisting of a battery, a diode, and a resistor. A...
1.5K
Sieve Analysis and Grading Curves
909
Sieve analysis is a method used to determine the particle size distribution of aggregate materials. This process involves the following steps:
909


