Обновить
Комментарии 16
Лучше бы zlib переписали. Было бы гораздо нагляднее. И сравнивать скорость сжатия и распаковки, и потребляемые ресурсы и читаемость кода по мере продвижения к цели.

Скорость сжатия и распаковки не должны измениться, по идее. Алгоритмы же не изменяют. Потребляемые ресурсы при "тупом" переписывании должны вырасти. Раст всё таки не про скорость и ресурсы (не в первую очередь), а про безопасность работы с ресурсами.

«В теории нет разницы между теорией и практикой. А на практике есть.» — Тут даже дело не в скорости. В самом процессе.

Вот например как на раст будет выглядеть программа, для равномерного растяжения колонок?
// scale.c
#include <stdio.h>
#include <stdlib.h>

int  scale_cmp(const void* a,const void *b) { return *(int*)a > *(int*)b; }
void scale(int n,int *x,int *w,int D,int *t) {
    int d,i,s,k;
    s=0;for(i=0;i<n;i++) s+=x[i];
    d=0;for(i=0;i<n;i++) {
      d+=w[i]=(x[i]*D)/s; t[i]=( ((w[i]+1)*s+x[i]-1)/x[i] )*n+i;
    }
    qsort(t,n,sizeof(*t),scale_cmp);
    for(k=0;d<D;k++,d++) {
        i=t[k]%n; w[i]++; t[k]=( ((w[i]+1)*s+x[i]-1)/x[i] )*n+i;
        if (t[k]<t[n-1]) {
          if (t[k]>t[k+1]) qsort(t+k,n-k,sizeof(*t),scale_cmp); k--;
        }
    }
}

int main(int argc,char **argv) {
    enum { n=5 };
    int i,D,w[n],t[n],x[n]={ 30,3,3,31,30 };
    for(D=1;D<=200;D++) {
        scale(n,x,w,D,t);
        printf("%3d:",D); for(i=0;i<n;i++) printf(" %2d",w[i]);
        printf("\n");
    }
    return 0;
}

А можно с чуть менее поганым форматированием? А то тут есть строка


if (t[k]>t[k+1]) qsort(t+k,n-k,sizeof(*t),scale_cmp); k--;

и из-за форматирования я не уверен, действительно ли k--; должно выполняться безусловно или же тут забыли фигурные скобки у оператора if.

