Найти subtuple в большую коллекцию?


У меня есть плоский массив < 1000 элементов, и мне нужно найти индексы меньшего кортеж/массив в массиве. Кортеж может быть различной длины (обычно между 2 и 5 пунктов, порядок важен).

Это моя первоначальная наивная реализация. Моими главными задачами являются:

  1. Это похоже на проблему в CS 101, так что я уверен, что я преувеличиваю.
  2. Удобочитаемость. Я могу разорвать этот вниз на более мелкие методы, но по сути это служебная функция в гораздо больших класса. Я думаю, я мог бы извлечь его в своем классе, но это чувствует, как Overkill, а также. Как есть, это слишком долго для меня, чтобы понять все это за один проход.

public int[] findIndices(final Object[] toSearch, final Object[] toFind) 
{
    Object first = toFind[0];

    List<Integer> possibleStartIndices = new ArrayList<Integer>();
    int keyListSize = toFind.length;
    for (int i = 0; i <= toSearch.length - keyListSize; i++) 
    {
        if (first.equals(toSearch[i])) 
        {
            possibleStartIndices.add(i);
        }
    }

    int[] indices = new int[0];
    for (int startIndex : possibleStartIndices) 
    {
        int endIndex = startIndex + keyListSize;
        Object[] possibleMatch = Arrays.copyOfRange(toSearch, startIndex, endIndex);
        if (Arrays.equals(toFind, possibleMatch)) {
            indices = toIndexArray(startIndex, endIndex);
            break;
        }
    }
    return indices;
}

private int[] toIndexArray(final int startIndex, final int endIndex) 
{
    int[] indices = new int[endIndex - startIndex];
    for (int i = 0; i < indices.length; i++)
        indices[i] = startIndex + i;

    return indices;
}


511
14
задан 27 января 2011 в 03:01 Источник Поделиться
Комментарии
4 ответа

Вот решение за o(Миннесота). Учитывая, что сена-это около 1000 в длину и иглы 5 или меньше, самый простой код, чтобы сделать поиск является, вероятно, лучшим. Но если проверка на равенство-это дорого, есть вещи, которые мы можем сделать, чтобы смягчить, что, хотя я не уверен, что переход на КМП или БМ поможет так много учитывая, что мы имеем дело с объектом здесь.

// assumes no null entries
// returns starting index of first occurrence of needle within haystack or -1
public int indexOf(final Object[] haystack, final Object[] needle)
{
foo: for (int a = 0; a < haystack.length - needle.length; a++) {
for (int b = 0; b < needle.length; b++) {
if (!haystack[a+b].equals(needle[b])) continue foo;
}
return a;
}
return -1;
}

5
ответ дан 27 января 2011 в 09:01 Источник Поделиться

Как быстрая подсказка, я бы посоветовал вам пропустить этап поиска возможных индексов начала.

Вместо этого, как вы уже перебирать весь список, чтобы найти возможные индексы пуск, тогда почему бы вам не проверить, что индекс сразу же, когда вы найти его? Будет что-то вроде:

public int[] findIndices(final Object[] toSearch, final Object[] toFind) 
{
Object first = toFind[0];

int keyListSize = toFind.length;
for (int startIndex = 0; startIndex <= toSearch.length - keyListSize; startIndex++)
{
if (first.equals(toSearch[startIndex]))
{
int endIndex = startIndex + keyListSize;
Object[] possibleMatch = Arrays.copyOfRange(toSearch, startIndex, endIndex);
if (Arrays.equals(toFind, possibleMatch)) {
return toIndexArray(startIndex, endIndex);
}
}
}

return new int[0];
}

4
ответ дан 27 января 2011 в 03:01 Источник Поделиться

Редактировать исходный код является неправильным. Добавлено лучше ниже.

Нечто подобное мог бы сделать это в один проход (я думаю - я не проверил его до смерти). Обратите внимание, что я только возвращает первый индекс, а затем может быть легко вычислен просто делаю новый массив, я, я+1, ..., я+н-1 и т. д. Проще (и медленнее), чем Бойера Мура, но по-прежнему О(Н):

public static <T> int indexOf(final T[] target, final T[] candidate) {

for (int t = 0, i = 0; i < target.length; i++) {
if (target[i].equals(candidate[t])) {
t++;
if (t == candidate.length) {
return i-t+1;
}
} else {
t = 0;
}
}

return -1;
}

Редактировать: это должно работать лучше, нет? Она не так чиста и проста, но теперь я более уверен, что это на самом деле правильно. Что происходит, когда мы терпим неудачу, мы BackTrack и перезагрузка.

public static <T> int indexOf(final T[] target, final T[] candidate) {
int t = 0, i = 0;
while (i < target.length)
{
if (target[i].equals(candidate[t])) {
t++;
if (t == candidate.length) {
return i-t+1;
}
} else {
i -= t;
t = 0;
}
i++;
}
return -1;
}

3
ответ дан 27 января 2011 в 06:01 Источник Поделиться

Для <1000 товаров, если проверять каждый пункт стоит непомерно дорого, я бы сказал, что Пабло имеет право идея просто проверяю на первом проходе. Это устраняет о(N) из алгоритма. Для большего числа, или где проверяют каждый товар подороже, что-то более сложное, вроде Бойера-Мура алгоритм, как mtnygard стиля предполагает может быть уместным.

1
ответ дан 27 января 2011 в 05:01 Источник Поделиться