Какой самый быстрый способ найти массив в другом массиве в Java?

Question

Есть ли эквивалент String.indexOf () для массивов? Если нет, есть ли более быстрый способ найти массив внутри другого, кроме линейного поиска?

Answer 1

Независимо от элементов ваших массивов, я считаю, что это мало чем отличается от проблемы поиска по строкам.

В этой статье содержится общее введение в различные известные алгоритмы.

Рабин-Карп и KMP могут быть вашими лучшими вариантами.

Вы должны быть в состоянии найти реализации этих алгоритмов на Java и адаптировать их к вашей проблеме..

Answer 2

List<Object> list = Arrays.asList(myArray);
Collections.sort(list);
int index = Collections.binarySearch(list, find);

OR

public static int indexOf(Object[][] array, Object[] find){
  for (int i = 0; i < array.length(); i ++){
    if (Arrays.equals(array[i], find)){
      return i;
    }
  }
  return -1;
}

OR

public static int indexOf(Object[] array, Object find){
  for (int i = 0; i < array.length(); i ++){
    if (array[i].equals(find)){
      return i;
    }
  }
  return -1;
}

OR

Object[] array = ...
int index = Arrays.asList(array).indexOf(find);

Answer 3

Насколько я знаю, НЕТ способа найти массив внутри другого без линейного поиска. String.indexOf использует линейный поиск, прямо внутри библиотеки.

Вы должны написать небольшую библиотеку indexOf, которая будет принимать два массива, тогда у вас будет код, похожий на indexOf.

Но как бы вы это ни делали, это линейный поиск под одеялом.

редактирование:

Посмотрев на ответ @ ahmadabolkader, я как бы забрал это. Хотя это все еще линейный поиск, это не так просто, как просто «реализовать его», если вы не ограничены достаточно маленькими наборами тестов / результатами.

Проблема возникает, когда вы хотите посмотреть, вписывается ли ... aaaaaaaaaaaaaaaaaab в строку (x1000000) ... aaaaaaaaab (другими словами, строки, которые обычно совпадают с большинством мест в строке поиска).

Я думал, что, как только вы найдете совпадение с первым персонажем, вы просто проверите все последующие символы один на один, но это качество будет ужасно ухудшаться, когда большинство символов совпадают большую часть времени. В ответе @ a12r был метод скользящего хэша, который звучал намного лучше, если это реальная проблема, а не просто задание.

Я просто собираюсь проголосовать за ответ @ a12r из-за этих потрясающих ссылок на Википедию.

Answer 4

Вы имеете в виду, у вас есть массив, элементы которого также являются элементами массива? Если это так и элементы отсортированы, вы можете использовать binarysearch из java.util.Arrays

Answer 5

Короткий ответ - нет - более быстрого способа найти массив в массиве с помощью некоторой существующей конструкции в Java. Исходя из того, что вы описали, рассмотрите возможность создания HashSet массивов вместо массива массивов.

Answer 6

Обычно в java вы находите вещи в коллекциях

• поместите их в хэш-карту (словарь) и найдите их по хешу.
• перебрать каждый объект и проверить его равенство

(1) не будет работать для вас, потому что хеш объекта массива не скажет вам, что содержимое одинаково. Вы можете написать какую-нибудь оболочку, которая создаст хеш-код на основе содержимого (вам также нужно убедиться, что возвращаемые значения соответствуют этому).

(2) также потребует немного работы, потому что равенство объектов для массивов только проверит, что объекты одинаковы. Вам нужно было обернуть массивы тестом содержимого.

Так что, по сути, нет, если вы сами не напишите.