algorithm ما - فرز 1 مليون من 8 أرقام في 1 ميغابايت من ذاكرة الوصول العشوائي




وانواعها الرئيسية (25)

We have 1 MB - 3 KB RAM = 2^23 - 3*2^13 bits = 8388608 - 24576 = 8364032 bits available.

We are given 10^6 numbers in a 10^8 range. This gives an average gap of ~100 < 2^7 = 128

Let's first consider the simpler problem of fairly evenly spaced numbers when all gaps are < 128. This is easy. Just store the first number and the 7-bit gaps:

(27 bits) + 10^6 7-bit gap numbers = 7000027 bits required

Note repeated numbers have gaps of 0.

But what if we have gaps larger than 127?

OK, let's say a gap size < 127 is represented directly, but a gap size of 127 is followed by a continuous 8-bit encoding for the actual gap length:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

إلخ

Note this number representation describes its own length so we know when the next gap number starts.

With just small gaps < 127, this still requires 7000027 bits.

There can be up to (10^8)/(2^7) = 781250 23-bit gap number, requiring an extra 16*781,250 = 12,500,000 bits which is too much. We need a more compact and slowly increasing representation of gaps.

The average gap size is 100 so if we reorder them as [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] and index this with a dense binary Fibonacci base encoding with no pairs of zeros (for example, 11011=8+5+2+1=16) with numbers delimited by '00' then I think we can keep the gap representation short enough, but it needs more analysis.

لدي جهاز كمبيوتر مع 1 ميغابايت من ذاكرة الوصول العشوائي وأي تخزين محلي آخر. يجب أن أستخدمه لقبول 1 مليون رقم عشري مكون من 8 أرقام عبر اتصال TCP ، وفرزها ، ثم إرسال القائمة التي تم فرزها عبر اتصال TCP آخر.

قد تحتوي قائمة الأرقام على نسخ مكررة ، والتي يجب ألا أتجاهلها. سيتم وضع الكود في ROM ، لذا لا يجب طرح حجم شفرتي من 1 ميجابايت. لدي بالفعل رمز لتشغيل منفذ Ethernet والتعامل مع اتصالات TCP / IP ، ويتطلب 2 كيلوبايت لبيانات الحالة الخاصة به ، بما في ذلك مخزن مؤقت سعة 1 كيلوبايت يتم من خلاله قراءة التعليمات البرمجية وكتابتها. هل هناك حل لهذه المشكلة؟

مصادر السؤال والجواب:
slashdot.org

cleaton.net


My suggestions here owe a lot to Dan's solution

First off I assume the solution must handle all possible input lists. I think the popular answers do not make this assumption (which IMO is a huge mistake).

It is known that no form of lossless compression will reduce the size of all inputs.

All the popular answers assume they will be able to apply compression effective enough to allow them extra space. In fact, a chunk of extra space large enough to hold some portion of their partially completed list in an uncompressed form and allow them to perform their sorting operations. This is just a bad assumption.

For such a solution, anyone with knowledge of how they do their compression will be able to design some input data that does not compress well for this scheme, and the "solution" will most likely then break due to running out of space.

Instead I take a mathematical approach. Our possible outputs are all the lists of length LEN consisting of elements in the range 0..MAX. Here the LEN is 1,000,000 and our MAX is 100,000,000.

For arbitrary LEN and MAX, the amount of bits needed to encode this state is:

Log2(MAX Multichoose LEN)

So for our numbers, once we have completed recieving and sorting, we will need at least Log2(100,000,000 MC 1,000,000) bits to store our result in a way that can uniquely distinguish all possible outputs.

This is ~= 988kb . So we actually have enough space to hold our result. From this point of view, it is possible.

[Deleted pointless rambling now that better examples exist...]

Best answer is here .

Another good answer is here and basically uses insertion sort as the function to expand the list by one element (buffers a few elements and pre-sorts, to allow insertion of more than one at a time, saves a bit of time). uses a nice compact state encoding too, buckets of seven bit deltas


Google 's (bad) approach, from HN thread. Store RLE-style counts.

