Новый конкурс им. Парсифаля. Задача крайне высокого уровня сложности

[Pashan]

Он чистую информацию (как массив) не сожмет.

Это как? А что такое программа в файле на диске, если не секрет? Это не информация, представленная байтовым массивом?

Архиватор просто отображает один блок информации в другой, предположительно меньшего размера. И умеет делать обратное отображение. То же самое можно сделать с любыми данными в оперативке.

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

[("")(Э_Є)("")]

Это брэд. Нет смысла сжимать числа в диапазоне 1-10. Это же сколько их должно быть, что бы возникла проблема с размером ? Да и если их "такая куча" вполне имеет смысл хранить массив на диски и мапить в оперативку, скорость особо не просядет.

[("")(Э_Є)("")]

Алгоритмов сжатия множество, всё зависит от того, что это за данные. Если допускаются "потери" то вааще куча. Изображение - жыпиг, текст - рары всякие, логически взаимосвязанные данные - нейронные сети. Можно еще использовать GPU фишки текстурные выборки. А представление данных уходит на второй план.

[("")(Э_Є)("")]

Да еще эти Вейвлеты

[Sazary]

("")(Э_Є)(""), первоначальная цель этого топика - подумать над идеями. Возможно, изобрести велосипед. Пусть даже с рваной цепью и с колесом "восьмеркой".
А с уже существующими архиваторами, вроде как, никто тягаться и не собирался )

[("")(Э_Є)("")]

Задачи решать лучше из реального мира, с "реальной" целью и при помощи адекватных средств. А бред каждый придумать может, вот например

typedef        std::list<
					std::list<
						std::list<
							std::list<MType>
							 >
						 >
  					 > 
			   MegaList;

 

std::list<MType> l;
MegaList ml;
...
MType l_arr [N] = ListToArray(l); 
MType ml_arr [N] = ListToArray(ml);

Функция обходит дерево и сохраняет его узлы в одномерный массив. Как такую штуку зашаблонить ?

[alexBlack]

По теме. Зачем вообще что-то хранить ?
Можно просто сгенерировать случайное число.
В примере класс NArray можно рассматривать как n-мерный массив.
Выполняются два основных условия:
- при обращении к ячейке возвращается одно и то-же значение (для каждой ячейки случайное)
- для разных экземпляров класса возвращаются разные значения.

    public class NArray
    {
        public int this[params int[] x]
        {
            get 
            {
                int k = 0;
                for (int i = 0; i < x.Length; i++)
                {
                    k = k * 10 + x[i];
                }
                Random r = new Random(seed+k);
                return r.Next(10);
            }
        }

        private static Random rnd = 
            new Random(unchecked((int) (DateTime.Now.Ticks)));
        private int seed = rnd.Next();
    }

    class Example
    {
        static void Main()
        {
            NArray a = new NArray();
            Console.WriteLine(a[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

Итого 0 байт для любой размерности.

[Sazary]

Сообщение от alexBlack

Можно просто сгенерировать случайное число.

А если есть конкретный N-мерный массив, заполненный определенными значениями?
Ведь, как я понимаю, здесь предложено заполнять случайными значениями только для примера.

------------------------
------------------------
В общем, такая идея.

N-мерный массив представлен в виде одномерного (в общем, так, как обсуждали в прошлой теме).
Выделяем память под новый массив из char, размером в SIZE/2 + 1, где SIZE - размер исходного массива.
Потом нужно сделать таблицу битовых сопоставлений. Пусть у нас всего 10 возможных вариантов для элемента (например, числа от 0 до 9).
Тогда 0 = 0000, 1 = 0001, 2 = 0010...и т.д.
Каждый элемент нового массива будет таким образом хранить два элемента исходного массива.
В итоге, для массива char'ов используемая память уменьшится в 2 раза, а для массива int'ов - в 8.

Исходный массив можно удалить. Чтобы получить значение элемента, сначала получаем его "реальный" индекс в исходном массиве. Потом берем нужный элемент нового массива (реальный индекс / 2), отделяем нужные 4 бита и преобразуем в соответствии с таблицей.

Очень лень писать функцию преобразования
Но идея такая )

[Парсифаль]

Я так и знал, что все сойдется на битовых преобразованиях. Сожмите еще..
Надо сжать на порядок - это цель)

[Парсифаль]

А бред каждый придумать может, вот например

По Вашему я придумал бред? Если этот этюд-головоломка кажется бредом - это повод этим бредом не заниматься. Смотрите другие темы.