Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Проверка неразрывности последовательности

Проверка неразрывности последовательности
Я
   Asmody
 
07.05.18 - 09:00
Задачка на утро понедельника:
Лента раздлена на ячейки. Длина ленты большая, но фиксированная.
Ячейка может быть либо заполнена, либо нет.
Требуется определить, что лента заполнена только в начале.
Т.е., если N - длина ленты, то все ячейки с номером i <= M заполнены, а, соответственно, все ячейки i > M незаполнены, где M <= N.
Допускается 1 проход, каждую ячейку можно проверить только 1 раз.
Условие со "звездочкой": алгоритм должен допускать распараллеливание.
 
 
   assasu
 
1 - 07.05.18 - 09:02
лента означает что с конца проход не возможен?
   Asmody
 
2 - 07.05.18 - 09:04
(1) Да.
   тарам пам пам
 
3 - 07.05.18 - 09:14
(0) А в чем подвох? Вроде тупой цикл по ячейкам с начала ленты :

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

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

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

КонецЦикла;

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


Распараллеливание вроде тоже возможно - разбиваем ленту на нужное число кусков, определяем ЗаполненаСНачала для каждого куска (параллельно), получаем по сути новую "свернутую" ленту, запускаем тот же алгоритм снова.
   Timon1405
 
4 - 07.05.18 - 09:22
(0)
Сумма=0;
цикл
Прибавляем к Сумме 2^(индекс текущей ячейки)
конец
прибавляем к Сумме еще +1
Если получилась точная степень двойки(2^M) - то все подряд, если не получилась > есть пропуски> не подряд
   Сияющий в темноте
 
5 - 07.05.18 - 10:03
А в чем проблема?
Пусть у нас лента длины А и количество потоков В.
мы делим ленту на количество потоков и выполняем проверку на нормальность.
каждый поток проверяет кусочек ленты и выставляет одно из четырех состояний:
1 все заполнены
2 все пустые
3 нормально (если заполнена часть слева)
4 ошибка,если заполнение неверное
вторая часть синхронизация потоков
каждый поток получает от предыдущего его состояние,проводит анализ и передает следующему:
анализ проводится так:
если слева все заполнены,то у нас может быть:
все заполнены,передаем все заполнены
нормально или все пустые,передаем все пустые
ошибкп,передаем ошибку
если слева нормально,то ошибка,т.к.мы нормально не передаем,
если слева все пустые,то передается все пустые,если все пустые или ошибка
если слева ошибка,то передаем ошибку
рекомендуется первым потокам давать меньший обьем ленты,чтобы они успевали сравнивать и обрабатывать синхронизацию,пока остальные работают
   Asmody
 
6 - 07.05.18 - 10:05
(4) Для больших N и M операции со степенями двойки будут немного неэффективными.
   vde69
 
7 - 07.05.18 - 10:10
1. проверяемый участок приним за всю длину
2. проверяем ячейку в 1/3 от начала, если ячейка пуста то проверяемый участок принимаем за участок до этой ячейки и повторяем п 2
3.  проверяем ячейку в 2/3 от начала, если ячейка пуста то проверяемый участок принимаем за участок до этой ячейки и повторяем п 2

и так далее дробим каждый из одной трети опять на трети и так далее...
   Asmody
 
8 - 07.05.18 - 10:11
(3) (5) В принципе, годится. Особенно, если "лента" в реальности уже как-то поделена на более крупные области.
Например, если "лента" - это календарь, а ячейки - дни, то можно сворачивать по неделям, месяцам и т.д.
   vde69
 
9 - 07.05.18 - 10:12
(7)+ вообще-то это классический патент "разделяй и властвуй"
   Timon1405
 
10 - 07.05.18 - 10:15
(9) "Допускается 1 проход" и "повторяем п2 " несовместимы
 
 Рекламное место пустует
   vde69
 
11 - 07.05.18 - 10:17
(10) это ОДИН проход... каждая ячейка будет опрошена не более 1 раза...

Суть - нам нужно найти наиболее близкую к началу пустую ячейку...
   Кирпич
 
12 - 07.05.18 - 10:25
Я вот тоже не понимаю в чем подвох. Просматривай сначала пока не наткнешься на первую пустую. Проще некуда. Распараллеливание какое то придумали ещё.
   Timon1405
 
