Snelste manier om te ontdekken of een string in een andere string voorkomt

Status
Niet open voor verdere reacties.
F

famlam

Gebruiker
Lid geworden
15 okt 2008
Berichten
416
Weet er iemand wat de snelste manier is om te ontdekken of een string in een andere string voorkomt? Ik heb beschikking over JQuery en 'normaal' javascript. Het moet het snelste zijn in Chrome en Safari. (Andere browsers maken me niet uit ;) )

Voorbeeld:
[JS]var url = "http://site.com/ads/image.jpg";
var check = ".com/ads/";
var rcheck = /\.com\/ads\//;[/JS]

De methoden die ik ken zijn
[JS]var doescontainstring = (url.indexOf(check) != -1);[/JS]
en
[JS]var doescontainstring = (rcheck.test(url));[/JS]
en
[JS]var doescontainstring = (url.match(rcheck));[/JS]

Kent er iemand nog meer snellere methoden, en weet er iemand welke de snelste is als er geen andere methodes zijn?

B.v.d.,
Famlam
 
Regular expressions zijn vaak niet het snelste. test en match zijn regex beesjes, dus denk dat die niet het snelste zijn.

Ik zou zelf voor indexOf gaan. Maar, je kan natuurlijk veel beter zelf een test doen!

[JS]var time = new Date().getTime();

var test = "stringz";
var instr = "in deze string staat toch echt stringz!";

var i, res, count = 100000; // oid

for(i=0; i<count; i++)
{
res = instr.indexOf(test); // deze veranderen met de test en match regexp's.
}

alert((new Date().getTime()) - time);[/JS]oid.
 
Voor Chrome geeft dat (met count 1.000.000, wat dicht in de buurt ligt van wat het echt is)
Code: 
indexOf:  250 - 376 - 311 - 314 - 322 --> 315 ms
test:     126 - 115 - 128 - 113 - 128 --> 122 ms
match:    245 - 249 - 250 - 238 - 226 --> 242 ms
Ik heb geen Safari geïnstalleerd, dus wat de resultaten daar zijn weet ik niet.

Maar zijn er misschien nòg snellere methoden?
Want 122 ms is nog steeds een 'te groot' getal :(
 
String.indexOf() en Regex.test() zijn erg aan elkaar gewaagd.
In Firefox is indexOf() veel sneller dan de andere twee. In Opera en Chrome is test() weer sneller.

Veel sneller zal het helaas niet gaan. Het blijft natuurlijk wel javascript :)
 
Ik vraag me af of Javascript wel de juiste tool is voor jouw probleem... wat probeer je te bereiken? Met iets meer informatie kunnen we misschien een betere oplossing vinden.
 
Frats zei:
Ik vraag me af of Javascript wel de juiste tool is voor jouw probleem... wat probeer je te bereiken? Met iets meer informatie kunnen we misschien een betere oplossing vinden.
Klik om te vergroten...

Ik ben een van de drie programmeurs van AdBlockforChrome, een AdBlock extensie voor Chrome en Safari.
Extensies kunnen alleen in js geprogrammeerd worden. Daarom is JS 'wel de juiste tool'.

De reden dat ik dit vraag is omdat ik het filter-matching onderdeel een beetje traag vind.
 
Dus het idee is dat je een gigantische lijst hebt met urls die 'verboden' zijn, en deze moet doorlopen?

Nou, dan kan je misschien beter een andere methode zoeken dan string-manipulatie... Ik ga er even over nadenken.
 
Jep, in dat geval is het de juiste tool... dan wordt het lastiger.
 
That Guy zei:
Dus het idee is dat je een gigantische lijst hebt met urls die 'verboden' zijn, en deze moet doorlopen?

Nou, dan kan je misschien beter een andere methode zoeken dan string-manipulatie... Ik ga er even over nadenken.
Klik om te vergroten...

Uitgebreidt komt het hierop neer: http://code.google.com/p/adblockforchrome/source/browse/trunk/filtering/filtertypes.js

