Задача на миллион

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

но блять сжать на столько без сохранения порядка это ахуенно я считаю

никто еще не предложил способ даже близко похожий на сжатие с сохранением индексации

Чувак, почитай про архиваторы. http://log.toeoda.com/Compression/Archivers/archivers.htm

Первые три метода такие очевидные, что я до них сам додумался минут за 20, при том, что такой обработкой данных никогда не занимался, остальные хитрее, я не въехал до конца.

Самое простое, что можно ебануть:

Анализируешь свой массив и ищешь самую популярную маску. Чтобы не заебываться, допустим, по старшим 6-8 битам, ищешь самую частую комбинацию. Точнее максимальным должно быть кол-во бит, умноженное на кол-во повторов. Допустим, оказалось, что у тебя у 400к чисел старшие биты "001010" 6х400=2.4мегабита инфы. Ебашишь второй массив с кодами, 1 и 0 тупо.

Смотришь - первое число не подходит, ебашим во второй массив 0, а в конечный полностью 32 бита слова, смотрим второе - подходит, ебашим во второй массив 1, а в конечный ебашим 26 бит слова, отрезав старшие биты, смотрим третье слово, не подхоодит: во второй - ноль, ко второму слову конечного массива в конец дописываем 6 старших бит третьего слова, а оставшиеся 26 в следующее. и т.д. и таким образом прессуем слова, вырезая повторяющийся кусок, кодируя его во второй массив 1 либо 0. Он займет 2мегабита инфы. Потом этот второй массив ебашишь в конец главного, а в начале делаешь пару меток для проги, пишешь туда слово, которое заменял и гг.

при восстановлении надо будет идти с самого начала: будешь смотришь на единичку, берешь 001010, плюсуешь к нему 26 бит, видишь 0 - копируешь все 32 бита. и т.д.

получишь 0.4мегаБИТА сжатия за один проход при хуевом раскладе.

маска может быть и не в начале 6 подряд, а например такая: ххх0 х101 ххх0 1010 1ххх хххх 0ххх ххх1

12 бит. на кодирование этой хуйни уйдет 2мегабита, значит если такая маска встречается в массиве чаще 167тыс. раз, то ты начинаешь получать профит.

граничное условие:

2 бита маски - нахуй не надо.

3 бита - более 667тыс

4 бита - более 500

5 более 400

6 - 333тыс

7 - 286

8 - 250

и т.д.

при кодировании двух масок вспомогательный второй массив займет максимум 3мегабита и т.д.

надеюсь автор отпишется получил ли он автомат

Только вот с массивом постфиксов такую хуйню ебашить нельзя, там порядок важен

бля лол точно

а не ну типа можно переделать немного, у нас же для одинаковых префиксов постфикс идет посорченый

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

но блять сжать на столько без сохранения порядка это ахуенно я считаю

никто еще не предложил способ даже близко похожий на сжатие с сохранением индексации

Чувак, почитай про архиваторы. http://log.toeoda.co...s/archivers.htm

Первые три метода такие очевидные, что я до них сам додумался минут за 20, при том, что такой обработкой данных никогда не занимался, остальные хитрее, я не въехал до конца.

 

Самое простое, что можно ебануть:

 

Анализируешь свой массив и ищешь самую популярную маску. Чтобы не заебываться, допустим, по старшим 6-8 битам, ищешь самую частую комбинацию. Точнее максимальным должно быть кол-во бит, умноженное на кол-во повторов. Допустим, оказалось, что у тебя у 400к чисел старшие биты "001010" 6х400=2.4мегабита инфы. Ебашишь второй массив с кодами, 1 и 0 тупо.

Смотришь - первое число не подходит, ебашим во второй массив 0, а в конечный полностью 32 бита слова, смотрим второе - подходит, ебашим во второй массив 1, а в конечный ебашим 26 бит слова, отрезав старшие биты, смотрим третье слово, не подхоодит: во второй - ноль, ко второму слову конечного массива в конец дописываем 6 старших бит третьего слова, а оставшиеся 26 в следующее. и т.д. и таким образом прессуем слова, вырезая повторяющийся кусок, кодируя его во второй массив 1 либо 0. Он займет 2мегабита инфы. Потом этот второй массив ебашишь в конец главного, а в начале делаешь пару меток для проги, пишешь туда слово, которое заменял и гг.

 

