Автор |
Сообщение |
|
|
Заголовок сообщения: |
Re: Быстро считать массив. |
|
|
Sotnik писал(а): Fort + GPU = реальная дружба в примерах, или дохлый номер? На Питоне пишут интерфейсы к GPU, на Форте можно то же самое делать.
[quote="Sotnik"]Fort + GPU = реальная дружба в примерах, или дохлый номер? [/quote] На Питоне пишут интерфейсы к 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 = реальная дружба в примерах, или дохлый номер?
[quote="chess"][quote="Sotnik"]DMETER - понятно что старт/стоп задачи считает, а где все эти дополнения SPF описаны?[/quote] Тут все примитивно: [code]: 'DMETER ( XT -- ) TIMER@ \ состояние системного таймера до запуска слова на исполнение 2>R EXECUTE \ запуск слова на исполнение S0 @ SP! \ сброс стека TIMER@ \ таймер после окончания 2R> D- \ время счета в тиках таймера 3890 \ тактовая частота процессора в мГц UM/MOD NIP CR . ." MKCEK " \ время счета в микросекундах ;
: DMETER ( "name" -- ) ' 'DMETER ;[/code] PS. Этот вариант измерения времени подходит для более-менее протяженных процессов ( от единиц микросекунд и более ).[/quote] 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. Этот вариант измерения времени подходит для более-менее протяженных процессов ( от единиц микросекунд и более ).
[quote="Sotnik"]DMETER - понятно что старт/стоп задачи считает, а где все эти дополнения SPF описаны?[/quote] Тут все примитивно: [code]: 'DMETER ( XT -- ) TIMER@ \ состояние системного таймера до запуска слова на исполнение 2>R EXECUTE \ запуск слова на исполнение S0 @ SP! \ сброс стека TIMER@ \ таймер после окончания 2R> D- \ время счета в тиках таймера 3890 \ тактовая частота процессора в мГц UM/MOD NIP CR . ." MKCEK " \ время счета в микросекундах ;
: DMETER ( "name" -- ) ' 'DMETER ;[/code] PS. Этот вариант измерения времени подходит для более-менее протяженных процессов ( от единиц микросекунд и более ).
|
|
|
|
Добавлено: Вс июл 29, 2018 15:10 |
|
|
|
|
|
Заголовок сообщения: |
Re: Быстро считать массив. |
|
|
Спасибо. Переваривалка массивов всё тормозит. Хотим в FPGA запихать, а все в отпусках.
DMETER - понятно что старт/стоп задачи считает, а где все эти дополнения SPF описаны?
Спасибо. Переваривалка массивов всё тормозит. Хотим в 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 раз
Ну вот более-менее оптимизированный вариант подсчета количества уникальных наборов [code]: 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 [/code] ЛОГ [code]15252428
65062 MKCEK Ok[/code] 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, и т.п. - куда уже конкретнее. И по очереди скидывать в общюю память. Был бы кэш у каждого ядра свой на пару мег - что ещё надо для счастья!? Так нет, придумали винду, морочает голову, путается под ногами, что-то требует.
[quote="chess"] Как и ожидалось время счета получилось около секунды(даже меньше - 0,364 секунды) [/quote] Спасибо. Ещё с тем вариантом не разобрались - как всегда есть место для оптимизации. :) DMETER я выкнул, не компилится а описания не нашёл. А так всё работает. [quote] организация оптимальной загрузки ядер на счет в зависимости от конкретной решаемой задачи[/quote] Что-то типа: 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) как на ассемблере так и на ЯВУ(С++), что касается С++, то этот язык как и многие аналогичные, это черный ящик, и что там есть по использованию многогоядерности на сегодня, тем и пользуются. В Форт можно конечно добавить то, что есть в С++ и даже больше, были бы соответствующие задачи. В вашем случае наверное можно обойтись.
Вот быстренько(не оптимальный вариант) сделал генератор уникальных наборов байтов для 6 переменных для N=255 [code]: 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[/code]
ЛОГ [code]15235488 364 msec[/code] PS. Как и ожидалось время счета получилось около секунды(даже меньше - 0,364 секунды) Вобщем время счета для всех вариантов будет около секунды-двух.
Насчет использования многоядерности для ускорения счета: главное не прямой доступ ко всей памяти(это дело 'техники' в прямом смысле), а организация оптимальной загрузки ядер на счет в зависимости от конкретной решаемой задачи. ОС этому в принципе не мешает, чему есть примеры программ под ОС(windows-linux-macos) как на ассемблере так и на ЯВУ(С++), что касается С++, то этот язык как и многие аналогичные, это черный ящик, и что там есть по использованию многогоядерности на сегодня, тем и пользуются. В Форт можно конечно добавить то, что есть в С++ и даже больше, были бы соответствующие задачи. В вашем случае наверное можно обойтись.
|
|
|
|
Добавлено: Вт июл 24, 2018 22:35 |
|
|
|
|
|
Заголовок сообщения: |
Re: Быстро считать массив. |
|
|
Hishnik писал(а): В принципе, это отдельная большая тема, но вкратце - форт тут ничем специально не поможет. Без операционной системы мгновенно пропадает большинство оборудования (нет драйверов), а тем, что остается, надо управлять вручную. Памятью в первую очередь (свопа не будет, это тоже вручную). Кэширование дисковых операций вручную. Вобщем, резкого роста производительности ждать не стоит. Нафиг эта винда под некоторые задачи. Я использовал, в древности, под ДОС-ом+форт+DN+WD, и всё работало на ура при 640к памяти. Прослойка не нужна. 1. Новые архитектуры и ДОС? 2. Или кто-то писал форт-ОС? 3. Или линукс? Не совсем понимаю идеологию цепляния за винду. Форт достаточен для решения определённых задач, не заточеных под видео/аудио/инет/1Ц и прочую "ерунду". Нужен инструмент для решения задач, иногда числомолотилка, иногда управление по COM порту. И надо использовать инструмент стоящий на столе и идеально подходящий для этого.
[quote="Hishnik"] В принципе, это отдельная большая тема, но вкратце - форт тут ничем специально не поможет. Без операционной системы мгновенно пропадает большинство оборудования (нет драйверов), а тем, что остается, надо управлять вручную. Памятью в первую очередь (свопа не будет, это тоже вручную). Кэширование дисковых операций вручную. Вобщем, резкого роста производительности ждать не стоит.[/quote] Нафиг эта винда под некоторые задачи. Я использовал, в древности, под ДОС-ом+форт+DN+WD, и всё работало на ура при 640к памяти. Прослойка не нужна. 1. Новые архитектуры и ДОС? 2. Или кто-то писал форт-ОС? 3. Или линукс? Не совсем понимаю идеологию цепляния за винду. Форт достаточен для решения определённых задач, не заточеных под видео/аудио/инет/1Ц и прочую "ерунду". Нужен инструмент для решения задач, иногда числомолотилка, иногда управление по COM порту. И надо использовать инструмент стоящий на столе и идеально подходящий для этого.
|
|
|
|
Добавлено: Вт июл 24, 2018 21:10 |
|
|
|
|
|
Заголовок сообщения: |
Re: Быстро считать массив. |
|
|
Sotnik писал(а): Насчёт многоядерности. Какая версия форта может работать с железом без винды? Использовать многоядерность, и всю оперативную память. В принципе, это отдельная большая тема, но вкратце - форт тут ничем специально не поможет. Без операционной системы мгновенно пропадает большинство оборудования (нет драйверов), а тем, что остается, надо управлять вручную. Памятью в первую очередь (свопа не будет, это тоже вручную). Кэширование дисковых операций вручную. Вобщем, резкого роста производительности ждать не стоит. Запуск кода в кольце 0 защищенного режима был подробно описан в серии "Библиотека системного программиста". На практике удобнее было пользоваться DOS-extender-ами, которые формировали код для запуска приложения и шлюзы к утилитам ДОС (с чистым BIOS работа была совсем кошмарная). В целом это далеко не революционный прорыв получается, и ничего такого сногсшибательного от Ring0 не видно.
[quote="Sotnik"]Насчёт многоядерности. Какая версия форта может работать с железом без винды? Использовать многоядерность, и всю оперативную память.[/quote] В принципе, это отдельная большая тема, но вкратце - форт тут ничем специально не поможет. Без операционной системы мгновенно пропадает большинство оборудования (нет драйверов), а тем, что остается, надо управлять вручную. Памятью в первую очередь (свопа не будет, это тоже вручную). Кэширование дисковых операций вручную. Вобщем, резкого роста производительности ждать не стоит.
Запуск кода в кольце 0 защищенного режима был подробно описан в серии "Библиотека системного программиста". На практике удобнее было пользоваться DOS-extender-ами, которые формировали код для запуска приложения и шлюзы к утилитам ДОС (с чистым BIOS работа была совсем кошмарная). В целом это далеко не революционный прорыв получается, и ничего такого сногсшибательного от Ring0 не видно.
|
|
|
|
Добавлено: Вт июл 24, 2018 15:28 |
|
|
|
|
|
Заголовок сообщения: |
Re: Быстро считать массив. |
|
|
chess писал(а): Можно записывать только уникальные наборы переменных, а потом получать с помощью перестановки байтов для каждого такого уникального набора переменных все перестановки этих байтов. Красивое решение. Спасибо. Похоже что позволит быстро поработать и с 6-ю байтами. Насчёт многоядерности. Какая версия форта может работать с железом без винды? Использовать многоядерность, и всю оперативную память. Глупость какая-то, иметь монстров, и не иметь доступа ко всем их возможностям... То-же и с моим смартом на андроидом. 8 ядер, 4 гег памяти - и весчь в себе. Но там хоть есть форты для ARM, но я знаю только, вроде, для STM32F429i-Discovery - детский вариант.
[quote="chess"]Можно записывать только уникальные наборы переменных, а потом получать с помощью перестановки байтов для каждого такого уникального набора переменных все перестановки этих байтов.[/quote] Красивое решение. Спасибо. :) Похоже что позволит быстро поработать и с 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 будет около секунды.
[quote="Sotnik"]А варианты для 6 переменных просто не поместятся в 4 ГБ оперативной памяти. 255 countsum6 D. дает 9 525 431 552 варианта, что после умножения на 6 байт получается гораздо больше 4 ГБ.[/quote] Можно записывать только уникальные наборы переменных, а потом получать с помощью перестановки байтов для каждого такого уникального набора переменных все перестановки этих байтов.
[code]: 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 ;[/code] Пример: [code]9 sum6 DROP 12 + 6 VARIANTS[/code] LOG [code]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 )[/code] 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.
[quote="dmitri"]Предлагаю более быстрый алгоритм перебора вариантов суммы[/quote] ИДЕАЛЬНО! Для моего варианта я и не ожидал! :) [quote]Таким образом, для 4 и 5 переменных возиться с массивами не имеет смысла, так как можно быстро генерировать все варианты на ходу.[/quote] Увы. Ещё работа с 16-ю массивами время занимает. Приходиться всё пробовать на 4-х... [quote] А варианты для 6 переменных просто не поместятся в 4 ГБ оперативной памяти. 255 countsum6 D. дает 9 525 431 552 варианта, что после умножения на 6 байт получается гораздо больше 4 ГБ.[/quote] По ходу вычислений массивов, их значения анализируются и размеры массивов уменьшаются кратно. Так что 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 ГБ.
Предлагаю более быстрый алгоритм перебора вариантов суммы [code]: 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[/code] Выполняется за 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 МБ каждый.
Переварили полученные массивы. Примерно стало видно что надо дописать. Вот только ограничения на размеры массивов какие, чтоб винда не подавилась? Хотелось бы про оперативке 4 ГГБ, получать 16 массивов, например до 200 МБ [b]каждый[/b].
|
|
|
|
Добавлено: Ср июл 11, 2018 12:34 |
|
|
|
|
|
Заголовок сообщения: |
Re: Быстро считать массив. |
|
|
chess писал(а): Насчет использования многоядерности - вопрос сложный, в двух словах не рассказать. Винда мешает? Если работа мешает пить водку, то... Я тут уже писал, что прослойку между прогой и железом надо выкидывать. Все против. Цитата: Я-то на самом деле не знаю что вам надо. Мне просто показались странными ваши слова про сутки счета. Похоже что так. Нужны все результаты (байты 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. Немного подкоректировал - выделенное.
[quote="chess"] Насчет использования многоядерности - вопрос сложный, в двух словах не рассказать. :( [/quote] Винда мешает? [s]Если работа мешает пить водку, то...[/s] Я тут уже писал, что прослойку между прогой и железом надо выкидывать. Все против. :shuffle; [quote]Я-то на самом деле не знаю что вам надо. Мне просто показались странными ваши слова про сутки счета.[/quote]Похоже что так. Нужны все результаты (байты 0-255) A,B,C,D при которых A+B+C+D=N (0-255 [b]старшие байты не учитываются[/b]).Таких [b]исходных[/b] N - 16 разных чисел. Для них есть до 2 829 056 байт вариантов совпадений A+B+C+D=N. 1+2+3+9=15, 1+2+4+8=15, Это ABCD = 32 разряда. Массив получается для: [b]\ --- 4 переменных [/b] \ 255 sum \ 2 829 056 [s]байт[/s] [b]слов![/b] \ 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 [b]\ --- 5 переменных[/b] \ 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 [b]\ --- 6 переменных [/b] \ ещё не почитал \ 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 [s]байт[/s] [b]слов![/b], что приемлемо для дальнейшей обработки. Массивы нужны в памяти для дальнейшего переваривания.
[code]: 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 ; [/code]
СПФ под DOD 6.22 есть версия? :?:
P.S. Немного подкоректировал - [b]выделенное[/b].
|
|
|
|
Добавлено: Ср июл 11, 2018 03:26 |
|
|
|
|