Forum > General

How can one optimise inserting an item into an array, anywhere but the end?

(1/9) > >>

Gustavo 'Gus' Carreno:
Hi Y'all,

In order to do that, one increments the length of the array by one, then moves all the elements that stand on the insertion index, and to the right of it, one place to the right and then insert our element at the insertion index.

For me, the logic implementation of shift-the-elements-to-the-right would be:

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---type  TMyArray: Array of Integer; // As a quick example procedure ShiftArrayRight(const AMyArray: TMyArray; AInsertionIndex: Integer);var  Index: Integer;begin  SetLength(AMyArray, Length(AMyArray)+1); // Would the const up there be an issue here?  for Index:= High(AMyArray) downto AInsertionIndex do  begin    AMyArray[Index]:= AMyArray[Pred(Index)];  end;end;
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?
Hence I'm asking the more experienced programmer in this forum to help me on this one.

As per usual, many, MANY thanks in advance!!


Don't use an array.


Yes, better use TFPGList<item_type_here>, it is generic. Unit FGL.
Item type must be (should) non-managed.

Gustavo 'Gus' Carreno:
Hey Mark,

--- Quote from: MarkMLl on August 11, 2022, 09:49:46 pm ---Don't use an array.

--- End quote ---

I like your Mister Miyagi answer: Best way to block a punch, no be there. LOL !!!  :D

How should I implement "no be there" in your opinion?

Cuz the only way I see to avoid the array is to use a linked list.

At their core, what do most of the TList* implementations use? An array, or a linked list? Something else I'm missing?


Gustavo 'Gus' Carreno:
Hey Alex,

--- Quote from: AlexTP on August 11, 2022, 09:54:14 pm ---Yes, better use TFPGList<item_type_here>, it is generic. Unit FGL.
Item type must be (should) non-managed.

--- End quote ---

Yes, that would also be my answer, but in it's core, does that generic use an array or a linked list?
And if it uses an array, how did the author manage the optimisation of inserting in the middle?



[0] Message Index

[#] Next page

Go to full version