Run results for: Intl.collator O(N*M) vs native String.prototype.includes O(N+M) 2

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/135.0.0.0 Safari/537.36

Browser: Chrome 135

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: one year ago

Test name	Executions per second
native String.prototype.includes O(N+M)	168534.2 Ops/sec
Intl.collator O(N*M)	248637.5 Ops/sec

HTML Preparation code:

<!--your preparation HTML code goes here-->

Script Preparation code:

const regions = [
  "сәлем", "рақмет", "кітап", "үй", "су",
  "нан", "бала", "ана", "әке", "күн",
  "ай", "жыл", "көлік", "жол", "тағам",
  "қала", "ауыл", "адам", "қол", "бас",
  "көз", "құлақ", "мектеп", "жұмыс", "денсаулық",
  
  "merhaba", "teşekkür", "kitap", "ev", "su",
  "ekmek", "çocuk", "anne", "baba", "gün",
  "ay", "yıl", "araba", "yol", "yemek",
  "şehir", "köy", "insan", "el", "baş",
  "göz", "kulak", "okul", "iş", "sağlık",

  "hello", "thank", "book", "house", "water",
  "bread", "child", "mother", "father", "day",
  "moon", "year", "car", "road", "food",
  "city", "village", "person", "hand", "head",
  "eye", "ear", "school", "work", "health",

  "привет", "спасибо", "книга", "дом", "вода",
  "хлеб", "ребёнок", "мама", "папа", "день",
  "луна", "год", "машина", "дорога", "еда",
  "город", "деревня", "человек", "рука", "голова",
  "глаз", "ухо", "школа", "работа", "здоровье"
]

Tests:

native String.prototype.includes O(N+M)
const CONVERTER = { // Казахский алфавит қ: 'к', ғ: 'г', ң: 'н', ү: 'у', ұ: 'у', һ: 'х', ө: 'о', і: 'i', // Турецкий алфавит ı: 'i', }; const converterPattern = Object.keys(CONVERTER) .map(ch => ch.replace(/[.*+?^${}()|[\]\\]/g, '\\$&')) // эскейпим для regexp .join(''); const NEEDS_TRANSLITERATION_REGEXP = new RegExp(`[\\u0300-\\u036f${converterPattern ? converterPattern : ''}]`, 'i'); const transliterateAndNormalize = (str) => { const normalizedStr = str.toLowerCase().normalize('NFD'); if (!NEEDS_TRANSLITERATION_REGEXP.test(normalizedStr)) { return normalizedStr; } return normalizedStr .split('') .map(char => CONVERTER[char] ?? char) .filter(char => !char.match(/[\u0300-\u036f]/)) // Убираем диакритические знаки .join(''); }; const includesSubString = (haystack, needle) => { /** Простейшие оптимизации */ if (needle.length > haystack.length) { return false; } if (haystack.toLowerCase().includes(needle.toLowerCase())) { return true; } const normalizedHaystack = transliterateAndNormalize(haystack); const normalizedNeedle = transliterateAndNormalize(needle); return normalizedHaystack.includes(normalizedNeedle); }; for (const region of regions) { includesSubString(region, 'turkey'); }
Intl.collator O(N*M)
const collator = new Intl.Collator(undefined, { sensitivity: 'base' }); function findSubstring(text, pattern) { const textLength = text.length; const patternLength = pattern.length; if (patternLength === 0) return 0; for (let i = 0; i <= textLength - patternLength; i++) { let found = true; for (let j = 0; j < patternLength; j++) { if (collator.compare(text[i + j], pattern[j]) !== 0) { found = false; break; } } if (found) return i; } return -1; } for (const region of regions) { findSubstring(region, 'turkey'); }