|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
Внезапно потребовался алгоритм нахождения most significant bit на pl/sql Хотелось бы, чтобы он надежно и быстро работал в диапазоне чисел: 0 - 170141183460469231731687303715884105727 (power(2,127)-1) К сожалению, стандартный Log(2,x) не пригоден к использованию на всем диапазоне, он быстро перестает различать Log(2,x) и Log(2, x-1), и трюками сорта Round(L,20) это не вылечишь. Деление в цикле с наращиванием счётчика сразу отбрасываем. На поверхности сейчас вижу либо явный двоичный поиск в массиве на 126 элементов, либо его реализацию последовательностью явных If-ов. Что к этому делу еще можно было бы приспособить, работающего хотя бы за логарифм от максимальной разрядности? Может кто покажет прямые трюки со значениями utl_raw.cast_from_number. Наверно что-то понятное и легко проверяемое там можно получать, стартуя с HexToRaw, но меня пока смущает необходимость приведения числа к строковому представлению в таком варианте... Что присоветуете, коллеги? а вдруг где-то в стандартных пакетах стандартная функция зашита... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 12:45 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
msb применительно к какому типу данных? За логарифм от разрядности - можно, полагаю, делением с двоичным поиском. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 12:55 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous, неотрицательный number, укладывающийся в набор значений до максимального беззнакового 126-битного целого. (диапазон я указал в первом посте) Двоичный поиск я вижу.. Сейчас думаю,как понизить его глубину. Вроде вдвое она должна разделяться в смысле максимального размера массива 63 а не 126, но пока не сообразил, как это точно выписать. Мне пока верится, что может найтись что-то чуть умнее/хитрее чем двоичный поиск. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 13:04 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
boobyДеление в цикле с наращиванием счётчика сразу отбрасываем. А почему, собственно? Делишь, например, на 65536 пока значение не войдёт в диапазон целого или хотя бы область определения логарифма. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 13:05 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby хитрее чем двоичный поиск. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 13:15 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov, понял, 4 деления, на 64-битных значениях Log уже какие-то признаки жизни показывает вроде. Спасибо. Положил на ум. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 13:17 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
Elic booby хитрее чем двоичный поиск. to_char(…, 'fmXXX…') - такого сорта начало мне понятно, дальше что-то про utl_raw. Что про цену to_char по отношению к логарифму можно сказать? Как-то to_char меня пока пугает, побаиваюсь я его.... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 13:24 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby дальше что-то про utl_raw. Код: plsql 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 13:40 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
Elic, над raw код такого типа будет за "константу" отрабатывать, на varchar2 - время length, например, окажется функцией текущей кодировки бд. я подумаю. msb - это фрагмент задачи. Может быть, внутреннее представление данных в ней целиком и правда разумно будет перевести в raw, отдавая только конечный результат в виде числа. Поток входного to_char, мне пока всё равно не нравится. Но, может быть... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 14:28 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
Логарифм... Есть жеж методы против Кольки Сапрыкина Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 14:36 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous, вау, красота-то какая. Пойду глаза промою, а то слепит, аж невмоготу. Премного благодарен. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 15:06 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous, Еще раз спасибо. И ведь я видел этот вариант в интернете, перед тем как писать, в виде кода на C, но целиком просклизил мимо него, теперь даже досадно. В частичное оправдание под капот кладу рядом с твоим, то, что получается после линеаризации и возвращения к "классическому" виду. Задача почти не встречается, но вдруг кому-то полезным окажется, поэтому оставил в коде комментарий для итересующихся, как оно работает. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 18:31 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby слепит, аж невмоготу. Это от отсутствия bitOr :( ...кстати, я там накосячил с порядками. Рекурсия не n+1, а n*2 плюс поправить кондиции ...а если немного вспомнить алгебру, то можно и чуть попроще... Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 19:12 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
Ну а если выбросить из головы глупости и двигать по-нашенски, по-базейски... Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32.
...на pl/sql аналогично используется ассоциативный массив, но там чуть сложнее - надо бить number на 4 binary_integer, в pl/sql оно 32-битное. Ну или длинный case сгенерить. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 19:37 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous, как bitor получить я понимал, как и то, почему в нём сначала минус кошерно риовать, а не плюс последний член. проскользил я мимо того обстоятельства, что между 32 разрядами и 128ю всего два шага алгоритма. то, что ты сейчас показываешь понятно, но общее число шагов вроде не уменьшает.. может быть, if-ы переставляются. про хранение поднабора степеней в массиве на небольшое число элементов я может быть посмотрю. PS я как раз агрегатный bitor сочиняю. и msb мне нужен, чтобы корректно обыгрывать случай применения в качестве аналитической функции. Так что в кишках чистый pl/sql будет. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 19:53 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby я как раз агрегатный bitor сочиняю. и msb мне нужен, чтобы корректно обыгрывать случай применения в качестве аналитической функции. Так что в кишках чистый pl/sql будет. Ну дык bitor(a,b) - он жеж -bitand(-a-1,-b-1)-1 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 20:19 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby, > Деление в цикле с наращиванием счётчика сразу отбрасываем. На C это был бы наверное самый быстрый способ (после разбивания по размеру слова архитектуры, по 32/64), т.к. цикл из двух-трех инструкций повтором в 30-60 выполняется быстрее чем вызов функции и возврат. Поиск в дереве - это всего 7 сравнений (но 128 бит, считаем как 14 сравнений машинных слов) тоже очень быстро если машинный код генерится хороший. Лукап по таблице еще не обсуждали? В сях это коротко и быстро. PL/SQL проверяет индексы, поэтому вряд ли. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
Больше таблица - больше скорость. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 20:29 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous, мне лично bitor(a,b) = a - bitand(a, b) + b намного приятнее. Такой я на автомате, с закрытыми глазами и не задумываясь, писать умею. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 20:32 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby про хранение поднабора степеней в массиве на небольшое число элементов я может быть посмотрю. Так что в кишках чистый pl/sql будет. Про BitOr я уже вроде сказал - если делать агрегатку, то зачем следить за msb я не очень понимаю. Про решение на pl/sql - всё достаточно просто, но ограничения на индексы ассоциативных массивов требуют либо уходить в строку, либо заниматься такой хренотенью: Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 20:47 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby andrey_anonymous, мне лично bitor(a,b) = a - bitand(a, b) + b намного приятнее. Ну я бы потестил по производительности. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 20:48 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous ... если делать агрегатку, то зачем следить за msb я не очень понимаю. ... Если задумывать честное применение в качестве аналитической функции, то полезно под рукой иметь честный способ частичного извлечения данных устаревшего окна и добавления данных нового без переиницализации состояния агрегата. Имея годный по скорости msb это можно поддержать. Правда может состоять в том, что это, на самом деле, всего лишь замедляющее агрегат излишество. Пока я еще не вполне понимаю, останется поддержка такого сорта кода, или нет в окончательном варианте. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 20:56 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
про "медленную проверку индекса массива". Ну, эта проверка все равно идет на атрибутах экземпляра типа, так что смертельно медленной она не будет. И, если уж смерть как хочется, чтобы "как в C по смещению" - извлечение подстроки из raw всегда есть, правда за счет работы с вызовом функции на стеке. (Может быть, так я и сделаю счетчик занятых битов в агрегате, пока не знаю еще, пока все это - ковыряния в носу.) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 21:02 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby Имея годный по скорости msb это можно поддержать. С ходу что-то не соображу как, было бы интересно при случае взглянуть. ...и вот еще, если данные изначально лежат в raw, то utl_raw умеет и or, и xor и даже complement :) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 21:02 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
andrey_anonymous booby Имея годный по скорости msb это можно поддержать. С ходу что-то не соображу как, было бы интересно при случае взглянуть. ...и вот еще, если данные изначально лежат в raw, то utl_raw умеет и or, и xor и даже complement :) вторую часть вопроса я потенциально держу в голове. Но тогда либо сам агрегат должен сразу работать с raw, а не с number, либо откуда-то надо брать тайные знания. Для number понятные мне продолжения в таком написании стартуют с hextoRaw. А to_char-у, который тот hex должен получить, я не доверяю в плане производительности. По первой части: потенциально одни и те же значения могут попадать в агрегат произвольное число раз. При оговоренной максимальной разрядности думаю держать счетчик попаданий в соответствующий бит счётчика-абака, Дальше, пока "разряд" абака больше единицы, он уменьшается на единицу, а если равен единице, то вместе с уменьшением значения в разряде абака, обнуляется бит агрегата. Для поданного на удаление из агрегата числа работа с ним должна начинаться с msb этого удаляемого числа. Вот всё. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 21:20 |
|
msb (most significant bit) на pl/sql есть готовый?
|
|||
---|---|---|---|
#18+
booby либо откуда-то надо брать тайные знания. Хранение number в oracle не предполагает его прозрачную конвертацию в бинарное целое и, соответственно, в raw - там банально десятичная степень, а не двоичная - т.е. мантисса не сохраняется при умножении/делении на степени 2. Потому и написал - "если данные хранятся в raw" hextoRaw принимает на вход только Hex, т.е. без to_char не обойтись (явно или неявно). Есть вариант cast_from_number, но он тоже потребует битовых операций - выделить мантиссу, степень, как-то домножить одно на другое но уже в виде целого - затем уже компоновать целевой целочисленный raw. booby Для поданного на удаление из агрегата числа работа с ним должна начинаться с msb этого удаляемого числа. Насколько я понимаю, в описанном варианте достаточно все равно с какого байта браться дерибанить число на биты (дабы вычитать побитовый абак). Если справа и делением - то окончание по достижению 0 и не требуется никакой msb... Впрочем, хозяин-барин, я не настаиваю :) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.09.2020, 21:37 |
|
|
start [/forum/topic.php?fid=52&msg=39999754&tid=1880837]: |
0ms |
get settings: |
7ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
149ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
60ms |
get tp. blocked users: |
1ms |
others: | 13ms |
total: | 257ms |
0 / 0 |