Your initial data structure is '99999999:0' (all zeros, haven't seen any numbers) and then lets say you see the number 3,866,344 so your data structure becomes '3866343:0,1:1,96133654:0' as you can see the numbers will always alternate between number of zero bits and number of '1' bits so you can just assume the odd numbers represent 0 bits and the even numbers 1 bits. This becomes (3866343,1,96133654)

Their problem doesn't seem to cover duplicates, but let's say they use "0:1" for duplicates.

Big problem #1: insertions for 1M integers would take ages .

Big problem #2: like all plain delta encoding solutions, some distributions can't be covered this way. For example, 1m integers with distances 0:99 (eg +99 each one). Now think the same but with random distance in the range of 0:99 . (Note: 99999999/1000000 = 99.99)

Google's approach is both unworthy (slow) and incorrect. But to their defense, their problem might have been slightly different.


A radix tree representation would come close to handling this problem, since the radix tree takes advantage of "prefix compression". But it's hard to conceive of a radix tree representation that could represent a single node in one byte -- two is probably about the limit.

But, regardless of how the data is represented, once it is sorted it can be stored in prefix-compressed form, where the numbers 10, 11, and 12 would be represented by, say 001b, 001b, 001b, indicating an increment of 1 from the previous number. Perhaps, then, 10101b would represent an increment of 5, 1101001b an increment of 9, etc.


هناك خدعة مستأسلة واحدة غير مذكورة هنا حتى الآن. نفترض أنه ليس لديك طريقة إضافية لتخزين البيانات ، ولكن هذا ليس صحيحًا تمامًا.

طريقة واحدة حول مشكلتك هي أن تفعل الشيء الفظيع التالي ، والذي لا ينبغي أن يحاول أي شخص تحت أي ظرف من الظروف: استخدم حركة مرور الشبكة لتخزين البيانات. لا ، أنا لا أقصد NAS.

يمكنك فرز الأرقام ببضعة بايت فقط من ذاكرة الوصول العشوائي بالطريقة التالية:

  • اتخذ أولاً متغيرين: COUNTER و VALUE .
  • أولاً قم بتعيين كافة السجلات إلى 0 ؛
  • في كل مرة تتلقى عددًا صحيحًا ، I بزيادة COUNTER وقمت بتعيين VALUE على max(VALUE, I) ؛
  • ثم أرسل حزمة طلب ارتداد ICMP ببيانات معيّنة إلى جهاز التوجيه. مسح I وتكرار.
  • في كل مرة تتلقى حزمة ICMP التي تم إرجاعها ، يمكنك ببساطة استخراج عدد صحيح وإرسالها مرة أخرى في طلب آخر الارتداد. هذا ينتج عدد كبير من طلبات ICMP scuttling إلى الخلف وإلى الأمام تحتوي على الأعداد الصحيحة.

بمجرد وصول COUNTER إلى 1000000 ، سيكون لديك جميع القيم المخزنة في الدفق المستمر لطلبات ICMP ، و VALUE الآن تحتوي على الحد الأقصى الصحيح. اختيار بعض threshold T >> 1000000 . حدد COUNTER إلى صفر. في كل مرة تتلقى فيها حزمة ICMP ، زيادة COUNTER وإرسال العدد الصحيح المحتوي ، أتراجع في طلب صدى آخر ، ما لم يكن I=VALUE ، وفي هذه الحالة نرسله إلى الوجهة للأعداد الصحيحة التي تم فرزها. بمجرد COUNTER=T ، إنقاص VALUE بمقدار 1 ، قم بإعادة ضبط COUNTER إلى صفر وكرر. بمجرد وصول VALUE إلى الصفر ، يجب أن تكون قد أرسلت جميع الأعداد الصحيحة بالترتيب من الأكبر إلى الأصغر إلى الوجهة ، واستخدمت فقط 47 بت من ذاكرة الوصول العشوائي للمتغيرين الثابتين (ومهما كان المبلغ الصغير الذي تحتاجه للقيم المؤقتة).

أعلم أن هذا أمر فظيع ، وأنا أعلم أنه يمكن أن يكون هناك الكثير من القضايا العملية ، لكنني اعتقدت أن ذلك قد يمنح بعضكم ضحكة أو على الأقل ترويعكم.


I think the solution is to combine techniques from video encoding, namely the discrete cosine transformation. In digital video, rather recording the changing the brightness or colour of video as regular values such as 110 112 115 116, each is subtracted from the last (similar to run length encoding). 110 112 115 116 becomes 110 2 3 1. The values, 2 3 1 require less bits than the originals.

So lets say we create a list of the input values as they arrive on the socket. We are storing in each element, not the value, but the offset of the one before it. We sort as we go, so the offsets are only going to be positive. But the offset could be 8 decimal digits wide which this fits in 3 bytes. Each element can't be 3 bytes, so we need to pack these. We could use the top bit of each byte as a "continue bit", indicating that the next byte is part of the number and the lower 7 bits of each byte need to be combined. zero is valid for duplicates.

As the list fills up, the numbers should be get closer together, meaning on average only 1 byte is used to determine the distance to the next value. 7 bits of value and 1 bit of offset if convenient, but there may be a sweet spot that requires less than 8 bits for a "continue" value.

Anyway, I did some experiment. I use a random number generator and I can fit a million sorted 8 digit decimal numbers into about 1279000 bytes. The average space between each number is consistently 99...

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);
    }
}