Да k-- выполняется не зависимо от условия.
output для проверки
1: 1 0 0 0 0
2: 1 0 0 1 0
3: 1 0 0 1 1
4: 2 0 0 1 1
5: 2 0 0 2 1
6: 2 0 0 2 2
7: 3 0 0 2 2
8: 3 0 0 3 2
9: 3 0 0 3 3
10: 4 0 0 3 3
11: 4 0 0 4 3
12: 4 0 0 4 4
13: 4 0 0 5 4
14: 5 0 0 5 4
15: 5 0 0 5 5
16: 5 0 0 6 5
17: 6 0 0 6 5
18: 6 0 0 6 6
19: 6 0 0 7 6
20: 7 0 0 7 6
21: 7 0 0 7 7
22: 8 0 0 7 7
23: 8 0 0 8 7
24: 8 0 0 8 8
25: 8 0 0 9 8
26: 9 0 0 9 8
27: 9 0 0 9 9
28: 9 0 0 10 9
29: 10 0 0 10 9
30: 10 1 0 10 9
31: 10 1 1 10 9
32: 10 1 1 10 10
33: 10 1 1 11 10
34: 11 1 1 11 10
35: 11 1 1 11 11
36: 11 1 1 12 11
37: 12 1 1 12 11
38: 12 1 1 12 12
39: 12 1 1 13 12
40: 13 1 1 13 12
41: 13 1 1 13 13
42: 13 1 1 14 13
43: 14 1 1 14 13
44: 14 1 1 14 14
45: 14 1 1 15 14
46: 15 1 1 15 14
47: 15 1 1 15 15
48: 15 1 1 16 15
49: 16 1 1 16 15
50: 16 1 1 16 16
51: 16 1 1 17 16
52: 17 1 1 17 16
53: 17 1 1 17 17
54: 17 1 1 18 17
55: 18 1 1 18 17
56: 18 1 1 18 18
57: 18 1 1 19 18
58: 19 1 1 19 18
59: 19 1 1 19 19
60: 19 1 1 20 19
61: 20 1 1 20 19
62: 20 2 1 20 19
63: 20 2 2 20 19
64: 20 2 2 20 20
65: 20 2 2 21 20
66: 21 2 2 21 20
67: 21 2 2 21 21
68: 21 2 2 22 21
69: 22 2 2 22 21
70: 22 2 2 23 21
71: 22 2 2 23 22
72: 23 2 2 23 22
73: 23 2 2 23 23
74: 23 2 2 24 23
75: 24 2 2 24 23
76: 24 2 2 24 24
77: 24 2 2 25 24
78: 25 2 2 25 24
79: 25 2 2 25 25
80: 25 2 2 26 25
81: 26 2 2 26 25
82: 26 2 2 27 25
83: 26 2 2 27 26
84: 27 2 2 27 26
85: 27 2 2 28 26
86: 27 2 2 28 27
87: 28 2 2 28 27
88: 28 2 2 29 27
89: 28 2 2 29 28
90: 29 2 2 29 28
91: 29 2 2 30 28
92: 29 2 2 30 29
93: 30 2 2 30 29
94: 30 3 2 30 29
95: 30 3 3 30 29
96: 30 3 3 31 29
97: 30 3 3 31 30
98: 31 3 3 31 30
99: 31 3 3 32 30
100: 31 3 3 32 31
101: 32 3 3 32 31
102: 32 3 3 33 31
103: 32 3 3 33 32
104: 33 3 3 33 32
105: 33 3 3 34 32
106: 33 3 3 34 33
107: 34 3 3 34 33
108: 34 3 3 35 33
109: 34 3 3 35 34
110: 34 3 3 36 34
111: 35 3 3 36 34
112: 35 3 3 36 35
113: 35 3 3 37 35
114: 36 3 3 37 35
115: 36 3 3 37 36
116: 36 3 3 38 36
117: 37 3 3 38 36
118: 37 3 3 38 37
119: 38 3 3 38 37
120: 38 3 3 39 37
121: 38 3 3 39 38
122: 38 3 3 40 38
123: 39 3 3 40 38
124: 39 3 3 40 39
125: 39 3 3 41 39
126: 40 3 3 41 39
127: 40 4 3 41 39
128: 40 4 4 41 39
129: 40 4 4 41 40
130: 40 4 4 42 40
131: 41 4 4 42 40
132: 41 4 4 42 41
133: 41 4 4 43 41
134: 42 4 4 43 41
135: 42 4 4 43 42
136: 42 4 4 44 42
137: 43 4 4 44 42
138: 43 4 4 44 43
139: 43 4 4 45 43
140: 44 4 4 45 43
141: 44 4 4 45 44
142: 44 4 4 46 44
143: 45 4 4 46 44
144: 45 4 4 46 45
145: 45 4 4 47 45
146: 46 4 4 47 45
147: 46 4 4 47 46
148: 46 4 4 48 46
149: 47 4 4 48 46
150: 47 4 4 48 47
151: 47 4 4 49 47
152: 48 4 4 49 47
153: 48 4 4 49 48
154: 48 4 4 50 48
155: 49 4 4 50 48
156: 49 4 4 50 49
157: 49 4 4 51 49
158: 50 4 4 51 49
159: 50 5 4 51 49
160: 50 5 5 51 49
161: 50 5 5 51 50
162: 50 5 5 52 50
163: 51 5 5 52 50
164: 51 5 5 52 51
165: 51 5 5 53 51
166: 52 5 5 53 51
167: 52 5 5 54 51
168: 52 5 5 54 52
169: 53 5 5 54 52
170: 53 5 5 54 53
171: 53 5 5 55 53
172: 54 5 5 55 53
173: 54 5 5 55 54
174: 54 5 5 56 54
175: 55 5 5 56 54
176: 55 5 5 56 55
177: 55 5 5 57 55
178: 56 5 5 57 55
179: 56 5 5 58 55
180: 56 5 5 58 56
181: 57 5 5 58 56
182: 57 5 5 59 56
183: 57 5 5 59 57
184: 58 5 5 59 57
185: 58 5 5 60 57
186: 58 5 5 60 58
187: 59 5 5 60 58
188: 59 5 5 61 58
189: 59 5 5 61 59
190: 60 5 5 61 59
191: 60 6 5 61 59
192: 60 6 6 61 59
193: 60 6 6 62 59
194: 60 6 6 62 60
195: 61 6 6 62 60
196: 61 6 6 63 60
197: 61 6 6 63 61
198: 62 6 6 63 61
199: 62 6 6 64 61
200: 62 6 6 64 62


ps: format.krzaq.cc

Примерно так. Сразу скажу, что я почти не пытался сделать код более идиоматичным (в частности, не выделил дублирующийся код (((w[i] + 1) * s + x[i] - 1) / x[i]) * n + i). Отмечу некоторую странность: если процент растяжения D (это же проценты, да?) составляет ровно 100 процентов, то шкала вроде должна получаться такой же, как и исходная, чего не наблюдается. Что-то ещё сказать не могу, потому что в логику вникнуть не пытался.

Нет не проценты. в x[] — ширины столбцов (или длины слов), а D — это желаемая ширина, w[] — результат. Оригинал, для примера, получиться при D=97.

Я раст не знаю, так посматриваю. Но со слайсами получилось хорошо. Думал будет хуже.

ps: Почему просто не написать t[k..n].sort() и x.iter().sum()?

ps: Почему просто не написать t[k..n].sort() и x.iter().sum()?

Второе — из-за того, что нужно каким-то образом уточнять тип, сам компилятор не выводит (собственно, именно это вы и сделали, явно указав тип у s). Первое — из-за того, что sort использует стабильную сортировку и выделяет буфер для промежуточных значений. Правда, конкретно в этом случае оно не проявляется, потому что маленькие слайсы сортируются in-place, но для больших слайсов это уже имеет значение.

Например, вот так:
play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=466e2f5667ac1d9484bdbe5c99e65cb5

Написал собственную сортировку дробей на коленке, которая сравнивает дроби, а не их целые части (как это было сделано в референсе). Вроде, сравнивать дроби правильнее: первая строчка, например, должна быть с четвертой единичкой, а не с первой.
Да наверно так будет лучше.
scale.c
// scale.c
#include <stdio.h>
#include <stdlib.h>

typedef struct { int n,d,i; } scale_wrk;
int scale_cmp(const void* lv,const void *rv) {
    scale_wrk *x=(scale_wrk *)lv, *y=(scale_wrk *)rv;
    int u=x->n*y->d, v=y->n*x->d;
    return u==v ? (x->i > y->i) : u > v;
}
void scale(int n,int *x,int *w,int D,scale_wrk *t) {
    int d,i,s,k;
    s=0;for(i=0;i<n;i++) s+=x[i];
    d=0;for(i=0;i<n;i++) {
        d+=w[i]=x[i]*D/s; 
        t[i].n=w[i]+1; t[i].d=x[i]; t[i].i=i; 
    }
    if (d>=D) return;
    qsort(t,n,sizeof(*t),scale_cmp);
    for(k=0;;) {
        i=t[k].i; w[i]++; if (++d>=D) break; ++t[k].n;
        if (scale_cmp(t+k,t+n-1)) k++;
        else { 
            if (scale_cmp(t+k,t+k+1))
                qsort(t+k,n-k,sizeof(*t),scale_cmp); 
        }
    }
}

int main(int argc,char **argv) {
    enum { n=5 };
    scale_wrk t[n];
    int i,D,w[n],x[n]={ 30,3,3,31,30 };
    for(D=1;D<=200;D++) {
        scale(n,x,w,D,t);
        printf("%3d:",D);
        for(i=0;i<n;i++) printf(" %2d",w[i]);
        printf("\n");
    }
    return 0;
}

ps: Умножение на sum у вас это видимо потому что ночью писали. Порядок дробей не меняется от постоянного положительного множителя, а вот на счет выкидывания порядка следования у меня есть сомнения (доказать отсутствие влияния на конечный результат у меня не получается).
Да, конечно, на sum можно не умножать.

От порядка следования, конечно, результат меняется (при D=2 можно увеличивать первую «30», а можно последнюю).

Но порядок следования в моем коде сохраняется — Rust автоматически выводит порядок для пар, если есть порядок на каждой из компонент (естественным образом: сначала по первой компоненте, а если есть равенство, то по второй). В результате, мне достаточно определить порядок на дробях. А когда я сортирую пару из дроби и индекса, под капотом используется то самое сравнение, которое Вы реализовали явно (а у меня оно вывелось из явного порядка на дробях и стандартного на usize).
Ясно — просто в rust sort по умолчанию это stable_sort
Дело не в stable_sort, можно вызывать ustable, ничего не изменится в результате.

Фокус в вот этой имплементации: doc.rust-lang.org/std/cmp/trait.Ord.html#impl-Ord-61
Если есть порядок на первом и втором элементе пары, то появляется порядок на парах (по которому я и сортирую).
Ничего не понял.
impl<A, B> Ord for (A, B) where
    A: Ord,
    B: Ord + ?Sized, 

Что это значит без фокусов?
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.