问题采访：从Mega的整数中查找中位数

有一个文件包含 10G /1000000000/ 整数的数量，请找到这些整数的中位数。 为此，你给了 2G 记忆。 任何人都可以用懂事吗？ 谢！
2021-03-20 添加评论
分享

没有找到相关结果

    已邀请:

    龙天

    赞同来自:

    创建一个包含的8字节龙数组 2^16 记录。 拍摄输入数字，幻灯片下降十六位并创建直方图。

    现在您在此直方图中指望，直到到达涵盖值中间点的单元格。

    再次进一步，忽略没有相同的上部位集的所有数字，并制作后一位。

    通过此直方图考虑，直到您到达覆盖中间的单元格 /总目录/ 价值观。

    现在你知道中位数
    O/n/

    时间我。
    O/1/

    空间 /在实践中 1 MB/.

    这是一个示例代码 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 bit 整数，您可以使用相同的策略 4 通道。
    2021-03-20 0 0
    分享

    二哥

    赞同来自:

    如果文件以文本格式为单位，则可以将其放入内存中，只要将内容转换为整数，因为存储在符号形式中的整数可以占用的空间，而不是存储在整数的形式中的空间根据整数的大小和文本文件的类型。 EDIT: 您已被最初的问题编辑; 现在我看到你不能在内存中读取它们，看

    如果您无法在内存中读取它们，那就是我提出的：

    了解您有多少整数。 你可能会从一开始就知道它。 如果没有，只需要一个通过文件。 假设它是。

    用你的 2G 记忆找到 x 最大的整数 /无论你有多合适/. 您可以通过文件，保持一致 x 一些排序列表中最大，摆动 rest 在案件的过程中。 现在你知道最大的整数 x-th. 您可以丢弃所有这些，除了最大的所有这些 x-th, 我名字 x1.

    再次通过，找到了以下内容 x 最大的整数

    较少的

    x1, 其中最小的是x2。

    我觉得你明白我克隆了什么。 几次通过后，您将阅读 /S/2/-th 最大的整数 /您需要追踪您找到了多少个整数/, 这是你的中位数。 如果一个 S 即使，你也会在中间平均两个。
    2021-03-20 0 0
    分享

    石油百科

    赞同来自:

    通过文件移动文件并找到整数的数量，以及最小和最大整数值。

    带上中间点 min 和 max 并得到 count, min 和 max 对于中点两侧的值 - 再次读取文件后。

    部分的数量 > count = > 中位于本节内。

    对该部分重复相同，考虑到尺寸 "左侧的部分" /易于维护/, 还有看 min = max.

    我相信它将适用于任意数量的部分。
    2021-03-20 0 0
    分享

    喜特乐

    赞同来自:

    履行
    http://en.wikipedia.org/wiki/External_sorting
    文件中的磁盘上的合并以对整数进行排序 /考虑到他们，如果尚未知道/.

    一旦文件进行排序，查找平均数 /奇怪的情况/ 或平均两个平均数字 /甚至是案例/ 在文件中获得中位数。

    所用的内存量可调，不依赖于源文件中的整数量。 其中一个外部排序注意事项是必须在磁盘上记录中间排序数据。

    指定的
    n

    = 源文件中的整数数：

    期间：
    O/nlogn/


    记忆：
    O/1/

    , 可调节的

    磁盘：
    O/n/
    2021-03-20 0 0
    分享

    快网

    赞同来自:

    检查Torben方法：
    http://ndevilla.free.fr/median/median/index.html
    . 它也有实现 C 在文档的底部。
    2021-03-20 0 0
    分享

    郭文康

    赞同来自:

    我最好的假设概率中位数是最快的。 食谱：

    采取下一组 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 &&="" +="" 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;
    

    
}


    opps似乎在谈论平均而不是中位数。 如果是这样，你需要一个中位数，而不是平均含义 - 忽略我的帖子。 在任何情况下，平均和中位数概念都非常接近。

    祝你好运。
    </array_size></time.h></stdio.h></stdlib.h>
    2021-03-20 0 0
    分享

    莫问

    赞同来自:

    我也问了同样的问题，我不能说一个确切的答案，所以在采访后，我看了几本关于接受采访的书，这就是我发现的，黑客攻击了编码的采访。

    示例：数字是随机生成并存储的数字 /扩展/ 大批。 如何
    你会跟随中位吗？

    我们的头脑风暴数据结构可能如下所示：

    * 已连接列表？ 最可能没有。 相关列表通常不受访问权限
    排序号码。

    * 大批？ 也许，但你已经有一个数组。 你可以以某种方式简化的元素吗？
    ? 这可能是昂贵的。 让我们推迟它并在必要时返回它。

    * 二叉树？ 这是可能的，因为二叉树应对订购。 事实上，如果二进制搜索树理想地平衡，顶部可以是中位数。 但要小心如果有偶数元素，中位数实际上是一种中等价值。
    两个中元素。 两个中间元素不能同时楼上。 这可能是一个可行的算法，但让我们回到他身边。

    * 桩？ 一堆在基本排序和跟踪最大值和最小值的跟踪中非常好。
    如果你有两堆，那么它真的很有趣，你可以跟踪大
    半个半元素。 大半半存储在我的地区
    更大一半的最小元素植根了。 较小的一半存储在
    最大桩，使得较小的一半的最大元素在根中。 现在，S.
    这些数据结构，您在根中有潜在的中位数元素。 如果一个
    堆不再具有相同的大小，可以快速 "rebalance" 堆，推动
    一个堆的元素并将其推到另一堆。

    请注意，您所做的越多，您的本能就越开发
    将应用数据结构。 您还将制定更细微的本能，即这些方法中的哪一种是最有用的。
    2021-03-20 0 0
    分享

    石油百科

    赞同来自:

    这是描述的算法 @Rex Kerrom实施了 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;
    
}


    可以找到一些测试示例和算法的更新
    https://github.com/Lowinator/F ... .java
    .
    2021-03-20 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    Copyright © 2023, All Rights Reserved