Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Сб июл 21, 2018 07:42

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
 Заголовок сообщения: Быстро считать массив.
СообщениеДобавлено: Пн июл 02, 2018 18:39 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
Понадобилось разложить все возможные варианты A+B+C+D=N (например при N=10)
По старой памяти быстренько попробовал на 16-ти битном GP-Forth V.94.7,
но тот ушёл в бесконечный цикл от первой же строки кода
HEX : Dump4 16 0 Do I . 4 +Loop ; Dump4 \ Привет Ларионову! :)
Взял Smal32 32-х битный, там на стеке число сразу по 4 байта, получил при N=10/286 совпадений, 11/364, 50/23426, и т.п.
Но время пересчёта для A+B+C+D ещё приемлемо, а при A+B+C+D+E+F счёт пойдёт на сутки...

Как оптимальней и быстрее на стеке сразу 4 байта 32-х битного числа суммировать быстро, пересчитывая все варианты, например, при N=10 и сохранять все варианты в память массивом для последующей обработки?

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Пн июл 02, 2018 18:59 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 564
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Прошу меня извинить за сообщение, недопёр.

А зачем понадобилось разложить?
Асинхронное шифрование собрались взламывать? :D

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Пн июл 02, 2018 19:02 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
Victor__v писал(а):
Эм, быстро сложить все числа из массива?

Положить все возможные варианты от сложения A+B+C+D=10 в массив.

Не знаю как и что взламывается. Я задачку решаю под небольшую идею. :)
N может быть любым числом, и A+B и т.д. может быть из 4-6 чисел.

Это быстрая работа с байтами в 32-х битном слове.

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Чт июл 05, 2018 23:07 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
на СПФ
Код:
: sum { n k \ a b c d e f cnt } n 1+ TO n
n 0 DO I TO a  n 0 DO I TO b
n 0 DO I TO c  n 0 DO I TO d
n 0 DO I TO e  n 0 DO I TO f
       a b c d e f + + + + + k =
       IF cnt 1+ TO cnt THEN
LOOP LOOP LOOP LOOP LOOP LOOP
cnt .
;
50 50 sum
3478761

считается за секунд 40
записать в массив тоже просто - на 1 м этапе считаем cnt, затем в хип по размеру счетчика пишем либо 32 разрядные числа
либо 64 разрядные ( это и будут упакованные результаты ).

_________________
С уважением, chess



За это сообщение автора chess поблагодарил: Sotnik
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Пт июл 06, 2018 01:12 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 6344
Благодарил (а): 14 раз.
Поблагодарили: 99 раз.
На такие случаи можно организовать ассемблерную версию нужного слова.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Пт июл 06, 2018 23:31 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
chess писал(а):
на СПФ
Пришлось читать инструкцию. :)
Цитата:
считается за секунд 40
У меня кляча старенькая, почти три минуты.
Всё работает. Перенесу всё на СПФ - и писать дальше. Спасибо. :)

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Пт июл 06, 2018 23:33 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
Hishnik писал(а):
На такие случаи можно организовать ассемблерную версию нужного слова.
На ARM не перенесётся. Потом писать под АРМ - дешевле, ядер побольше, и пошустрее они.

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Вт июл 10, 2018 00:14 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
chess писал(а):
на СПФ
Код удобный. Есть новшества. Где про них подробнее почитать?
Цитата:
считается за секунд 40
Это минимальный диапазон. По времени алгоритм как и у меня было - перебор, только вид сбоку. :)
Я немного оптимизировал сам алгоритм, выкинув ненужные переборы - заработало НАМНОГО шустрее.
Цитата:
записать в массив тоже просто - на 1 м этапе считаем cnt, затем в хип по размеру счетчика пишем либо 32 разрядные числа либо 64 разрядные ( это и будут упакованные результаты ).
Куда эти несколько десятков массивов по 150 мб свалить в RAM, чтоб потом не спеша переварить? Винда подавиться... Как в СПФ такое реализовать?

И как разделить задачу по разным ядрам? Идеология какая? У меня их в ПК под виндой 4, а в смарте под андроидом 8 шт по 2 ГГц?
По разным компам в сети я знаю как раскидывать. :)

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Вт июл 10, 2018 21:24 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2109
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 36 раз.
Добавил упаковку и запись наборов в 32 битные ячейки в хип, при условии, что
каждое число из шести в наборе не больше 63. Пишется только пять чисел в 32 разряда. 6-е число может быть получено
вычетом из k суммы 5 чисел упакованных в ячейку. Если разрядность чисел в наборе будет больше 6, то придется упаковывать в 64-разрядные ячейки.

