Interview de questions: trouver la médiane d'un méga nombre d'entiers

Il y a un fichier qui contient 10G /1000000000/ Le nombre d'entiers, veuillez trouver la médiane de ces entiers. Pour cela, vous donnez 2G Mémoire. Quelqu'un peut-il venir avec une manière raisonnable? Remercier!
Invité:

Blanche

Confirmation de:

Créer un tableau de 8ges longs contenant 2^16 enregistrements. Prenez les numéros d'entrée, faites glisser les 20 bits inférieurs et créez un histogramme.

Maintenant, vous comptez dans cet histogramme jusqu'à ce que vous atteigniez la cellule qui couvre le point central des valeurs.

Allez encore en ignorant tous les chiffres qui n'ont pas le même ensemble de bits supérieurs et de faire ces derniers bits.

Considérer à travers cet histogramme jusqu'à atteindre la cellule qui couvre le milieu /Liste totale/ valeurs.

Maintenant, vous savez médian dans
O/n/

Temps i.
O/1/

espacer /En pratique sous 1 MB/.

Voici un exemple de code Scala, Ce qui fait:


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 donc cela fonctionne sur un petit ensemble de données d'entrée:


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


Si vous êtes stocké 64 bit entiers, vous pouvez utiliser la même stratégie pour 4 Passage.

Blanche

Confirmation de:

Si le fichier est dans un format de texte, vous pouvez la mettre en mémoire, simplement convertir les choses en entiers tels qu'ils lisent, car l'entier stocké sous forme de symboles peut occuper plus d'espace qu'un entier stocké sous la forme d'un entier, dans En fonction de la taille des entiers et du type de fichier texte. EDIT: Vous avez été modifié par votre question initiale; Maintenant, je vois que vous ne pouvez pas les lire en mémoire, voir

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

Découvrez combien d'entiers vous avez. Vous le savez peut-être dès le début. Sinon, un seul passage à travers le fichier est requis. Supposons que c'est avec.

Utilise ton 2G mémoire à trouver x les plus gros entiers /Peu importe combien vous en conviennent/. Vous pouvez faire un passage dans le fichier, en gardant x la plus grande dans une liste triée, se balançant rest Au cours de l'affaire. Maintenant, vous connaissez le plus grand nombre entier x-th. Vous pouvez vous écarter tout cela, à l'exception du plus grand x-th, Que je nomme x1.

Faire un autre passage, ayant trouvé ce qui suit x les plus gros entiers

moins

x1, Le plus petit est x2.

Je pense que vous comprenez ce que je suis clone. Après plusieurs passes, vous allez lire dans /S/2/-th le plus grand entier /Vous devrez suivre le nombre d'entiers que vous avez trouvés/, Quelle est votre médiane. Si un S Même, alors vous serez en moyenne deux au milieu.

Catherine

Confirmation de:

Déplacez le fichier dans le fichier et trouvez le nombre d'entiers, ainsi que la valeur entière minimale et maximale.

Prendre le point d'intermédiaire min et max Et obtenir count, min et max Pour les valeurs des deux côtés du point milieu - Après avoir lu le fichier à nouveau.

Nombre de sections > count = > Médian se trouve à l'intérieur de cette section.

Répétez la même chose pour la section, en tenant compte de la taille "sections de la gauche" /facile à maintenir/, et aussi regarder min = max.

Je suis sûr que cela fonctionnera pour un nombre arbitraire de sections.

Alice

Confirmation de:

Effectuer
http://en.wikipedia.org/wiki/External_sorting
Fusions sur le disque dans le fichier pour trier les entiers /Considérant qu'ils ne sont pas encore connus/.

Une fois le fichier trié, trouvez le numéro moyen /cas étrange/ Ou en moyenne deux nombres moyens /même cas/ Dans le dossier pour obtenir une médiane.

La quantité de mémoire utilisée est réglable et ne dépend pas de la quantité d'entiers dans le fichier source. L'une des précautions de tri externes est que les données de tri intermédiaires doivent être enregistrées sur le disque.

Ensemble
n

= Nombre d'entiers dans le fichier source:

Durée:
O/nlogn/


Mémoire:
O/1/

, Ajustable

Disque:
O/n/

Agathe

Confirmation de:

Vérifiez la méthode Torben ici:
http://ndevilla.free.fr/median/median/index.html
. Il a aussi des implémentations dans C Au bas du document.

