ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / msb (most significant bit) на pl/sql есть готовый?
25 сообщений из 87, страница 2 из 4
  2  все
msb (most significant bit) на pl/sql есть готовый?
    #40000060
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
andrey_anonymous,

возможно я не понял последнюю ремарку.
Начиная справа я должен проверить все разряды (126 по задуманному дизайну).
Начиная с msb и двигаясь вниз по разрядам, я смогу останавливаться только на выставленных в 1 разрядах, игнорируя нулевые.
У меня такая идея была - я не знаю, как двигаясь с младшего разряда, проскакивать в анализируемом числе нулевые.
...
Рейтинг: 0 / 0
17.09.2020, 21:46
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000064
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
booby
Начиная с msb и двигаясь вниз по разрядам, я смогу останавливаться только на выставленных в 1 разрядах, игнорируя нулевые.

Должно быть я не догоняю.
Пропускать нулевые двигаясь слева - это ведь опять вычисление msb?
Если да, то не дешевле тупо делить на два или даже пройтись по строке?
Если нет - то как пропустить нулевой бит и почему не выполнить ту же операцию над исходным числом вместо вычисления msb?
...
Рейтинг: 0 / 0
17.09.2020, 21:51
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000065
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
Вообще я бы попробовал сразу разделить число на целые покороче (бит по 16, к примеру) и обрабатывать ненулевые, это +-константное время.
...
Рейтинг: 0 / 0
17.09.2020, 21:55
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000067
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
...промеждупрочим, а для зачем вообще на биты уходить?
Можно же обойтись десятичными разрядами.
...
Рейтинг: 0 / 0
17.09.2020, 22:02
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000073
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
andrey_anonymous
booby
Начиная с msb и двигаясь вниз по разрядам, я смогу останавливаться только на выставленных в 1 разрядах, игнорируя нулевые.

Должно быть я не догоняю.
Пропускать нулевые двигаясь слева - это ведь опять вычисление msb?
Если да, то не дешевле тупо делить на два или даже пройтись по строке?
Если нет - то как пропустить нулевой бит и почему не выполнить ту же операцию над исходным числом вместо вычисления msb?

В общем, все да.

msb выглядит полезным при любом варианте - он даёт верхнюю оценку размера цикла и разряд, за которым "битов нет".
если в исследуемом числе биты сильно разрекжены, то bitand(x, msb-1) даст возможность пропустить "много разрядов".
Как дальше этим воспользоваться наилучшим образом - пока открыто..

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

Даже если двигаться по каждому разряду - при наличии msb я могу обойтись простым делением в цикле,
и мне не потребуется сравнение на превышении степени значения анализируемого числа на каждом шаге,
как это было бы при движении от младшего разряда.
...
Рейтинг: 0 / 0
17.09.2020, 22:18
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000074
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
andrey_anonymous
...промеждупрочим, а для зачем вообще на биты уходить?
Можно же обойтись десятичными разрядами.


Там всего 16 байтов. Начиная со старшего, пропускаем все нулевые (допустим, байты 15,14,13 нулевые, 12й-ненулевой).
сузили ответ до 88 -95 (0-based).
Допустим в байте 12 число 66 - это бит номер 6, посчитать или сдвигом вправо, не более 7 раз, или в таблице посмотреть.
88 +6 = 94й бит.

Скан снизу вверх займет дольше, т.к. надо посмотреть все байты.
Скан сверху вниз останавливается найдя первый неноль.
...
Рейтинг: 0 / 0
17.09.2020, 22:19
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000075
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
andrey_anonymous
...промеждупрочим, а для зачем вообще на биты уходить?
Можно же обойтись десятичными разрядами.

ну, я десятичной арифметики не знаю.
Может и не знал никогда, я в школе уже давно учился.
И вообще - это голландские методы.
...
Рейтинг: 0 / 0
17.09.2020, 22:19
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000087
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
booby
голландские методы.

Применительно к number с его bcd-мантиссой и десятичным порядком самое оно, деление на 10 - то же что деление на 2 в сях
...
Рейтинг: 0 / 0
18.09.2020, 00:12
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000088
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
andrey_anonymous,

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