Simpel gezegd komt het hierop neer:
We converteren alle regels (zoals ||banners.helpmij.nl^) naar 'controleerbare' regels. Banners.helpmij.nl zou bijvoorbeeld '://banners.helpmij.nl' worden (en een tweede variant).
Vervolgens wordt dit opgeslagen. Wanneer er een pagina wordt geladen worden alle resource-URLs door al die filters gecontroleerd. Indien er een match is wordt dit ding geblokkeerd, anders gebeurt er niets.

Op dit moment gebeurt dit door regels met * naar regex te converteren, en alle andere naar testbare strings. Over korte tijd converteren we alles naar regex, zodat we alleen maar regex.test() hoeven te gebruiken. Maar ook dit kost nog vrij veel tijd (43-53 ms per 10.000.000 filters op mijn computer per resource.) Daarom zoeken we naar snellere manieren (zonder extra geheugen te gebruiken, die filters kosten al meer dan genoeg).
 
Waarschijnlijk is het het snelste om een object als hash te gebruiken en in die hash urls op te slaan.

Zoiets als:
[JS]
var hash = {};
// per domein urls opslaan
hash['domain'] = {
urls: ['url1', 'url2']
};
[/JS]
Daarna kun je de urls checken door ze uit de hash te halen.
[JS]
var urls = hash[varWithDomain];
[/JS]
Je kan ze waarschijnlijk nog verder onderverdelen om nog sneller resultaten te behalen.
 
Ah, ik zie dat net even te laat was met mijn reactie :)

Het is sowieso goed om alle String.match(RegExp) to vervangen door RegExp.test(string);
Probeer ook veelgebruikte expressies niet telkens opnieuw te initialiseren, maar hergebruik hetzelfde object.
 
Laatst bewerkt:
voilajs zei:
Waarschijnlijk is het het snelste om een object als hash te gebruiken en in die hash urls op te slaan.

Zoiets als:
[JS]
var hash = {};
// per domein urls opslaan
hash['domain'] = {
urls: ['url1', 'url2']
};
[/JS]
Daarna kun je de urls checken door ze uit de hash te halen.
[JS]
var urls = hash[varWithDomain];
[/JS]
Je kan ze waarschijnlijk nog verder onderverdelen om nog sneller resultaten te behalen.
Klik om te vergroten...

De meeste filters (zoals '.com/ads/') zijn niet domein-afhankelijk. En zelfs al hebben ze een domeinnaam in het filter, dan kunnen ze nog steeds op andere domeinen gebruikt worden. Bijvoorbeeld: ||doubleclick.net^third-party wordt gebruikt op filehippo.com maar niet op doubleclick.net zelf.
 
