Непятничная задачка

← →
Sha © (2005-02-15 12:45) [40]

> default © (15.02.05 12:10) [37]
> отсюда и стремление к теоргранице при возрастании численности групп

Все не так просто. Общая тенденция, конечно, имеется. Но не факт, что всегда для больших групп результат будет лучше, чем для меньших.

← →
default © (2005-02-15 12:48) [41]

Sha © (15.02.05 12:45) [40]
надо
max_number * (max_number-1) *
(max_number-2) * (max_number-3)
при групировках общее число сэконемленных бит равно но поскольку разрозненность сплотнения этих бит разная то и сжимаемость разная
и факт что будет всегда рост

← →
default © (2005-02-15 12:55) [42]

Sha © (15.02.05 12:45) [40]
"при групировках общее число сэконемленных бит равно но поскольку разрозненность сплотнения этих бит разная то и сжимаемость разная"
расплывчатая фраза но я думаю вы поняли о чём я
при перестановках по 2 и по 3 имеем затраты бит
Log2[m(m-1)]+Log2[(m-2)(m-3)]+Log2[(m-4)(m-5)]=
Log2[m(m-1)(m-2)]+Log2[(m-3)(m-4)(m-5)]
как вижно нужное число бит одинаково - оптимум, НО за счёт разрозенности сплотнения имеем ситуацию [37]

← →
Sha © (2005-02-15 13:09) [43]

> default © (15.02.05 12:48) [41]
> надо
> max_number * (max_number-1) * (max_number-2) * (max_number-3)

Ну так это другое кодирование: не [34], а [35] :)

а твой пост default © (15.02.05 12:10) [37] относился
к palva1 (15.02.05 10:09) [34]

← →
default © (2005-02-15 13:17) [44]

Sha © (15.02.05 13:09) [43]
так я так и думал давно:)хотя писал m^2 вместо m(m-1) в посте [30]
это была просто невнимательность
сути дела о чём там говорится это не меняет
так вы ещё сомневаетесь в том что рост очевиден?
логарифмов не хватило?:) понятно что если мы одном месте будем копить состояния лишние, то быстрее экономию бит получить нежели эти состоянии будут копиться не в одном месте
вот так на словах смысл таков
или математически через логарифмы - чем больше округлений тем больше нужно бит а округлений тем больше чем на меньшие грцппы мы разбиваем исходную перестановку

← →
Sha © (2005-02-15 13:23) [45]

> default © (15.02.05 13:17) [44]
> так вы ещё сомневаетесь в том что рост очевиден?

Вовсе нет, см. [40].

Я хочу только, чтобы ты понял, что примерами в математике можно доказать существование, а не всеобщность :)

← →
default © (2005-02-15 13:37) [46]

Sha © (15.02.05 13:23) [45]
считаете что возможны выражения вида?
Round(Log2[m(m-1)])+Round(Log2[(m-2)(m-3)])+Round(Log2[(m-4)(m-5)]) <=
Round(Log2[m(m-1)(m-2)])+Round(Log2[(m-3)(m-4)(m-5)])
?
Round тут округление в ближайшему большему целому

← →
Sha © (2005-02-15 13:53) [47]

> default © (15.02.05 13:37) [46]
> считаете что возможны выражения вида?
> Round(Log2[m(m-1)])+Round(Log2[(m-2)(m-3)])+Round(Log2[(m-4)(m-5)]) <=
> Round(Log2[m(m-1)(m-2)])+Round(Log2[(m-3)(m-4)(m-5)])
> Round тут округление в ближайшему большему целому

Возможность записи не отрицаю.
Истинность надо доказывать.
Но нам не эти выражения нужны.
Твое утверждение было не относительно этих, может быть истинных для любого m, выражений.
Оно касалось нашей конкретной задачи. А для нее даже пользуясь хорошими формулами из-за краевых условий (например 256 на 9 не делится, а на 8 делится) мы можем получить неоптимальный результат.

← →
Sha © (2005-02-15 14:05) [48]

> Sha © (15.02.05 13:53) [47]
Есть более тонкие причины.
В общем, для доказательства или опровержения гипотезы в нашем случае проще написать программу.

← →
palva © (2005-02-15 14:13) [49]

Я попробовал с группами по 8. Получилось 1786 224 - такие пироги.

Вот программа, походил по ней отладчиком. Надеюсь, не ошибся, как в прошлый раз.
{$APPTYPE CONSOLE} var i: Cardinal; sumofbits, max_number: Integer; function log2(n: int64): Integer; var i, r: Integer; begin r := 0; for i := 1 to 64 do begin if Odd(n) then r := i; n := n shr 1; end; Result := r; end; var i64: Int64; begin sumofbits := 0; max_number := 256; for i := 0 to 32 do begin i64 := max_number * max_number; i64 := i64*i64; i64 := i64*i64 - 1; if i64 <= 0 then sumofbits := sumofbits + 64 else sumofbits := sumofbits + log2(i64); max_number := max_number - 8; end; WriteLn(sumofbits, " ", (sumofbits + 7) div 8) // 1698 213 end.
Сразу можно высказать соображение, что избыточность зависит не только от размера группы, но и от основания системы счисления. Поэтому выгодно в начале алгоритма работать группами меньшего размера, а дальше увеличивать размер группы. Размер группы тоже не обязательно должен быть степенью двойки. Возможно, существует какая то оптимальная последовательность: сначала столько-то групп из 2 байтов, потом столько-то из трех и т. д.