как смутная пока идея - идеально было бы получать два соседних показателя степени
для заполненных разрядов в числе, стартуя с некоторого заданного
(в общем - не важно даже, в каком обязательно направлении двигаясь).

Тогда стартуя с msb (или даже lsb, в расчете, что он "где-то рядом"), можно было бы быстро и точно вставать только на значимые разряды.
Думаю, для обоих вариантов (право/лево, msb/lsb) подходящий код должен обнаружиться и быть сходной степени сложности.
...
Рейтинг: 0 / 0
18.09.2020, 00:13
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000089
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
andrey_anonymous
booby
голландские методы.

Применительно к number с его bcd-мантиссой и десятичным порядком самое оно, деление на 10 - то же что деление на 2 в сях

Уговорил, обращусь к изучению наследия Симона Стевина - изобретателя десятичного поиска.
...
Рейтинг: 0 / 0
18.09.2020, 00:16
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000091
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
andrey_anonymous
...промеждупрочим, а для зачем вообще на биты уходить?
Можно же обойтись десятичными разрядами.


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

Зато центнерная ордината хранится прямо в числе - ничего не надо считать.
Код: plaintext
1.
2.
3.
4.
SQL> select dump(170141183460469231731687303715884105727) from dual
  2  /
DUMP(1701411834604692317316873
--------------------------------------------------------------------------
Typ=2 Len=21:  212 ,2,71,15,12,84,47,5,70,24,18,32,69,74,4,72,59,85,11,58,28

В первом байте хранится центнерная ордината 19 для 100^19 (там надо 193 вычесть) а
по следующему байту сразу видна самая старшая десятичная цифра.

Это значит что все арифметические операции с NUMBER выполняются практически в столбик,
без привлечения скоростных возможностей процессора, а с делением таких чисел вообще атас.
Зато их удобно хранить и печатать. И еще log10 наверное быстро работает.

Ради любопытства, посчитал простую арифметику миллион раз на PL/SQL и на сях. Разница в скорости около 300 раз.
...
Рейтинг: 0 / 0
18.09.2020, 00:19
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000092
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НеофитSQL
Гость
andrey_anonymous
booby
голландские методы.

Применительно к number с его bcd-мантиссой и десятичным порядком самое оно, деление на 10 - то же что деление на 2 в сях


Лучше делить на 100 (декремент мантиссы на 1), иначе будет все число двигать на полбайта.
...
Рейтинг: 0 / 0
18.09.2020, 00:22
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000096
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
У меня впечатление, что тема, по крупному, исчерпана.
Спасибо всем, кто так или иначе участвовал.

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

Ещё раз всем спасибо.
...
Рейтинг: 0 / 0
18.09.2020, 01:23
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000101
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
НеофитSQL
Действительно, я только что для себя обнаружил что NUMBER хранится в десятичном виде
НеофитSQL
Зато центнерная ордината хранится прямо в числе - ничего не надо считать.
Код: plaintext
ну зачем опять что-то придумывать от себя... Чти доку:
https://docs.oracle.com/en/database/oracle/oracle-database/19/lnoci/data-types.html#LNOCI-GUID-91151345-2C67-41BC-A782-AD4816B89BCF


НеофитSQL
Ради любопытства, посчитал простую арифметику миллион раз на PL/SQL и на сях. Разница в скорости около 300 раз.
нашел что сравнивать...



andrey_anonymous,

почему в PL/SQL с NUMBER, а не simple_double? a в SQL c binary_double?
...
Рейтинг: 0 / 0
18.09.2020, 02:02
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000102
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
xtender
почему в PL/SQL с NUMBER, а не simple_double? a в SQL c binary_double?
т.е. т.к. ищется только старший бит, то погрешностью младших разрядов в binary_double можно спокойно пренебречь
...
Рейтинг: 0 / 0
18.09.2020, 02:06
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000105
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
xtender,

Number заказывал я как топикстартер.
У binary_double другой диапазон, да и для него нет самостоятельного определения bitand в pl/sql.
Он быстрый, но в этой задаче - не нужный.
Думаю, что всё-таки ты pls_integer подразумевал.

это хороший короткий вариант.
Но тут уж точно поле состояния агрегата в объекте будет raw.
С учетом его знаковости - я не проверял, правильно ли он держит 31 бит в процессе вычисления.
Но то, что на 30 битах с ним можно работать без опасений и быстро - это очевидно.
...
Рейтинг: 0 / 0
18.09.2020, 02:52
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000107
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
booby
У binary_double другой диапазон
достаточный для твоих условий
booby
Думаю, что всё-таки ты pls_integer подразумевал.
нет, именно binary_double как раз из-за диапазона


booby
для него нет самостоятельного определения bitand в pl/sql.
вообще в первую очередь я подумал про dump для него:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
  1  with t(x) as (
  2  select cast(column_value as binary_double) from table(sys.odcinumberlist(1,2,4,8,32,64,128,1024,170141183460469231731687303715884105727))
  3  )
  4  select
  5  x,
  6  dump(x,16) dd
  7* from t
SQL> /

         X DD
---------- --------------------------------------------------
  1.0E+000 Typ=101 Len=8: bf,f0,0,0,0,0,0,0
  2.0E+000 Typ=101 Len=8: c0,0,0,0,0,0,0,0
  4.0E+000 Typ=101 Len=8: c0,10,0,0,0,0,0,0
  8.0E+000 Typ=101 Len=8: c0,20,0,0,0,0,0,0
  3.2E+001 Typ=101 Len=8: c0,40,0,0,0,0,0,0
  6.4E+001 Typ=101 Len=8: c0,50,0,0,0,0,0,0
 1.28E+002 Typ=101 Len=8: c0,60,0,0,0,0,0,0
1.024E+003 Typ=101 Len=8: c0,90,0,0,0,0,0,0
1.701E+038 Typ=101 Len=8: c7,e0,0,0,0,0,0,0

9 rows selected.
...
Рейтинг: 0 / 0
18.09.2020, 04:16
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000108
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
booby,

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
with t(x) as (
select cast(column_value as binary_double) from table(sys.odcinumberlist(1,2,4,8,32,64,128,1024,170141183460469231731687303715884105727))
)
select 
x,
dump(x,16) dd,
regexp_replace(dump(x,16), '.*: .(.),(.).*','\1\2') bb,
to_number(regexp_replace(dump(x,16), '.*: .(.),(.).*','\1\2'),'XX')+1 msb
from t;

         X DD                                                 BB                MSB
---------- -------------------------------------------------- ---------- ----------
  1.0E+000 Typ=101 Len=8: bf,f0,0,0,0,0,0,0                   ff                256
  2.0E+000 Typ=101 Len=8: c0,0,0,0,0,0,0,0                    00                  1
  4.0E+000 Typ=101 Len=8: c0,10,0,0,0,0,0,0                   01                  2
  8.0E+000 Typ=101 Len=8: c0,20,0,0,0,0,0,0                   02                  3
  3.2E+001 Typ=101 Len=8: c0,40,0,0,0,0,0,0                   04                  5
  6.4E+001 Typ=101 Len=8: c0,50,0,0,0,0,0,0                   05                  6
 1.28E+002 Typ=101 Len=8: c0,60,0,0,0,0,0,0                   06                  7
1.024E+003 Typ=101 Len=8: c0,90,0,0,0,0,0,0                   09                 10
1.701E+038 Typ=101 Len=8: c7,e0,0,0,0,0,0,0                   7e                127

9 rows selected.
...
Рейтинг: 0 / 0
18.09.2020, 04:22
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000109
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
xtender,

ff + 1 = 0, просто лень допилить
...
Рейтинг: 0 / 0
18.09.2020, 04:25
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000199
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
Ну и чем это предпочтительнее to_char с прямым подсчетом?
...
Рейтинг: 0 / 0
18.09.2020, 11:45
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000209
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
andrey_anonymous,

Код: plsql
1.
to_number(replace(substr(dump(x,16), 17,3),','),'XX')+1


to_char(x,'fmXXXXXXXXXXXXXXXX') + что именно? хардкодинг через decode от substr + length * 8? или to_number от substr(to_char(x,'fmXXXXXXXXXXXXXXXX'),1,1) + что?
Покажи, что именно ты имеешь ввиду? сравним
...
Рейтинг: 0 / 0
18.09.2020, 12:00
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000212
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
andrey_anonymous,

или 22199578 предпочтительнее чем простой короткий to_number(replace(substr(dump(x,16), 17,3),','),'XX')+1
...
Рейтинг: 0 / 0
18.09.2020, 12:02
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000220
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
xtender
andrey_anonymous,
или 22199578 предпочтительнее чем простой короткий to_number(replace(substr(dump(x,16), 17,3),','),'XX')+1


А в чем тут проблема, короткий поиск по крошечному наглухо закэшированному индексу без преобразований типов - вполне себе вариант на мой взгляд для sql-решения.

Твой метод предполагает:
1. расходы на cast (сопоставимо с to_char)
2. dump-преобразование double в строку
2.1 нештатное использование dump (где-то гарантируется формат его выдачи?)
3. строчные операции над результатом dump (особенно regexp)
4. to_number

Метод Elic:
1. to_char
2. substr 1-го байта и его decode.
3. обратный to_number

Если уж идти в строчку - я бы предпочел вариант Виталия уже ввиду отсутствия рисков side-effect.
...
Рейтинг: 0 / 0
18.09.2020, 12:26
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000221
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
andrey_anonymous,

ну закодь - посмотрим, сравним
...
Рейтинг: 0 / 0
18.09.2020, 12:27
| Ответить | Цитировать | Написать  
msb (most significant bit) на pl/sql есть готовый?
    #40000226
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sayan Malakshinov
Модератор форума
andrey_anonymous,

вот как точка отсчета:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
with 
  t(n) as (select level from dual connect by level<=5e3) 
 ,s0(x) as (select t1.n*1e6 + t2.n as x from t t1,t t2) -- 5e3^2 - 38.7sec - 757085000
select 
   sum(to_number(replace(substr(dump(cast(x as binary_double),16), 17,3),','),'XX')+1) sum_msb
from s0 
/


Этих двух я не дождался:
 
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
with 
  t(n) as (select level from dual connect by level<=5e3) 
 ,s0 (x) as (select t1.n*1e6 + t2.n as x from t t1,t t2) -- 5e3^2 - 38.7 - 757085000
 , powers as  (select power(2,level-1) msb, level-1 msb_pos from dual connect by level < 129)
select sum(Msb_pos)
from s0
   , lateral(-- закос под трюк "поиск максимума, не превосходящего N", на этом форуме впервые продемонстрированый коллегой Elic лет... много тому :)
            select msb y, msb_pos from powers where msb<x+1 order by msb desc fetch first 1 row only)