There is one solution to this problem across all possible inputs. Cheat.

  1. Read m values over TCP, where m is near the max that can be sorted in memory, maybe n/4.
  2. Sort the 250,000 (or so) numbers and output them.
  3. Repeat for the other 3 quarters.
  4. Let the receiver merge the 4 lists of numbers it has received as it processes them. (It's not much slower than using a single list.)

This is assuming base 10 and as an example, your memory is using 8 bit words: Memory map the entire range of numbers using 3 bit increments. The First 3 bits would correspond to the number 0. The second set of 3 bit would map to number 1. Three hundred thousandth set of 3-bit would map to the number 300k. Repeat this until you have mapped out all the 8 digit numbers. This would total 375k bytes in total if memory range was continuous.

The 1st bit out of the 3 would mark the presence of the number. The next 2 bits would indicate the amount of duplicates that could be represented in bytes(1..3) if none, the duplicates field would be 00. There will be a second list that uses a counter that increments each time a 3 bit field is marked as having a duplicate. If it marked with 1 it will have a single bit range to count the amount of duplicates it has. 8 bits can represent a range 255.

As I'm losing track of thoughts. The second list will keep track of how many duplicates for each number. if the 255th number has a duplicate and is the first number to have a duplicate it's index in the list will be 0. If 23,543 is the second number to have a duplicate it's index will be 1. Wash,rise and repeat.

Worst case scenario is you have 500k numbers with duplicates. This can be represented by a single byte(since 1 fits in easy). So 375kB(ideally) + 500kB bytes is close to .875MB. Depending on your processor this should leave enough room left over for pointers,indexing and all of the other fun stuff.

If you have a single number that has 1M duplicates. all you need is 3 bytes, since your limited to 1M numbers, that's all you have to worry about. So on your second list it will be just be 3 byes with the total amount.

Now for the fun part. The second list will need to be sorted for each new number that comes in. In the 3 bit field the last 2 are the number of bytes that contains the number of duplicates. Since the second list is expected to be in order it will need to be sorted. Since the amount of bytes can vary. Think insertion sort!

This would keep the amount of pointers and things you need to increment to a minimum so you should have a little bit of flexibility with the maybe 250k bytes left.

GoodLuck! This sounds so much more elegant in my mind...


إليك بعض رموز C ++ التي تعمل على حل المشكلة.

دليل على استيفاء قيود الذاكرة:

المحرر: لا يوجد أي دليل على الحد الأقصى من متطلبات الذاكرة التي يقدمها المؤلف سواء في هذا المنشور أو في مدوناته. نظرًا لأن عدد البتات اللازمة لتشفير قيمة ما يعتمد على القيم التي تم ترميزها سابقًا ، فمن المحتمل أن يكون هذا الإثبات غير تافه. ويلاحظ المؤلف أن أكبر حجم مشفر يمكن أن يتعثر عليه تجريبيا كان 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 بايت للمتغيرات المتبقية ومساحة مكدس.

يعمل في حوالي 23 ثانية على بلدي زيون W3520. يمكنك التحقق من أن البرنامج يعمل باستخدام البرنامج النصي Python التالي ، بافتراض اسم برنامج sort1mb.exe .

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!')

يمكن العثور على شرح مفصل للخوارزمية في سلسلة المشاركات التالية:


If we don't know anything about those numbers, we are limited by the following constraints:

  • we need to load all numbers before we can sort them them,
  • the set of numbers is not compressible.

If these assumptions hold, there is no way to carry out your task, as you will need at least 26,575,425 bits of storage (3,321,929 bytes).

What can you tell us about your data ?


Now aiming to an actual solution, covering all possible cases of input in the 8 digit range with only 1MB of RAM. NOTE: work in progress, tomorrow will continue. Using arithmetic coding of deltas of the sorted ints, worst case for 1M sorted ints would cost about 7bits per entry (since 99999999/1000000 is 99, and log2(99) is almost 7 bits).

But you need the 1m integers sorted to get to 7 or 8 bits! Shorter series would have bigger deltas, therefore more bits per element.

I'm working on taking as many as possible and compressing (almost) in-place. First batch of close to 250K ints would need about 9 bits each at best. So result would take about 275KB. Repeat with remaining free memory a few times. Then decompress-merge-in-place-compress those compressed chunks. This is quite hard , but possible. أعتقد.

The merged lists would get closer and closer to the 7bit per integer target. But I don't know how many iterations it would take of the merge loop. Perhaps 3.

But the imprecision of the arithmetic coding implementation might make it impossible. If this problem is possible at all, it would be extremely tight.

Any volunteers?


I would exploit the retransmission behaviour of TCP.

  1. Make the TCP component create a large receive window.
  2. Receive some amount of packets without sending an ACK for them.
    • Process those in passes creating some (prefix) compressed data structure
    • Send duplicate ack for last packet that is not needed anymore/wait for retransmission timeout
    • Goto 2
  3. All packets were accepted

This assumes some kind of benefit of buckets or multiple passes.

Probably by sorting the batches/buckets and merging them. -> radix trees

Use this technique to accept and sort the first 80% then read the last 20%, verify that the last 20% do not contain numbers that would land in the first 20% of the lowest numbers. Then send the 20% lowest numbers, remove from memory, accept the remaining 20% of new numbers and merge.**


I have a computer with 1M of RAM and no other local storage

Another way to cheat: you could use non-local (networked) storage instead (your question does not preclude this) and call a networked service that could use straightforward disk-based mergesort (or just enough RAM to sort in-memory, since you only need to accept 1M numbers), without needing the (admittedly extremely ingenious) solutions already given.

This might be cheating, but it's not clear whether you are looking for a solution to a real-world problem, or a puzzle that invites bending of the rules... if the latter, then a simple cheat may get better results than a complex but "genuine" solution (which as others have pointed out, can only work for compressible inputs).


There are 10^6 values in a range of 10^8, so there's one value per hundred code points on average. Store the distance from the Nth point to the (N+1)th. Duplicate values have a skip of 0. This means that the skip needs an average of just under 7 bits to store, so a million of them will happily fit into our 8 million bits of storage.

These skips need to be encoded into a bitstream, say by Huffman encoding. Insertion is by iterating through the bitstream and rewriting after the new value. Output by iterating through and writing out the implied values. For practicality, it probably wants to be done as, say, 10^4 lists covering 10^4 code points (and an average of 100 values) each.

A good Huffman tree for random data can be built a priori by assuming a Poisson distribution (mean=variance=100) on the length of the skips, but real statistics can be kept on the input and used to generate an optimal tree to deal with pathological cases.


We could play with the networking stack to send the numbers in sorted order before we have all the numbers. If you send 1M of data, TCP/IP will break it into 1500 byte packets and stream them in order to the target. Each packet will be given a sequence number.

We can do this by hand. Just before we fill our RAM we can sort what we have and send the list to our target but leave holes in our sequence around each number. Then process the 2nd 1/2 of the numbers the same way using those holes in the sequence.

The networking stack on the far end will assemble the resulting data stream in order of sequence before handing it up to the application.

It's using the network to perform a merge sort. This is a total hack, but I was inspired by the other networking hack listed previously.


I think one way to think about this is from a combinatorics viewpoint: how many possible combinations of sorted number orderings are there? If we give the combination 0,0,0,....,0 the code 0, and 0,0,0,...,1 the code 1, and 99999999, 99999999, ... 99999999 the code N, what is N? In other words, how big is the result space?

Well, one way to think about this is noticing that this is a bijection of the problem of finding the number of monotonic paths in an N x M grid, where N = 1,000,000 and M = 100,000,000. In other words, if you have a grid that is 1,000,000 wide and 100,000,000 tall, how many shortest paths from the bottom left to the top right are there? Shortest paths of course require you only ever either move right or up (if you were to move down or left you would be undoing previously accomplished progress). To see how this is a bijection of our number sorting problem, observe the following:

You can imagine any horizontal leg in our path as a number in our ordering, where the Y location of the leg represents the value.

So if the path simply moves to the right all the way to the end, then jumps all the way to the top, that is equivalent to the ordering 0,0,0,...,0. if it instead begins by jumping all the way to the top and then moves to the right 1,000,000 times, that is equivalent to 99999999,99999999,..., 99999999. A path where it moves right once, then up once, then right one, then up once, etc to the very end (then necessarily jumps all the way to the top), is equivalent to 0,1,2,3,...,999999.

Luckily for us this problem has already been solved, such a grid has (N + M) Choose (M) paths:

(1,000,000 + 100,000,000) Choose (100,000,000) ~= 2.27 * 10^2436455

N thus equals 2.27 * 10^2436455, and so the code 0 represents 0,0,0,...,0 and the code 2.27 * 10^2436455 and some change represents 99999999,99999999,..., 99999999.

In order to store all the numbers from 0 to 2.27 * 10^2436455 you need lg2 (2.27 * 10^2436455) = 8.0937 * 10^6 bits.

1 megabyte = 8388608 bits > 8093700 bits

So it appears that we at least actually have enough room to store the result! Now of course the interesting bit is doing the sorting as the numbers stream in. Not sure the best approach to this is given we have 294908 bits remaining. I imagine an interesting technique would be to at each point assume that that is is the entire ordering, finding the code for that ordering, and then as you receive a new number going back and updating the previous code. Hand wave hand wave.


While receiving the stream do these steps.

1st set some reasonable chunk size

Pseudo Code idea:

  1. The first step would be to find all the duplicates and stick them in a dictionary with its count and remove them.
  2. The third step would be to place number that exist in sequence of their algorithmic steps and place them in counters special dictionaries with the first number and their step like n, n+1 ... ,n+2, 2n, 2n+1, 2n+2...
  3. Begin to compress in chunks some reasonable ranges of number like every 1000 or ever 10000 the remaining numbers that appear less often to repeat.
  4. Uncompress that range if a number is found and add it to the range and leave it uncompressed for a while longer.
  5. Otherwise just add that number to a byte[chunkSize]

Continue the first 4 steps while receiving the stream. The final step would be to either fail if you exceeded memory or start outputting the result once all the data is collected by beginning to sort the ranges and spit out the results in order and uncompressing those in order that need to be uncompressed and sort them when you get to them.


(My original answer was wrong, sorry for the bad math, see below the break.)

وماذا عن هذا؟

The first 27 bits store the lowest number you have seen, then the difference to the next number seen, encoded as follows: 5 bits to store the number of bits used in storing the difference, then the difference. Use 00000 to indicate that you saw that number again.

This works because as more numbers are inserted, the average difference between numbers goes down, so you use less bits to store the difference as you add more numbers. I believe this is called a delta list.

The worst case I can think of is all numbers evenly spaced (by 100), eg Assuming 0 is the first number:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit to the rescue!

If all you had to do was sort them, this problem would be easy. It takes 122k (1 million bits) to store which numbers you have seen (0th bit on if 0 was seen, 2300th bit on if 2300 was seen, etc.

You read the numbers, store them in the bit field, and then shift the bits out while keeping a count.

BUT, you have to remember how many you have seen. I was inspired by the sublist answer above to come up with this scheme:

Instead of using one bit, use either 2 or 27 bits:

  • 00 means you did not see the number.
  • 01 means you saw it once
  • 1 means you saw it, and the next 26 bits are the count of how many times.

I think this works: if there are no duplicates, you have a 244k list. In the worst case you see each number twice (if you see one number three times, it shortens the rest of the list for you), that means you have seen 50,000 more than once, and you have seen 950,000 items 0 or 1 times.

50,000 * 27 + 950,000 * 2 = 396.7k.

You can make further improvements if you use the following encoding:

0 means you did not see the number 10 means you saw it once 11 is how you keep count

Which will, on average, result in 280.7k of storage.

EDIT: my Sunday morning math was wrong.

The worst case is we see 500,000 numbers twice, so the math becomes:

500,000 *27 + 500,000 *2 = 1.77M

The alternate encoding results in an average storage of

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

: (


The trick is to represent the algorithms state, which is an integer multi-set, as a compressed stream of "increment counter"="+" and "output counter"="!" characters. For example, the set {0,3,3,4} would be represented as "!+++!!+!", followed by any number of "+" characters. To modify the multi-set you stream out the characters, keeping only a constant amount decompressed at a time, and make changes inplace before streaming them back in compressed form.

تفاصيل

We know there are exactly 10^6 numbers in the final set, so there are at most 10^6 "!" characters. We also know that our range has size 10^8, meaning there are at most 10^8 "+" characters. The number of ways we can arrange 10^6 "!"s amongst 10^8 "+"s is (10^8 + 10^6) choose 10^6 , and so specifying some particular arrangement takes ~0.965 MiB ` of data. That'll be a tight fit.

We can treat each character as independent without exceeding our quota. There are exactly 100 times more "+" characters than "!" characters, which simplifies to 100:1 odds of each character being a "+" if we forget that they are dependent. Odds of 100:101 corresponds to ~0.08 bits per character , for an almost identical total of ~0.965 MiB (ignoring the dependency has a cost of only ~12 bits in this case!).

The simplest technique for storing independent characters with known prior probability is Huffman coding . Note that we need an impractically large tree (A huffman tree for blocks of 10 characters has an average cost per block of about 2.4 bits, for a total of ~2.9 Mib. A huffman tree for blocks of 20 characters has an average cost per block of about 3 bits, which is a total of ~1.8 MiB. We're probably going to need a block of size on the order of a hundred, implying more nodes in our tree than all the computer equipment that has ever existed can store.). However, ROM is technically "free" according to the problem and practical solutions that take advantage of the regularity in the tree will look essentially the same.

Pseudo-code

  • Have a sufficiently large huffman tree (or similar block-by-block compression data) stored in ROM
  • Start with a compressed string of 10^8 "+" characters.
  • To insert the number N, stream out the compressed string until N "+" characters have gone past then insert a "!". Stream the recompressed string back over the previous one as you go, keeping a constant amount of buffered blocks to avoid over/under-runs.
  • Repeat one million times: [input, stream decompress>insert>compress], then decompress to output

الحل ممكن فقط بسبب الاختلاف بين 1 ميغا بايت و 1 مليون بايت. هناك حوالي 2 إلى القوة 8093729.5 طرق مختلفة لاختيار 1 مليون أرقام مكونة من 8 أرقام مع التكرارات المسموح بها والطلب غير مهم ، لذلك لا تحتوي الآلة التي تحتوي على 1 مليون بايت من ذاكرة الوصول العشوائي فقط على حالات كافية لتمثيل كل الاحتمالات. لكن 1M (أقل من 2k لـ TCP / IP) هو 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-bytes.

قيم رأس القائمة الفرعية الأربعة المحتملة هي:

00 قائمة فرعية فارغة ، لا شيء يتبع.

01 Singleton ، هناك إدخال واحد فقط في القائمة الفرعية والاحتفاظ به 7 بتات.

10 تحتوي القائمة الفرعية على 2 أرقام مميزة على الأقل. يتم تخزين الإدخالات في ترتيب غير تنازلي ، باستثناء أن الإدخال الأخير أقل من أو يساوي الأول. يتيح هذا تحديد نهاية القائمة الفرعية. على سبيل المثال ، سيتم تخزين الأرقام 2،4،6 كـ (4،6،2). سيتم تخزين الأرقام 2،2،3،4،4 (2،3،4،4،2).

11 تحتفظ القائمة الفرعية بتكرارين أو أكثر لرقم واحد. البتات 7 القادمة تعطي الرقم. ثم تأتي صفر أو أكثر من الإدخالات ذات 7 بت مع القيمة 1 ، متبوعة بإدخال 7 بت بالقيمة 0. يحدد طول هيئة القائمة الفرعية عدد مرات التكرار. على سبيل المثال ، سيتم تخزين الأرقام 12،12 كـ (12،0) ، سيتم تخزين الأرقام 12،12،12 على أنها (12،1،0) ، 12،12،12،12 ستكون (12،1) ، 1،0) وما إلى ذلك.

أبدأ بقائمة فارغة ، اقرأ مجموعة من الأرقام في وتخزينها كأعداد صحيحة 32 بت ، وقم بفرز الأرقام الجديدة في المكان (باستخدام heapsort ، على الأرجح) ثم دمجها في قائمة مرتبة مدمجة جديدة. كرر ذلك حتى لا يكون هناك المزيد من الأرقام للقراءة ، ثم اسلك القائمة المدمجة مرة أخرى لتوليد الإخراج.

يمثل السطر أدناه الذاكرة فقط قبل بدء عملية دمج القائمة. "O" s هي المنطقة التي تحتوي على الأعداد الصحيحة 32-بت المفروزة. "X" هي المنطقة التي تحمل القائمة المدمجة القديمة. علامات "=" هي مساحة التوسعة للقائمة المدمجة ، 7 بت لكل عدد صحيح في "O" s. "Z" s هي أخرى عشوائي عشوائي.

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

يبدأ روتين الدمج بالقراءة في أقصى اليسار "O" وفي أقصى اليسار "X" ، ويبدأ الكتابة في أقصى اليسار "=". لا يلتقط مؤشر الكتابة مؤشر قراءة القائمة المدمجة حتى يتم دمج كل الأعداد الصحيحة الجديدة ، لأن كلا المؤشرين يقدمان 2 بت لكل قائمة فرعية و 7 بتات لكل إدخال في القائمة المدمجة القديمة ، وهناك مساحة إضافية كافية إدخالات 7 بت للأرقام الجديدة.

الجزء 2 ، يحشر في 1M

للضغط على الحل أعلاه إلى 1M ، أحتاج إلى جعل تنسيق القائمة المضغوط أكثر ضغطًا قليلاً. سأتخلص من أحد أنواع القوائم الفرعية ، بحيث لن يكون هناك سوى 3 قيم رأسية ممكنة مختلفة لرأس القائمة. ثم يمكنني استخدام "00" و "01" و "1" كقيم رأس القوائم الفرعية وحفظ بعض البتات. أنواع القوائم الفرعية هي:

قائمة فرعية فارغة ، لا شيء يتبع.

B Singleton ، هناك إدخال واحد فقط في القائمة الفرعية والاحتفاظ به 7 بتات.

C تحتوي القائمة الفرعية على رقمين متميزين على الأقل. يتم تخزين الإدخالات في ترتيب غير تنازلي ، باستثناء أن الإدخال الأخير أقل من أو يساوي الأول. يتيح هذا تحديد نهاية القائمة الفرعية. على سبيل المثال ، سيتم تخزين الأرقام 2،4،6 كـ (4،6،2). سيتم تخزين الأرقام 2،2،3،4،4 (2،3،4،4،2).

D تتكون القائمة الفرعية من تكرارين أو أكثر لرقم واحد.

ستكون قيم رأس القائمة الفرعية 3 "A" و "B" و "C" ، لذلك أحتاج إلى طريقة لتمثيل القوائم الفرعية من نوع D.

لنفترض أن لدي رأس قائمة فرعية من النوع C متبوعًا بـ 3 إدخالات ، مثل "C [17] [101] [58]". لا يمكن أن يكون هذا جزءًا من قائمة فرعية من النوع C صالحة كما هو موضح أعلاه ، نظرًا لأن الإدخال الثالث أقل من الثاني ولكنه أكثر من الأول. يمكنني استخدام هذا النوع من الإنشاء لتمثيل قائمة فرعية من نوع D. في بعض الشيء ، في أي مكان لدي "C {00 ؟؟؟؟؟} {1 ؟؟؟؟؟؟} {01 ؟؟؟؟؟}" هي قائمة فرعية مستحيلة من نوع C. سأستخدم هذا لتمثيل قائمة فرعية تتكون من 3 أو أكثر من تكرار رقم واحد. تشفر الكلمات الأولين من 7 بت الرقم (بت "N" أدناه) وتليها صفر أو أكثر {0100001} كلمات متبوعة بكلمة {0100000}.

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

هذا فقط يترك القوائم التي تحمل بالضبط 2 تكرار رقم واحد. سأمثل هؤلاء الذين لديهم نمط ثانٍ مستحيل من نوع C-type: "C {0 ؟؟؟؟؟؟} {11 ؟؟؟؟؟} {10 ؟؟؟؟؟}". هناك الكثير من المساحة ل 7 بتات من الرقم في أول كلمتين ، لكن هذا النمط أطول من القائمة الفرعية التي يمثلها ، مما يجعل الأمور أكثر تعقيدًا بعض الشيء. يمكن اعتبار علامات الاستفهام الخمسة في النهاية ليست جزءًا من النمط ، لذلك لدي: "C {0NNNNNN} {11N ؟؟؟؟} 10" كنمطتي ، مع تكرار الرقم المخزن في "N "ليالي. هذا 2 بت طويلة جدا.

سأضطر إلى اقتراض 2 بت وتسديدها من 4 البتات غير المستخدمة في هذا النمط. عند القراءة ، عند مواجهة "C {0NNNNNN} {11N00AB} 10" ، يتم إخراج مثيلات 2 من الرقم في الحرف "N" ، الكتابة فوق "10" في النهاية مع البتات A و B ، وإرجاع مؤشر القراءة بمقدار 2 بت. تقرأ المدمرة على ما يرام لهذه الخوارزمية ، حيث يتم تمرير كل قائمة المدمجة مرة واحدة فقط.

عند كتابة قائمة فرعية مكونة من تكرارين لرقم واحد ، اكتب "C {0NNNNNN} 11N00" واضبط عداد bits المقترض على 2. في كل كتابة حيث يكون عداد البت المقترض غير صفري ، يتم تقليله لكل جزء مكتوب و يتم كتابة "10" عندما يصل العداد إلى الصفر. لذا فإن الخانتين التاليتين ستدخلان الفتحات A و B ، ثم تنزل الـ "10" إلى النهاية.

مع 3 قيم رأس القائمة الفرعية التي يمثلها "00" و "01" و "1" ، يمكنني تعيين "1" لنوع القائمة الفرعية الأكثر شيوعًا. سأحتاج إلى جدول صغير لتعيين قيم رأس القوائم الفرعية إلى أنواع القوائم الفرعية ، وسأحتاج إلى عداد التكرار لكل نوع من القوائم الفرعية حتى أعرف ما أفضل تعيين لرأس القائمة الفرعية.

يحدث أسوأ تمثيل أدنى للقائمة المدمجة كاملة الملء عندما تكون جميع أنواع القوائم الفرعية مشهورة بنفس القدر. في هذه الحالة أقوم بحفظ 1 بت لكل 3 رؤوس القوائم الفرعية ، وبالتالي فإن حجم القائمة هو 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3 بت. تقريبًا إلى حد كلمة 32 بت ، بت 8302112 بت ، أو 1037764 بايت.

1M ناقص 2K لحالة TCP / IP والمخازن المؤقتة هو 1022 * 1024 = 1046528 بايت ، وترك لي 8764 بايت للعب مع.

ولكن ماذا عن عملية تغيير تخطيط رأس القائمة الفرعية؟ في مخطط الذاكرة أدناه ، "Z" هو حمل عشوائي ، "=" هو مساحة حرة ، "X" هي القائمة المدمجة.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

ابدأ بالقراءة في أقصى اليسار "X" وابدأ الكتابة في أقصى اليسار "=" وعمل بشكل صحيح. عندما تنتهي ، ستكون القائمة المدمجة أقصر قليلاً وستكون في النهاية الخاطئة للذاكرة:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

إذن سأحتاج إلى نقلها إلى اليمين:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

في عملية تغيير مناظرة الرأس ، سيتم تغيير ما يصل إلى 1/3 من رؤوس القوائم الفرعية من 1 بت إلى 2 بت. في أسوأ الحالات ستكون هذه كلها على رأس القائمة ، لذلك سأحتاج على الأقل إلى 781250/3 بتخزين مجاني قبل أن أبدأ ، الأمر الذي يعيدني إلى متطلبات الذاكرة الخاصة بالنسخة السابقة من القائمة المدمجة: (

للتغلب على ذلك ، سوف أقسم الشرائح الفرعية لـ 781250 إلى 10 مجموعات فرعية من 78125 لكل منها. كل مجموعة لديها تعيين رأس القائمة الفرعية المستقلة الخاصة بها. باستخدام الحروف من أ إلى ي للمجموعات:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

تتقلص كل مجموعة فرعية أو تبقى كما هي أثناء تغيير مناظرة رأس القائمة الفرعية:

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

الحالة الأسوأ للتوسع المؤقت لمجموعة قائمة فرعية أثناء تغيير الخرائط هو 78125/3 = 26042 بت ، أقل من 4 كيلو بايت. إذا سمحت بـ 4k بالإضافة إلى 1037764 بايت لقائمة مضغوطة مملوءة بالكامل ، فإن ذلك يترك لي 8764 - 4096 = 4668 بايت لـ "Z" s في خريطة الذاكرة.

يجب أن يكون ذلك كثيرًا لجداول تعيين رؤوس القوائم الفرعية 10 ، و 30 عددًا لرؤوس عناوين القوائم الفرعية ، والعدادات الأخرى القليلة ، والمؤشرات ، والمخازن المؤقتة الصغيرة التي سأحتاج إليها ، والمساحة التي استخدمتها بدون ملاحظة ، مثل مساحة مكدس لعناوين إرجاع المكالمات الوظيفية ، و المتغيرات المحلية.

الجزء 3 ، كم من الوقت يستغرق لتشغيل؟

باستخدام قائمة مضغوطة فارغة ، سيتم استخدام رأس القائمة من 1 بايت لقائمة فرعية فارغة ، وسيكون حجم بداية القائمة 781250 بت. في أسوأ الحالات ، تزداد القائمة 8 بت لكل رقم مضاف ، لذا يلزم 32 + 8 = 40 بتة من المساحة الحرة لكل من أرقام 32-بت يتم وضعها أعلى مخزن القائمة ثم يتم فرزها ودمجها. في أسوأ الحالات ، يؤدي تغيير تعيين رأس القائمة الفرعية إلى استخدام مساحة 2 * 781250 + 7 * إدخالات - 781250/3 بت.

مع سياسة تغيير تخطيط رأس القائمة الفرعية بعد كل عملية دمج خامسة بمجرد وجود 800000 رقم على الأقل في القائمة ، سيشمل أسوأ حالة تشغيل ما مجموعه حوالي 30 مليون من نشاط القراءة والكتابة المدمجة.

مصدر:

http://nick.cleaton.net/ramsortsol.html


You just need to store the differences between the numbers in sequence, and use an encoding to compress these sequence numbers. We have 2^23 bits. We shall divide it into 6bit chunks, and let the last bit indicate whether the number extends to another 6 bits (5bits plus extending chunk).

Thus, 000010 is 1, and 000100 is 2. 000001100000 is 128. Now, we consider the worst cast in representing differences in sequence of a numbers up to 10,000,000. There can be 10,000,000/2^5 differences greater than 2^5, 10,000,000/2^10 differences greater than 2^10, and 10,000,000/2^15 differences greater than 2^15, etc.

So, we add how many bits it will take to represent our the sequence. We have 1,000,000*6 + roundup(10,000,000/2^5)*6+roundup(10,000,000/2^10)*6+roundup(10,000,000/2^15)*6+roundup(10,000,000/2^20)*4=7935479.

2^24 = 8388608. Since 8388608 > 7935479, we should easily have enough memory. We will probably need another little bit of memory to store the sum of where are when we insert new numbers. We then go through the sequence, and find where to insert our new number, decrease the next difference if necessary, and shift everything after it right.


يرجى الاطلاع على الإجابة الصحيحة الأولى أو الإجابة الأخيرة باستخدام الترميز الحسابي . أدناه قد تجد بعض المرح ، ولكن ليس حل مقاوم للرصاص 100٪.

هذه مهمة مثيرة للاهتمام ، وهنا حل آخر. آمل أن يجد شخص ما النتيجة مفيدة (أو على الأقل مثيرة للاهتمام).

المرحلة 1: هيكل البيانات الأولية ، نهج الضغط الخام ، النتائج الأساسية

دعونا نفعل بعض الرياضيات البسيطة: لدينا 1M (1048576 bytes) من ذاكرة الوصول العشوائي المتاحة في البداية لتخزين 10 ^ 6 8 أرقام عشرية. [0؛ 99999999]. لذا ، يحتاج الأمر إلى تخزين عدد واحد من 27 بت (مع افتراض استخدام الأرقام غير الموقعة). وبالتالي ، لتخزين تيار الخام ~ سوف تكون هناك حاجة 3.5M من ذاكرة الوصول العشوائي. لقد قال أحدهم بالفعل أنه لا يبدو مجديًا ، لكنني أقول إن المهمة يمكن حلها إذا كانت المدخلات "جيدة بما فيه الكفاية". في الأساس ، فإن الفكرة هي لضغط البيانات المدخلة مع عامل الضغط 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 ) هي خيار جيد للاستمرار. لقد قمت بإعداد رمز بسيط ، ولكن لا تزال هناك بعض التفاصيل التي يجب إبرازها:

  1. تكون الذاكرة محدودة ، لذا فإن الفكرة تتمثل في كتابة الأرقام واستخدام الدلاء المضغوطة (الحجم الديناميكي) كخزن مؤقت
  2. من الأسهل تحقيق عامل ضغط أفضل مع البيانات المكوّنة مسبقًا ، لذلك يوجد مخزن مؤقت ثابت لكل مجموعة (يجب فرز الأرقام من المخزن المؤقت قبل LZMA)
  3. يحمل كل مجموعة نطاقًا محددًا ، لذلك يمكن إجراء الفرز النهائي لكل مجموعة على حدة
  4. يمكن ضبط حجم مجموعة البيانات بشكل صحيح ، لذلك ستكون هناك ذاكرة كافية لفك ضغط البيانات المخزنة والقيام بالفرز النهائي لكل مجموعة على حدة

يرجى ملاحظة أن الكود المرفق هو POC ، ولا يمكن استخدامه كحل نهائي ، إنه يوضح فقط فكرة استخدام العديد من المخازن المؤقتة الصغيرة لتخزين الأرقام المجهضة بطريقة مثلى (ربما مضغوطة). لا يقترح LZMA كحل نهائي. يتم استخدامه كأقصى طريقة ممكنة لإدخال ضغط على هذا PoC.

انظر رمز PoC أدناه (يرجى ملاحظة أنه مجرد عرض توضيحي ، LZMA-Java ستحتاج إلى 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 لصالح نهج أبسط وأفضل (إن أمكن). هناك الكثير من الحلول الجيدة بما في ذلك الترميز الحسابي ، وشجرة Radix وما إلى ذلك.

على أي حال ، سيكون نظام الترميز البسيط ولكن المفيد أكثر توضيحية من مكتبة خارجية أخرى ، مما يوفر بعض الخوارزمية الرائعة. الحل الفعلي بسيط جدًا: نظرًا لوجود دلاء مع بيانات تم تصنيفها جزئيًا ، يمكن استخدام deltas بدلاً من الأرقام.

يُظهر اختبار الإدخال العشوائي نتائج أفضل قليلاً:

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. لا يقدم نتائج سيئة للغاية

يمكن العثور على التعليمات البرمجية الكاملة here ، يمكن العثور على تطبيقات BinaryInput و BinaryOutput here

الاستنتاج النهائي

لا يوجد خاتمة نهائية :) في بعض الأحيان تكون فكرة جيدة بالفعل للانتقال إلى مستوى واحد ومراجعة المهمة من وجهة نظر meta-level .

كان من الممتع قضاء بعض الوقت بهذه المهمة. راجع للشغل ، هناك الكثير من الإجابات المثيرة للاهتمام أدناه. شكرا لاهتمامكم وتهدئة سعيدة.


إجابة جيلمانوف خاطئة جداً في افتراضاتها. يبدأ المضاربة في أساس مقياس غير مجدية من مليون أعداد صحيحة متتالية . هذا يعني عدم وجود ثغرات. تلك الفجوات العشوائية ، مهما كانت صغيرة ، تجعلها حقا فكرة سيئة.

جربها بنفسك. احصل على 1 مليون من الأعداد الصحيحة من 27 بتة ، وقم بفرزها وضغطها باستخدام 7-Zip و xz وكل ما تريده من LZMA. والنتيجة أكثر من 1.5 ميغابايت. الفرضية في الأعلى هي ضغط الأرقام التسلسلية. حتى ترميز دلتا أكثر من 1.1 ميغابايت . ونعتقد أن هذا يستخدم أكثر من 100 ميغابايت من ذاكرة الوصول العشوائي للضغط. لذلك حتى الأعداد الصحيحة المضغوطة لا تتناسب مع المشكلة ولا تهتم بتشغيل وقت استخدام ذاكرة الوصول العشوائي .

يحزنني كيف أن الناس يتفوقون على الرسومات وترشيدها.

#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);

}

Now compress ints.bin with LZMA...

$ 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

Suppose this task is possible. Just prior to output, there will be an in-memory representation of the million sorted numbers. How many different such representations are there? Since there may be repeated numbers we can't use nCr (choose), but there is an operation called multichoose that works on multisets .

  • There are 2.2e2436455 ways to choose a million numbers in range 0..99,999,999.
  • That requires 8,093,730 bits to represent every possible combination, or 1,011,717 bytes.

So theoretically it may be possible, if you can come up with a sane (enough) representation of the sorted list of numbers. For example, an insane representation might require a 10MB lookup table or thousands of lines of code.

However, if "1M RAM" means one million bytes, then clearly there is not enough space. The fact that 5% more memory makes it theoretically possible suggests to me that the representation will have to be VERY efficient and probably not sane.








algorithm sorting embedded ram