Какой самый эффективный алгоритм поиска индексов нескольких символов внутри строки (javascript)?

Question

Я ищу самый быстрый метод, который я могу использовать для поиска в теле текста индексов из нескольких символов.

Например:

searchString = 'abcdefabcdef'; 
searchChars  = ['a','b'];
// returns {'a':[0,6], 'b':[1,7]}

Answer 1

Вы должны иметь возможность использовать регулярное выражение, чтобы найти все вхождения каждого персонажа.Что-то вроде:

function findIndexes(find, str) {
  var output = {};
  for (var i = 0; i < find.length; i++) {
    var m = [];
    var r = new RegExp('.*?' + find[i], 'g');
    var ofs = -1;
    while ((x = r.exec(str)) != null) {
      ofs += x[0].length;
      m.push(ofs);
    }
    output[find[i]] = m;
  }
  return output;
}

Редактировать:

Внесены некоторые изменения, и теперь это работает.:) Тем не менее, поскольку в Javascript нет метода совпадений, чтобы получить все совпадения сразу, на самом деле нет никакого улучшения по сравнению с использованием indexOf ...: P

Edit 2:

Однако,Вы можете использовать регулярное выражение, чтобы найти любой из символов, поэтому вам нужно зациклить строку только один раз, а не один раз для каждого символа.:)

function findIndexes(find, str) {
  var output = {};
  for (var i = 0; i < find.length; i++) output[find[i]] = [];
  var r = new RegExp('.*?[' + find.join('') + ']', 'g');
  var ofs = -1;
  while ((x = r.exec(str)) != null) {
    ofs += x[0].length;
    output[x[0].substr(x[0].length-1,1)].push(ofs);
  }
  return output;
}

Answer 2

После синхронизации нескольких однопроходных алгоритмов и регулярного выражения Гуффы я закончил с этим:

function findIndexesMultiPass(str,find) {
  var x, output = {};

  for (var i = 0; i < find.length; i++) {
    output[find[i]] = [];
    x = 0;
    while ((x = str.indexOf(find[i], x)) > -1) {
      output[find[i]].push(x++);
    }
  }

  return output;
}

var searchString = "abcd abcd abcd";
var searchChars  = ['a', 'b'];
var result = findIndexesMultiPass(searchString, searchChars);
// {'a':[0,5,10], 'b':[1,6,11]}

Это оказалось довольно медленно:

function findIndexesOnePass(str,find) {
  var output = {};

  for (var i = 0; i < find.length; i++) {
    output[find[i]] = [];
  }

  for (var i = 0; i < str.length; i++) {
    var currentChar = str.charAt(i);
    if (output[currentChar] !== undefined) {
      output[currentChar].push(i);
    }
  }

  return output;
}

var searchString = "abcd abcd abcd";
var searchChars  = ['a', 'b'];
var result = findIndexesOnePass(searchString, searchChars);
// {'a':[0,5,10], 'b':[1,6,11]}

Грубые времена (индексы из 3 символов)

Google Chrome (Mac)
findIndexesMultiPass: 44ms
findIndexesOnePass: 799ms
findIndexesRegEx: 95ms

Safari
findIndexesMultiPass: 48ms
findIndexesOnePass: 325ms
findIndexesRegEx: 293ms

Firefox
findIndexesMultiPass: 56ms
findIndexesOnePass: 369ms
findIndexesRegEx: 786ms

Answer 3

Если предположить, что нужно искать несколько букв и много букв (то есть, небольшое количество букв, длинные строки), последняя является наиболее эффективной, поскольку вы только просматриваете строку один раз, а затем проверяете каждую букву.

Другой просматривает строку столько раз, сколько букв для поиска.