Don't use an array.
Yes, better use TFPGList<item_type_here>, it is generic. Unit FGL.
Item type must be (should) non-managed.
First, you can use the standard Insert function for arrays.
But if you want to do it yourself, this is what I use:
System.Move(fItems[Index], fItems[Index + 1], SizeOf(Item) * (fCount - Index));
I separately keep track of the number items (fCount) and the capacity of the array, which may be more than fCount.
How should I implement "no be there" in your opinion?
At their core, what do most of the TList* implementations use? An array, or a linked list? Something else I'm missing?
Don't use an array.
- What's the algorithm that implements that move?
- Does it copy from left-to-right or form right-to-left? If it copies from left to right, then all values are now the same as insertion point
- Does it copy the chunk to another place and then back to the original position+1?
- What if the array is so big that it crosses page boundaries, is Move aware of that?
Cheers,
Gus
As you can see in the source move is done in Assembler.
In the very early days of Pascal you had to take care of moving left or right, there was moveL and moveR.
That was replaced long time ago by only one move that takes care of the direction.
I have moved big pieces of data with fpc and I never had problems.
Ultimately what I'm trying to do is avoid using binary trees.
Depends on what you want. If you want deterministic walking of the datastructure and not necessarily infinity scalability, array of arrays can be quite ok, see e.g. http://www.stack.nl/~marcov/lightcontainers.zip
Ultimately what I'm trying to do is avoid using binary trees.
Mandating that is likely to be incompatible with your original "optimise" request.
MarkMLl
I was afraid someone would say that, and quite frankly, I think I know it in my bones, but hey, if you don't ask you keep ignorant :)
Well, there's B-Trees, B+-Trees and Bonsai Trees... and there was something about those that made IBM buy the company that invented them.
There's definitely hybrid approaches you could use. For example, if you knew that your overall array would never have more than 64K elephants you could implement it as 256 dynamic arrays each of up to 256 elements, each of which had an index, and an otter class wrapper to handle indexed access.
The absolutely crucial thing is to look at how often there is a mid-array insertion, and how far it is from the end, relative to the number of reads.
To be quite honest, a lot of the usage will see the array containing only around 1 to ~50 items. Yeah, again stuff from the coder I mentioned in the "non-blocking" post :(
But I like to have it future proof, where there could be items in the hundreds, thousands even...
For something that small, have a maximal-sized array of integers as an index and an unsorted dynamic array. But be aware that extending a dynamic array can be slow, so do it in chunks.
And you've now also gave me the answer to why there is a variable called capacity attached to dynamic arrays. We have to SetLengh() in chunks because it's costly!!Is this something that will be Windows only or does it have to be multiplatform ?
Copy the Memory starting at Pos 1 in Source-Array with Length 41*MemberSize (Member can be 2 Bytes, 4 Bytes, 8 Bytes, A "hidden" Pointer--> Strings, Records etc.) to DestArray[1]
Assign Array-Member[42] the new value
Copy the Memory starting at Pos 42 in Source-Array to Dest-Array[43] with Length 59*MemberSize
Discard/Destroy/Erase Source-Array
Mark, don't get me wrong: I actually agree with you, i just addressed the original question, and my answer was, how i did/do it in VBA
However the management and performance burden would be substantially worse than using e.g. index+store, or "doing it properly" with a linked list or tree.
MarkMLl
And for small amounts contained in the array, it will make sense.
But at what point is this approach gonna be inefficient?
So my original idea to optimise it is to have a low level call that would shift a whole block of mem, one byte to the right.
But then more questions appear:
- Is this possible?
- Is it the best solution?
- When does the array pass the boundary of a page, and there need to be 2 mem copy operations?
Is this something that will be Windows only or does it have to be multiplatform ?
TList (and generics like TFPGList) are based on array internally. And yes, inserting to the middle - makes slow array moving - like Move( ) that you seen in this thread. So it is not optimal. What is optimal from the point of view of insertion - is linked list.
For small arrays you can just as well use Insert and call it a day as it tries to be as performant as possible for what it can work with. Not to mention that it also deals with the nitty, gritty details of managed types.
For larger arrays you will likely need additional or different data structures (e.g. the mentioned binary trees).
Also as long as you aren't developing a database system that needs to be sure where each page is (in memory or on disk) then you don't need to deal with pages aside from "is it valid?".
Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend %)Now I can remember my old professor saying : "In the end it all boils down to a vector, be it to the vector of the main memory".
Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend %)
Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend %)
Considering that, the dynamic arrays can give a memory size benefit, not a speed one. Splitting the array to smaller chunks is just marginally better, since the problem of shifting the tail remains, just the tail becomes smaller.Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend %)
MarkMLI maybe found it too obvious, but one more difference: A normal multidimensional array has a rectangular shape (in 2D) and so on in larger dimensions, while (for dynamic arrays) an array of an array can have different size rows.
How can one optimise inserting an item into an array, anywhere but the end?Here IMHO the most straightforward answer:
Don't use an array.
MarkMLl
Strange professor, because a multiple dimension array has a linear layout in memory, same as a one dimensional array, so unless you sort, it is O(N) and the sort is costly. Basics.Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend %)Now I can remember my old professor saying : "In the end it all boils down to a vector, be it to the vector of the main memory".
Why strange? Isn't it the same statement? Or maybe I didn't wrote it well in English %)Strange professor, because a multiple dimension array has a linear layout in memory, same as a one dimensional array, so unless you sort, it is O(N) and the sort is costly. Basics.Is an "array of arrays" the same thing as a multidimensional array ... Asking for a friend %)Now I can remember my old professor saying : "In the end it all boils down to a vector, be it to the vector of the main memory".
In the case at hand, one should assume O(N). It is impossible to improve on that.
In the case at hand, one should assume O(N). It is impossible to improve on that.