Re: How to allcate an array of strings dynamically

Tech Tip: Click here to run a free scan for Windows Errors and optimize PC performance

OK, here's a little exercise in algorithm design...

Working on an embedded system, data is loaded. Because there can be insertions and
deletions during execution, it is stored as a 2-way linked list. In the original model of
the code, the data came in unsorted order and it didn't matter. In the new code, for
performance reasons the data had to be sorted. Whole new algorithms were added for
processing, to add to the original functionality. And performance mattered.

First approximation: read the data into the list. Build an array, copy pointers to the
objects into the array. Call qsort on the array and sort it according to the criteria for
comparison. Then relink the list elements based on the sequence of items in the array.
Now the array is sorted, and we can proceed.

OK, some files are so large that after they are read in, there is no space to allocate the
array. What to do? The list still needs to be sorted...the new code can no longer
operate with an unsorted list.

Next task: while traversing the list when the device is running, there are "conditional
branches" (in effect). If a criterion is met when the node is processed, control proceeds
either to the next node, or a nonadjacent node. But the nonadjacent node is determined by
the input data, and can be any of the several thousand nodes that exist. This is realtime
system on a relatively slow embedded system, and therefore O(n/2) is completely
unacceptable from a performance viewpoint; we'd miss the realtime window by orders of
magnitude. But there isn't space to allocate an array and do bsearch. What to do?

Parameters: Assume a 5MHz machine or thereabouts (ok, it was an 8088). Assume there will
be < 5000 elements in the list (all we could fit into 640K).

Additional problem: for localization, we didn't have room in memory to hold all the user
messages, prompts, etc. So all text for messages was kept in a file. How to implement
LoadString? [Parameters: most messages were < 20 characters, but there were a lot > 45
characters, particularly error messages]. Design an implementation for what we would now
recognize as LoadString that ran on a bare machine, using only standard C file I/O.

[These were very real problems I had to solve. So the assignment is to come up with
solutions to these problems. Answers not due for a week, because I'll be off teaching a
device driver course near Washington DC and I never go online when I travel]

Code never matters, Data is all that matters. The above problems represent data
problems. Code size grew because code was added to enhance performance, both performance
in speed and performance in memory size. Code size was irrelevant compared to data size
problems. Ultimately, we had to address the fact that we were running 1.7MB code in a
640K machine with no virtual memory, but that's a different story (once we solved the
problem, the code size grew from 380K to 1.7MB with no change in the size of the data
space, but that represents a now-dead technological solution, and one of the few remaining
manifestations of this technology today is in the Space Shuttle).
joe

On Sat, 23 Jun 2007 22:53:06 GMT, MrAsm <mrasm@xxxxxxx> wrote:

On Sat, 23 Jun 2007 18:47:30 -0400, Joseph M. Newcomer
<newcomer@xxxxxxxxxxxx> wrote:

Ah, but the issue here is whether or not the access needs to be done while the list is
being built, or is done AFTER the list is built! If AFTER the list is built, then it is
trivial:

I understand: you convert to array after the list is built: you're
right.

...
Without an understanding of the ultimate use of the data structure, a complete solution
cannot be proposed.

Yes, you're right.

MrAsm
Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Relevant Pages

  • Re: help about code composer studio
    ... better way of getting data into an array using the DSP board? ... Need to learn how to apply control theory in your embedded system? ... "Applied Control Theory for Embedded Systems" by Tim Wescott ...
    (comp.dsp)
  • Re: Deleting Array Element
    ... Perhaps an array is the wrong choice for your data and algorithm? ... You might be thinking of a linked-list, which can be built on top of an array, if you like. ... Direct replies will be blacklisted. ...
    (comp.lang.c)
  • Converting byte[] to float ...
    ... (It arrives on the windows platform from an embedded system via USB). ... How can I extract/convert/assign the encoded array to a native float variable? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)