Follow our illustrated blog on Embedded Software Architecture

How to build a hybrid solar/wind energy harvester?

The red-black tree and hash table

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)

red-black tree

The even more advanced container we look at now is the red-black tree, which is a type of self-balancing binary search tree. Especially, interesting is the time complexity in big O notation:

Action/Subject       Average          Worst case
Space                          O(n)                O(n)
Search                        O(log n)         O(log n)
Insert                          O(log n)         O(log n)
Delete                         O(log n)         O(log n)

Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees.

The above statement should ring a bell for embedded software engineers that need manipulations on data sets in a time-deterministic and predictable manner. If a simple array (vector) or linked list does not handle it, consider the red-black tree instead of a simple binary tree which could become unbalanced. If however, the data is known beforehand (and constant), one could balance the tree at build time and do lookups with simpler and smaller code. Do not implement red-black trees yourself but use an existing robust and debugged implementation such as the one found in kazlib.

The “Home of Kazlib” has more data container goodies:
It has implementations for linked lists, red-black trees and hashes.

Hash tables

A hash table is a data structure that allows one to store – and find again – items at a particular memory space or “bucket”. The hash table uses a function to calculate an index which points at a specific “bucket”. In this bucket, we can find the element associated with the key we are searching for. If there are multiple elements in the visited bucket, we need to test all these elements in order to find the correct one.

So, in general, the efficiency of a hash table depends on

  • the number of buckets,
  • the number of elements in the hash table,
  • and the distribution of these elements across the different buckets.
  • the computing efficiency of the hashing function

There exist various kinds of different hash table variants using different hash functions and conflict resolve methods (when 2 or more elements land in the same bucket).

When to use

On larger datasets, the hash table approach is usually more efficient than the red black tree but again depending on the efficiency of the hash table (more – possibly empty – buckets means more memory usage/waste) and the calculation (and distribution) efficiency of the hash function itself on the embedded target. As always, the trade-off is memory versus speed.

 

 

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)
Share

3D printing of enclosures

printed in translucent white ABS

Having the correct and proper enclosures, is a mechanical (and also a marketing) problem many electronics projects suffer from. It is also related to anticipated sales numbers. For big numbers, a custom enclosure which is produced with an injection … [Continue reading]

Vector, list and tree

Choice of containers Information technology, even embedded devices, is about information gathering, processing or calculation, and control. Input and data needs to be juggled around and maybe sorted. In this article, we want to point out some … [Continue reading]

Priority inversion

I found the inspiration for this article while working on a consultancy job: Priority inversion. In computer science, priority inversion is a (potential) problematic scenario in scheduling in which a high priority task is indirectly preempted by a … [Continue reading]

Progress update

Time for another update. The Green4 project is progressing steadily. In the last few months, we have been busy preparing the Green4 prototypes. Test software has been developed which is already very usable, but it is still in a state of flux as we … [Continue reading]

Embedding a Basic interpreter

The green4 stm32 cortex m3 microprocessor we selected is - according to today's standards - a rather small microprocessor in Flash (128KB) and RAM (8KB). why an interpreter The Green4 device is running control software on top of FreeRTOS, with a … [Continue reading]

Green4 charge controller: wiring diagrams part 2

Wiring diagram: wind turbine to dump load In contrast to solar panels, a wind turbine can't be disconnected in case it generates too much power. We need to brake it by attaching a load to it. However, wind power can't always flow through the charge … [Continue reading]

Green4 charge controller: wiring diagrams part 1

charge controller wiring batteries to external device

Introduction Instead of endlessly listing requirements and specifications, we prefer to demonstrate the architecture of our Green4 charge controller by means of wiring diagrams and other illustrations. The Green4 is designed to be a versatile … [Continue reading]

Open source implementations of malloc

On (very) small embedded systems without a full OS (e.g. because there is only a scheduler), one can (and should) usually live without dynamic memory allocation. But sometimes, it is really needed or it is just more convenient. It is possible to … [Continue reading]

DC motor control with the mosfet switch board

Although, there is no such thing as a general purpose mosfet switch board because of the wide variations in application specific load (resistive, capacitive, inductive or mixed) characteristics, we were able to investigate and demonstrate DC motor … [Continue reading]