1

A bit algorithmic problem, or may be optimization one, or Dynamic Programming.

Let's say we have N files to compress. The average compression ratio is L. The compression time of a file depends on two factors - 1. Size of the file currently being processed, and 2. Memory space left in system (Total = M, occupied = sum of file size of compressed and uncompressed files)

So

t(i) = K * s(i) / (M-L*(s(1)+s(2)+....+s(i))-(s(i+1) + s(i+2) + .....+ s(n))

where s(i) is the size of ith file and t(i) is the time taken to compress ith file.

What I have to do, is to calculate the optimal series of the files to be compressed so that total time required is minimum. So how to compute that series?

4
  • 2
    Sounds a bit like homework, not?
    – Till
    May 4, 2014 at 4:43
  • 1
    Sounds a bit, but it is not. This just came to my mind while I was thinking about practicing questions on DP.
    – kushpf
    May 4, 2014 at 4:44
  • On first, it seems that optimal strategy is first to compress the largest file.
    – Ante
    May 4, 2014 at 8:32
  • @Ante it is actually just the opposite. Check out Ralor's answer :)
    – kushpf
    May 4, 2014 at 16:58

2 Answers 2

2

It seems that the best approach is to sort files by size and process it. This greedy approach may be explained as "compress small file first to avoid compressing it after big file".

Possible approvement is:

if we have two files A,B such that size(A) <= size(B) we can prove that time

t(A,B) <= t(B,A)

A/M + B/(M - L*A) <= B/M + B/(M - L*B)

A*(1/M - 1/(M - L*B)) <= B*(1/M - 1/(M - L*A))

B/A >= (1/M - 1/(M - L*B)) / (1/M - 1/(M - L*A)) = B*(M - L*A) / (A*(M - L*B))

1 >= (M - L*A)/(M - L*B)

-L*B >= -L*A

B >= A

so that mean first equation was right too (if didn't failed somewhere :D)

Sorting give us the guarantee of A < B for every pair of files.

I wrote O(N!) bruteforce for N <= 10. And it gives sorted arrays for every test I can think about.

test : N, L, M, K and N files

8 0.5 80.0 1.0

7 1 6 3 4 5 6 5

result :

0.515769

1 3 4 5 5 6 6 7

#include <iostream>
#include <algorithm>
using namespace std;

// will work bad for cnt > 10 because 10! = 3628800
int perm[] = {0,1,2,3,4,5,6,7,8,9};
int bestPerm[10];
double sizes[10];

double calc(int cnt, double L, double M, double K, double T) {
    double res = 0.0, usedMemory = 0.0;
    for(int i = 0; i < cnt; i++) {
        int ind = perm[i];
        res += K * sizes[ind] / (M - L * usedMemory - (T - usedMemory)); 
        usedMemory += sizes[ind];
    }
    return res;
}

int main() {
    int cnt;
    double L,M,K,T = 0.0;
    cin >> cnt >> L >> M >> K;
    for(int i = 0; i < cnt; i++)
        cin >> sizes[i], T += sizes[i];

    double bruteRes = 1e16;
    int bruteCnt = 1;
    for(int i = 2; i <= cnt; i++)
        bruteCnt *= i;
    for(int i = 0; i < bruteCnt; i++) {
        double curRes = calc(cnt, L, M, K, T);
        if( bruteRes > curRes ) {
            bruteRes = curRes;
            for(int j = 0; j < cnt; j++)
                bestPerm[j] = perm[j];
        }
        next_permutation(perm, perm + cnt);
    }
    cout << bruteRes << "\n";
    for(int i = 0; i < cnt; i++)
            cout << sizes[bestPerm[i]] << " ";
    cout << "\n";

    return 0;
}

Updated Implementation for case when L is different for all files pastebin (it seems that bruteforce prefer to sort them by descending order of compression ratio L[i] and use the smaller files first, if L is equal).

8
  • res += K * sizes[ind] / (M - L * usedMemory - (T - usedMemory)); where T is the total size of the files. However, even this gives the output in ascending order. Thanks. I want to know if you can suggest some changes which results in a trade-off, and either ascending or descending order is not optimal.
    – kushpf
    May 4, 2014 at 16:52
  • @k_programmer I fixed it. It doesn't changed a lot, because it's like invert L = 1-L and substituite M -= T after reading values. My first thoughts was to try ascending and descending order, or find some middle position "k" by ternary search and divide all files to 2 groups, but I found it useless. My friend said that this problem is simple in case when L is same for all files, but we both just think that approvement shown above is right. You can try to run bruteforce on 10^6 of random (but correct) data sets and check whether answer will be sorted in all of them.
    – Ralor
    May 4, 2014 at 17:44
  • What about variable L? Let me try by varying L :)
    – kushpf
    May 5, 2014 at 17:18
  • With variable L, it gives a series neither ascending nor descending - exactly as I wanted! But now the problem is how to calculate the optimal series dynamically (using DP etc) ?
    – kushpf
    May 5, 2014 at 18:36
  • @k_programmer I've updated the post with pastebin link, problem is still easy when L[i] is different) Greedy still wins)
    – Ralor
    May 5, 2014 at 22:18
0

Suppose you have a schedule that claims to be optimal. Consider any file and the one processed just after it. If you could improve the schedule by swapping them, it couldn't be optimal. So if you can show that it is always best to process a small file before a large one when the two are side by side then you can show that the best schedule is in sorted order with the smallest files first, because you can improve any other schedule.

Because you are just swapping two adjacent files the times taken to process files before and after these two are not changed - the same amount of memory is available before and after. You might as well scale the problem so that one of the files is of size one unit. Supposing that you have a total of K units of memory free before the first file, and supposing the second file is of size x units with a compression ratio of 1:L you end up with something like 1/K + x/(K+L) - x/K - 1/(K - xL) as the difference in compression times due to this pair of files - my algebra is horribly error-prone, but I think this boils down to something like L^2x(1-x) over something complicated but positive, which shows that for a pair of files you always want to compress the short one first, so by what I said earlier the best schedule is in sorted order with the shortest file first.

1
  • Yea, it seems so, and almost proved by Ralor's answer. Very nice explanation! However, it'd be great if you suggest some changes in the question itself such that the optimal order isn't either of ascending or descending order.
    – kushpf
    May 4, 2014 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.