在1 MB RAM中排序100万个8位数字

问题描述 投票:634回答:36

我有一台1 MB RAM的计算机,没有其他本地存储。我必须使用它通过TCP连接接受100万个8位十进制数,对它们进行排序,然后通过另一个TCP连接发送排序列表。

数字列表可能包含重复项,我不能丢弃。代码将放在ROM中,因此我不需要从1 MB中减去代码的大小。我已经有驱动以太网端口和处理TCP / IP连接的代码,它的状态数据需要2 KB,包括1 KB缓冲区,代码将通过该缓冲区读写数据。有这个问题的解决方案吗?

问答来源:

slashdot.org

cleaton.net

algorithm sorting embedded ram
36个回答
427
投票

到目前为止,这里没有提到一个相当偷偷摸摸的伎俩。我们假设您没有额外的方法来存储数据,但这并不严格。

解决问题的一种方法是执行以下可怕的操作,在任何情况下都不应该尝试任何人:使用网络流量来存储数据。不,我不是指NAS。

您可以通过以下方式仅使用几个字节的RAM对数字进行排序:

  • 首先取两个变量:COUNTERVALUE
  • 首先将所有寄存器设置为0;
  • 每当你收到一个整数I,增加COUNTER并将VALUE设置为max(VALUE, I);
  • 然后将数据集为I的ICMP echo请求包发送给路由器。擦除我并重复。
  • 每次收到返回的ICMP数据包时,只需提取整数并在另一个echo请求中再次将其发回。这会产生大量的ICMP请求,它们向前和向后扫描包含整数。

一旦COUNTER到达1000000,您就会将所有值存储在不间断的ICMP请求流中,而VALUE现在包含最大整数。选择一些threshold T >> 1000000。将COUNTER设置为零。每次收到ICMP数据包时,增加COUNTER并在另一个echo请求中发送包含的整数I,除非I=VALUE,在这种情况下将其发送到排序整数的目标。一旦COUNTER=TVALUE减少1,将COUNTER重置为零并重复。一旦VALUE达到零,你应该按照从大到小的顺序传输所有整数到目的地,并且只使用大约47位的RAM用于两个持久变量(以及临时值所需的任何小量)。

我知道这很可怕,我知道可能存在各种各样的实际问题,但我认为这可能会让你们中的一些人大笑或者至少让你们感到恐惧。


10
投票

所有可能的输入都有一个解决这个问题的方法。作弊。

  1. 通过TCP读取m值,其中m接近可以在内存中排序的最大值,可能是n / 4。
  2. 对250,000(左右)数字进行排序并输出。
  3. 重复其他3个季度。
  4. 让接收器合并它在处理它们时收到的4个数字列表。 (它比使用单个列表慢得多。)

7
投票

我会尝试一下000000000000000000000000000 00111 1100100 ^^^^^^^^^^^^^ a million times 27 + 1,000,000 * (5+7) bits = ~ 427k 。如果可以将数据存储在树中,则可以执行有序遍历来传输数据。

我不确定你能把它装到1MB,但我认为值得一试。


7
投票

你用的是什么类型的电脑?它可能没有任何其他“正常”本地存储,但它有没有视频RAM,例如?每像素1百万像素×32位(比如说)非常接近您所需的数据输入大小。

(我在很大程度上要求记住旧的Radix Tree,如果您选择低分辨率或低色深度屏幕模式,它可以“借用”VRAM来扩展可用的系统RAM!)。这在只有几MB普通RAM的机器上非常有用。


6
投票

基数树表示将接近处理此问题,因为基数树利用“前缀压缩”。但是很难想象一个基数树表示可以代表一个字节中的单个节点 - 两个可能是极限。

但是,无论数据如何表示,一旦它被排序,它可以以前缀压缩形式存储,其中数字10,11和12将由例如001b,001b,001b表示,表示增量为1从前一个号码。那么,10101b可能代表5,1101001b的增量,增量为9,等等。


6
投票

在10 ^ 8的范围内有10 ^ 6个值,因此平均每百个代码点有一个值。存储从第N个点到第(N + 1)个的距离。重复值跳过0.这意味着跳过需要平均不到7位才能存储,因此其中有数百万将很高兴地适应我们的800万位存储。

需要将这些跳过编码为比特流,例如通过霍夫曼编码。插入是通过迭代比特流并在新值之后重写。通过迭代并写出隐含值来输出。实际上,它可能希望完成,例如,10 ^ 4个列表,每个列表覆盖10 ^ 4个代码点(平均值为100个值)。

通过假设跳过的长度上的泊松分布(均值=方差= 100),可以先验地建立用于随机数据的良好霍夫曼树,但是可以在输入上保持真实的统计数据并用于生成用于处理的最优树。病理病例。


5
投票

我有一台带有1M RAM的计算机,没有其他本地存储

另一种欺骗方式:您可以使用非本地(联网)存储(您的问题不排除这一点)并调用可以使用简单的基于磁盘的mergesort的网络服务(或者只是足够的RAM来排序内存,因为您只需要接受1M的数字),而不需要已经给出的(无可否认的非常巧妙)解决方案。

这可能是作弊,但目前尚不清楚你是在寻找现实世界问题的解决方案,还是一个引起规则弯曲的谜题......如果是后者,那么简单的作弊可能比复杂的结果更好但“真正的”解决方案(正如其他人所指出的那样,只适用于可压缩输入)。


5
投票