при восстановлении надо будет идти с самого начала: будешь смотришь на единичку, берешь 001010, плюсуешь к нему 26 бит, видишь 0 - копируешь все 32 бита. и т.д.

 

получишь 0.4мегаБИТА сжатия за один проход при хуевом раскладе.

 

маска может быть и не в начале 6 подряд, а например такая: ххх0 х101 ххх0 1010 1ххх хххх 0ххх ххх1

12 бит. на кодирование этой хуйни уйдет 2мегабита, значит если такая маска встречается в массиве чаще 167тыс. раз, то ты начинаешь получать профит.

 

граничное условие:

2 бита маски - нахуй не надо.

3 бита - более 667тыс

4 бита - более 500

5 более 400

6 - 333тыс

7 - 286

8 - 250

и т.д.

при кодировании двух масок вспомогательный второй массив займет максимум 3мегабита и т.д.

не ну это хуйня же

нужно чтобы в самом худшем случае было немного больше двух

для 12битовой маски, если я правильно понял, худший случай это 247, что вообще пиздец хуево

у тебя тервер есть в курсе? посчитай вероятность того, что в миллионе рандомных 32битных чисел есть 500 тысяч чисел, у которых 4 бита совпадают.

я думаю надо захуярить 2 варианта

первый если большинство чисел большие вариант с повторениями

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

у тебя тервер есть в курсе? посчитай вероятность того, что в миллионе рандомных 32битных чисел есть 500 тысяч чисел, у которых 4 бита совпадают.

всм у тебя маска для определенных позиций же

не важна вероятность, нужно чтобы алгоритм в худшем случае сжимал до немного больше 2 мегабайт, так что в некоторых случаях это будет норм, но отталкиваться надо от худшего случая

ну вопщем все, у меня автомат

у него способ немного отличался от моего, так же надо было разделять число по 2 байта, но там делалось типа двумерного массива

ну и офк индексация была не нужна, ибо как я и говорил, с ней сжать нихуя не получится так сильно, это тупо невозможно

спасибо всем, кто участвовал в дискуссии

у тебя тервер есть в курсе? посчитай вероятность того, что в миллионе рандомных 32битных чисел есть 500 тысяч чисел, у которых 4 бита совпадают.

всм у тебя маска для определенных позиций же

не важна вероятность, нужно чтобы алгоритм в худшем случае сжимал до немного больше 2 мегабайт, так что в некоторых случаях это будет норм, но отталкиваться надо от худшего случая

ну вопщем все, у меня автомат

у него способ немного отличался от моего, так же надо было разделять число по 2 байта, но там делалось типа двумерного массива

ну и офк индексация была не нужна, ибо как я и говорил, с ней сжать нихуя не получится так сильно, это тупо невозможно

спасибо всем, кто участвовал в дискуссии

у тебя тервер есть в курсе? посчитай вероятность того, что в миллионе рандомных 32битных чисел есть 500 тысяч чисел, у которых 4 бита совпадают.

всм у тебя маска для определенных позиций же

не важна вероятность, нужно чтобы алгоритм в худшем случае сжимал до немного больше 2 мегабайт, так что в некоторых случаях это будет норм, но отталкиваться надо от худшего случая

а захуярить анализ массива и сделать для худшего случая другой вид сжатия?

 

ну вопщем все, у меня автомат

у него способ немного отличался от моего, так же надо было разделять число по 2 байта, но там делалось типа двумерного массива

ну и офк индексация была не нужна, ибо как я и говорил, с ней сжать нихуя не получится так сильно, это тупо невозможно

спасибо всем, кто участвовал в дискуссии

твой препод идиот

ну судя по тому, что ты написал выше про анализ массива, идиот тут ты

разбить 4 байтовый массив на два массива по 2 байта это просто топ1 оптимизация

разбить 4 байтовый массив на два массива по 2 байта это просто топ1 оптимизация

у тебя тервер есть в курсе? посчитай вероятность того, что в миллионе рандомных 32битных чисел есть 500 тысяч чисел, у которых 4 бита совпадают.

всм у тебя маска для определенных позиций же

не важна вероятность, нужно чтобы алгоритм в худшем случае сжимал до немного больше 2 мегабайт, так что в некоторых случаях это будет норм, но отталкиваться надо от худшего случая

а захуярить анализ массива и сделать для худшего случая другой вид сжатия?

 

ну вопщем все, у меня автомат

