Задачка на утро понедельника:
Лента раздлена на ячейки. Длина ленты большая, но фиксированная.
Ячейка может быть либо заполнена, либо нет.
Требуется определить, что лента заполнена только в начале.
Т.е., если N - длина ленты, то все ячейки с номером i <= M заполнены, а, соответственно, все ячейки i > M незаполнены, где M <= N.
Допускается 1 проход, каждую ячейку можно проверить только 1 раз.
Условие со "звездочкой": алгоритм должен допускать распараллеливание.

лента означает что с конца проход не возможен?

(1) Да.

(0) А в чем подвох? Вроде тупой цикл по ячейкам с начала ленты :


ЗаполненаСНачала = Истина;
БылаПустая = Ложь;
Для Каждого Ячейка Из Лента Цикл

    Если Не Ячейка.Пустая() И БылаПустая Тогда
       ЗаполненаСНачала = Ложь;
       Прервать;
    КонецЕсли;

    Если Ячейка.Пустая() Тогда
        БылаПустая = Истина;
    КонецЕсли;

КонецЦикла;

Возврат ЗаполненаСНачала;


Распараллеливание вроде тоже возможно - разбиваем ленту на нужное число кусков, определяем ЗаполненаСНачала для каждого куска (параллельно), получаем по сути новую "свернутую" ленту, запускаем тот же алгоритм снова.

(0)
Сумма=0;
цикл
Прибавляем к Сумме 2^(индекс текущей ячейки)
конец
прибавляем к Сумме еще +1
Если получилась точная степень двойки(2^M) - то все подряд, если не получилась > есть пропуски> не подряд

А в чем проблема?
Пусть у нас лента длины А и количество потоков В.
мы делим ленту на количество потоков и выполняем проверку на нормальность.
каждый поток проверяет кусочек ленты и выставляет одно из четырех состояний:
1 все заполнены
2 все пустые
3 нормально (если заполнена часть слева)
4 ошибка,если заполнение неверное
вторая часть синхронизация потоков
каждый поток получает от предыдущего его состояние,проводит анализ и передает следующему:
анализ проводится так:
если слева все заполнены,то у нас может быть:
все заполнены,передаем все заполнены
нормально или все пустые,передаем все пустые
ошибкп,передаем ошибку
если слева нормально,то ошибка,т.к.мы нормально не передаем,
если слева все пустые,то передается все пустые,если все пустые или ошибка
если слева ошибка,то передаем ошибку
рекомендуется первым потокам давать меньший обьем ленты,чтобы они успевали сравнивать и обрабатывать синхронизацию,пока остальные работают

(4) Для больших N и M операции со степенями двойки будут немного неэффективными.

1. проверяемый участок приним за всю длину
2. проверяем ячейку в 1/3 от начала, если ячейка пуста то проверяемый участок принимаем за участок до этой ячейки и повторяем п 2
3.  проверяем ячейку в 2/3 от начала, если ячейка пуста то проверяемый участок принимаем за участок до этой ячейки и повторяем п 2

и так далее дробим каждый из одной трети опять на трети и так далее...

(3) (5) В принципе, годится. Особенно, если "лента" в реальности уже как-то поделена на более крупные области.
Например, если "лента" - это календарь, а ячейки - дни, то можно сворачивать по неделям, месяцам и т.д.

(7)+ вообще-то это классический патент "разделяй и властвуй"

(9) "Допускается 1 проход" и "повторяем п2 " несовместимы

(10) это ОДИН проход... каждая ячейка будет опрошена не более 1 раза...

Суть - нам нужно найти наиболее близкую к началу пустую ячейку...

Я вот тоже не понимаю в чем подвох. Просматривай сначала пока не наткнешься на первую пустую. Проще некуда. Распараллеливание какое то придумали ещё.

(12) видимо в том, что стоимость алгоритма будет порядка N а хочется сократить время расчета пропорционально количеству потоков

(12) соглашусь, все равно в обязательном порядке придется проверить все ячейки от начала до первой пустой. Все остальные варианты будут проверять больше ячеек.

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

(1) "лента означает что с конца проход не возможен?"
(2) Да.

А значит, что кроме последовательного прохода - других вариантов нет, т.к. нет возможности попасть в случайное место. Никакого паралеливания при последовательно связанном списке невозможно

(16) Допустим, что ленту можно заранее "порезать" на части.

(12) А вдруг в хвосте где-то заполненная ячейка?

(18) Ничего тут не выдумаешь. Тупо проверяй всю ленту и всё.

(6) почему?
степень двойки - всего лишь единица в одном из разрядов регистра, с остальными нулями.
00010000 = 16 = 2^4
умножение и деление на 2 соответственно сдвиг регистра влево вправо - базовые операции для любого процессора.

(20) а потом длина ленты превысит суммарную доступную разрядность регистров

Степень двойки это бит в наборе,каждую ячейку можнл обозначить битом и их и проверять

(22) Это та же самая задача, только с битами.

режем ленту на куски, по кол-ву потоков. Проходим каждым потоком свой участок, в каждом шаге проверяем заполненность ячейки и сравниваем со статусом первой в своем отрезке. после того, как любой один поток нашел смену статуса(все до эого были А, сейчас Б) - его прекращаем, фиксируем отрезок и точку смены. добиваем остальные потоки. Если найдена еще одна такая точка - то ЛОЖЬ. Если все потоки завершились удачно без смены статуса, выстраиваем их и проверяем последовательность.

(20) Я знаю про 128-битные процессоры, больше, вроде, не было (да и не имеет смысла). Реальные современные процессоры 64-битные. Т.е. эффективно можно оперировать длинами ленты до 64 ячеек. Дальше начинаются песни и пляски.
Хорошо, если мы имеем дело с Haskell, где Integer в теории (-∞,∞), а ghc считается наиболее оптимизированным компилятором для математики. В реальном мире (1С, или javascript, или типа того) все не так радужно.

1. Должно быть только одно сочетание "10"
2. Не должно быть сочетаний "01"
3. Для учета перехода на границах делаем "перехлест" на 1 бит при проверке кусков.

1111000000

Проверяем по 4 бита пусть:
1111
1000
0000

(26)+ 4. Не забыть к последнему куску дописать 0, вдруг все 1

(23') это как раз и есть представление ленты,и разным потокам просьо дают разые куски памяти,кратные 64 бита,т.к.их процессор за раз проверяет.
блок отличный от всех нулей и всех единиу должен быть только один,его проверяем сдвигом

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