;
/
with 
  t(n) as (select level from dual connect by level<=5e3) -- 5e3 - 38.7 - 757085000
 ,s0 (x) as (select t1.n*1e6 + t2.n as x from t t1,t t2)
, s1 as  (select x, bitand(-x/2-1, -x/4-1) y from s0)
, s2 as  (select x, bitand(y, y/4 - 1) y from s1)
, s8 as  (select x, bitand(y, y/16 - 1) y from s2)
, s16 as (select x, bitand(y, y/256 - 1) y from s8)
, s32 as (select x, bitand(y, y/65536 - 1) y from s16)
, s64 as (select x, bitand(y, y/4294967296 - 1) y from s32)
, s128 as(select x, -(bitand(y, y/18446744073709551616 - 1)) y from s64)
select sum(log(2,y)) Msb_pos
from s128
;

...
Рейтинг: 0 / 0
18.09.2020, 12:39
| Ответить | Цитировать | Написать  
25 сообщений из 87, страница 2 из 4
  2  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / msb (most significant bit) на pl/sql есть готовый?
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=40000087&tid=1880837]:
 0ms
get settings:
 7ms
get forum list:
 11ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 55ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 52ms
get tp. blocked users:
 1ms
others: 303ms
total:  446ms
созд. / загр.: 446ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]