Интервью: найти медианную из числа целых чисел

Существует файл, содержащий число целых чисел 10G (1000000000), найдите медиану этих целых чисел. вам предоставляется 2G-память для этого. Может ли кто-нибудь придумать разумный способ? благодарю!

Ответ 1

Создайте массив из 8-байтных длин, содержащий 2 ^ 16 записей. Возьмите свои номера ввода, сдвиньте нижние шестнадцать бит и создайте гистограмму.

Теперь вы рассчитываете на этой гистограмме, пока не дойдете до бункера, который покрывает среднюю точку значений.

Пройдите снова, игнорируя все числа, которые не имеют того же набора верхних бит, и сделайте гистограмму нижних бит.

Подсчитайте эту гистограмму, пока не дойдете до бункера, который покрывает среднюю точку (всего списка).

Теперь вы знаете медианное, в O(n) время и O(1) пространство (на практике, менее 1 МБ).

Вот пример кода Scala, который делает это:

def medianFinder(numbers: Iterable[Int]) = {
  def midArgMid(a: Array[Long], mid: Long) = {
    val cuml = a.scanLeft(0L)(_ + _).drop(1)
    cuml.zipWithIndex.dropWhile(_._1 < mid).head
  }
  val topHistogram = new Array[Long](65536)
  var count = 0L
  numbers.foreach(number => {
    count += 1
    topHistogram(number>>>16) += 1
  })
  val (topCount,topIndex) = midArgMid(topHistogram, (count+1)/2)
  val botHistogram = new Array[Long](65536)
  numbers.foreach(number => {
    if ((number>>>16) == topIndex) botHistogram(number & 0xFFFF) += 1
  })
  val (botCount,botIndex) =
    midArgMid(botHistogram, (count+1)/2 - (topCount-topHistogram(topIndex)))
  (topIndex<<16) + botIndex
}

и здесь он работает с небольшим набором входных данных:

scala> medianFinder(List(1,123,12345,1234567,123456789))
res18: Int = 12345

Если у вас есть 64-битные целые числа, вы можете использовать ту же стратегию за 4 прохода.

Ответ 2

Вы можете использовать алгоритм Medians of Medians.

Ответ 3

Если файл находится в текстовом формате, вы можете поместить его в память, просто преобразуя его в целые числа, когда вы их читаете, поскольку целое число, сохраненное как символы, может занимать больше места, чем целое число, сохраненное как целое число, в зависимости от размера целых чисел и типа текстового файла. EDIT: вы отредактировали свой оригинальный вопрос; Теперь я вижу, что вы не можете прочитать их в памяти, см. Ниже.

Если вы не можете прочитать их в памяти, вот что я придумал:

Выясните, сколько целых чисел у вас есть. Вы можете знать это с самого начала. Если нет, то только один проход через файл. Пусть говорят, что это S.
Используйте 2G памяти, чтобы найти x самых больших целых чисел (сколько бы вы ни поместились). Вы можете сделать один проход через файл, сохраняя x наибольшим в сортированном списке какого-то рода, отбросив остальное, как вы идете. Теперь вы знаете x-мерное целое число. Вы можете отбросить все из них, кроме x-го самого большого, который я назову x1.
Пройдите еще один проход, найдя следующие x наибольших целых чисел меньше x1, наименьшее из которых - x2.
Я думаю, вы можете видеть, где я собираюсь с этим. После нескольких проходов вы прочитаете в (S/2) -ом наибольшем целое число (вам нужно будет отслеживать, сколько целых чисел вы нашли), что является вашим медианом. Если S четно, вы усредняете два посередине.

Ответ 4

Сделайте проход через файл и найдите количество целых чисел и минимальное и максимальное целочисленное значение.

Возьмите среднюю точку min и max и получите count, min и max для значений по обе стороны от средней точки - путем повторного чтения файла.

count count > count = > медиана лежит внутри этого раздела.

Повторите для раздела с учетом размера "разделов влево" (легко поддерживать), а также просмотра min = max.

Уверен, что это работает и для произвольного количества разделов.

Ответ 5

Сделайте на диске external mergesort в файле для сортировки целых чисел (считая их, если они еще не известны).
После сортировки файла найдите среднее число (нечетный случай) или усредните два средних числа (даже случай) в файле, чтобы получить медиану.

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

Учитывая n= количество целых чисел в исходном файле:

Продолжительность: O(nlogn)
Память: O(1), настраивается
Диск: O(n)

Ответ 6

Ознакомьтесь с методом Torben здесь: http://ndevilla.free.fr/median/median/index.html. Он также имеет реализацию в C в нижней части документа.

Ответ 7

Мое лучшее предположение, что вероятностная медиана медианов будет самой быстрой. Рецепт:

Возьмем следующий набор из N целых чисел (N должно быть достаточно большим, скажем, 1000 или 10000 элементов)
Затем вычислить медиану этих целых чисел и присвоить ее переменной X_new.
Если итерация не первая - вычислите медиану двух медианов:

X_global = (X_global + X_new)/2
Когда вы увидите, что X_global колеблется не так много - это означает, что вы нашли приблизительную медиану данных.

Но есть некоторые примечания:

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

EDIT: Я немного поиграл с этим алгоритмом, немного изменил идею - на каждой итерации мы должны суммировать X_new с уменьшающимся весом, например:

X_global = k * X_global + (1.-k) * X_new:

k из [0,5.. 1] и увеличивается на каждой итерации.

Точка - это сделать расчет медианной, чтобы быстро сходиться к некоторому числу в очень небольшом количестве итераций. Так что очень приблизительная медиана (с большой ошибкой) найдена между 100000000 элементами массива только в 252 итерациях!!!. Проверьте этот эксперимент C:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ARRAY_SIZE 100000000
#define RANGE_SIZE 1000

// probabilistic median of medians method
// should print 5000 as data average
// from ARRAY_SIZE of elements
int main (int argc, const char * argv[]) {
    int iter = 0;
    int X_global = 0;
    int X_new = 0;
    int i = 0;
    float dk = 0.002;
    float k = 0.5;
    srand(time(NULL));

    while (i<ARRAY_SIZE && k!=1.) {
        X_new=0;
        for (int j=i; j<i+RANGE_SIZE; j++) {
            X_new+=rand()%10000 + 1;
        }
        X_new/=RANGE_SIZE;

        if (iter>0) {
            k += dk;
            k = (k>1.)? 1.:k;
            X_global = k*X_global+(1.-k)*X_new;

        }
        else {
            X_global = X_new;
        }

        i+=RANGE_SIZE+1;
        iter++;
        printf("iter %d, median = %d \n",iter,X_global);
    }

    return 0;

}

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

Удачи.

Ответ 8

Вот алгоритм, описанный @Rex Kerr, реализованный в Java.

/**
 * Computes the median.
 * @param arr Array of strings, each element represents a distinct binary number and has the same number of bits (padded with leading zeroes if necessary)
 * @return the median (number of rank ceil((m+1)/2) ) of the array as a string
 */
static String computeMedian(String[] arr) {

    // rank of the median element
    int m = (int) Math.ceil((arr.length+1)/2.0);

    String bitMask = "";
    int zeroBin = 0;

    while (bitMask.length() < arr[0].length()) {

        // puts elements which conform to the bitMask into one of two buckets
        for (String curr : arr) {
            if (curr.startsWith(bitMask))
                if (curr.charAt(bitMask.length()) == '0')
                    zeroBin++;
        }

        // decides in which bucket the median is located
        if (zeroBin >= m)
            bitMask = bitMask.concat("0");
        else {
            m -= zeroBin;
            bitMask = bitMask.concat("1");
        }

        zeroBin = 0;
    }

    return bitMask;
}

Некоторые тестовые примеры и обновления алгоритма можно найти здесь.

Ответ 9

Мне также задавали тот же вопрос, и я не мог сказать точный ответ, поэтому после интервью я просмотрел несколько книг об интервью и вот что я нашел из книги интервью Cracking The Coding.

Пример: числа генерируются случайным образом и сохраняются в (расширяющийся) массив. Как бы вы сохранили след медианы?

Наш мозговой штурм структуры данных может выглядеть следующим образом:

• Связанный список? Возможно нет. Связанные списки, как правило, не очень хорошо подходят для доступа и сортировки номеров.

• массив? Возможно, но у вас уже есть массив. Не могли бы вы как-то сохранить элементы отсортированными? Это, вероятно, дорого. Позвольте удержаться от этого и вернуться к нему, если это необходимо.

• Бинарное дерево? Это возможно, поскольку двоичные деревья довольно хорошо справляются с упорядочением. На самом деле, если бинарное дерево поиска идеально сбалансировано, вершина может быть медиана. Но будьте осторожны - если есть четное количество элементов, медиана на самом деле является средним из двух средних элементов. Средние два элемента не могут быть оба наверху. Это, вероятно, работоспособный алгоритм, но давайте вернемся к нему.

• куча? Куча действительно хороша в базовом упорядочении и отслеживании макс и мин. Это действительно интересно - если бы у вас было две кучи, вы могли бы отслеживать большую половину и меньшую половину элементов. Большая половина хранится в минимальной куче, так что самый маленький элемент в большей половине находится в корне. Меньшая половина хранится в максимальной куче, так что самый большой элемент меньшей половины находится в корне. Теперь, с этими структурами данных, у вас есть потенциальные медианные элементы в корнях. Если кучи уже не одного размера, вы можете быстро "перебалансировать" кучи, вытолкнув элемент из одной кучи и вытолкнув его на другую.

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