у него способ немного отличался от моего, так же надо было разделять число по 2 байта, но там делалось типа двумерного массива

ну и офк индексация была не нужна, ибо как я и говорил, с ней сжать нихуя не получится так сильно, это тупо невозможно

спасибо всем, кто участвовал в дискуссии

твой препод идиот

ну судя по тому, что ты написал выше про анализ массива, идиот тут ты

идиоты ты и твой препод ибо без индексации это хуита

погугли "сжатие" и ты поймешь что сжатие предполагает возможность восстановление в ИСХОДНОМ виде

а вот если бы ты уебок погугли то ты бы возможно нашел это

http://ru.wikipedia....атие_без_потерь

и увидел бы теорему в самом начале

хотя ты видимо слишком идиот, чтобы понять ее, но я надеюсь ты постараешься

так вот чтобы сжать что-то без потерь эффективно, нужно иметь дополнительную информацию, как при сжатии звука например

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

там речь идет о картинках музыке и тд

у тебя же индексированный массив

теряя индексы теряется весь смысл массива в 99% случаев

привет вам всем студентам и преподавателям шараги

Допустимость потерь

 

 

если в условии этого нет - составитель задачи уебан

и это факт

самая ебучая тема на моей памяти

там речь идет о картинках музыке и тд

у тебя же индексированный массив

теряя индексы теряется весь смысл массива в 99% случаев

привет вам всем студентам и преподавателям шараги

 

Допустимость потерь

 

 

если порядок не важен эту нужно указывать в условии задачи

если в условии этого нет - составитель задачи уебан

и это факт

я просто хуй знает что тебе сказать

ты понимаешь что это НЕВОЗМОЖНО?

просто передай преподу что он идиот вот и всё

сокол подзаебал уже

Смотри, как я сжал данные по твоему методу:

а6б2в5д4е7ё2ж1и7й1к2л3н1о7п3р3с6т6ф1х1ч2ы3ю1

Нихуя не понятно? Исходная фраза была такая: "ты и твой препод - долбоёбы, если считаете, что подсчёт количества вариантов префиксов равен сжатию данных.", я просто посчитал все варианты букв.

Передай своему долбоебскому преподу охуенную методику сжатия данных, без сохранения порядка:

1. считаем количество нулей в массиве.

2. считаем кол-во единиц ( 4мб - кол-во нулей)

3. по теории вероятности их будет примерно по два мегабайта, но чего-то окажется меньше.

4. ебашишь меньшее число в ответ.

5. Та-дам! ты "сжал" исходный массив в меньше, чем два мегабайта. Кол-во единиц находишь вычитанием.

иди за нобелевкой, долбоеб.

надеюсь, что это не твой препод - рак, а ты, т.к хуево понял задание и сформулировал его здесь "своими словами", проебав половину смысла.

ах, ты его наверное просто посортил, взял массив возможных префиксов, ... и ебанул сюда.

Смотри, как я сжал данные по твоему методу:

 

а6б2в5д4е7ё2ж1и7й1к2л3н1о7п3р3с6т6ф1х1ч2ы3ю1

 

Нихуя не понятно? Исходная фраза была такая: "ты и твой препод - долбоёбы, если считаете, что подсчёт количества вариантов префиксов равен сжатию данных.", я просто посчитал все варианты букв.

 

Передай своему долбоебскому преподу охуенную методику сжатия данных, без сохранения порядка:

1. считаем количество нулей в массиве.

2. считаем кол-во единиц ( 4мб - кол-во нулей)

3. по теории вероятности их будет примерно по два мегабайта, но чего-то окажется меньше.

4. ебашишь меньшее число в ответ.

5. Та-дам! ты "сжал" исходный массив в меньше, чем два мегабайта. Кол-во единиц находишь вычитанием.

 

иди за нобелевкой, долбоеб.

 

надеюсь, что это не твой препод - рак, а ты, т.к хуево понял задание и сформулировал его здесь "своими словами", проебав половину смысла.

 

ах, ты его наверное просто посортил, взял массив возможных префиксов, ... и ебанул сюда.

просто сделал мой день :lol:

надеюсь повылезают еще долбаебы вроде тебя и сокола :lol:

один долбаеб с группы кстати пытался ему пропихнуть сжатие по сраному ключу

поржал с него знатно :lol:

он такой еще типа "Ну архиваторы же по такому алгоритму работают..."