Array.insert(array) ??

[Janoscharlipp]

Hallo,

ich muss an einer Bestimmten Stelle in ein Array ein anderes Array einfügen. Da ich das ziemlich, bzw. sehr oft mahcen muss, brauche ich dazu eine möglichst schnelle Variante.
Leider komme ich nicht auf was schnelles, hier meine bisherige Version:

Array.prototype.insert = function(index,elements)
{
    var temp0 = this.slice(0,index);
    var temp1 = this.slice(index);
    return temp0.concat(elements,temp1);
} 

diese Funktion ist viel zu langsam, braucht bei mir bei sowas:

arr = new Array(1,2,3,7,8,9);
ins = new Array(4,5,6);
arr = arr.insert(3,ins); 

ca. 5ms.

Hat jemand vielleicht einen besseren Ansatz?

[e2e4]

Müsste eigentlich etwas schneller sein:

Array.prototype.insert = function( index, elements ){
        var r = this.slice( index );
        this.length = index;
        return this.concat( elements, r );
} 

Ansonsten vielleicht die Datenstruktur nochmal überdenken.

[kelor]

sagt mal.... hab ich was nicht verstanden?

wie wäre es mit nem simplen 'splice', der ist viel schneller als concat und konsorten.

Array.prototype.insert = function(index,elements){
        var i=0;
        while(i++ <elements.length) this.splice(index+(i-1),0,elements[i-1]);
        return this;
}
 
 
arr = [1,2,3,7,8,9];
ins = [4,5,6];
arr.insert(stelle,ins); 

greetz

kelor

[e2e4]

Das is ja nun noch langsamer, wobei ich jetzt beim Testen festgestellt hab, das meine Variante auch nicht schneller als Janos ist. Sie ist im Gegenteil noch einen Tick langsamer....

[Janoscharlipp]

vielen Dank.
Da also nichts, oder nicht mehr viel rauszuholen ist, muss ich mir das anders ausdenken.
Wie würdet ihr das denn machen:
Ich hab ne Funtion, der gebe ich in einem Array zwei Punkte:

startPoint = {x:100,y:100};
endPoint = {x:300,y:300};
way = getWay([startPoint,endPoint]); 

diese Funktion soll jetzt prüfen ob der Weg von p1 zu p2 frei ist, wenn ja, einfach wieder die Punkte zurück geben, wenn nicht, einen Umgehungspunkt finden, und rekursiv mit dem neuen Wegpunkt zwei mal sich selbst aufrufen. Also in Pseudocode sowas:

getWay = function(p1,p2)
{
var way = [p1,p2];  
if(freeWay(p1,p2))
{
return way
}
else
{
var p3 = getNewPoint(p1,p2);
newWay1 = getWay(p1,p3);
newWay2 = getWay(p3,p2);
 
return newWay1.concat(newWay2);
} 

(nicht so genau nehmen... nur im Prinzip )

Sollte ich da immer das Weg-Array als Referenz weitergeben, und jede neue Funktion bastelt daran rum, oder sollte jede Funktion ihr Ergebnis returnen und die parent-Funktion setzt dann das Ergebnis in ihr Array ein, und returnt das, bis dann shcließlich der finale Weg rauskommt?

[kelor]

Das is ja nun noch langsamer

wieso ist die langsamer?

beweisführung?!


greetz

kelor

[Janoscharlipp]

hier noch ein kleiner Array.insert prototyp, leider der langsamste

Array.prototype.insert = function(index,elements)
{
    elements.unshift(0);
    elements.unshift(index);
    this.splice.apply(this,elements);
return this;
} 

[kelor]

wie errechnest du bzw willst du errechnenn einen neuen punkt, janosch...?


schon ein script / eine funktion?



greetz

kelor

[Janoscharlipp]

@kelor
bei mir ist deine auch langsamer:

Array.prototype.insert = function(index,elements)
{
    var temp0 = this.slice(0,index);
    var temp1 = this.slice(index);
    return temp0.concat(elements,temp1);
}
 
Array.prototype.insertKelor = function(index,elements){
        var i=0;
        while(i++ <elements.length) this.splice(index+(i-1),0,elements[i-1]);
}
 
 
t = getTimer();
for(var i=0; i<cnt; i++)
{
    arr = new Array(1,2,3,7,8,9);
    arr = arr.insert(3,ins);
}
trace(getTimer()-t+" : "+arr);
 
 
t = getTimer();
for(var i=0; i<cnt; i++)
{
    arr = new Array(1,2,3,7,8,9);
    arr.insertKelor(3,ins);
}
trace(getTimer()-t+" : "+arr);
 
// Ausgabe:
// 147 : 1,2,3,4,5,6,7,8,9
// 316 : 1,2,3,4,5,6,7,8,9 
 

[Janoscharlipp]

keine Funktion aber eine Idee, und einen Entwurf *geheimniskram*

[e2e4]

For all your pathfinding needs:
http://theory.stanford.edu/~amitp/GameProgramming/

[Janoscharlipp]

thx, e2e4, aber bei mir wird das komplett anders aussehen. Ohne Grid...

[e2e4]

Na dann:
http://216.5.163.53/DirectX4VB/Tutor...M_Dijkstra.asp

[Janoscharlipp]

das ist schick, das werde ich mir mal durchlesen.
Allerdings möchte ich auf jeden Fall meine Idee mal ausprobieren, ich hoffe komplett ohne Wegpunkte, Nodes, Graphen und ähnlihces auszukommen.
Mir geht es jetzt mehr um die sache Referenz übergeben, oder Ergebnis returnen.

[e2e4]

Referenz und in die immer nur die Punkte reinpushen die begehbar sind. Dann müsste das eigentlich linear von statten gehen.