How to write code to place timer values in order from low to high

I’d like to create a patch that retains the smallest timer values in order from low to high. I have the logic generated for collecting the timer values, see below. I’m uncertain how to push the current time values down to make room for the new fastest time. Is there any existing node I am unfamiliar with that could help me achieve this. I’m only interested in saving the four fastest time values. If a new value is larger than the current top four values then nothing happens. But if a new value is less than the 2nd fastest time the 2nd place value gets moved to third and third moves to forth and the new time takes the 2nd place.

In short,


Here is a xodball:
biggest-timer.xodball (31.6 KB)

Each of four values are stored in the buffer node.
We got a condition for each one which tests should the new value be placed here or not (greater and e/comparison/between).
Another case: updating of the “greater” buffer. In this case we have to take a value from the “greater” buffer and react on the pulse produced by change of the “greater” buffer. It could be a gated pulse of the first one, or chain of “greater” pulses merged using some any nodes.

This patch uses a lot of memory on Arduino Uno.

Sketch uses 13736 bytes (42%) of program storage space. Maximum is 32256 bytes.
Global variables use 463 bytes (22%) of dynamic memory, leaving 1585 bytes for local variables. Maximum is 2048 bytes.

I bet this task could be solved using C++ code in a more optimal way :stuck_out_tongue:

Slightly different approach (not any better…just different; in fact, the other approach would be less cluttered if more values are going to be stored) that uses less program mem, but more var mem
Sketch uses 11962 bytes (37%) of program storage space. Maximum is 32256 bytes.
Global variables use 495 bytes (24%) of dynamic memory, leaving 1553 bytes for local variables. Maximum is 2048 bytes.

Val0 is new value. Val1 is highest recorded value, Val2 next highest, etc.
Buffer nodes store highest values seen.
The row of watch nodes at the bottom are your stored data.

Rather than try to determine which buffers should be pulsed to update we just push the same value into the buffer if it is not supposed to update.

For each new value, lowest row of if-else only apply if Val0>Val1 (new highest value): Shift all values, pushing new value into Val1. Defer nodes after buffer allow us to loop the value back up, but they also postpone updates until all buffer nodes update (so we don’t for example read Val0 into 1st buffer, then copy it to all the other buffers instead of shifting existing values).

The next row of if-else are ignored if Val0>Val1, but used if Val0>Val2 (new value is 2nd highest value seen). Push Val0 into 2nd buffer and shift the rest of the values into next buffers.

Process repeats for each row of if-else, with one less if-else node needed for each row.

NOTE: if Val0 is updated when Stop pulse is made, you probably want a defer node before sending it to buffer nodes to make sure if-else nodes have refreshed before updating buffers.

Thank you both for the help. I’ll give it a try tomorrow.

Just for kicks, I thought I’d implement using my gweimer/utils/queue-buffer node since my last example was basically a stack (but values can be inserted in the middle). Not surprisingly since queue-buffer is a more generic node using select, it uses more memory than either of the other solutions.
Sketch uses 17354 bytes (53%) of program storage space. Maximum is 32256 bytes.
Global variables use 580 bytes (28%) of dynamic memory, leaving 1468 bytes for local variables. Maximum is 2048 bytes.

It is not obvious from the picture, but the queue-buffer-MEM is linked to the queue-buffer-NEW of the node to its right (used to shift values to the right).

I sort of “cheated” a little. I have no use for the POP function of queue-buffer node, so I used it to insert the new Val0 into the appropriate location (queue-buffer-OLD is always Val0). Once I determine where Val0 gets inserted, I POP it into that location, then PUSH all the buffers to the right of it to shift the other values. Note that the 1st buffer never shifts, the 2nd only has 1 way to shift, but 3rd and 4th buffer have multiple ways to shift, so ‘any’ nodes are used to join the pulses.

If you were going to add additional buffers, you could reduce the required links by daisy-chaining the any nodes to join PUSH pulses. If any buffer has its PUSH pin pulsed, all buffers to the right will need pulsed.
It also happens to reduce memory usage slightly:
Sketch uses 17294 bytes (53%) of program storage space. Maximum is 32256 bytes.
Global variables use 578 bytes (28%) of dynamic memory, leaving 1470 bytes for local variables. Maximum is 2048 bytes.

Using a custom queue/buffer node for this application simplifies the patch & reduces memory usage:
Sketch uses 11888 bytes (36%) of program storage space. Maximum is 32256 bytes.
Global variables use 480 bytes (23%) of dynamic memory, leaving 1568 bytes for local variables. Maximum is 2048 bytes.

The max-buffer node:

Each max-buffer takes one input value. It stores the higher of new or existing value & passes the smaller value on to the next max-buffer node, which repeats the process. Beautific simplicity (at least in the patch using max-buffer…)

Note: If DONE pulse will start processing of MEM value, then a defer should be added between PUSH and DONE so MEM value gets updated before DONE pulse is sent. Unfortunately, that currently breaks the code and the pulse never makes it to all the max-buffers. I have a separate discussion about that (seems to be a bug that pulse is lost after passing through 3 defer nodes).

1 Like

I think this multi-level patch design is exemplary! Simplicity is beautiful, and, I would add, very considerate of third parties looking at new code.
Factoring [common modules out] is used all the time in both software and hardware.
In C++ coding, creating a new class and instantiating it multiple times greatly simplifies the design and 3rd parties’ maintenance of it.
In hardware, anything used frequently is best put on its own small PC board and easily replicated.
Designing by putting together multiple level modules is the essence of amplifying one’s design power. :+1: :+1:, Gweimer!
I nominate this project to go into a XOD tutorial, clearly illustrating the reason for making your own patch.

