Быстро считать массив.

Sotnik

Понадобилось разложить все возможные варианты 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 и сохранять все варианты в память массивом для последующей обработки?

Victor__v

Прошу меня извинить за сообщение, недопёр.

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

Sotnik

Victor__v писал(а):

Эм, быстро сложить все числа из массива?

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

Не знаю как и что взламывается. Я задачку решаю под небольшую идею.

N может быть любым числом, и A+B и т.д. может быть из 4-6 чисел.

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

chess

на СПФ

Код:

: 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 разрядные ( это и будут упакованные результаты ).

Hishnik

На такие случаи можно организовать ассемблерную версию нужного слова.

Sotnik

chess писал(а):

на СПФ

Пришлось читать инструкцию.

Цитата:

считается за секунд 40

У меня кляча старенькая, почти три минуты.
Всё работает. Перенесу всё на СПФ - и писать дальше. Спасибо.

Sotnik

Hishnik писал(а):

На такие случаи можно организовать ассемблерную версию нужного слова.

На ARM не перенесётся. Потом писать под АРМ - дешевле, ядер побольше, и пошустрее они.

Sotnik

chess писал(а):

на СПФ

Код удобный. Есть новшества. Где про них подробнее почитать?

Цитата:

считается за секунд 40

Это минимальный диапазон. По времени алгоритм как и у меня было - перебор, только вид сбоку.

Я немного оптимизировал сам алгоритм, выкинув ненужные переборы - заработало НАМНОГО шустрее.

Цитата:

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

Куда эти несколько десятков массивов по 150 мб свалить в RAM, чтоб потом не спеша переварить? Винда подавиться... Как в СПФ такое реализовать?

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

chess

Добавил упаковку и запись наборов в 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, при этом каждый раз
освобождая хип.
Насчет использования многоядерности - вопрос сложный, в двух словах не рассказать.

Какие новшества имеете ввиду?
Насчет упрощения алгоритма - это первым делом, конечно. Я-то на самом деле не знаю что вам надо. Мне просто показались странными ваши слова про сутки счета.

Sotnik

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. Немного подкоректировал - выделенное.

Sotnik

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

dmitri

Предлагаю более быстрый алгоритм перебора вариантов суммы

Код:

: 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 ГБ.

Sotnik

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.

chess

Sotnik писал(а):

А варианты для 6 переменных просто не поместятся в 4 ГБ оперативной памяти. 255 countsum6 D. дает 9 525 431 552 варианта, что после умножения на 6 байт получается гораздо больше 4 ГБ.

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

Код:

: sum6 { n \ a b c d e f cnt6 arr6 len6 arrt }
    15252428 6 * TO len6 len6 ALLOCATE THROW TO arr6 arr6 TO arrt  \ 15 252 428  6 *  - количество байтов для записи наборов для 6 переменных при N = 256
    n . CR
    n 6 / 1+ 0 DO  I TO a a b > IF LEAVE THEN
    n 5 / 1+ a DO  I TO b b c > IF LEAVE THEN
    n 4 / 1+ b DO  I TO c c d > IF LEAVE THEN
    n 3 / 1+ c DO  I TO d d e > IF LEAVE THEN
    n 2 / 1+ d DO  I TO e e f > IF LEAVE THEN
    n     1+ e DO  I TO f a b c d e f + + + + + n =
                   IF
                   arr6 cnt6 6 * + TO arrt
                   a 48 + arrt C! b 48 + arrt 1+ C! c 48 + arrt 2+ C! d 48 +  arrt 3 + C! e 48 + arrt 4 + C! f 48 + arrt 5 + C!
                   cnt6 1+ TO cnt6
                      a . b . c . d . e . f . CR
                      LEAVE
                   THEN
               LOOP LOOP LOOP LOOP LOOP LOOP
  arr6 cnt6 DUP . CR 6 * RESIZE THROW cnt6 6 *
;

\ Генератор перестановок байтов
: cswap { a1 a2 -- }
    a1 C@ a2 C@ a1 C! a2 C!
;
: cnotfind ( c s2 s1 -- t/f )
    1 -ROT ?DO OVER I C@ = IF 0 AND LEAVE THEN LOOP
    SWAP DROP
;
: variants ( 0 s2 s1 str len --> count s2 s1' str len )
    2>R 2DUP - 1 < IF
        2>R 1+ 2R>
        2R> 2DUP TYPE CR
        EXIT
    THEN
    DUP >R BEGIN 2DUP > WHILE
        DUP C@ OVER R@ cnotfind IF
            DUP R@ cswap
            R> 1+ SWAP 2R> ROT >R
            RECURSE
            R> -ROT 2>R SWAP 1- >R
            DUP R@ cswap
        THEN
    1+
    REPEAT DROP R> 2R>
;
: VARIANTS ( a u --> n )
    DUP 0 = IF 2DROP 0 EXIT THEN
    2DUP 2>R OVER + SWAP 0 -ROT 2R> variants 2DROP 2DROP
;

Пример:

Код:

9 sum6 DROP 12 + 6 VARIANTS

LOG

Код:

9
0 0 0 0 0 9
0 0 0 0 1 8
0 0 0 0 2 7
0 0 0 0 3 6
0 0 0 0 4 5
0 0 0 1 1 7
0 0 0 1 2 6
0 0 0 1 3 5
0 0 0 1 4 4
0 0 0 2 2 5
0 0 0 2 3 4
0 0 0 3 3 3
0 0 1 1 1 6
0 0 1 1 2 5
0 0 1 1 3 4
0 0 1 2 2 4
0 0 1 2 3 3
0 0 2 2 2 3
0 1 1 1 1 5
0 1 1 1 2 4
0 1 1 1 3 3
0 1 1 2 2 3
0 1 2 2 2 2
1 1 1 1 1 4
1 1 1 1 2 3
1 1 1 2 2 2
26
000027  \ генерация перестановок для третьего набора
000072
000207
000270
000720
000702
002007
002070
002700
007020
007002
007200
020007
020070
020700
027000
070020
070002
070200
072000
200007
200070
200700
207000
270000
700020
700002
700200
702000
720000

 Ok ( 30 )

PS. Время даже для переборного варианта при 6 переменных и N=255 (правда усеченного) около 30 сек. А если написать генератор уникальных наборов, то время для 6 переменных и N=255 будет около секунды.

Sotnik

chess писал(а):

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

Красивое решение. Спасибо.

Похоже что позволит быстро поработать и с 6-ю байтами.

Насчёт многоядерности. Какая версия форта может работать с железом без винды?
Использовать многоядерность, и всю оперативную память.
Глупость какая-то, иметь монстров, и не иметь доступа ко всем их возможностям...

То-же и с моим смартом на андроидом. 8 ядер, 4 гег памяти - и весчь в себе.
Но там хоть есть форты для ARM, но я знаю только, вроде, для STM32F429i-Discovery - детский вариант.

Быстро считать массив.

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