Код:
: sum { n k \ a b c d e f cnt arr -- arr u }
20000000 ALLOCATE THROW TO arr
n arr C! k arr 1+ C! arr 2+ TO arr
n 1+ TO n
n 0 DO I TO a  n 0 DO I TO b
n 0 DO I TO c  n 0 DO I TO d
n 0 DO I TO e  n 0 DO I TO f
       a b c d e f + + + + + k =
       IF a b  6 LSHIFT c 12 LSHIFT
            d 18 LSHIFT e 24 LSHIFT + + + + \ упаковка 5 чисел ( от 0 до 63 ) в 32 бита
            arr cnt CELLS + !
          cnt 1+ TO cnt
       THEN
LOOP LOOP LOOP LOOP LOOP LOOP
arr 2- cnt CELLS 2+ RESIZE THROW TO arr
arr cnt CELLS 2+
cnt . CR
;

: TST 50 50 sum ; TST

3478761

Ok ( 11264036 13915046 )
После можно сбрасывать из хипа такие массивы на диск, например на SSD, при этом каждый раз
освобождая хип.
Насчет использования многоядерности - вопрос сложный, в двух словах не рассказать. :(
Какие новшества имеете ввиду?
Насчет упрощения алгоритма - это первым делом, конечно. Я-то на самом деле не знаю что вам надо. Мне просто показались странными ваши слова про сутки счета.

_________________
С уважением, chess



За это сообщение автора chess поблагодарил: Sotnik
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Ср июл 11, 2018 03:26 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
chess писал(а):
Насчет использования многоядерности - вопрос сложный, в двух словах не рассказать. :(
Винда мешает? Если работа мешает пить водку, то... Я тут уже писал, что прослойку между прогой и железом надо выкидывать. Все против. :shuffle;
Цитата:
Я-то на самом деле не знаю что вам надо.
Мне просто показались странными ваши слова про сутки счета.
Похоже что так. Нужны все результаты (байты 0-255) A,B,C,D при которых A+B+C+D=N (0-255 старшие байты не учитываются).Таких исходных N - 16 разных чисел. Для них есть до 2 829 056 байт вариантов совпадений A+B+C+D=N.
1+2+3+9=15, 1+2+4+8=15, Это ABCD = 32 разряда.
Массив получается для:
\ --- 4 переменных
\ 255 sum \ 2 829 056 байт слов!
\ 254 sum \ 2 796 160
\ 200 sum \ 1 373 701
\ 120 sum \ 302621
\ 100 sum \ 176851
\ 50 sum \ 23426
\ 20 sum \ 1771
\ 10 sum \ 286
\ 4 sum \ 35
\ 2 sum \ 10
\ --- 5 переменных
\ 255 sum \ ещё не почитал
\ 200 sum \ 70 058 751 байт
\ 129 sum \ 12 457 445
\ 128 sum \ 12 082 785
\ 127 sum \ 11 716 640
\ 100 \ 4 598 126
\ 50 \ 316251
\ 20 sum \ 10626
\ 15 sum \ 3876
\ 12 sum \ 1820
\ 10 sum \ 1001
\ 5 sum \ 126
\ 2 sum \ 15
\ --- 6 переменных
\ ещё не почитал
\ 128 sum \ 321 402 081
\ 100 sum \ 96 560 646
\ 70 sum \ 17 259 390
\ 60 sum \ 8 259 888
\ 50 sum \ 3 478 761
\ 40 sum \ 1 221 758
\ 20 sum \ 53 130
Для проверки концепции хватит и 4 байт.
Получается из 16 чисел результатов, 16 массивов до 2 829 056 байт слов!, что приемлемо для дальнейшей обработки.
Массивы нужны в памяти для дальнейшего переваривания.

Код:
: sum  { n k \  a b c d e f   a1 b1 c1 d1 e1 f1  cnt } n 1+ TO n    k 1+ TO n
       \ n - MAX число бит, k - сумма чисел, cnt - число совпадений
    n 0 DO  I TO a  a .  \ старший байт
\   n 0 DO  I TO b
    n 0 DO  I TO c
    n 0 DO  I TO d
    n 0 DO  I TO e
    n 0 DO  I TO f       \ младший байт
              a   c d e f   + + + + k =  If    cnt 1+ TO cnt   Then
        LOOP LOOP LOOP LOOP \ LOOP
                                  a k =  If Cr cnt .  Key Bye  Then  \ исключение ненужных проходов
                                  LOOP    ." полный перебор " cnt . Cr Key Bye ;


СПФ под DOD 6.22 есть версия? :?:

P.S. Немного подкоректировал - выделенное.

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Ср июл 11, 2018 12:34 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
Переварили полученные массивы. Примерно стало видно что надо дописать.
Вот только ограничения на размеры массивов какие, чтоб винда не подавилась?
Хотелось бы про оперативке 4 ГГБ, получать 16 массивов, например до 200 МБ каждый.

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Сб июл 14, 2018 10:55 
Не в сети

Зарегистрирован: Чт июл 12, 2018 02:33
Сообщения: 1
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Предлагаю более быстрый алгоритм перебора вариантов суммы
Код:
: countsum4 ( n -- dcnt ) 0. ROT 2 + 1 DO I DUP 1+ 2 */ 0 D+ LOOP ;                                                                                                     
: countsum5 ( n -- dcnt ) 0. ROT 1+ 0 DO I countsum4 D+ LOOP ;
: countsum6 ( n -- dcnt ) 0. ROT 1+ 0 DO I countsum5 D+ LOOP ;

: nextsum4 ( n1 n2 n3 n4 -- n1' n2' n3' n4' | )
DUP IF 1 -1 D+ EXIT THEN
DROP DUP IF 1 -1 D+ 0 SWAP EXIT THEN
DROP DUP IF 1 -1 D+ OVER . 0. ROT EXIT THEN
2DROP ;

: dosum4 ( n -- )
>R 0. 0 R> DUP countsum4 DROP DUP . CR 0 ?DO nextsum4 LOOP ;

: nextsum5 ( n1 n2 n3 n4 n5 -- n1' n2' n3' n4' n5' | )
DUP IF 1 -1 D+ EXIT THEN
DROP DUP IF 1 -1 D+ 0 SWAP EXIT THEN
DROP DUP IF 1 -1 D+ 0. ROT EXIT THEN
DROP DUP IF 1 -1 D+ >R DUP . 0. 0 R> EXIT THEN
2DROP ;

: dosum5 ( n -- )
>R 0. 0. R> DUP countsum5 DROP DUP . CR 0 ?DO nextsum5 LOOP ;

: nextsum6 ( n1 n2 n3 n4 n5 n6 -- n1' n2' n3' n4' n5' n6' | )
DUP IF 1 -1 D+ EXIT THEN
DROP DUP IF 1 -1 D+ 0 SWAP EXIT THEN
DROP DUP IF 1 -1 D+ 0. ROT EXIT THEN
DROP DUP IF 1 -1 D+ >R 0. 0 R> EXIT THEN
DROP DUP IF 1 -1 D+ >R DUP . 0. 0. R> EXIT THEN
2DROP ;

: dosum6 ( n -- )
>R 0. 0. 0 R> DUP countsum6 2DUP D. CR
SWAP >R 0 ?DO -1 0 DO nextsum6 LOOP nextsum6 LOOP
R> 0 ?DO nextsum6 LOOP ;

.( 4 переменных - ) 50 dosum4 CR CR
.( 5 переменных - ) 50 dosum5 CR CR
.( 6 переменных - ) 50 dosum6

Выполняется за 0,02 секунды. Для сравнения: код chess для N = 50 на моем ноутбуке выполняется 2,5 минуты.
Для N = 255 этот код выполняется: по 4 переменным - 0,01 секунды, по 5 переменным - 0,7 секунды, по 6 переменным - 36 секунд.
Таким образом, для 4 и 5 переменных возиться с массивами не имеет смысла, так как можно быстро генерировать все варианты на ходу.
А варианты для 6 переменных просто не поместятся в 4 ГБ оперативной памяти. 255 countsum6 D. дает 9 525 431 552 варианта, что после умножения на 6 байт получается гораздо больше 4 ГБ.



За это сообщение автора dmitri поблагодарил: Sotnik
Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Быстро считать массив.
СообщениеДобавлено: Вс июл 15, 2018 15:36 
Не в сети

Зарегистрирован: Пн окт 05, 2009 18:21
Сообщения: 132
Откуда: Минск
Благодарил (а): 8 раз.
Поблагодарили: 0 раз.
dmitri писал(а):
Предлагаю более быстрый алгоритм перебора вариантов суммы
ИДЕАЛЬНО! Для моего варианта я и не ожидал! :)
Цитата:
Таким образом, для 4 и 5 переменных возиться с массивами не имеет смысла, так как можно быстро генерировать все варианты на ходу.
Увы. Ещё работа с 16-ю массивами время занимает. Приходиться всё пробовать на 4-х...
Цитата:
А варианты для 6 переменных просто не поместятся в 4 ГБ оперативной памяти. 255 countsum6 D. дает 9 525 431 552 варианта, что после умножения на 6 байт получается гораздо больше 4 ГБ.
По ходу вычислений массивов, их значения анализируются и размеры массивов уменьшаются кратно. Так что 6 переварятся запросто. Но это только как с 4-мя всё разложим по полочкам - тренировка на кроликах.

Не понятно ещё какие ограничения на размер памяти для СПФ - размеры массивов максимальные, чтоб винда не подавилась? В какой момент это наступит и придётся переписывать алгоритм?
Хотелось бы про оперативке 4 ГГБ, получать 16 массивов, например до 200 МБ каждый.

Для четырёх байт, получается 2 829 056 *4 = ~10мб * 16 массивов = 160 мб. Для промежуточных выводов из 16 массивов ещё мегабайт 200.

_________________
Сотник.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB