Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет qwerty ([info]qwerty)
@ 2010-01-24 17:11:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Задачка

Есть одномерный массив целых. В начале его расположен массив A длиной a, в конце B длиной b, а посредине не интересующий нас мусор длиной c. Требуется красивым образом переместить B в начало, за ним расположить A, причем сделав при этом не более a+b чтений и записей в массив. Судьба мусора не интересует. Файлы, посторонняя память и рекурсия категорически отсутствуют.


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

Re: ХЗ как тут форматировать
[info]blue_slonopotam
2010-01-27 00:15 (ссылка)
не готов долго думать, но

моя запись иллюстрирует не доказательство, но некоторый ход мысли - НОД может быть 1 и a+c может быть больше размера линии кэша, из чего следует, что кэшу несдобровать в любом случае.

Я сомневаюсь в существовании "Третий-с-половиной ещё и сына кэш не так убивает".

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

Re: ХЗ как тут форматировать
[info]faceted-jacinth.livejournal.com
2010-01-27 01:06 (ссылка)
А, я не прав был. То есть он говорит, что в 60% случаев там вообще получится один цикл (прыгающий как безумный по всему массиву), и в остальных случаях локальность будет только на первой итерации обычно, но "It [loop fusion] is, nevertheless, an important technique that is worth demonstrating" =) Типа, его прёт, что её можно сделать достаточно генерик и без залезания в нутро компилятора, и она будет работать быстро!

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

Re: ХЗ как тут форматировать
[info]blue_slonopotam
2010-01-27 01:37 (ссылка)
Изучение алгебры полезно для душевного здоровья, видимо, и автору этой книжки тоже.

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


(Читать комментарии) -