我认为解决方案是结合视频编码技术,即离散余弦变换。在数字视频中,而不是将视频的亮度或颜色改变为常规值,例如110 112 115 116,每个都从最后一个中减去(类似于行程长度编码)。 110 112 115 116变为110 2 3 1.值2 3 1比原件需要更少的位。

因此,假设我们在输入值到达套接字时创建一个输入值列表。我们存储在每个元素中,而不是值,而是存储在它之前的元素的偏移量。我们按照我们的方式排序,因此抵消只会是积极的。但是偏移量可以是8位十进制数,这适合3个字节。每个元素不能是3个字节,所以我们需要打包这些。我们可以使用每个字节的最高位作为“继续位”,表示下一个字节是数字的一部分,每个字节的低7位需要组合。零对重复有效。

当列表填满时,数字应该更加接近,这意味着平均只有1个字节用于确定到下一个值的距离。如果方便的话,7位值和1位偏移量,但是对于“继续”值,可能存在需要少于8位的最佳位置。

无论如何,我做了一些实验。我使用随机数生成器,我可以将一百万个排序的8位十进制数放入大约1279000字节。每个数字之间的平均空间始终为99 ...

Acorn RISC PC

4
投票

在我们拥有所有数字之前,我们可以使用网络堆栈按排序顺序发送数字。如果发送1M数据,TCP / IP会将其分解为1500字节数据包并将其流式传输到目标。每个数据包将被赋予序列号。

我们可以手工完成。在我们填充RAM之前,我们可以对我们的内容进行排序并将列表发送到目标,但在每个数字周围留下序列中的漏洞。然后使用序列中的那些孔以相同的方式处理第二个1/2的数字。

远端的网络堆栈将按顺序组合生成的数据流,然后再将其交付给应用程序。

它正在使用网络执行合并排序。这是一个彻头彻尾的黑客,但我受到了之前列出的其他网络黑客的启发。


4
投票

来自HN线程的谷歌(糟糕)方法。存储RLE风格的计数。

你的初始数据结构是'99999999:0'(全零,没有看到任何数字),然后让你说你看到数字3,866,344所以你的数据结构变为'3866343:0,1:1,96133654:0',因为你可以看到数字将始终在零位数和“1”位数之间交替,因此您可以假设奇数代表0位而偶数代表1位。这变成了(3866343,1,96133654)

他们的问题似乎没有覆盖重复,但让我们说他们使用“0:1”来复制。

大问题#1:1M整数的插入需要很长时间。

大问题#2:像所有普通的delta编码解决方案一样,某些发行版不能以这种方式覆盖。例如,1m整数,距离为0:99(例如每个+99)。现在想一想,但随机距离在0:99范围内。 (注:99999999/1000000 = 99.99)

谷歌的做法既不值得(慢)又不正确。但为了防守,他们的问题可能略有不同。


3
投票

