javascript array['id'] performance - Softwareontwikkeling

zaterdag 31 oktober 2009 19:59

Acties:

0 Henk 'm!

Topicstarter

Hi,

javascript heeft de mogelijkheid om een array te gebruiken alsof het een hashtable is (dus: array['apple'] = new Apple(); en dan referencen met array['apple']). Dit is precies wat ik nodig heb, maar ik maak me zorgen over de performance. Weet iemand waar ik hier meer over kan vinden?

In O(n) specs zou mooi zijn (dus is het een lineaire call O(n) of juist niet O(1) ) Verschilt dit per browser? Wordt elke keer de key geparsed bijvoorbeeld? (Wat betekend dat array[1] veel sneller is dan array['apple']?

Ik zou sowieso wel wat meer willen weten over dit soort dingen in javascript..

Thanks!

zaterdag 31 oktober 2009 20:01

Acties:

0 Henk 'm!

crisp

Devver

Pixelated

Sowieso moet je daar geen array voor misbruiken, voor hashmaps gebruik je een Object:

JavaScript:

1
2
3

var hashmap = {};
hashmap.foo = 'bar';
hashmap['woei'] = 1337;

qua performance lijkt me het erg implementatie-afhankelijk. Ik zou zeggen: zet een testcase op en probeer het uit

[ Voor 25% gewijzigd door crisp op 31-10-2009 20:03 ]

Intentionally left blank

zaterdag 31 oktober 2009 20:32

Acties:

0 Henk 'm!

Garma

Topicstarter

van wat ik ervan begreep (zoals hier beschreven: klik) is een object en een array hetzelfde in javascript.. dus dat zou niet uit moeten maken. Dat klopt met wat jij suggereert met

code:

1	var hashmap = {};

want {} is short voor lege array

Anyway, een testcase had ik nog niet eens aan gedacht

dat ga ik inderdaad maar eens bouwen.

[ Voor 18% gewijzigd door Garma op 31-10-2009 21:07 ]

zaterdag 31 oktober 2009 21:05

Acties:

0 Henk 'm!

Garma

Topicstarter

hmmm dit is erg interessant

HTML:

<html>
<head>
    <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.3.2/jquery.min.js" ></script>

<script type="text/javascript">
$(document).ready(function(){
    var arr1 = new Array();
    var starttime = 0;
    
    // assign hash
    starttime = gettime();  
    for(var i = 0; i < 1000000; i++){
        var index = "A"+i;
        arr1[index] = "Koekenbakker";
    }   
    $("#mybox").text("hashing: " + (gettime() - starttime));
    
    // assign index
    var arr2 = new Array();
    starttime = gettime();
    for(var i = 0; i < 1000000; i++){
        var index = "A"+i;
        arr2[i] = "Koekenbakker";
    }
    $("#mybox2").text("indexing: " + (gettime() - starttime));
    
    // read hash
    starttime = gettime();  
    for(var i = 0; i < 1000000; i++){
        var index = "A"+i;
        var value = arr1[index]
    }   
    $("#mybox5").text("read hashing: " + (gettime() - starttime));
    
    var arr2 = new Array();
    starttime = gettime();
    for(var i = 0; i < 1000000; i++){
        var index = "A"+i;
        var value = arr2[i]
    }
    $("#mybox6").text("read indexing: " + (gettime() - starttime));
    
    
});
function gettime(){
    var date = new Date();
    return date.getTime();
}
</script>
</head>
<body>
<form>
<div id="mybox"></div>
<div id="mybox2"></div>
<div id="mybox5"></div>
<div id="mybox6"></div>
</form>
</body>
</html>

Je kan [code=html|js|css|php|...][/code] gebruiken voor highlighting en let er even op dat je niet dubbelpost binnen 24 uur!

getest in FF:
hashing: 1335
indexing: 239
read hashing: 1036
read indexing: 696

getest in IE (delen door 10 want ie doet moeilijk over lange scripts)
hashing: 152
indexing: 115
read hashing: 143
read indexing: 114

Conclusies:
-> IE is trager dan FF
-> hashes writen is veel trager dan indexen
-> hashes lezen is trager maar niet veel trager dan indexen

[ Voor 3% gewijzigd door BtM909 op 31-10-2009 23:45 ]

zaterdag 31 oktober 2009 22:49

Acties:

0 Henk 'm!

Verwijderd

Garma schreef op zaterdag 31 oktober 2009 @ 20:32:
want {} is short voor lege array

Nee, {} is een (lege) object literal. [] is een array literal. Een array is wel een object, maar niet elk object is een array

Lees dat artikel van Crockford nog maar eens goed.

In je test overschrijf je trouwens arr2 voordat je read indexing test. Niet dat het veel uitmaakt voor de resultaten.

P.S. Je moet wel zo'n beetje alle paden van optimalizatie van je code hebben bewandeld voordat je je zorgen moet gaan maken over dit soort zaken, is mijn ervaring.

[ Voor 4% gewijzigd door Verwijderd op 31-10-2009 22:51 ]

zaterdag 31 oktober 2009 23:26

Acties:

0 Henk 'm!

Garma

Topicstarter

hmm inderdaad nog eens goed lezen. bedankt voor je opmerkingen

-> edit: hm je hebt gelijk, maar ik snap niet wat verder het verschil is..? De length-property, nou, ja fijn.. Puur om semantische redenne zou ik dan Object moeten gebruiken, klopt dat?

tsja, ik wil deze structuur gebruiken voor de basis van een applicatie die ik aan eht schrijven ben. Heel relaxt dat hashtable-achtige maar het maakt nogal wat uit of dat dan O(n) kost of O(1). In het eerste geval ga ik gewoon aan de slag met indexen maar het lijkt er op dat het niet al te veel uit maakt

Het is niet bepaald een website die ik aan het schrijven ben dus ik wil niet later in de problemen komen.

[ Voor 16% gewijzigd door Garma op 31-10-2009 23:29 ]

zondag 1 november 2009 01:01

Acties:

0 Henk 'm!

crisp

Devver

Pixelated

Garma schreef op zaterdag 31 oktober 2009 @ 23:26:

-> edit: hm je hebt gelijk, maar ik snap niet wat verder het verschil is..? De length-property, nou, ja fijn.. Puur om semantische redenne zou ik dan Object moeten gebruiken, klopt dat?

Arrays hebben natuurlijk ook nog wat extra methods. Het bijhouden van de length property maakt het gebruik van een array als hashmap overigens juist ook iets trager dan een object. Daarbij is het common practice om arrays te extenden met prototyped methods wat het uitlezen mbv for-in uitdagender maakt (je zal voor elke property moeten checken of het een eigen property is of een prototyped method).

Object extenden is natuurlijk 'verboten'

tsja, ik wil deze structuur gebruiken voor de basis van een applicatie die ik aan eht schrijven ben. Heel relaxt dat hashtable-achtige maar het maakt nogal wat uit of dat dan O(n) kost of O(1). In het eerste geval ga ik gewoon aan de slag met indexen maar het lijkt er op dat het niet al te veel uit maakt

Hier wat cijfers waar je denk ik meer aan hebt mbt je vraag:

hashmap:
500000 items schrijven naar obj1: 1401ms
1000000 items schrijven naar obj2: 3858ms
1000000 lookups in obj1: 1393ms
1000000 lookups in obj2: 2880ms

array (indexed):
500000 items schrijven naar arr1: 381ms
1000000 items schrijven naar arr2: 1457ms
1000000 lookups in arr1: 880ms
1000000 lookups in arr2: 1823ms

(Firefox 3.5.3, winXP)

Het is niet bepaald een website die ik aan het schrijven ben dus ik wil niet later in de problemen komen.

Je grootste probleem zal dan eerder zijn dat IE's JS engine gewoon gruwelijk traag is

Intentionally left blank

zondag 1 november 2009 01:04

Acties:

0 Henk 'm!

Verwijderd

Garma schreef op zaterdag 31 oktober 2009 @ 23:26:
-> edit: hm je hebt gelijk, maar ik snap niet wat verder het verschil is..? De length-property, nou, ja fijn.. Puur om semantische redenne zou ik dan Object moeten gebruiken, klopt dat?

Bij een Array krijg je, als je indexes gebruikt, allerlei hele nuttige methods.

Het is niet bepaald een website die ik aan het schrijven ben dus ik wil niet later in de problemen komen.

Ik ga er even van uit dat je een browser-based applicatie schrijft (HTML+CSS+JS). De overhead van zaken op het scherm toveren, content updaten, ajax calls, etc is zo groot dat optimalizaties op het nivo van array/object access vrijwel onopgemerkt zullen blijven.

zondag 1 november 2009 01:15

Acties:

0 Henk 'm!

crisp

Devver

Pixelated

Overigens zijn de resultaten van jouw en mijn benchmarks behoorlijk vertroebelt; het samenstellen van de index-variabele maakt al een aanzienlijk deel uit van de totale processingtijd.

Intentionally left blank

zondag 1 november 2009 10:12

Acties:

0 Henk 'm!

Garma

Topicstarter

crisp schreef op zondag 01 november 2009 @ 01:15:
Overigens zijn de resultaten van jouw en mijn benchmarks behoorlijk vertroebelt; het samenstellen van de index-variabele maakt al een aanzienlijk deel uit van de totale processingtijd.

@Crisp: klopt, ik heb ze expres laten staan in alle loops. Het gaat dan ook om relatieve tijden.
bedankt voor de results.Het lijkt er op dat een array een stuk sneller is.. wat gek is gezien het feit dat het beiden objecten zijn.

@mod: bedankt voor het highlighten vroeg me al af hoe dat ging, en wat bedoel je met dubbelpost binnen 24 uur?

@blues: tsja dat ligt er maar aan wat je doet natuurlijk en hoeveel elementen je over praat

Het zou me niet verbazen als ik hier en daar over arrays van >1000 elementen moet itereren. Maar opzich heb je gelijk dat dat nog steeds niet al te veel tijd kost.

[ Voor 15% gewijzigd door Garma op 01-11-2009 10:13 ]

zondag 1 november 2009 15:13

Acties:

0 Henk 'm!

.oisyn

Moderator Devschuur®

Demotivational Speaker

Overigens zijn arrays ook geen echte arrays, maar ook hashtables. De int indices worden ook gewoon eerst geconverteerd naar string.

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.

Pagina: 1

Reageer