1

I want to know the best algorithm where I can create a "sorted" list based on the key (ranging from 0 to 2 power 32) and traverse them in sorted order when needed in an embedded device. I am aware of possible options namely

  1. sorted linklist As number of nodes in the linked list increases searching for the right node in the list for insertion/update operations takes more time O(n)

  2. Hash Might be the current best choice until and unless we do not have collisions with the hashing logic

  3. Table of size 2 power 32 Wastage of space

Is there any other best alternative which is suited to be used in an embedded device ?

codingfreak
  • 4,467
  • 11
  • 48
  • 60
  • Can you deal with sorting entries after collecting them all, or do you need the collection sorted after each entry is added? – cHao Feb 13 '18 at 18:15
  • The answer is: it depends. What comes to mind immediately is that you just store everything in an array (which is space-efficient) and then sort before you traverse (which is _O(N)_ for integers). – Richard Feb 13 '18 at 18:43
  • 1
    It also depends on the expected (max) size of the collection. Could it really grow to 2 billion? – H H Feb 13 '18 at 18:59
  • This question seems to have died. Did my answer help at all? – Richard Mar 06 '18 at 21:05

1 Answers1

0

There are many design choices to be weighed.

Generalities

Since you're working on an embedded device, it's reasonable to assume that you have limited memory. In such a situation, you'll probably want to choose memory-compact data structures over performant data structures.

Linked lists tend to scatter their contents across memory in a way which can make accesses slow, though this will depend somewhat on your architecture.

The Options You've Proposed

  1. Sorted linked-list. This structure is already slow to access (O(n)), slow to construct (O(N²)), and slow to traverse (because a linked-list scatters memory, which reduces your ability to pre-fetch).

  2. Hash table: This is a fast structure (O(1) access, O(N) construction). There are two problems, though. If you use open addressing, the table must be no more than about 70% full or performance will degrade. That means you'll be wasting some memory. Alternatively, you can use linked list buckets, but this has performance implications for traversal. I have an answer here which shows order-of-magnitude differences in traversal performance between a linked-list bucket design and open addressing for a hash table. More problematically, hash tables work by "randomly" distributing data across memory space. Getting an in-order traversal out of that will require an additional data structure of some sort.

  3. Table of size 2 power 32. There's significant wastage of space for this solution. But also poor performance since, I expect, most of the entries of this table will be empty, but they must all be traversed.

An Alternative

Sort before use

If you do not need your list to always be sorted, I'd suggest adding new entries to an array and then sorting just prior to traversal. This gives you tight control over your memory layout, which is contiguous, so you'll get good memory performance. Insertion is quick: just throw your new data at the beginning or end of the array. Traversal, when it happens, will be fast because you just walk along the array. The only potentially slow bit is the sort.

You have several options for sort. You'll want to keep in mind that your array is either mostly sorted (only a few insertions between traversals) or mostly unsorted (many insertions between traversals). In the mostly-sorted case, insertion sort is a good choice. In the mostly-unsorted case, [quicksort](https://en.wikipedia.org/wiki/Quicksort] is solid. Both have the benefit of being in-place, which reduces memory consumption. Timsort balances these strategies.

Richard
  • 56,349
  • 34
  • 180
  • 251