Question d'entretien: trouver la médiane à partir d'un nombre méga d'entiers

Question

Il y a un fichier qui contient 10G (1000000000) nombre d'entiers, veuillez trouver la médiane de ces entiers. vous disposez d'une mémoire 2G pour ce faire. Quelqu'un peut-il trouver un moyen raisonnable? Merci!

Answer 1

Créer un tableau de 8 octets aspire à ce que a 2^16 entrées. Prenez votre saisie de nombres, de changement sur le fond seize bits, et de créer un histogramme.

Maintenant, vous comptez, dans l'histogramme jusqu'à ce que vous atteignez le bin qui couvre le milieu de la valeurs.

Passer à nouveau, en ignorant tous les nombres qui n'ont pas le même nombre de bits, et de faire un histogramme de bas de bits.

Comptez, par le biais de l'histogramme jusqu'à ce que vous atteignez le bin qui couvre le milieu de la (l'ensemble de la liste de valeurs.

Maintenant, vous savez la médiane, en O(n) du temps et O(1) de l'espace (dans la pratique, de moins de 1 MO).

Voici quelques exemples de Scala code qui fait cela:

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
}

et ici, c'est de travailler sur un petit ensemble de données d'entrée:

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

Si vous avez des entiers 64 bits stockés, vous pouvez utiliser la même stratégie en 4 passages à la place.

Answer 2

Vous pouvez utiliser l' algorithme Medians of Medians .

Answer 3

Si le fichier est au format texte, vous pouvez être en mesure de l'adapter en mémoire seulement par la conversion de choses à des nombres entiers comme vous le lisez dans, depuis un entier stocké en tant que personnages peuvent prendre plus de place qu'un entier stocké sous forme d'un nombre entier en fonction de la taille des entiers et le type de fichier texte. EDIT: Vous avez modifié votre question de départ; je vois maintenant que vous ne pouvez pas lire dans la mémoire, voir ci-dessous.

Si vous ne pouvez pas lire dans la mémoire, c'est ce que je suis venu avec:

1. Figure combien de nombres entiers que vous avez. Vous savez peut-être ce dès le début. Si non, alors il ne prend qu'un seul passage dans le fichier. Disons que c'est S.

2. Utilisez votre 2G de mémoire pour trouver le x plus grand des entiers (cependant beaucoup que vous pouvez adapter). Vous pouvez faire un passage dans le fichier, en gardant le x est plus grand dans une liste triée d'une certaine sorte, en rejetant le reste, comme vous allez. Maintenant, vous savez la x-ième plus grand entier. Vous pouvez jeter tous ces sauf pour la x-ième plus grande, que je vais appeler x1.

3. Faire un autre passage, la recherche de la prochaine x plus grand des entiers de moins de x1, le moindre de ce qui est x2.

4. Je pense que vous voyez où je veux en venir. Après quelques passes, vous avez lu dans le (S/2)-ième plus grand entier (vous devez garder une trace de combien d'entiers que vous avez trouvé), ce qui est votre médiane. Si S est même alors, vous aurez la moyenne de deux par le milieu.

Answer 4

Faire une passe dans le fichier, et de trouver le comte d'entiers et le minimum et le maximum de valeur de type entier.

Prendre le milieu de min et max, et obtenir count, min et max pour les valeurs de chaque côté du milieu - une fois de plus la lecture du fichier.

partition count > count => médiane se situe à l'intérieur de cette partition.

Répétez l'opération pour la partition, en tenant compte de la taille de la partition vers la gauche' (facile à maintenir), et aussi regarder pour min = max.

Suis sûr que cela avait du travail pour un nombre arbitraire de partitions ainsi.

Answer 5

1. Faire un disque externe mergesort sur le fichier pour trier les entiers (et les compte si ce n'est pas déjà connue).
2. Une fois que le fichier est trié, cherchent à le nombre moyen (cas particulier), ou la moyenne de deux nombre du milieu (même affaire) dans le fichier afin d'obtenir la médiane.

La quantité de mémoire utilisée est réglable et affectée par le nombre d'entiers dans le fichier d'origine. Une mise en garde de l'externe, le tri est que l'intermédiaire de tri des données doivent être écrites sur le disque.

Compte tenu de n = nombre d'entiers dans le fichier d'origine:

• Temps d'exécution: O(nlogn)
• Mémoire: O(1), réglable
• Disque: O(n)