The only hard part is realizing there is a way to solve the problem that can be put into a single node like this. I was thinking on this “simple” task for days before I realized how simply the solution could be done. The original solutions did not lend easily to consolidating into a single node, but moving to a queue solution helped lead to the final solution.

If you “enjoyed” this torturous development process, check out library laid out as a tutorial where I tried to show that code development is not always a clean, simple process and often hits dead-ends and messy solutions before coming up with a good solution. Beautiful code is usually a result of multiple cleanups more than a brilliant mind just immediately coming up with that solution. Experience will allow you to skip more of the cleanup steps. Don’t get discouraged trying to compare your original solution with someone else’s cleaned-up version. Don’t be afraid to try things that might not work–it might lead to a beautiful solution that you would never have found otherwise. I knew the queue-buffer solution would use more memory, but I didn’t know if it would be simpler until I tried it. It wasn’t much simpler than the original example, but did lead to the single-node solution. Just be sure to save your current solution before diving into a crazy new idea; it can be VERY frustrating running down a rabbit trail and realize you can’t get back to something that was working. Disk space for saving multiple versions of a project is cheap; you might even want a section of that broken code for something later…or realize how you could fix it if you still had a copy…

When it comes to memory usage, are those values ​​with debugging turned on? debugging uses a large percentage

My posts were with debug turned on. Since it was always on, it produces a good relative comparison between the options, but you are right, it is not a good absolute value to use for planning resource usage in a larger program that won’t be using debug. I have seen posts that select can be a memory hog, so I was interested how other solutions compared.

The “max buffer” logic worked great. I was asking for a patch that would save the fastest times, “min buffer”. So I tweaked your “max buffer” patch to look like this and added/changed what’s circled in red. Perhaps the new portion on the left could be simplified, but it did the job.

Thank you gweimer for steering me in the right direction. I did notice that as we used it this weekend we where getting a lot of repeated time values to the exact hundredths place. This doesn’t seem realistic. Could the logic in the node be written to help the timer operate more precisely?

I don’t understand the purpose of the clock/flip-flop code. You are changing the value this node is storing without changing the value to pass on to the next buffer or updating later buffers independent of when a new value is getting pushed into the buffer? Seems this would explain the repeated values as later nodes do the same thing with input value not getting changed…

My intension was to predefine all stored values at 8 second. I know the task we were timing would take less than 8 seconds. It could be an infinity for that matter. I used the if-else statement to accomplish it. Otherwise, the buffer value would start at 0 second and I never would be less then 0, thus it would never store any new values. Is there a better way to predefine the buffers with a value larger than 0? In the max buffer example you created, all timer values would be greater than 0. In my example, if I didn’t predefine the buffer to 8, I would never store any new values because they’d be greater than 0. I’m trying to save the fastest times, not the slowest times. I didn’t know how else to do it. It seemed to work. Maybe there’s a better way?

In regards to the repeated values, I had a momentary button I would push if I wanted to pass the new timer value to the buffers for placing evaluation. If the timed value was achieved by cheating, I would not push the button, thus it would get disqualified. I noticed the repeating timer values when the button wasn’t pushed. I don’t think the buffer code that you helped me generate had anything to do with it. I figured it had more to do with the processing time of the Arduino UNO. What are your thoughts?

I realized a while after I posted that was probably your intent. I didn’t look closely & thought if-else-F was 0, not 8 and for some reason was assuming clock was connected to flip-flop-TGL instead of SET. This should work for your program, but is probably not ideal as a general solution.

One option would be to test if new number is less than old OR old number is equal 0. This would cause 0 to always be replaced by new value, but means 0 will never be stored if it is a valid value (would not be in your case, but for generic min-buffer, it could be a problem).

Another idea I had was to have node store state to know if it has a valid value. This gets more complicated, since you won’t want to pass an invalid value to the next node & you need to remember if value has been stored.

For any of these solutions, something we have over-looked is you probably want a way to reset your buffers so you can start looking for a new set of min/max numbers.

Pretty ugly, and doesn’t add code to reset MEM when output is not VALID (what should it be set to???):

flip-flop starts as 0/false, indicating MEM is not valid. gate at the bottom prevents CHAIN from sending a pulse if MEM was not valid–we don’t want next node thinking it is getting a valid number. I kept DONE just for completeness…you may need some other action following buffer update even if it didn’t have a valid value.

Abusing casting in C++, you can use OVF value to indicate current value is not valid, removing the need for VLD output pin.

node {
    // Internal state variables defined at this level persists across evaluations
    float ovf = (unsigned int) -1;

    void evaluate(Context ctx) {        
        if (isSettingUp() || isInputDirty<input_RST>(ctx)) {
            emitValue<output_MEM>(ctx, ovf);
            emitValue<output_PASS>(ctx, ovf);
        if (isInputDirty<input_PUSH>(ctx)){
            auto New = getValue<input_NEW>(ctx);
            auto Old = getValue<output_MEM>(ctx);
            if (Old == ovf || New < Old) {
                emitValue<output_MEM>(ctx, New);
                emitValue<output_PASS>(ctx, Old);
            } else {
                emitValue<output_MEM>(ctx, Old);
                emitValue<output_PASS>(ctx, New);
            if (Old != ovf) {
                emitValue<output_CHAIN>(ctx, true);
            emitValue<output_DONE>(ctx, true);

Comparing min-buffer with min-buff-code after 2 pushes:

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.