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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Пт июл 15, 2016 23:03 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Не, ну это не программа минимум.
Тут же есть локальные переменные,
И ещё
Код:
beg end + 2/ TO mid

Уязвимое место в плане переполнения, быть может.
Сейчас уже сделал бинарный поиск, иначе, однако, но работает

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Сб июл 16, 2016 09:43 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Цитата:
Не, ну это не программа минимум.
Тут же есть локальные переменные,
И ещё

Код:
beg end + 2/ TO mid

Уязвимое место в плане переполнения, быть может.
Сейчас уже сделал бинарный поиск, иначе, однако, но работает

Для SPF4 переполнения не будет. В других случаях можно заменить на
Код:
beg end beg - 2/ + TO mid

Минимум в каком смысле?
Побочные эффекты локальных переменных в SPF выражаются только в чуть меньшем быстродействии по сравнению с быстродействием кода без их использования.
Если нужно максимальное быстродействие, то писать надо ассемблером.
Есть рабочий код? Если не трудно, приведите.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Пн июл 18, 2016 20:33 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Код:
: BIN-SEARCH ( zn a b -- 0|-1)

  2>R
  BEGIN
 
  2R@ + 2/ >R
  DUP R@ @ <
   IF 
    [ 0x8F C, 0x44 C, 0x24 C, 0 C, ] \ R-STACK NIP
   ELSE

     DUP R@ @ = IF
      [ 0x8D C, 0x64 C, 0x24 C,  3 CELLS C, ] \ R-STACK 3DROP
       DROP -1
       [ 0xEB C, HERE DATA>FLOAT32 0 C, ] 
               THEN

    [ 0x8F C, 0x44 C, 0x24 C, CELL C, ]
    \ R-STACK ( ST END MID --  MID END )
     
   THEN 
 
   2R@ - CELL MOD
   IF 
   RDROP R> @ =
   [ 0xEB C, HERE DATA>FLOAT32 0 C, ] 
   THEN
   
   AGAIN
  [
    \  чтобы потом можно было прямо в код подставить
    HERE FDUP FLOAT>DATA32 - 1- FLOAT>DATA32 C!
    HERE FDUP FLOAT>DATA32 - 1- FLOAT>DATA32 C!
   
  ] 
;