13 - 07.05.18 - 10:29
(12) видимо в том, что стоимость алгоритма будет порядка N а хочется сократить время расчета пропорционально количеству потоков
   vde69
 
14 - 07.05.18 - 10:29
(12) соглашусь, все равно в обязательном порядке придется проверить все ячейки от начала до первой пустой. Все остальные варианты будут проверять больше ячеек.
   бомболюк
 
15 - 07.05.18 - 10:31
если ячейки последовательно пронумерованы можно одним запросом обойтись.
   bolobol
 
16 - 07.05.18 - 10:39
(1) "лента означает что с конца проход не возможен?"
(2) Да.

А значит, что кроме последовательного прохода - других вариантов нет, т.к. нет возможности попасть в случайное место. Никакого паралеливания при последовательно связанном списке невозможно
   Asmody
 
17 - 07.05.18 - 10:40
(16) Допустим, что ленту можно заранее "порезать" на части.
   Asmody
 
18 - 07.05.18 - 10:41
(12) А вдруг в хвосте где-то заполненная ячейка?
   Кирпич
 
19 - 07.05.18 - 10:58
(18) Ничего тут не выдумаешь. Тупо проверяй всю ленту и всё.
   Bigbro
 
20 - 07.05.18 - 11:14
(6) почему?
степень двойки - всего лишь единица в одном из разрядов регистра, с остальными нулями.
00010000 = 16 = 2^4
умножение и деление на 2 соответственно сдвиг регистра влево вправо - базовые операции для любого процессора.
   тарам пам пам
 
21 - 07.05.18 - 11:47
(20) а потом длина ленты превысит суммарную доступную разрядность регистров
   Сияющий в темноте
 
22 - 07.05.18 - 21:22
Степень двойки это бит в наборе,каждую ячейку можнл обозначить битом и их и проверять
   Asmody
 
23 - 07.05.18 - 22:14
(22) Это та же самая задача, только с битами.
   Dirk Diggler
 
24 - 07.05.18 - 22:23
режем ленту на куски, по кол-ву потоков. Проходим каждым потоком свой участок, в каждом шаге проверяем заполненность ячейки и сравниваем со статусом первой в своем отрезке. после того, как любой один поток нашел смену статуса(все до эого были А, сейчас Б) - его прекращаем, фиксируем отрезок и точку смены. добиваем остальные потоки. Если найдена еще одна такая точка - то ЛОЖЬ. Если все потоки завершились удачно без смены статуса, выстраиваем их и проверяем последовательность.
   Asmody
 
25 - 07.05.18 - 22:52
(20) Я знаю про 128-битные процессоры, больше, вроде, не было (да и не имеет смысла). Реальные современные процессоры 64-битные. Т.е. эффективно можно оперировать длинами ленты до 64 ячеек. Дальше начинаются песни и пляски.
Хорошо, если мы имеем дело с Haskell, где Integer в теории (-∞,∞), а ghc считается наиболее оптимизированным компилятором для математики. В реальном мире (1С, или javascript, или типа того) все не так радужно.
   Garykom
 
26 - 07.05.18 - 23:12
1. Должно быть только одно сочетание "10"
2. Не должно быть сочетаний "01"
3. Для учета перехода на границах делаем "перехлест" на 1 бит при проверке кусков.

1111000000

Проверяем по 4 бита пусть:
1111
1000
0000
   Garykom
 
27 - 07.05.18 - 23:15
(26)+ 4. Не забыть к последнему куску дописать 0, вдруг все 1
   Сияющий в темноте
 
28 - 08.05.18 - 09:42
(23') это как раз и есть представление ленты,и разным потокам просьо дают разые куски памяти,кратные 64 бита,т.к.их процессор за раз проверяет.
блок отличный от всех нулей и всех единиу должен быть только один,его проверяем сдвигом
   Кирпич
 
29 - 08.05.18 - 09:52
Про потоки тоже ерунда. Если лента в оперативной памяти, то потоки нафиг не нужны. Быстрее будет пройти по массиву в одном потоке. Ибо на создание потоков уйдет время, на синхронизацию, на переключение между потоками и т.п. Если лента гигантсих размеров и читается с диска, то можно и потоками, а лучше вообще отдельными процессами.


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Рекламное место пустует