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.
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)
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?
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?
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....
Quote from: oex on September 12, 2010, 04:08:32 PM
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
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