Hannah

Confirmation de:

Ma meilleure hypothèse selon laquelle la médiane médiane probabiliste sera la plus rapide. Recette:

Prendre le prochain ensemble de N entiers /N Doit être assez grand, disons, 1000 ou 10000 Éléments/

Puis calculez la médiane de ces entiers et attribuez-la une variable X_new.

Si l'itération n'est pas la première - Calculer la médiane de deux médiane:

X_global = /X_global + X_new/ / 2


Quand tu vois ça X_global hésité pas fort - Cela signifie que vous avez trouvé une médiane de données approximative.

Mais il y a quelques notes :

La question se pose, que l'erreur médiane soit autorisée ou non.

Les entiers doivent être distribués de manière aléatoire uniformément au travail

EDIT:

J'ai joué un peu avec cet algorithme, un peu changé l'idée - À chaque itération, nous devons résumer X_new Avec une diminution du poids, par exemple:

X_global = k*X_global + /1. - k/*X_new :

k de [0.5 .. 1.], et augmente à chaque itération.

L'essence est de rendre le calcul de la médiane de convertir rapidement à un certain nombre pour un très petit nombre d'itérations. Si très approximatif médiane /Avec une grosse erreur/ situé entre 100000000 Éléments de tableau

seul 252 itération !

!! Vérifiez cette expérience 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 &&="" +="" 1;="" =range_size;="" for="" if="" int="" iter="" j="i;" j++="" j<i+range_size;="" k!="1./" x_new="" x_new+="rand//000" {="" }="">0/ {
k += dk;
k = /k&gt;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;

}


Les OPPP semblent parler de la moyenne, pas sur la médiane. Si oui, et vous avez besoin d'une médiane et non de signification moyenne - ignorer mon post. En tout état de cause, les concepts moyens et médians sont très proches.

Bonne chance.
</array_size></time.h></stdio.h></stdlib.h>

Emilie

Confirmation de:

J'ai également posé la même question et je ne pouvais pas dire une réponse exacte, alors après l'entrevue, j'ai examiné plusieurs livres lors d'une interview, et c'est ce que j'ai trouvé, piratage du livre une entrevue avec codage.

Exemple: Les chiffres sont générés et stockés au hasard /expansion/ déployer. comment
Souhaitez-vous suivre la médiane?

Notre structure de données de brainstorming peut ressembler à ceci:

* Liste connectée? Le plus probablement pas. Les listes associées ne sont généralement pas bien adaptées à l'accès et
Numéros de tri.

* Déployer? Peut-être que, mais vous avez déjà un tableau. Pourriez-vous en quelque sorte rationaliser les éléments
? Ceci est probablement cher. Reportons-le et revenons-y, si nécessaire.

* Arbre binaire? C'est possible car les arbres binaires font face à la commande. En fait, si l'arbre de recherche binaire est parfaitement équilibré, le sommet peut être médian. Mais soyez prudent s'il y a un nombre pair d'éléments, la médiane est en réalité une valeur moyenne.
Deux éléments moyens. Deux éléments moyens ne peuvent pas être simultanément à l'étage. C'est probablement un algorithme fonctionnel, mais revenons à lui.

* Pile? Un groupe est vraiment bon dans la commande de base et le suivi des valeurs maximales et minimales.
C'est vraiment intéressant si vous aviez deux tas, vous pourriez suivre grand
Demi et demi-éléments. La grande moitié est stockée dans un minecraft, telle
Que le plus petit élément de la plus grande moitié est enraciné. La moitié plus petite est stockée dans
La pile maximale, de telle sorte que le plus gros élément d'une moitié plus petite est à la racine. Maintenant, S.
Ces structures de données, vous avez des éléments médians potentiels dans les racines. Si un
Les tas n'ont plus la même taille, vous pouvez rapidement "rebalance" Tas, poussant
Élément d'un tas et en poussant à un autre.

Veuillez noter que plus vous faites de problèmes, plus votre instinct a développé votre instinct sur lequel
La structure de données sera appliquée. Vous développerez également un instinct plus subtil sur lequel de ces approches est la plus utile.

Blanche

Confirmation de:

Voici l'algorithme décrit @Rex Kerrom implémenté dans 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;
}


Certains exemples de test et mises à jour de l'algorithme peuvent être trouvés
https://github.com/Lowinator/F ... .java
.

Pour répondre aux questions, connectez-vous ou registre