Есть ли более быстрый способ найти значение в многомерном массиве и вернуть все его индексы, чем для (for ())?

Question

Мне нужно найти значение двумерного массива и вернуть его индексы. Например, если мой искомый термин находится в массиве [i] [j], я хочу вернуть [i, j].

Естественно, я придумал это простое решение:

function find(str){
    for(let o = 0; o < array.length; o++){
        for(let k = 0; k < array[o].length; k++){
            if(array[o][k] == str){
                return [o, k];
            }
        }
    }
}

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

Я создал простой полный пример, включающий «тест»:

// setup to hide foo in an array
var array = [];
for(let i = 0; i < 100; i++){
    array.push([])
    for(let j = 0; j < 100; j++){
        if(i == 99 && j == 99) array[i].push("foo"); // intentionally hiding the searched term at the worst-case position for the algorithm of find()
        else array[i].push("bar");
    }
}

// function to find foo
function find(str){
    for(let o = 0; o < array.length; o++){
        for(let k = 0; k < array[o].length; k++){
            if(array[o][k] == str){
                return [o, k];
            }
        }
    }
}

// lets say we need to find foo 200 times
var a = window.performance.now();
for(let i = 0; i < 200; i++){
    console.log(i, find("foo")); // if you're happy and you know it, tell us what you found
}
var b = window.performance.now();

// print performance result
$('body').html((b-a) + " ms");

JSfiddle для эталонного примера: http://jsfiddle.net/3t0db1cq/11/

(примечание: в этом тестовом примере я произвел поиск 'foo' 200 раз, поэтому вы можете спросить, почему я не просто кеширую его. На самом деле я буду искать разные термины, поэтому кэширование едва повысит производительность. Также я намеренно поместил искомый термин в наихудшую позицию массива для этого теста)

Можете ли вы помочь мне найти лучший алгоритм для find()? Чтобы быть справедливым для теста производительности, переместите искомый термин в наихудшую позицию в массиве для вашего алгоритма, если вы хотите сравнить результаты.

(для этого предназначены веб-сайты, поэтому все обычные браузеры должны его поддерживать)

Answer 1

Если вы знакомы с SQL, один из способов сделать это - использовать sqllite. Это очень простой способ запустить sql в браузере.

https://www.tutorialspoint.com/html5/html5_web_sql.htm

К сожалению, это поддерживается не во всех браузерах, поэтому вам нужно иметь общее представление о вашей аудитории.

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

// setup to hide foo in an array
var array = [];
for(let i = 0; i < 100; i++){
    array.push([])
    for(let j = 0; j < 100; j++){
        if(i == 99 && j == 99) array[i].push("foo"); // intentionally hiding the searched term at the worst-case position for the algorithm of find()
        else array[i].push("bar");
    }
}

//Create your reverse mapped array. This only runs once at startup, but now allows you to 
function buildReverse(arr) {
    var reverseArr = {};
    for(let o = 0; o < arr.length; o++){
        for(let k = 0; k < arr[o].length; k++){
          reverseArr[arr[o][k]] = [o, k];
        }
    }
  return reverseArr
}
var reverseArr = buildReverse(array);
function find(str){
    if (reverseArr[str] != undefined) {
      return reverseArr[str]; 
      // or 
      //return [reverseArr[str][0], reverseArr[str][1]]
      //, etc...
    }
    return "";
}

// lets say we need to find foo 200 times
var a = window.performance.now();
for(let i = 0; i < 200; i++){
    console.log(i, find("foo")); // if you're happy and you know it, tell us what you found
}
var b = window.performance.now();

// print performance result
$('body').html((b-a) + " ms");

Answer 2

Мне кажется, что вы сопоставляете ключ (пару целых чисел) со строковым значением и хотите вернуть ключ для этого значения.

Поскольку вы используете массив, каждая операция поиска всегда O (n ^ 2) в худшем случае, не существует «умного» способа использования этой структуры данных

Как сказал @Richrd, вы можете построить обратное отображение из строковых значений в пару целых чисел и искать их. Простой способ - использовать javascript Map () (хэш-карту). Хотя вы можете захотеть взглянуть на реализацию trie для отображения строки в целое число.

Но возникает вопрос: если вы выполняете много таких обратных поисков, то зачем сначала хранить эти данные в виде 2d-массива строк? Вы могли бы сэкономить больше времени, сохранив эти данные в виде карты строк в целые числа.