Ik kan zo snel niet een alternatief bedenken voor test.
met count 1.000.000, wat dicht in de buurt ligt van wat het echt is
Klik om te vergroten...
Als je resultaat rond de 50 ms ligt (weet niet meer waar ik dat vandaan had, geloof van de google-code pagina's), moet ik zeggen dat dat toch een redelijke preformance is. Nu heeft Chrome het snelste JS-engine, maar ik denk niet of je er met een andere (of zelfgemaakte) functie sneller van af komt.

Mischien kan je nog wat kleine aanpassingen maken aan je loop zelf (heb niet de hele google-code-src doorgenomen, maargoed), maar of dat veel zal uitmaken... denk het niet.
 
Je kan eigenlijk al best snel een beter resultaat halen. Zeker als de code vaak word herhaald.

Bijvoorbeeld (regel 28 - 31)
[JS]
// old style selector syntax contains a #, then some text, then a (.
else if (text.match(/##/) || text.match(/#.*\(/))
cache[text] = new SelectorFilter(text);
else if (text.match(/^@@/))
[/JS]

In dit stukje code word al 3 keer een match() gebruikt waar een test() sneller zou zijn.
daarbij komt dat de regex die gebruikt elke keer opnieuw word geinitialiseert, wat ook weer cpu snoept op den duur.
Het bovenstaande kun je dus best herschrijven naar bijvoorbeeld:
[JS]
// Filter Class members voor hergebruik
Filter.matchOldHash = /##/;
Filter.matchOldDot = /#.*\(/;
Filter.matchAt = /^@@/;
[/JS]
en dan...
[JS]
// old style selector syntax contains a #, then some text, then a (.
else if (Filter.matchOldHash.test(text) || Filter.matchOldDot.test(text)) // misschien kun je hier zelf één expressie van maken?
cache[text] = new SelectorFilter(text);
else if (Filter.matchAt.test(text))
[/JS]
Als dit stukje code 10.000 keer word uitgevoerd zal je al zeker zichtbare winst behalen. :d
 
Laatst bewerkt:
voilajs zei:
Je kan eigenlijk al best snel een beter resultaat halen. Zeker als de code vaak word herhaald.

Bijvoorbeeld (regel 28 - 31)
[JS]
// old style selector syntax contains a #, then some text, then a (.
else if (text.match(/##/) || text.match(/#.*\(/))
cache[text] = new SelectorFilter(text);
else if (text.match(/^@@/))
[/JS]

In dit stukje code word al 3 keer een match() gebruikt waar een test() sneller zou zijn.
daarbij komt dat de regex die gebruikt elke keer opnieuw word geinitialiseert, wat ook weer cpu snoept op den duur.
Het bovenstaande kun je dus best herschrijven naar bijvoorbeeld:
[JS]
// Filter Class members voor hergebruik
Filter.matchOldHash = /##/;
Filter.matchOldDot = /#.*\(/;
Filter.matchAt = /^@@/;
[/JS]
en dan...
[JS]
// old style selector syntax contains a #, then some text, then a (.
else if (Filter.matchOldHash.test(text) || Filter.matchOldDot.test(text)) // misschien kun je hier zelf één expressie van maken?
cache[text] = new SelectorFilter(text);
else if (Filter.matchAt.test(text))
[/JS]
Als dit stukje code 10.000 keer word uitgevoerd zal je al zeker zichtbare winst behalen. :d
Klik om te vergroten...

De overstap van match naar test heb ik nu al aangepast (in een branch, dus je ziet het nog niet in de oude link). Dat andere zal ik later doen, nadat een andere branch ge'merged' is. Ik zal eens een testje draaien wat sneller is:
de twee regexen achter elkaar testen of /regex1|regex2/ gebruiken...

EDIT: de /##/ || /#.*\(/ methode is sneller dan de /##|#.*\(/ methode. Het scheelt 0.2 ms op 1000000 filters, dus verwaarloosbaar, maar toch is hij sneller (tenminste op Chrome)
 
Laatst bewerkt:
Ik heb net even getest om te kijken wat het verschil is met lokaal geinitialiseerde regex objecten tegenover globaal hergebruik.

Over 1000000 herhalingen win je met Chrome 1ms.
Maar in Safari is het verschil wel 70ms.
 
voilajs zei:
Ik heb net even getest om te kijken wat het verschil is met lokaal geinitialiseerde regex objecten tegenover globaal hergebruik.

Over 1000000 herhalingen win je met Chrome 1ms.
Maar in Safari is het verschil wel 70ms.
Klik om te vergroten...

Dankjewel!
Ik wacht eventjes totdat de andere branches door de anderen goedgekeurd zijn (dat duurt waarschijnlijk ~2 dagen en daarna voer ik deze verandering waarschijnlijk ook door. Tenzij de andere programmeurs (2 Amerikanen) me voor zijn.
Overigens is die verandering minder belangrijk dan de andere, aangezien die code maar één keer uitgevoerd hoeft te worden (bij het starten v.d. browser), terwijl de andere code op elke pagina uitgevoerd moet worden (we kunnen de filters vantevoren namelijk wel 'voorbereiden', maar we kunnen niet voorspellen welke resources geladen zullen worden).
 
voilajs zei:
Cool! Ben benieuwd hoeveel verschil het gaat maken :cool:
Klik om te vergroten...

Op deze pagina met de standaardinstellingen/filters scheelt het tussen de 50 en de 60 ms, op mijn lokale AdBlockversie, die de nieuwste veranderingen al wel heeft. Dit is een verbetering van ongeveer 30%, dus alvast DANKJEWEL!!!
 
Status
Niet open voor verdere reacties.
                    Steun ons                    

Nieuwste berichten

Terug
Bovenaan Onderaan