Не идеально, конечно, но работает. Только Поиск двух крайних значений не фурычит, Печалька :(

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Пт июл 22, 2016 20:15 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Код:
: arr \ -- a u
  S" 0123456789" ;

: BinSearchL { a u Byte \ beg mid end -- Index|0 }
  a TO beg a u + TO end
  BEGIN
    beg end beg - 2/ + TO mid
    mid C@ Byte = IF mid a - EXIT THEN
    beg mid = mid end = OR IF 0 EXIT THEN
    mid C@ Byte < IF   mid TO beg ELSE mid TO end THEN
  AGAIN ;

\              1 2 3      4   5   6
: BinSearchM ( a u Byte \ beg mid end -- Index|0 )
  3/1:412+:6
   /B46+`2/:55b3=
     /?51-;t
     /45=56=|?y;t
     /5b3<?5:4e5:6t
   /O'1f ;

: BinSearchF ( a u Byte -- Index|0 )
  ROT DUP >R -ROT >R OVER +                    \ beg=a end=a+u     R: a Byte
  BEGIN
    2DUP + 2/ >R  2R@ C@ =                     \ mid=(beg+end)/2
    IF R> NIP NIP RDROP R> - EXIT THEN         \ Index=mid-a
    2DUP R@ = SWAP R@ = OR                     \ (beg=mid or mid=end) and (Byte <> mid C@)
    IF 2R> 2DROP RDROP 2DROP 0 EXIT THEN       \ 0
    2R@ C@ < IF DROP R> ELSE NIP R> SWAP THEN  \ end=mid | beg=mid
  AGAIN
;

: BinSearchA ( a u Byte -- Index|0 )
  $ 4 B=@P   D=A     C=B  C+@P   NIP
  L1: A^A    A+B     A+C  1Aa>>  @bA=bD?
  L3  J=     B=A?
  L4  J=     A=C?
  L4  J=     @bA=bD?
  L2  J<     C=A
  L1  JMP
  L2: B=A
  L1  JMP
  L3: A-@P   NIP
  L5  JMP
  L4: A^A    NIP
  L5:
;

STARTLOG
SEE BinSearchA

: testL  arr [CHAR] 3 BinSearchL ;
: testM  arr [CHAR] 3 BinSearchM ;
: testF  arr [CHAR] 3 BinSearchF ;
: testA  arr [CHAR] 3 BinSearchA ;

\ Времена исполнения
METER0 testL  \ форт с локальными переменными
METER0 testM  \ форт с манипуляторами
METER0 testF  \ plain форт
METER0 testA  \ форт с встроенным ассемблером

LOG

CODE BinSearchA
5D536F 8B5D04           MOV     EBX , 4 [EBP]
5D5372 8BD0             MOV     EDX , EAX
5D5374 8BCB             MOV     ECX , EBX
5D5376 034D00           ADD     ECX , 0 [EBP]
5D5379 8D6D04           LEA     EBP , 4 [EBP]
5D537C 33C0             XOR     EAX , EAX
5D537E 03C3             ADD     EAX , EBX
5D5380 03C1             ADD     EAX , ECX
5D5382 D1F8             SAR     EAX , 1
5D5384 3810             CMP     [EAX] , DL
5D5386 7414             JE      5D539C
5D5388 3BD8             CMP     EBX , EAX
5D538A 7418             JE      5D53A4
5D538C 3BC1             CMP     EAX , ECX
5D538E 7414             JE      5D53A4
5D5390 3810             CMP     [EAX] , DL
5D5392 7C04             JL      5D5398
5D5394 8BC8             MOV     ECX , EAX
5D5396 EBE4             JMP     5D537C
5D5398 8BD8             MOV     EBX , EAX
5D539A EBE0             JMP     5D537C
5D539C 2B4500           SUB     EAX , 0 [EBP]
5D539F 8D6D04           LEA     EBP , 4 [EBP]
5D53A2 EB05             JMP     5D53A9
5D53A4 33C0             XOR     EAX , EAX
5D53A6 8D6D04           LEA     EBP , 4 [EBP]
5D53A9 C3               RET     NEAR
END-CODE
( 59 bytes, 27 instructions )

166  nsec
182  nsec
142  nsec
95  nsec

PS.
Простота алгоритма бинарного поиска позволяет достаточно просто написать бин. поиск
даже на plain Forth(базовый набор слов ядра).
По быстроте написания полностью рабочей программы лидером является форт с манипуляторами(около минуты-печати меньше! :) ),
затем идет форт с локальными метками(2 мин), затем plain форт(10 мин) и чуть от него отстает ассемблер
(по причине примитивности алгоритма).
По скорости исполнения кода впереди конечно ассм, затем plain форт и чуть от него отстают
остальные два способа.
Ваш способ форт+ассемблерные вставки - по времени написания(хотя вы ее еще не дописали) хуже форта,
по быстродействию кода аналогичен форту.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Сб июл 23, 2016 19:42 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
На ассме написать не получилось. У меня какие-то нелады с cmp
А над ассемблерными вставками я и не думал. Код уже был написан. Всякие там dup drop nip swap для стека возвратов
А использование f-стека в качестве стека потока-управления для меня чуть ли не ежедневная практика.
Ну, а значение 0xe9 и 0xeb мне известно.
Таким макаром хорошо лямбды читерные строить :D
Код уже написан до ума доведён, оттестирован на корректность. Но ассм.вариант для поиска среди значений размером с двойное слово, мне не помешал бы. Плохо когда в тебе гнездится перфекционист :evil:

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Вс июл 24, 2016 12:36 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Цитата:
У меня какие-то нелады с cmp

Код:
: CMP
\ все варианты инструкции CMP для Х86
\ (с использованием регистров EAX EBX ECX AX BX CX AL BL CL )
  A=B?
  A=@B?
  @A=B?
  $ 0 A=@BC?
  $ 0 @AB=C?
  $ 1 A=#?
  $ 1 @A=#?
  $ 0 $ 1 @AB=#?
  $ 1 A=b#?
  $ 1 @A=b#?
  $ 4 @bAB=b#?
  A=B?
  bA=@bB?
  @bA=bB?
  $ 0 bA=@bBC?
  $ 0 @bAB=bC?
  $ 1 bA=b#?
  $ 1 @bA=b#?
  $ 1 @bAB=b#?
  wA=wB?
  wA=@wB?
  @wA=wB?
  $ 0 wA=@wBC?
  $ 0 @wAB=wC?
  $ 1 wA=w#?
  $ 1 @wA=w#?
  $ 0 $ 4 $ 1 @wAB=w#?
  $ 1 wA=b#?
  $ 1 @wA=b#?
  $ 1 @wAB=b#?
  ;
  SEE CMP
LOG
CODE CMP
5D507B 3BC3             CMP     EAX , EBX
5D507D 3B03             CMP     EAX , [EBX]
5D507F 3918             CMP     [EAX] , EBX
5D5081 3B440B00         CMP     EAX , 0 [EBX] [ECX]
5D5085 394C1800         CMP     0 [EAX] [EBX] , ECX
5D5089 81F801000000     CMP     EAX , # 1
5D508F 813801000000     CMP     [EAX] , # 1
5D5095 817C180001000000 CMP     0 [EAX] [EBX] , # 1
5D509D 83F801           CMP     EAX , # 1
5D50A0 833801           CMP     [EAX] , # 1
5D50A3 803C1804         CMP     [EAX] [EBX] , # 4
5D50A7 3BC3             CMP     EAX , EBX
5D50A9 3A03             CMP     AL , [EBX]
5D50AB 3818             CMP     [EAX] , BL
5D50AD 3A440B00         CMP     AL , 0 [EBX] [ECX]
5D50B1 384C1800         CMP     0 [EAX] [EBX] , CL
5D50B5 80F801           CMP     AL , # 1
5D50B8 803801           CMP     [EAX] , # 1
5D50BB 803C1801         CMP     [EAX] [EBX] , # 1
5D50BF 66               D16:
5D50C0 3BC3             CMP     AX , BX
5D50C2 66               D16:
5D50C3 3B03             CMP     AX , [EBX]
5D50C5 66               D16:
5D50C6 3918             CMP     [EAX] , BX
5D50C8 66               D16:
5D50C9 3B440B00         CMP     AX , 0 [EBX] [ECX]
5D50CD 66               D16:
5D50CE 394C1800         CMP     0 [EAX] [EBX] , CX
5D50D2 66               D16:
5D50D3 81F80100         CMP     AX , # 1
5D50D7 66               D16:
5D50D8 81380100         CMP     [EAX] , # 1
5D50DC 66               D16:
5D50DD 817C18040100     CMP     4 [EAX] [EBX] , # 1
5D50E3 66               D16:
5D50E4 83F801           CMP     AX , # 1
5D50E7 66               D16:
5D50E8 83780001         CMP     0 [EAX] , # 1
5D50EC 66               D16:
5D50ED 833C1801         CMP     [EAX] [EBX] , # 1
5D50F1 C3               RET     NEAR
END-CODE
( 119 bytes, 42 instructions )


Какие могут быть вопросы к cmp?
Может к командам ветвления по результатам cmp?
Или надо сравнивать 64 разрядные числа на аппаратном уровне?
Ну тогда можно использовать инструкции ММХ-набора(PCMPEQ, PCMPGT).

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


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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Есть ли способ "заархивировать" число двойной длины в обычное число?
Число именно ДВОЙНОЙ ДЛИНЫ.
Касательно, зачем.
64-битный хеши всей кучей заполняют почти весь доступный хип, а он ещё нужен СУБД и строкам.
Или хотя бы заархивировать с 8 байт до 6.
P.S вот сюда бы числа полторашной длины :)

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Вт сен 06, 2016 14:45 
Не в сети

Зарегистрирован: Пт июн 06, 2008 14:21
Сообщения: 128
Откуда: Карелия
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Про сжатие можно посмотреть здесь https://www.opendesign.com/files/guestdownloads/OpenDesign_Specification_for_.dwg_files.pdf


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Вт сен 06, 2016 17:37 
Не в сети
Аватара пользователя

Зарегистрирован: Вт авг 12, 2008 03:18
Сообщения: 327
Откуда: Москва
Благодарил (а): 36 раз.
Поблагодарили: 7 раз.
Victor__v писал(а):
Есть ли способ "заархивировать" число двойной длины в обычное число?

Или хотя бы заархивировать с 8 байт до 6.
P.S вот сюда бы числа полторашной длины :)


Структура из 16 и 32 битных целых и использовать сдвиги, не пойдет?

ps Возможно не втему, просто недавно читал статью, что хешировать
большой объем данных ересь. Сам я в этом ноль, передаю что читал.

_________________
Линукс решает, винда глотает.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Вт сен 06, 2016 21:50 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Цитата:
хешировать
большой объем данных ересь

В целом да.
Если входной массив достаточно большой, коллизии для 64-х битных хешей неизбежны, про 32-х битные говорить не приходится

Цитата:
Структура из 16 и 32 битных целых и использовать сдвиги, не пойдет?

Была мысля выкинуть часть хеша.
Использовать сдвиги? Простите, не понял. Где их использовать?
Для архивации навряд ли подходит, ибо треба восстановимость "архива" .
Пробовал заархивировать 64-битный хеш функции Ly.
Получилось урезать один байт. Но решение было практически в лоб. Вряд ли сработает для всех значений.
Цитата:
Про сжатие можно посмотреть здесь https://www.opendesign.com/files/guestd ... _files.pdf

Благодарю

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Чт сен 08, 2016 15:44 
Не в сети

Зарегистрирован: Сб май 13, 2006 18:17
Сообщения: 42
Благодарил (а): 2 раз.
Поблагодарили: 0 раз.
Victor__v писал(а):
Есть ли способ "заархивировать" число двойной длины в обычное число?
Число именно ДВОЙНОЙ ДЛИНЫ.
Касательно, зачем.
64-битный хеши всей кучей заполняют почти весь доступный хип, а он ещё нужен СУБД и строкам.
Или хотя бы заархивировать с 8 байт до 6.
P.S вот сюда бы числа полторашной длины :)


Записывайте числа по какому-нибудь большому основанию, например 250. Правда тогда вам придется ввести новые символы, обозначающие цифры. Я использовал для этого значки псевдографики из ASCII.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Чт сен 08, 2016 17:17 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Цитата:
Записывайте числа по какому-нибудь большому основанию, например 250. Правда тогда вам придется ввести новые символы, обозначающие цифры. Я использовал для этого значки псевдографики из ASCII

Как-то не понятно с идеей.
По какому бы не записывали основанию числа их размер будет 8 байт.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Чт сен 08, 2016 18:55 
Не в сети

Зарегистрирован: Сб май 13, 2006 18:17
Сообщения: 42
Благодарил (а): 2 раз.
Поблагодарили: 0 раз.
Victor__v писал(а):
P.S вот сюда бы числа полторашной длины

Если INT64 вам много, а INT32 мало, подобным образом удобно преобразовать число в такой вид, когда надо будет тратить на число ровно столько бит, сколько оно занимает.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Чт сен 15, 2016 15:56 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1288
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Собственно, идея.
Где применять сопрограммы в форте?
У меня идей как-то нет.
Единственное что дошло, так это возможность получать данные из каждой итерации циклов. Но где и это применить хз.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Подскажите идею...
СообщениеДобавлено: Чт сен 15, 2016 16:12 
Victor__v писал(а):
Где применять сопрограммы в форте?

http://fforum.winglion.ru/viewtopic.php?p=41938#p41938


Вернуться к началу
  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.

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


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

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


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

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