为了表示排序的数组,可以只存储第一个元素和相邻元素之间的差异。通过这种方式,我们关注编码10 ^ 6个元素,这些元素总和可以达到最多10 ^ 8。让我们称之为D.要编码D的元素,可以使用public class Test { public static void main(String[] args) throws IOException { // 1 million values int[] values = new int[1000000]; // create random values up to 8 digits lrong Random random = new Random(); for (int x=0;x<values.length;x++) { values[x] = random.nextInt(100000000); } Arrays.sort(values); ByteArrayOutputStream baos = new ByteArrayOutputStream(); int av = 0; writeCompact(baos, values[0]); // first value for (int x=1;x<values.length;x++) { int v = values[x] - values[x-1]; // difference av += v; System.out.println(values[x] + " diff " + v); writeCompact(baos, v); } System.out.println("Average offset " + (av/values.length)); System.out.println("Fits in " + baos.toByteArray().length); } public static void writeCompact(OutputStream os, long value) throws IOException { do { int b = (int) value & 0x7f; value = (value & 0x7fffffffffffffffl) >> 7; os.write(value == 0 ? b : (b | 0x80)); } while (value != 0); } } 。可以在运行中创建霍夫曼代码的字典,并且每次在排序的数组中插入新项目时插入阵列(插入排序)。请注意,当字典因新项目而更改时,应更新整个数组以匹配新编码。

如果我们具有相同数量的每个唯一元素,则用于编码D的每个元素的平均比特数被最大化。假设D中的元素d1,d2,...,dN每次出现F次。在那种情况下(在最坏的情况下,我们有输入序列中的0和10 ^ 8)我们有

sum(1 <= i <= N)F。di = 10 ^ 8

哪里

sum(1 <= i <= N)F = 10 ^ 6,或F = 10 ^ 6 / N,归一化频率为p = F / 10 ^ = 1 / N

平均位数为-log2(1 / P)= log2(N)。在这种情况下,我们应该找到一个最大化N的情况。如果我们有从di开始的di的连续数字,或者di = i-1,则会发生这种情况。

10 ^ 8 =和(1 <= i <= N)F。di = sum(1 <= i <= N)(10 ^ 6 / N)(i-1)=(10 ^ 6 / N)N( N-1)/ 2

N <= 201.对于这种情况,平均位数是log2(201)= 7.6511,这意味着每个输入元素需要大约1个字节来保存排序的数组。注意,这并不意味着D一般不能超过201个元素。它只是播种,如果D的元素均匀分布,它不能超过201个唯一值。


409
投票

Here's some working C++ code解决了这个问题。

证明满足内存约束:

编辑:没有证据证明作者在本文或他的博客中提供了最大内存要求。由于编码值所需的比特数取决于先前编码的值,因此这种证明可能是非平凡的。作者指出,他根据经验偶然发现的最大编码大小是1011732,并且任意选​​择缓冲区大小1013000

typedef unsigned int u32;

namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes

    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes

    ...

这两个阵列一起占用1045000字节的存储空间。这留下1048576 - 1045000 - 2×1024 = 1528字节用于剩余变量和堆栈空间。

它在我的Xeon W3520上运行大约23秒。假设程序名为sort1mb.exe,您可以使用以下Python脚本验证程序是否正常工作。

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

该算法的详细说明可在以下系列文章中找到:


3
投票

我会利用TCP的重传行为。

  1. 使TCP组件创建一个大型接收窗口。
  2. 接收一定数量的数据包而不为它们发送ACK。 处理那些创建一些(前缀)压缩数据结构的传递 为不再需要的最后一个数据包发送重复的ack /等待重传超时 转到2
  3. 所有数据包都被接受了

这假定了桶或多次通过的某种好处。

可能通过对批次/桶进行分类并合并它们。 - >基数树

使用此技术接受并排序前80%然后读取最后20%,验证最后20%不包含将落在最低数字的前20%中的数字。然后发送20%的最低数字,从内存中删除,接受剩余的20%的新数字并合并。**


2
投票

如果输入流可以被接收几次,那么这将更容易(没有关于它,想法和时间性能问题的信息)。

然后,我们可以计算小数值。使用计数值,可以很容易地生成输出流。通过计算值进行压缩。它取决于输入流中的内容。


1
投票

如果输入流可以被接收几次,那么这将更容易(没有关于这个,想法和时间性能问题的信息)。然后,我们可以计算小数值。使用计数值,可以很容易地生成输出流。通过计算值进行压缩。它取决于输入流中的内容。


1
投票

排序是这里的次要问题。正如其他人所说,只是存储整数很难,并且不能对所有输入起作用,因为每个数字需要27位。

我对此的看法是:只存储连续(排序)整数之间的差异,因为它们很可能很小。然后使用压缩方案,例如每个输入编号有2个附加位,用于编码存储该编号的位数。就像是:

Huffman code

应该可以在给定的内存约束内存储相当数量的可能输入列表。如何选择压缩方案以使其在最大输入数量上工作的数学计算超出了我的要求。

我希望您能够利用您输入的特定于域的知识来找到基于此的足够好的整数压缩方案。

哦,然后,当您收到数据时,在排序列表上执行插入排序。


1
投票

现在旨在实现一个实际的解决方案,涵盖8位数范围内所有可能的输入情况,只有1MB的RAM。注意:正在进行中,明天将继续。使用排序的整数的增量的算术编码,对于1M排序的整数的最坏情况将花费大约每个条目7位(因为99999999/1000000是99,并且log2(99)几乎是7位)。

但是你需要将1m整数排序为7或8位!较短的系列会有更大的增量,因此每个元素的位数更多。

我正在努力尽可能多地进行压缩(几乎)压缩。第一批接近250K的润滑剂最多需要大约9位。因此结果大约需要275KB。重复几次剩余的可用内存。然后解压缩 - 合并 - 压缩这些压缩块。这很难,但可能。我认为。

合并列表将越来越接近每个整数目标的7位。但我不知道合并循环需要多少次迭代。也许3。

但算术编码实现的不精确可能使其无法实现。如果这个问题完全可能,那将非常紧张。

有志愿者吗?


1
投票

您只需按顺序存储数字之间的差异,并使用编码来压缩这些序列号。我们有2 ^ 23位。我们将它分成6位块,并让最后一位指示该数字是否扩展到另外6位(5位加上扩展块)。

因此,000010是1,000100是2. 000001100000是128.现在,我们考虑表示最大10,000,000的数字序列差异的最差演员。可能存在大于2 ^ 5的10,000,000 / 2 ^ 5个差异,大于2 ^ 10的10,000,000 / 2 ^ 10个差异,以及大于2 ^ 15的10,000,000 / 2 ^ 15个差异等。

因此,我们添加表示序列所需的位数。我们有1,000,000 * 6 +综合报道(10,000,000 / 2 ^ 5)* 6 +综合报道(10,000,000 / 2 ^ 10)* 6 +综合报道(10,000,000 / 2 ^ 15)* 6 +综述(10,000,000 / 2 ^ 20)* 4 = 7935479。

2 ^ 24 = 8388608.自8388608> 7935479以来,我们应该很容易拥有足够的内存。我们可能需要另外一点内存来存储插入新数字时的总和。然后我们查看序列,找到插入新数字的位置,必要时减少下一个差异,然后将所有内容移到右后方。


1
投票

如果我们对这些数字一无所知,我们受到以下限制的限制:

  • 我们需要加载所有数字才能对它们进行排序,
  • 这组数字不可压缩。

如果这些假设成立,则无法执行任务,因为您将需要至少26,575,425位存储(3,321,929字节)。

您能告诉我们您的数据有哪些?


1
投票

诀窍是表示算法状态,它是一个整数多组,作为“增量计数器”=“+”和“输出计数器”=“!”的压缩流。字符。例如,集合{0,3,3,4}将表示为“!+++ !! +!”,后跟任意数量的“+”字符。要修改多组,您可以流出字符,一次只保留一个解压缩的常量,然后在以压缩格式回流之前进行更改。

细节

我们知道最终集合中确实有10 ^ 6个数字,因此最多有10 ^ 6“!”字符。我们也知道我们的范围大小为10 ^ 8,这意味着最多有10 ^ 8“+”个字符。我们可以在10 ^ 8“+”之间安排10 ^ 6“!”的方式是00 -> 5 bits 01 -> 11 bits 10 -> 19 bits 11 -> 27 bits ,因此指定一些特定的排列需要(10^8 + 10^6) choose 10^6`数据。那将是一个紧密的契合。

我们可以将每个角色视为独立角色而不超出我们的配额“+”字符的确比“!”多100倍。字符,如果我们忘记它们是依赖的,那么每个字符的简化为100:1的几率为“+”。 100:101的赔率对应于~0.965 MiB,对于几乎相同的~0.08 bits per character总数(在这种情况下忽略依赖性只有~0.965 MiB的成本!)。

用于存储具有已知先验概率的独立字符的最简单技术是~12 bits。请注意,我们需要一个不切实际的大树(10个字符的块的霍夫曼树每块的平均成本约为2.4位,总共约为2.9 Mib。对于20个字符的块,一个霍夫曼树具有每块的平均成本大约3比特,总共约1.8 MiB。我们可能需要一个大约一百块的块,这意味着我们的树中的节点比以前存在的所有计算机设备都要多。 )。然而,根据问题,ROM在技术上是“免费的”,并且利用树中的规律性的实际解决方案看起来基本相同。

伪代码

  • 具有存储在ROM中的足够大的霍夫曼树(或类似的逐块压缩数据)
  • 从压缩的10 ^ 8“+”字符串开始。
  • 要插入数字N,请将压缩的字符串流出,直到N“+”个字符已经过去,然后插入“!”。将重新压缩的字符串流回到前一个字符串上,保持一定量的缓冲块以避免过度/欠量运行。
  • 重复一百万次:[输入,流解压缩>插入>压缩],然后解压缩到输出

1
投票

我们有1 MB - 3 KB RAM = 2 ^ 23 - 3 * 2 ^ 13位= 8388608 - 24576 = 8364032位可用。

我们在10 ^ 8范围内给出10 ^ 6个数字。这给出了~100 <2 ^ 7 = 128的平均间隙

当所有间隙都小于128时,让我们首先考虑相当均匀间隔数的简单问题。这很容易。只需存储第一个数字和7位间隙:

(27位)+ 10 ^ 6 7位间隙数= 7000027位

注意重复数字的间隙为0。

但如果我们的差距大于127呢?

好吧,假设间隙大小<127直接表示,但间隙大小为127,接着是实际间隙长度的连续8位编码:

Huffman coding

等等

请注意,此数字表示描述了自己的长度,因此我们知道下一个间隙编号何时开始。

只有很小的间隙<127,这仍然需要7000027位。

最多可以有(10 ^ 8)/(2 ^ 7)= 781250 23位间隙数,需要额外的16 * 781,250 = 12,500,000位,这太多了。我们需要更紧凑和缓慢增加的差距表示。

平均间隙大小为100,所以如果我们将它们重新排序为[100,99,101,98,102,...,2,198,1,199,0,200,201,202,...]并将其编入索引密集的二进制Fibonacci基编码没有零对(例如,11011 = 8 + 5 + 2 + 1 = 16),数字由'00'分隔,那么我认为我们可以保持差距表示足够短,但它需要更多分析。


0
投票

在接收流时执行这些步骤。

第1集合一些合理的块大小

伪代码的想法:

  1. 第一步是查找所有重复项并将其粘贴在字典中并计算并删除它们。
  2. 第三步是将数字存在于算法步骤的顺序中,并将它们放在计数器特殊字典中,第一个数字和它们的步骤如n,n + 1 ...,n + 2,2n,2n + 1, 2N + 2 ...
  3. 开始以块的形式压缩一些合理的数字范围,例如每1000个或10000个剩余的数字,这些数字似乎不常重复。
  4. 如果找到一个数字,则解压缩该范围并将其添加到范围中并使其保持未压缩一段时间。
  5. 否则只需将该数字添加到一个字节[chunkSize]

在接收流时继续前4个步骤。最后一步是在超出内存时失败或者在收集完所有数据后开始输出结果,方法是开始对范围进行排序并按顺序吐出结果并解压缩那些需要解压缩的数据并在需要时对其进行排序你找到了他们。


363
投票

请参阅first correct answerthe later answer with arithmetic encoding。下面你可能会发现一些有趣的,但不是100%的防弹解决方案。

这是一项非常有趣的任务,这是另一种解决方案。我希望有人会发现结果有用(或至少有趣)。

第1阶段:初始数据结构,粗略压缩方法,基本结果

让我们做一些简单的数学运算:我们有1M(1048576字节)的RAM最初可用于存储10 ^ 6 8位十进制数。 [0; 99999999]。因此,需要存储一个数字27位(假设将使用无符号数)。因此,要存储原始流〜需要3.5M的RAM。有人已经说过这似乎不可行,但我会说如果输入“足够好”,任务就可以解决了。基本上,想法是压缩因子为0.29或更高,并以适当的方式进行排序。

让我们先解决压缩问题。已经有一些相关的测试:

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

“我进行了一项测试,使用各种形式的压缩来压缩一百万个连续的整数。结果如下:”

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

看起来LZMA(Lempel–Ziv–Markov chain algorithm)是继续使用的好选择。我准备了一个简单的PoC,但仍有一些细节要突出:

  1. 内存有限,因此想法是预先设定数字并使用压缩桶(动态大小)作为临时存储
  2. 使用预先排序的数据更容易实现更好的压缩因子,因此每个桶都有一个静态缓冲区(缓冲区中的数字要在LZMA之前排序)
  3. 每个桶都有一个特定的范围,因此可以分别对每个桶进行最终排序
  4. 可以正确设置存储桶的大小,因此将有足够的内存来解压缩存储的数据并分别对每个存储桶进行最终排序

请注意,附加代码是POC,它不能用作最终解决方案,它只是演示了使用几个较小的缓冲区以某种最佳方式(可能是压缩)存储预分类数字的想法。 LZMA不是最终解决方案。它被用作向此PoC引入压缩的最快方式。

请参阅下面的PoC代码(请注意它只是一个演示,要编译它将需要LZMA-Java):

public class MemorySortDemo {

static final int NUM_COUNT = 1000000;
static final int NUM_MAX   = 100000000;

static final int BUCKETS      = 5;
static final int DICT_SIZE    = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE  = 1024;
static final int BUFFER_SIZE  = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;

static class Producer {
    private Random random = new Random();
    public int produce() { return random.nextInt(NUM_MAX); }
}

static class Bucket {
    public int size, pointer;
    public int[] buffer = new int[BUFFER_SIZE];

    public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
    public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
    public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();

    public void submitBuffer() throws IOException {
        Arrays.sort(buffer, 0, pointer);

        for (int j = 0; j < pointer; j++) {
            tempDataOut.writeInt(buffer[j]);
            size++;
        }            
        pointer = 0;
    }

    public void write(int value) throws IOException {
        if (isBufferFull()) {
            submitBuffer();
        }
        buffer[pointer++] = value;
    }

    public boolean isBufferFull() {
        return pointer == BUFFER_SIZE;
    }

    public byte[] compressData() throws IOException {
        tempDataOut.close();
        return compress(tempOut.toByteArray());
    }        

    private byte[] compress(byte[] input) throws IOException {
        final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
        final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));

        final Encoder encoder = new Encoder();
        encoder.setEndMarkerMode(true);
        encoder.setNumFastBytes(0x20);
        encoder.setDictionarySize(DICT_SIZE);
        encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);

        ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
        encoder.writeCoderProperties(encoderPrperties);
        encoderPrperties.flush();
        encoderPrperties.close();

        encoder.code(in, out, -1, -1, null);
        out.flush();
        out.close();
        in.close();

        return encoderPrperties.toByteArray();
    }

    public int[] decompress(byte[] properties) throws IOException {
        InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
        ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
        BufferedOutputStream out = new BufferedOutputStream(data);

        Decoder decoder = new Decoder();
        decoder.setDecoderProperties(properties);
        decoder.code(in, out, 4 * size);

        out.flush();
        out.close();
        in.close();

        DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
        int[] array = new int[size];
        for (int k = 0; k < size; k++) {
            array[k] = input.readInt();
        }

        return array;
    }
}

static class Sorter {
    private Bucket[] bucket = new Bucket[BUCKETS];

    public void doSort(Producer p, Consumer c) throws IOException {

        for (int i = 0; i < bucket.length; i++) {  // allocate buckets
            bucket[i] = new Bucket();
        }

        for(int i=0; i< NUM_COUNT; i++) {         // produce some data
            int value = p.produce();
            int bucketId = value/BUCKET_RANGE;
            bucket[bucketId].write(value);
            c.register(value);
        }

        for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
            bucket[i].submitBuffer();
        }

        byte[] compressProperties = null;
        for (int i = 0; i < bucket.length; i++) { // compress the data
            compressProperties = bucket[i].compressData();
        }

        printStatistics();

        for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
            int[] array = bucket[i].decompress(compressProperties);
            Arrays.sort(array);

            for(int v : array) {
                c.consume(v);
            }
        }
        c.finalCheck();
    }

    public void printStatistics() {
        int size = 0;
        int sizeCompressed = 0;

        for (int i = 0; i < BUCKETS; i++) {
            int bucketSize = 4*bucket[i].size;
            size += bucketSize;
            sizeCompressed += bucket[i].compressedOut.size();

            System.out.println("  bucket[" + i
                    + "] contains: " + bucket[i].size
                    + " numbers, compressed size: " + bucket[i].compressedOut.size()
                    + String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
        }

        System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
                + String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
                + String.format(" compression factor %.2f",(double)sizeCompressed/size));
    }
}

static class Consumer {
    private Set<Integer> values = new HashSet<>();

    int v = -1;
    public void consume(int value) {
        if(v < 0) v = value;

        if(v > value) {
            throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
        }else{
            v = value;
            values.remove(value);
        }
    }

    public void register(int value) {
        values.add(value);
    }

    public void finalCheck() {
        System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
    }
}

public static void main(String[] args) throws IOException {
    Producer p = new Producer();
    Consumer c = new Consumer();
    Sorter sorter = new Sorter();

    sorter.doSort(p, c);
}
}

随机数字产生以下内容:

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44

对于简单的升序(使用一个桶),它产生:

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06

编辑

结论:

  1. 不要试图欺骗Nature
  2. 使用更简单的压缩,内存占用更少
  3. 真的需要一些额外的线索。常见的防弹解决方案似乎不可行。

阶段2:增强压缩,最终结论

如前一节中已经提到的,可以使用任何合适的压缩技术。因此,让我们摆脱LZMA,转而采用更简单,更好(如果可能)的方法。有很多很好的解决方案,包括Arithmetic codingRadix tree等。

无论如何,简单但有用的编码方案将比另一个外部库更具说明性,提供一些漂亮的算法。实际的解决方案非常简单:由于存在具有部分排序数据的存储桶,因此可以使用增量而不是数字。

随机输入测试显示略好的结果:

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34

示例代码

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

请注意,这种方法:

  1. 不消耗大量内存
  2. 适用于溪流
  3. 提供不那么糟糕的结果

完整的代码可以找到qazxsw poi,二进制输入和二进制输出实现可以找到here

定论

没有最终结论:)有时,从here的角度来看,提升一级并审查任务是一个非常好的主意。

花一些时间完成这项任务很有趣。顺便说一下,下面有很多有趣的答案。感谢您的关注和愉快的编码。


-1
投票

由于ROM大小不计,除了TCP缓冲区之外不需要任何额外的RAM。只需实现一个大的有限状态机。每个状态代表读入的多组数字。读取一百万个数字之后,只需要打印与达到状态相对应的数字。


169
投票

只有1兆字节和1百万字节之间的差异才能实现解决方案。大约有2个功率8093729.5不同的方式来选择100万个8位数字,允许重复,并且命令不重要,因此只有100万字节RAM的机器没有足够的状态来代表所有可能性。但是1M(TCP / IP少于2k)是1022 * 1024 * 8 = 8372224位,因此可以实现解决方案。

第1部分,初始解决方案

这种方法需要略高于1M,我将其改进以适应1M以后。

我将存储0到99999999范围内的紧凑排序列表作为7位数字的子列表序列。第一个子列表包含0到127之间的数字,第二个子列表包含128到255之间的数字等.100000000/128正好是781250,因此需要781250个这样的子列表。

每个子列表由一个2位子列表头和一个子列表主体组成。子列表主体每个子列表条目占用7位。子列表全部连接在一起,格式使得可以分辨一个子列表的结束位置和下一个子列表的开始位置。完全填充列表所需的总存储量为2 * 781250 + 7 * 1000000 = 8562500位,大约为1.021 M字节。

4个可能的子列表标题值为:

00清空子列表,后面没有任何内容。

01单例,子列表中只有一个条目,接下来的7位保留它。

10子列表至少包含2个不同的数字。条目以非递减顺序存储,除了最后一个条目小于或等于第一个条目。这允许识别子列表的结尾。例如,数字2,4,6将存储为(4,6,2)。数字2,2,3,4,4将存储为(2,3,4,4,2)。

11子列表包含2个或更多个单个数字的重复。接下来的7位给出了数字。然后得到零或多个值为1的7位条目,接着是值为0的7位条目。子列表主体的长度决定了重复次数。例如,数字12,12将存储为(12,0),数字12,12,12将存储为(12,1,0),12,12,12,12将存储为(12,1) ,1,0)等。

我从一个空列表开始,读取一堆数字并将它们存储为32位整数,对新数字进行排序(可能使用heapsort),然后将它们合并到一个新的紧凑排序列表中。重复直到没有更多数字要读取,然后再次走紧凑列表以生成输出。

下面的行表示列表合并操作开始之前的内存。 “O”是保存排序的32位整数的区域。 “X”是保存旧紧凑列表的区域。 “=”符号是紧凑列表的扩展空间,“O”中的每个整数为7位。 “Z”是其他随机开销。

meta-level

合并例程开始读取最左边的“O”和最左边的“X”,并开始在最左边的“=”处写入。在所有新的整数合并之前,写指针不会捕获紧凑列表读指针,因为两个指针为每个子列表提前2位,为旧压缩列表中的每个条目提前7位,并且有足够的额外空间用于新数字的7位条目。

第2部分,将其塞进1M

要将上面的解决方案挤压到1M,我需要使紧凑列表格式更紧凑。我将摆脱其中一个子列表类型,因此只有3种不同的子列表标题值。然后我可以使用“00”,“01”和“1”作为子列表标题值并保存几位。子列表类型是:

空子列表,后面没有任何内容。

B Singleton,子列表中只有一个条目,接下来的7位保留它。

C子列表包含至少2个不同的数字。条目以非递减顺序存储,除了最后一个条目小于或等于第一个条目。这允许识别子列表的结尾。例如,数字2,4,6将存储为(4,6,2)。数字2,2,3,4,4将存储为(2,3,4,4,2)。

D子列表包含2个或更多个单个数字的重复。

我的3个子列表标题值将是“A”,“B”和“C”,所以我需要一种方法来表示D类型的子列表。

假设我有C型子列表标题后跟3个条目,例如“C [17] [101] [58]”。这不能是如上所述的有效C类子列表的一部分,因为第三个条目小于第二个条目但是多于第一条目。我可以使用这种类型的构造来表示D类子列表。在比特术语中,我有“C {00 ?????} {1 ??????} {01 ?????}”是一个不可能的C型子列表。我将使用它来表示由3个或更多个单个数字重复组成的子列表。前两个7位字对数字进行编码(下面的“N”位),然后是零个或多个{0100001}字,后跟{0100000}字。

ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX

这只留下了只包含2个重复单个数字的列表。我将用另一个不可能的C型子列表模式代表那些:“C {0 ??????} {11 ?????} {10 ?????}”。前两个单词中7位数字有足够的空间,但这种模式比它所代表的子列表更长,这使得事情变得更复杂。最后的五个问号可以被认为不是模式的一部分,所以我有:“C {0NNNNNN} {11N ????} 10”作为我的模式,其中要重复的数字存储在“N”中“S。那是2位太长了。

我将不得不借用2位并从这种模式中的4个未使用的位中支付它们。在读取时,遇到“C {0NNNNNN} {11N00AB} 10”时,输出“N”中数字的2个实例,用位A和B覆盖末尾的“10”,并将读取指针倒回2位。破坏性读取对于该算法是可以的,因为每个紧凑列表仅被移动一次。

写入单个数字的2个重复的子列表时,写入“C {0NNNNNN} 11N00”并将借位计数器设置为2.在每次写入时,借位计数器为非零,对于写入的每个位,它都会递减。当计数器达到零时写入“10”。所以写入的下两位将进入插槽A和B,然后“10”将被放到最后。

使用由“00”,“01”和“1”表示的3个子列表标题值,我可以将“1”分配给最流行的子列表类型。我需要一个小表来将子列表头值映射到子列表类型,并且我需要每个子列表类型的出现计数器,以便我知道最佳子列表头映射是什么。

当所有子列表类型同样受欢迎时,出现完全填充的紧凑列表的最坏情况最小表示。在这种情况下,我为每3个子列表标题保存1位,因此列表大小为2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3位。舍入到32位字边界,即8302112位,或10​​37764字节。

1M减去TCP / IP状态和缓冲区的2k是1022 * 1024 = 1046528字节,留下8764字节。

但是更改子列表头映射的过程呢?在下面的存储器映射中,“Z”是随机开销,“=”是自由空间,“X”是紧凑列表。

For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.

从最左边的“X”开始阅读并开始写在最左边的“=”并向右工作。当它完成后,紧凑列表将会更短一点,并且它将位于错误的内存末尾:

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

那么我需要将它分流到右边:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

在标头映射更改过程中,最多1/3的子列表标头将从1位更改为2位。在最坏的情况下,这些都将位于列表的首位,因此在开始之前我将需要至少781250/3位的空闲存储空间,这使我回到了先前版本的紧凑列表的内存要求: (

为了解决这个问题,我将把781250子列表分成10个子列表组,每个子列表包含78125个子列表。每个组都有自己独立的子列表头映射。使用字母A到J为组:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

在子列表标题映射更改期间,每个子列表组都缩小或保持不变:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

在映射更改期间,子列表组的最坏情况临时扩展是78125/3 = 26042位,低于4k。如果我允许4k加上1037764字节用于完全填充的紧凑列表,那么对于存储器映射中的“Z”,我留下8764 - 4096 = 4668字节。

对于10个子列表头映射表,30个子列表头事件计数以及我需要的其他几个计数器,指针和小缓冲区,以及我在没有注意到的情况下使用的空间,如函数调用返回地址的堆栈空间和局部变量。

第3部分,运行需要多长时间?

对于空紧凑列表,1位列表标题将用于空子列表,列表的起始大小将为781250位。在最坏的情况下,列表对于每个添加的数字增长8位,因此每个32位数字需要32 + 8 = 40位的可用空间放置在列表缓冲区的顶部,然后进行排序和合并。在最坏的情况下,更改子列表标头映射会导致空间使用量为2 * 781250 + 7 *个条目 - 781250/3位。

一旦在列表中存在至少800000个数字,在每第五次合并之后改变子列表头部映射的策略,最坏的情况运行将涉及总共约30M的紧凑列表读取和写入活动。

资源:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ======= ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ


55
投票

吉尔马诺夫的答案在其假设中是非常错误的。它开始根据一百万个连续整数的毫无意义的度量进行推测。这意味着没有差距。那些随机的差距,无论多么小,都会让它成为一个糟糕的主意。

亲自尝试一下。得到100万随机27​​位整数,对它们进行排序,用http://nick.cleaton.net/ramsortsol.html,xz压缩,无论你想要什么LZMA。结果超过1.5 MB。最重要的前提是压缩序列号。甚至delta编码也超过1.1 MB。不用担心这会使用超过100 MB的RAM进行压缩。因此,即使压缩整数也不适合这个问题,更不用说运行时RAM的使用。

让我感到很难过的是人们如何赞美漂亮的图形和合理化。

7-Zip

现在使用LZMA压缩ints.bin ...

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

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

41
投票

我认为考虑这个问题的一种方法是从组合学的角度来看:有多少可能的排序数字排序组合?如果我们给组合0,0,0,....,0代码0和0,0,0,...,1代码1,和99999999,99999999,... 99999999代码N,什么是N?换句话说,结果空间有多大?

好吧,考虑到这一点的一种方法是注意到这是在N×M网格中找到单调路径数量的问题的双射,其中N = 1,000,000且M = 100,000,000。换句话说,如果你的网格宽度为1,000,000,高度为100,000,000,那么从左下角到右上角的最短路径是多少?最短的路径当然要求你只要向右或向上移动(如果你要向下或向左移动,你将取消之前完成的进展)。要查看这是否是我们的数字排序问题的双射,请遵守以下内容:

您可以将我们路径中的任何水平支路想象为我们排序中的数字,其中支路的Y位置代表值。

因此,如果路径只是一直向右移动到最后,那么一直跳到顶部,这相当于排序0,0,0,...,0。如果它开始一直跳到顶部然后向右移动1,000,000次,那相当于99999999,99999999,...,99999999。它向右移动一次,然后向上移动一次,然后向右移动一次的路径,然后一次,等到最后(然后必然一直跳到顶部),相当于0,1,2,3,...,999999。

幸运的是,这个问题已经解决了,这样的网格有(N + M)选择(M)路径:

(1,000,000 + 100,000,000)选择(100,000,000)〜= 2.27 * 10 ^ 2436455

N因此等于2.27 * 10 ^ 2436455,因此代码0代表0,0,0,...,0和代码2.27 * 10 ^ 2436455,一些变化代表99999999,99999999,...,99999999。

为了存储从0到2.27 * 10 ^ 2436455的所有数字,您需要lg2(2.27 * 10 ^ 2436455)= 8.0937 * 10 ^ 6位。

1兆字节= 8388608位> 8093700位

所以看来我们至少实际上有足够的空间来存储结果!当然,有趣的是在数字流输入时进行排序。不确定最好的方法是给出我们剩余的294908位。我想一个有趣的技术是在每个点假设这是整个排序,找到该排序的代码,然后当你收到一个新的数字返回并更新以前的代码。手波手波。


20
投票

我在这里的建议很大程度上归功于$ xz -f --keep ints.bin # 100 MB RAM $ 7z a ints.bin.7z ints.bin # 130 MB RAM $ ls -lh ints.bin* 3.8M ints.bin 1.1M ints.bin.7z 1.2M ints.bin.xz

首先,我假设解决方案必须处理所有可能的输入列表。我认为流行的答案没有做出这个假设(IMO是一个巨大的错误)。

众所周知,任何形式的无损压缩都会减小所有输入的大小。

所有流行的答案都假设他们能够有效地应用压缩,以便为他们提供额外的空间。事实上,一大块额外的空间足够大,可以以未压缩的形式保存部分完成的列表的某些部分,并允许它们执行排序操作。这只是一个不好的假设。

对于这样的解决方案,任何知道如何进行压缩的人都能够设计一些不能很好地压缩该方案的输入数据,并且“解决方案”很可能会因空间不足而中断。

相反,我采取数学方法。我们可能的输出是长度LEN的所有列表,包括0..MAX范围内的元素。 LEN为1,000,000,MAX为100,000,000。

对于任意LEN和MAX,编码此状态所需的位数为:

Log2(MAX Multichoose LEN)

因此,对于我们的数字,一旦我们完成接收和排序,我们将至少需要Log2(100,000,000 MC 1,000,000)位来存储我们的结果,以便能够唯一地区分所有可能的输出。

Dan's solution。所以我们实际上有足够的空间来保持我们的结果。从这个角度来看,这是可能的。

[现在存在更好的例子,删除了毫无意义的漫无边际......]

最佳答案This is ~= 988kb

另一个好的答案is here并且基本上使用插入排序作为将列表扩展一个元素的函数(缓冲一些元素和预先排序,允许一次插入多个元素,节省一点时间)。使用一个很好的紧凑状态编码,七位增量的桶


18
投票

假设这个任务是可能的。在输出之前,将存在百万个已排序数字的内存表示。有多少种不同的表示形式?由于可能有重复的数字,我们不能使用nCr(选择),但有一个名为multichoose的操作适用于is here

  • multisets方法可以在0..99,999,999的范围内选择一百万个数字。
  • 这需要2.2e2436455位来表示每个可能的组合,或1,011,717字节。

所以从理论上讲,如果你能想出一个合理的数字列表的理智(足够)表示,那么它是可能的。例如,疯狂的表示可能需要10MB的查找表或数千行代码。

但是,如果“1M RAM”意味着一百万字节,那么显然没有足够的空间。事实上,5%的内存使其在理论上成为可能,这一事实向我表明,该表示必须非常高效且可能并不理智。


12
投票

(我原来的回答是错误的,抱歉数学不好,见下面的休息。)

这个怎么样?

前27位存储您看到的最低数字,然后与下一个数字的差异,编码如下:5位用于存储用于存储差异的位数,然后是差值。使用00000表示您再次看到该号码。

这是有效的,因为随着插入的数字越来越多,数字之间的平均差异会下降,因此在添加更多数字时使用较少的位来存储差异。我相信这被称为增量列表。

我能想到的最糟糕的情况是所有数字均匀间隔(100),例如假设0是第一个数字:

8,093,730

Reddit来救援!

如果您只需要对它们进行排序,那么这个问题就很容易了。需要122k(100万位)才能存储您看到的数字(如果看到0则为第0位,如果看到2300则为第2300位,等等)。

您读取数字,将它们存储在位字段中,然后在保持计数的同时将位移出。

但是,你必须记住你见过多少。我受到上面的子列表答案的启发,想出了这个方案:

不使用一位,而是使用2位或27位:

  • 00表示您没有看到该号码。
  • 01意味着你曾经看过它
  • 1意味着你看到它,接下来的26位是多少次的计数。

我认为这是有效的:如果没有重复,你有一个244k列表。在最坏的情况下,您会看到每个数字两次(如果您看到一个数字三次,它会缩短列表的其余部分),这意味着您已经多次看到50,000个,并且您已经看到了950,000个项目0或1次。

50,000 * 27 + 950,000 * a = 396。

如果使用以下编码,则可以进一步改进:

0意味着你没有看到数字10意味着你曾经看过它11你是如何计算的

平均而言,这将导致280.7k的存储空间。

编辑:我周日早上的数学错了。

最糟糕的情况是我们两次看到500,000个数字,所以数学变为:

500,000 * 27 + 500,000 * a = 1.h.

备用编码导致平均存储空间

500,000 * 27 + 500,000 = 1.70米

: (

© www.soinside.com 2019 - 2024. All rights reserved.