Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 15:04

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Быстро считать массив.
Автор Сообщение
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Sotnik писал(а):
Fort + GPU = реальная дружба в примерах, или дохлый номер?

На Питоне пишут интерфейсы к GPU, на Форте можно то же самое делать.
Сообщение Добавлено: Чт мар 26, 2020 00:39
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
chess писал(а):
Sotnik писал(а):
DMETER - понятно что старт/стоп задачи считает, а где все эти дополнения SPF описаны?

Тут все примитивно:
Код:
: 'DMETER ( XT -- )
  TIMER@                       \ состояние системного таймера до запуска слова на исполнение
  2>R
  EXECUTE                      \ запуск слова на исполнение
  S0 @ SP!                     \ сброс стека
  TIMER@                       \ таймер после окончания
  2R>
  D-                           \ время счета в тиках таймера
  3890                         \ тактовая частота процессора в мГц
  UM/MOD NIP CR . ."  MKCEK "  \ время счета в микросекундах
;

: DMETER  ( "name" -- )
   '  'DMETER  ;

PS.
Этот вариант измерения времени подходит для более-менее протяженных процессов ( от единиц микросекунд и более ).

1. Win10x64 - не рабо-о-отает... :(

2. Fort + GPU = реальная дружба в примерах, или дохлый номер? :)
Сообщение Добавлено: Пн мар 23, 2020 15:29
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Sotnik писал(а):
DMETER - понятно что старт/стоп задачи считает, а где все эти дополнения SPF описаны?

Тут все примитивно:
Код:
: 'DMETER ( XT -- )
  TIMER@                       \ состояние системного таймера до запуска слова на исполнение
  2>R
  EXECUTE                      \ запуск слова на исполнение
  S0 @ SP!                     \ сброс стека
  TIMER@                       \ таймер после окончания
  2R>
  D-                           \ время счета в тиках таймера
  3890                         \ тактовая частота процессора в мГц
  UM/MOD NIP CR . ."  MKCEK "  \ время счета в микросекундах
;

: DMETER  ( "name" -- )
   '  'DMETER  ;

PS.
Этот вариант измерения времени подходит для более-менее протяженных процессов ( от единиц микросекунд и более ).
Сообщение Добавлено: Вс июл 29, 2018 15:10
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Спасибо. Переваривалка массивов всё тормозит. Хотим в FPGA запихать, а все в отпусках.

DMETER - понятно что старт/стоп задачи считает, а где все эти дополнения SPF описаны?
Сообщение Добавлено: Вс июл 29, 2018 02:49
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Ну вот более-менее оптимизированный вариант подсчета количества уникальных наборов
Код:
: gen6 { n \ a b c d e f  A B C D E F  cnt } n TO f  1 TO cnt
n 6 / TO A
n A - 5 / TO B
n A - B - 4 / TO C
n A - B - C - 3 / TO D
n A - B - C - D - 2 / TO E
n A - B - C - D - E - TO F       \ определение конечного набора A B C D E F
BEGIN
\ a . b . c . d . e . f . CR
f e - 1 >
IF   e 1+ TO e f 1- TO f
ELSE d 1+ TO d d TO e n a - b - c - e 2* - TO f e f >
     IF c 1+ TO c c TO d d TO e n a - b - e 3 * - TO f e f >
        IF b 1+ TO b b TO c c TO d d TO e n a - e 4 * - TO f e f >
           IF a 1+ TO a a TO b b TO c c TO d d TO e n e 5 * - TO f
           THEN
        THEN
     THEN
THEN
a A = b B = c C = d D = e E = f F = AND AND AND AND AND
cnt 1+ TO cnt
UNTIL
\ a . b . c . d . e . f . CR
cnt . CR
;

: tst 255 gen6 ; DMETER tst

ЛОГ
Код:
15252428

65062  MKCEK
Ok

PS. 0,364 CEK / 0,065 CEK = 5,6
Ускорение почти в 6 раз
Сообщение Добавлено: Сб июл 28, 2018 22:07
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
chess писал(а):
Как и ожидалось время счета получилось около секунды(даже меньше - 0,364 секунды)
Спасибо. Ещё с тем вариантом не разобрались - как всегда есть место для оптимизации. :)
DMETER я выкнул, не компилится а описания не нашёл. А так всё работает.
Цитата:
организация оптимальной загрузки ядер на счет в зависимости от конкретной решаемой задачи
Что-то типа: Begin1 <тело1> Until1, Begin2 <тело2> Until2, и т.п. - куда уже конкретнее.
И по очереди скидывать в общюю память. Был бы кэш у каждого ядра свой на пару мег - что ещё надо для счастья!? Так нет, придумали винду, морочает голову, путается под ногами, что-то требует. :)
Сообщение Добавлено: Ср июл 25, 2018 03:16
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Вот быстренько(не оптимальный вариант) сделал генератор уникальных наборов байтов для 6 переменных для N=255
Код:
: gen6-255
{ a b c d e f \ fl } 0 TO fl
a b c d e f
f e - 1 >
IF   e 1+ TO e f 1- TO f 2DROP e f fl EXIT
ELSE d 1+ TO d d TO e 255 a - b - c - d - e - TO f f e - 1 >
     IF   DROP 2DROP d e f fl EXIT
     ELSE c 1+ TO c c TO d d TO e 255 a - b - c - d - e - TO f  f e - 1 >
          IF   2DROP 2DROP c d e f fl EXIT
          ELSE b 1+ TO b b TO c c TO d d TO e 255 a - b - c - d - e - TO f f e - 1 >
               IF  DROP 2DROP 2DROP b c d e f fl EXIT
               ELSE a 1+ TO a a TO b b TO c c TO d d TO e 255 a - b - c - d - e - TO f f e - 1 >
                    IF    2DROP 2DROP 2DROP a b c d e f fl EXIT
                    ELSE  2DROP 2DROP 2DROP 1 TO fl fl
                    THEN
               THEN
          THEN
     THEN