← →
palva © (2005-02-15 14:38) [50]

В третьей строчке Cardinal нелогично. Нужно заменить на Integer. Да и комментарий в предпоследней строчке устарел...

← →
Sha © (2005-02-15 14:49) [51]

> palva © (15.02.05 14:13) [49]
> Я попробовал с группами по 8. Получилось 1786 224 - такие пироги.

Я тоже попробовал по варианту [35]: 1699/213

program CodePerm3; {$APPTYPE CONSOLE} function ilog2(c: int64): cardinal; begin; Result:=0; while c<>0 do begin; c:=c shr 1; inc(Result); end; end; var i, maxi: integer; bits, c, t: int64; begin; maxi:=4; //2:1743/218 4:1713/215 8:1699/213 bits:=0; c:=256; while c>0 do begin; t:=1; for i:=1 to maxi do begin; if c=0 then break; t:=t*c; c:=c-1; end; bits:=bits + ilog2(t-1); end; writeln(bits, " ", (bits + 7) div 8); readln; end.

← →
default © (2005-02-15 14:51) [52]

palva © (15.02.05 14:38) [50]
теперь я понял ваше наверно
вы зачем-то рассматриваете комбинации к примеру m^4 когда возможно только m(m-1)(m-2)(m-3) комбинаций
сами внося этим ненужную избыточность...
Sha © (15.02.05 14:05) [48]
вообщем согласен с [40]

← →
default © (2005-02-15 14:55) [53]

palva © (15.02.05 14:13) [49]
" Возможно, существует какая то оптимальная последовательность: сначала столько-то групп из 2 байтов, потом столько-то из трех и т. д."
ясно что чем больше групп с большим число элементов тем лучше - как минимум общая тенденция таково - что так всегда - всё-таки нужно доказать

← →
Sha © (2005-02-15 15:10) [54]

> palva © (15.02.05 14:13) [49]
> Возможно, существует какая то оптимальная последовательность:
> сначала столько-то групп из 2 байтов, потом столько-то из трех и т. д."

> default © (15.02.05 14:55) [53]

Есть интересная модификация [35]: "набивание под завязку".
В этом варианте мы четырьмя байтами кодируем столько, сколько сможем. При этом получаем высокую степень упаковки (1710/214) и высокую скорость.

program CodePerm2; {$APPTYPE CONSOLE} uses SysUtils; function ilog2(c: int64): cardinal; begin; Result:=0; while c<>0 do begin; c:=c shr 1; inc(Result); end; end; var max, bits, c, t: int64; begin; max:=$FFFFFFFF; bits:=0; c:=256; while c>0 do begin; t:=1; while max div t >= c do begin; if c=0 then break; t:=t*c; c:=c-1; end; bits:=bits + ilog2(t-1); end; writeln(bits, " ", (bits + 7) div 8); readln; end.

← →
palva © (2005-02-15 15:10) [55]

default © (15.02.05 14:51) [52]
> вы зачем-то рассматриваете комбинации к примеру m^4 когда возможно только m(m-1)(m-2)(m-3) комбинаций

Настало просветление. Я просто не видел хорошего алгоритма для устранения этой избыточности. Например, кодирую 3-й и 4-й байты 120, 23. Первый из них не больше чем 254, второй не больше чем 253. Я кодирую их как 254*120+23. Теперь, когда я стал отвечать, я увидел правильный алгоритм. Это надо кодировать как 253*120+23. Тогда, конечно, чем длиннее группа, тем выгоднее.

Мне мешала усвоенная очень давно идея позиционной системы счисления.

> default ©

Это интересно:

1. При кодировании с набиванием под завязку по 63 бита (max:=$7FFFFFFFFFFFFFFF;) мы получаем результат 1696/212, очень близкий к теоретическому минимуму (210).

2. Кодирование с набиванием под завязку по 60 битов (max:=$0FFFFFFFFFFFFFFF;) дает лучшее сжатие (1698/213),
чем по 61 биту (max:=$1FFFFFFFFFFFFFFF;) (1699/213), что противоречит твоим ожиданиям.

3. Еще более поразительно то, что результат для 54-битного кодирования (max:=$003FFFFFFFFFFFFF;) (1697/213) лучше, чем для
62-битного (max:=$3FFFFFFFFFFFFFFF;) (1698/213).

Да, интересно.

Sha © (15.02.05 16:02) [56]
хех:)это мне урок на счёт очевидности:)
я вот щас подумываю над доказательство и как паз не вижу безоговорочности роста сжатия при увеличении размеры группы
теперь интересно определить условия при которых "меньшее" кодировании имеет верх над "большим"

default © (15.02.05 16:48) [59]

Причина кроется в "более полном" использовании битов в целом по всем группам.

Количество неполнот может быть большим, но если их величина мала, то суммарная неполнота может оказаться небольшой.

Так устроен мир :)

Sha © (15.02.05 16:56) [60]
это понятно, я хотел какие-нибудь формулы найти для этого...да думаю и смысла-то в этом нет, проще вышеприведёнными алгоритмами проверить

Непятничная задачка Найти похожие ветки