Алгоритм Median of Medians не работает последовательно

Я реализовал алгоритм выбора/медианы медиан, используя в качестве ссылки следующее: http://www.ics.uci.edu/~eppstein/161/960130.html (ранее ссылка была здесь медиана медиан в Java).

Мой код работает для небольших массивов (~100) и даже работает для массивов размером 100001 http://pastebin.com/mwRc4Hig (ответ 5008), но затем не работает с входным массивом размером 10001 http://pastebin.com/YwVBmgDk (ответ 4960, мой код выводит 4958).

Обратите внимание, что правильные ответы для приведенных выше текстов эквивалентны сортировке массива и возврату элемента в массиве [массив.длина / 2], независимо от того, является ли размер массива четным или нечетным.

Я не уверен, как отладить эту проблему. Функциональность кажется произвольной, и я просто потерян. Ниже приведен мой код:

public class MedianOfMedians {

public static void main(String[] args) {
    MedianOfMedians mds = new MedianOfMedians();
    mds.run();
}

private void run() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] numArray = new int[n];
    for (int i = 0; i < n; i++) {
        numArray[i] = in.nextInt();
    }
    int median = select(numArray, numArray.length / 2);
    System.out.print(median);
}

private int select(int[] numArray, int k) {
    if (numArray.length <= 10) {
        int[] sorted = insertionSort(numArray);
        return sorted[k];
    }

    int divCount = (numArray.length % 5 == 0) ? numArray.length / 5 - 1 : numArray.length / 5;
    int[] medOfMed = new int[divCount + 1];
    int counter = 0;
    int[] subArray;

    while (counter <= divCount) {
        subArray = splitByFive(counter, divCount, numArray);
        medOfMed[counter] = select(subArray, subArray.length / 2);
        counter++;
    }

    int M = select(medOfMed, numArray.length / 10);

    List<Integer> lt = new ArrayList<>();
    List<Integer> eq = new ArrayList<>();
    List<Integer> gt = new ArrayList<>();
    for (int i : numArray) {
        if (i < M) {
            lt.add(i);
        } else if (i == M) {
            eq.add(i);
        } else {
            gt.add(i);
        }
    }
    if (k < lt.size()) {
        return select(createArray(lt), k);
    } else if (k > lt.size() + eq.size()) {
        return select(createArray(gt), k - lt.size() - eq.size());
    } else {
        return M;
    }
}

private int[] splitByFive(int splitIter, int divisions, int[] toSplit) {
    int numToCopy;
    if (splitIter == divisions) {
        numToCopy = toSplit.length - (5 * splitIter);
    } else {
        numToCopy = 5;
    }
    int[] subArray = new int[numToCopy];
    System.arraycopy(toSplit, splitIter * 5, subArray, 0, numToCopy);
    return subArray;
}

private int[] createArray(List<Integer> list) {
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        result[i] = list.get(i);
    }
    return result;
}

private int[] insertionSort(int[] numArray) {
    for (int i = 1; i < numArray.length; i++) {
        int j = i;
        while (j - 1 >= 0 && numArray[j] < numArray[j - 1]) {
            int temp = numArray[j];
            numArray[j] = numArray[j - 1];
            numArray[j - 1] = temp;
            j--;
        }
    }
    return numArray;
}
}

java arrays algorithm median-of-medians
person MMP    schedule 06.07.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

Если есть ввод, на котором алгоритм терпит неудачу (а он есть, как вы обнаружили), то существует наименьший такой ввод — и чем меньше этот ввод, тем легче понять, что происходит не так. Поскольку алгоритм является рекурсивным, у вас есть хороший способ изолировать первое место, где что-то пошло не так: вы можете проверить правильность результата, который вы собираетесь вернуть из select() (используя медленный, надежный метод, такой как копирование данных во временную память). буфер, сортируя его, а затем захватывая элемент, находящийся на полпути) просто перед возвратом значения. Сделать это будет намного проще, если вы перестроите функцию так, чтобы она использовала только один оператор return, например:

private int select(int[] numArray, int k) {
    int knownCorrectAnswer = selectSlowlyButDefinitelyCorrectly(numArray, k);
    int willReturn;
    if (numArray.length <= 10) {
        int[] sorted = insertionSort(numArray);
        willReturn = sorted[k];    // Just remember what we will return
    } else {    // Need to add else branch here now

        ...

        if (k < lt.size()) {
            willReturn = select(createArray(lt), k);
        } else if (k > lt.size() + eq.size()) {
            willReturn = select(createArray(gt), k - lt.size() - eq.size());
        } else {
            willReturn = M;
        }
    }    // End of inserted else branch

    if (willReturn == knownCorrectAnswer) {
        return willReturn;
    } else {
        yell("First problem occurs with numArray=<...> and k=<...>!");
    }
}

yell() должен распечатать весь экземпляр проблемы и остановить программу (например, сгенерировав исключение). Преимущество этой настройки заключается в том, что вы знаете, что когда вызывается yell(), каждый вызов select(), который уже завершен, был правильным, поскольку в противном случае yell() уже был бы вызван, а программа остановилась бы раньше. Таким образом, вывод, произведенный yell(), гарантированно будет первой (не обязательно самой маленькой, но часто и такой) подзадачей, в которой что-то пошло не так.

person j_random_hacker    schedule 06.07.2015