kouzdra: Задачка забавная

(Добавить комментарий)

	lolepezy 2005-10-28 16:29 (ссылка)
	Может проще смоделировать ? Программку написать можно за полчаса. Аналитика здесь сложная очень, скорее всего. Ну либо простая, но не очевидная. (Ответить) (Ветвь дискуссии)

kouzdra
2005-10-28 16:51 (ссылка)

Вопрос, именно - "как" - приходящая в голову идея -
брать с запасом и по модулю. Работает неплохо, но
вряд ли это оптимально. Можно попробовать какой-нибудь
код с коррекцией сверху прикрутить (и пользоваться
возможностью делать ошибки).

Она в принципе неактуальна (соображение из
которого она возникла не подтвердилось), но
все равно любопытно.

(Ответить) (Уровень выше) (Ветвь дискуссии)

lolepezy
2005-10-28 17:13 (ссылка)

Если я все правильно понимаю, то задача сводится к тому, чтобы минимизировать кол-во попаданий единиц в "уже занятые" биты.
Поэтому логичнее всего, наверное, использовать схемы, вроде тех, что используются для генерации псевдослучайных последовательностей.
Что-то типа код=(x_n-z)%m, m - большое число, близкое к 2^k.
И плюс к этому несколько попыток с разными z и m.
А дальше все зависит от распределения исходной последовательности.

Ну вы это и сказали, в принципе :)

(Ответить) (Уровень выше)

	ifp5 2005-10-28 16:35 (ссылка)
	А можно как-то поформальнее сформулировать? (Ответить) (Ветвь дискуссии)

	kouzdra 2005-10-28 16:52 (ссылка)
	Ну как-то доопределить источник последовательностей (например - марковский) и максимизировать мат.ожидание длины последовательности. Но это скорее ненужное усложнение. (Ответить) (Уровень выше)

	qwerty 2005-10-28 20:37 (ссылка)
	Если ты про флэшки, то реальная задача не совсем такая - не обязательно модифицированную область писать на место, можно ее перемэпить. (Ответить) (Ветвь дискуссии)

kouzdra
2005-10-28 21:20 (ссылка)

Речь о том, чтобы попробовать родить что-то более пристойное, чем JFFS2. А там возможность хотя бы 2-3 раза подправить управляющие структуры без их перемещения может довольно много сэкономить.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	qwerty 2005-10-28 21:45 (ссылка)
	Может быть, функцию стоимости минимизировать, включая и перемапливание? Мапить можно поверх ранее использованной области, по возможности с внесением мимимума новых единиц. (Ответить) (Уровень выше) (Ветвь дискуссии)

kouzdra
2005-10-28 22:28 (ссылка)

Нет - похоже, что не надо. Скорее - просто "патчи" к управляющим структурам накапливать в логе. и коммитить его "оптом" вреямя от времени в реальеные структуры. Собственно проблема именно в том, что "перемапливание" в файловой системе само по себе влечет дальнейший update всяких индексов и так - до корня. Хочется это делать пореже.

(Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2005-10-29 00:21 (ссылка)

Да, это хороший вариант. А сами патчи посильнее пожать, по возможности используя поменьше единиц.

А почему бы и не использовать повторно подходящие освободившиеся блоки? Развесить временные структурки для быстрого поиска в дровах. Хотя вероятность, конечно, не велика.

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

(Ответить) (Уровень выше)

	polytheme 2005-10-29 12:56 (ссылка)
	C*k/log(n), как кажется. выжженные биты информации не несут, среднее количество выжигаемых бит на каждом шаге - log(n)/2. (Ответить)