insertion table

[ecube]

Forgive my ignorance but i'm not fully understanding an insert table say we have this in our table

1
2
4
5

and we want to add a 3, is everything below 2 swapped? because that seems really ineffecient for a big table where the data is already pre organized and you just want to add 1 value.

[oex]

As far as I understand it yes.... I would use a seperate (faster) memcopy routine after the position is found rather than a swapping routine if you get my drift.... You could use a seperate index and update every X records depending on search weight (although a tree would be much more efficient if you are able to implement it)

[Tedd]

You'd need to copy everything down and then insert the new item, yes.
And a simple memcopy would be a problem because the regions overlap, but there are versions built to handle that.

A tree structure would allow you to make many insertions with minimal overhead, and you get a binary search for free (as long as the tree is mostly balanced.) However, it would require twice as much memory as a flat list (for a simple list of numbers.)
But, as always, it all depends on what you're doing and what your aim is (usually: speed Vs memory usage.) If your insertions are minimal, will they really be a problem? If you have many insertions and the memory is there, why not use it?

[ecube]

thanks guys, i'm thinking I might use an insertion table but on a smaller table, a 2 layer

say my tables only for strings, my first layer is a-z each letter pointing to a list of strings that fit that letter category

I think using binary search it'll be much faster, because it'll search the 26 letter categories first, then search one of their sub category for the ordered strings.
What you think?

[oex]

It will almost certainly be faster.... As Tedd says balance is important.... You might find you have 256 's' words and 1 'z' word.... If this is the case,strings are X or more characters in length and search speed is critical you might be better off using an evenly distributed X multi letter first level table.... It really depends on the data and the application....

[ecube]

It will almost certainly be faster.... As Tedd says balance is important.... You might find you have 256 's' words and 1 'z' word.... If this is the case,strings are X or more characters in length and search speed is critical you might be better off using an evenly distributed X multi letter first level table.... It really depends on the data and the application....

Think that's the first programming related post i've seen you give oex, nice  :bg

[vanjast]

IF I understand you correctly..

Each value can be a struct.
Psuedo typing

Value Struct
   PrevPointer :DWORD
   NextPointer:DWORD
   Value: WhateverSize
Ends

When inserting/adding/deleting al you do is compare the values and adjust the 'pointers'.
When buffering file saves you 'walk the tree of pointers'
:lol