THEN
;

: genr6 { n \ cnt }
0 0 0 0 0 n
BEGIN
gen6-255  cnt 1+ TO cnt
UNTIL
cnt . CR
;
: tst 255 genr6 ; DMETER tst


ЛОГ
Код:
15235488
364  msec

PS.
Как и ожидалось время счета получилось около секунды(даже меньше - 0,364 секунды)
Вобщем время счета для всех вариантов будет около секунды-двух.

Насчет использования многоядерности для ускорения счета:
главное не прямой доступ ко всей памяти(это дело 'техники' в прямом смысле),
а организация оптимальной загрузки ядер на счет в зависимости от конкретной решаемой задачи.
ОС этому в принципе не мешает, чему есть примеры программ под ОС(windows-linux-macos) как на ассемблере так и на ЯВУ(С++), что касается С++,
то этот язык как и многие аналогичные, это черный ящик, и что там есть по использованию многогоядерности на сегодня, тем
и пользуются. В Форт можно конечно добавить то, что есть в С++ и даже больше, были бы соответствующие задачи. В вашем случае наверное можно обойтись.
Сообщение Добавлено: Вт июл 24, 2018 22:35
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Hishnik писал(а):
В принципе, это отдельная большая тема, но вкратце - форт тут ничем специально не поможет. Без операционной системы мгновенно пропадает большинство оборудования (нет драйверов), а тем, что остается, надо управлять вручную. Памятью в первую очередь (свопа не будет, это тоже вручную). Кэширование дисковых операций вручную. Вобщем, резкого роста производительности ждать не стоит.

Нафиг эта винда под некоторые задачи. Я использовал, в древности, под ДОС-ом+форт+DN+WD, и всё работало на ура при 640к памяти. Прослойка не нужна.
1. Новые архитектуры и ДОС?
2. Или кто-то писал форт-ОС?
3. Или линукс?
Не совсем понимаю идеологию цепляния за винду. Форт достаточен для решения определённых задач, не заточеных под видео/аудио/инет/1Ц и прочую "ерунду". Нужен инструмент для решения задач, иногда числомолотилка, иногда управление по COM порту.
И надо использовать инструмент стоящий на столе и идеально подходящий для этого.
Сообщение Добавлено: Вт июл 24, 2018 21:10
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Sotnik писал(а):
Насчёт многоядерности. Какая версия форта может работать с железом без винды?
Использовать многоядерность, и всю оперативную память.

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

Запуск кода в кольце 0 защищенного режима был подробно описан в серии "Библиотека системного программиста". На практике удобнее было пользоваться DOS-extender-ами, которые формировали код для запуска приложения и шлюзы к утилитам ДОС (с чистым BIOS работа была совсем кошмарная). В целом это далеко не революционный прорыв получается, и ничего такого сногсшибательного от Ring0 не видно.
Сообщение Добавлено: Вт июл 24, 2018 15:28
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
chess писал(а):
Можно записывать только уникальные наборы переменных, а потом получать с помощью перестановки байтов для каждого такого уникального набора переменных все перестановки этих байтов.
Красивое решение. Спасибо. :)
Похоже что позволит быстро поработать и с 6-ю байтами.

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

То-же и с моим смартом на андроидом. 8 ядер, 4 гег памяти - и весчь в себе.
Но там хоть есть форты для ARM, но я знаю только, вроде, для STM32F429i-Discovery - детский вариант.
Сообщение Добавлено: Вс июл 22, 2018 23:32
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
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 будет около секунды.
Сообщение Добавлено: Вс июл 22, 2018 21:24
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
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.
Сообщение Добавлено: Вс июл 15, 2018 15:36
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Предлагаю более быстрый алгоритм перебора вариантов суммы
Код:
: 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 ГБ.
Сообщение Добавлено: Сб июл 14, 2018 10:55
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
Переварили полученные массивы. Примерно стало видно что надо дописать.
Вот только ограничения на размеры массивов какие, чтоб винда не подавилась?
Хотелось бы про оперативке 4 ГГБ, получать 16 массивов, например до 200 МБ каждый.
Сообщение Добавлено: Ср июл 11, 2018 12:34
  Заголовок сообщения:  Re: Быстро считать массив.  Ответить с цитатой
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. Немного подкоректировал - выделенное.
Сообщение Добавлено: Ср июл 11, 2018 03:26

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


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