21

Re: Абстрактна алгебра, теорія груп, скінченні групи.

koala написав:

ООП = АТД + успадкування + поліморфізм. АТД в Haskell ніби є (ага, робіть монади без них).
Що саме вам треба успадковувати і поліморфувати?

дивіться прикол --
є певний код на python
(повинен виводити з певними змінами матрицю),
і я отримав запитання у себе в телеграм чаті,
чому він виводить не

* . . . . 
. * . . . 
. . * . . 
. . . * . 
. . . . * 

а

* . . . . 
* * . . . 
* * * . . 
* * * * . 
* * * * * 

гіст https://gist.github.com/221V/c9f752e395 … 3915e14789

з однієї сторони, я пайтон другий раз бачу (перший раз -- нейронку писав на хаскелі з нуля, дивлячись на пайтон-імплементацію)
з іншої сторони, результат роботи прикладу дивує, відрізняється від аналогічного на php/js

довелось піти з запитанням далі, і більш досвідчені пайтоністи пояснили:
(варнінг, російська)

Прихований текст

XXX:
Когда пишешь так (matrix = [['.']*n]*n),
то у тебя получается по факту N строк в матрице,
которые ссылаются на одну и ту же строку,
поэтому меняя что-либо в одной строке у тебя поменяется во всех строках
Исправь на matrix = [['.' for _ in range(n)] for _ in range(n)]

YYY:
Немного не так. Строки иммутабельны. Проблема во втором умножении листа.
Лист листов , умноженный на n создаёт  n ссылок на один и то же лист
[1]*3
тут все ок
[[1]] * 3
тут создаётся лист из трех ссылок на [1]

Прихований текст

і тут Тарас усвідомив та просвітлів --
не такий пайтон чудовий, як його розхваляють,
і не завжди його магія корисна,
а в haskell всякої такої напряжної фігні на порядки менше, імхо
тобто я для себе вибираю js (vanilla, лише для браузера), erlang (де числодробилка не горить), haskell (де потрібна хороша числодробилка, чи на десктоп віконечка з gtk+)
+ мб ще Kotlin для андроіда чи й wasm
і ще десь залишиться php для якогось дрібного фрілансу, чи потицяти asm для задоволення цікавості :)

хоча, розбирати в оптимізаціях компіляторів та оптимізаторів, і в сотнях нових спецкоманд сучасних процесорів -- це те ще збочення, подивився і половину бажання колупати asm як рукою зняло :)

прошу пробачення за оффтоп, таку цікаву тему зіпсував, мовчу)

Подякували: leofun011

22

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Ласкаво прошу в розділ про Python, якщо хочете там вилити.
Так, мови поділяються на дві категорії: ті, які лають, і ті, якими не користуються. У Python-а це чи не основна халепа - неочевидні передачі посилань замість значень. Але є ж і переваги.

Подякували: 221VOLT, leofun01, ostap34PHP3

23

Re: Абстрактна алгебра, теорія груп, скінченні групи.

221VOLT написав:
leofun01 написав:

За часів заснування проекту мені довелось вибирати між кількома мовами (C++, Java, C#, Python, PHP, Haskell).
Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.



Поки нема документації по коду - так, це жах.



Не робіть, не повторюйте моїх помилок. Я вже наступив на ці граблі, тільки час марно потратив.

Замість "простенького конструктора" використовую Inkscape, але він "пише не охайно", після нього доводиться повністю переписувати.

не розумію, в чім там складність підтримки
не розумію, про які саме корисні потрібні властивості ООП, відсутні в haskell, йде мова
(мб тому, що я ще не повністю вивчив хаскель, "не осилив" ООП, та не розумію, чому так багато людей навколо так захоплено видихає "ООП, ООП")


та ні, я скоріше про сам код, організацію коду та синтаксис
(мої особисті заморочки по темі "подобається/не подобається", не звертайте уваги)


чому граблі та час марно потратив?

FakiNyan написав:

пишіть на js, для строгої типізації можна було б typescript накатити, я вам кажу, круто було б.

прошу пробачення за оффтоп, а у чім перевага js над haskell чи C# (в контексті цієї теми)?
допустимо, в haskell багато де ноги з математики ростуть, C# -- приємний звичний інструмент для ТС, а js ?

там багато приколів є, а ще то можна в бровзері запускати, зараз весь світ рухається в сторону того,, що більшість завдань можна буде робити в бровзері + бровзери всюди є, а це означає, що для кодування пану леофун01 треба буде лише бровзер, бровзер може бути навіть на мобілці. Ви уявляєте? От поїхав пан леофун01 в сусіднє село до дівчат, а дівчата не прийшли, і шо робити? правильно, діставати свого мобільного девайса і кодити! JS дозволяє робити то без проблем.
І якщо пану леофун01 колись набридне математика, і він захоче просто шльопати формочки і додавати 2 до 2 використовуючи якийсь модній сучасний фреймворк - то він вже буде знати JS, і йому не потрібно буде напружуватись з пошуком роботи.

Подякували: leofun011

24

Re: Абстрактна алгебра, теорія груп, скінченні групи.

FakiNyan написав:

пишіть на js, для строгої типізації можна було б typescript накатити

+ за TypeScript, обов'язково його розгляну. Та спочатку мені треба JavaScript довчити.

221VOLT написав:

не розумію, в чім там складність підтримки

Я абсолютно не пам'ятаю, що я робив 2 місяці назад. Іноді доводиться повертатись до давно написаного коду і читати його як чужий. На Haskell я б не зміг так.

221VOLT написав:

не розумію, про які саме корисні потрібні властивості ООП, відсутні в haskell, йде мова

  • Опис типів (структури, класи). Мені зручно думати про абстрактні типи як про класи об'єктів, які об'єднують в собі дані і методи їх обробки.

  • Наслідування. Будь-який елемент скінченної групи { є елементом групи (довільної), є елементом скінченної множини }, будь-який елемент групи є елементом множини, і будь-який елемент скінченної множини є елементом множини (довільної). Таких послідовностей наслідування там багато.

  • Поліморфізм. Зберігати групи можна по різному, відповідно і поведінка формування груп має бути різною, і способи отримання елементів мають бути різними (загалом).

221VOLT написав:
leofun01 написав:

Поки нема документації по коду - так, це жах.

та ні, я скоріше про сам код, організацію коду та синтаксис

Якщо виникають питання по коду то задавайте, все поясню.

221VOLT написав:
leofun01 написав:

Я вже наступив на ці граблі, тільки час марно потратив.

чому граблі та час марно потратив?

Щоб зробити робочий продукт (SVG редактор), треба :

  1. прочитати специфікацію по SVG (це вже купа роботи),

  2. запрограмувати відрисовку кожного елемента (а їх там з пів сотні різних типів).

Навіть якщо відкинути все, і працювати тільки з path, circle і g, то для них потрібна обробка атрибутів.
В мене це була вже друга спроба зробити подібний редактор і вона провалилася.

koala написав:

ООП = АТД + успадкування + поліморфізм. АТД в Haskell ніби є (ага, робіть монади без них).
Що саме вам треба успадковувати і поліморфувати?

Якщо в двох словах, то відповідь є в цьому повідомленні вище. А для уявлення загальної картини пропоную переглянути діаграму класів :
ClassDiagram_Part1.png

FakiNyan написав:

От поїхав пан леофун01 в сусіднє село до дівчат, а дівчата не прийшли, і шо робити? правильно, діставати свого мобільного девайса і кодити!

:D ... :(
Тру сторі.

Подякували: 221VOLT, dot, FakiNyan3

25

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Недавно зробив групу перестановок ізоморфну до групи трансформацій тесеракта (384 елементи).
Довго медитував над тою таблицею і ... тепер в мене купа роботи. Якби ж я міг передати ту красу, яку побачив ...

Подякували: 221VOLT1

26 Востаннє редагувалося 221VOLT (05.10.2019 18:37:58)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Прихований текст

мм... перестановки на хаскелі можна генераторами зробити

в чім відмінність?
де практичне застосування, окрім криптографії, брутфорсу і всякого такого



запитання з метою визначитись, де у черзі задач можна відвести місце цим приколам

... а краса є всюди) у всьому) завжди

Подякували: leofun011

27

Re: Абстрактна алгебра, теорія груп, скінченні групи.

221VOLT написав:

в чім відмінність?

Відмінність між чим ?
В ролі генератора я використовую метод CreateGroup<PermutationInt64>(...), який на основі кількох початкових перестановок генерує список всіх можливих результатів їх додавання.

221VOLT написав:

з метою визначитись ... де практичне застосування

Мета: розвертати багатовимірні масиви за мілісекунди, не залежно від їхніх розмірів.
Так, це можливо. Цього можна досягнути за рахунок обробки індексів, а не самого масиву. Ідея в тому, що користувач (програміст) замість масиву, створює екземпляр класу-обгортки, і цей екземплар містить посилання на масив (довільних розмірів) і дані про трансформацію (кілька байт). Коли користувач викликає метод повороту масиву, то для користувача це виглядає наче масив реально розвернувся, бо в елементів масиву тепер нові індекси. Але на рівні віртуальної памяті (і на фізичному рівні) масив не змінився і його елементи сидять в тих самих місцях, змінилося тільки значення трансформації, яке впливає на обробку індексів, які передає користувач.
Захотів розвернути масив 500Мб => 100мсек => готово.

Можна піти дальше і розвертати будь-які об'єкти, наприклад геометричні фігури ...

Самі перестановки - не ціль, а інструмент для її досягнення. Без них я б не зміг знайти властивості трансформацій у багатовимірних просторах.
На даний момент я намагаюсь створити спосіб обробки індексів для 4-вимірних масивів, тому група перестановок побудована саме для тесеракта. І саме на прикладі цієї фігури я знайшов спосіб узагальнити алгоритми на куби більших вимірностей.

Подякували: 221VOLT, ReAl2

28 Востаннє редагувалося 221VOLT (06.10.2019 01:39:13)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Прихований текст

складно... не доганяю... ідіотом почуваюсь)

leofun01 написав:

В ролі генератора я використовую метод CreateGroup<PermutationInt64>(...), який на основі кількох початкових перестановок генерує список всіх можливих результатів їх додавання.

combinations1 :: Int -> [a] -> [[a]]
combinations1 0 _  = return []
combinations1 n xs = do y:xs2 <- tails xs
                        ys <- combinations1 (n - 1) xs2
                        return (y:ys)

{-
ghci> combinations1 2 [0,1,2,3]
[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]
ghci> combinations1 3 [0,1,2,3]
[[0,1,2],[0,1,3],[0,2,3],[1,2,3]]
ghci> combinations1 4 [0,1,2,3]
[[0,1,2,3]]
-}

подібне до цього? (це унікальні значення)

+

replicateM2 0 xs = return []
replicateM2 n xs = do
   b <- replicateM2 (n-1) xs
   a <- xs
   return (b ++ [a])
Прихований текст
ghci> replicateM2 2 [0,1,2,3]
[[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3],[3,0],[3,1],[3,2],[3,3]]
ghci> replicateM2 4 [0,1,2,3]
[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,0,3],[0,0,1,0],[0,0,1,1],[0,0,1,2],[0,0,1,3],[0,0,2,0],[0,0,2,1],[0,0,2,2],[0,0,2,3],[0,0,3,0],[0,0,3,1],[0,0,3,2],[0,0,3,3],[0,1,0,0],[0,1,0,1],[0,1,0,2],[0,1,0,3],[0,1,1,0],[0,1,1,1],[0,1,1,2],[0,1,1,3],[0,1,2,0],[0,1,2,1],[0,1,2,2],[0,1,2,3],[0,1,3,0],[0,1,3,1],[0,1,3,2],[0,1,3,3],[0,2,0,0],[0,2,0,1],[0,2,0,2],[0,2,0,3],[0,2,1,0],[0,2,1,1],[0,2,1,2],[0,2,1,3],[0,2,2,0],[0,2,2,1],[0,2,2,2],[0,2,2,3],[0,2,3,0],[0,2,3,1],[0,2,3,2],[0,2,3,3],[0,3,0,0],[0,3,0,1],[0,3,0,2],[0,3,0,3],[0,3,1,0],[0,3,1,1],[0,3,1,2],[0,3,1,3],[0,3,2,0],[0,3,2,1],[0,3,2,2],[0,3,2,3],[0,3,3,0],[0,3,3,1],[0,3,3,2],[0,3,3,3],[1,0,0,0],[1,0,0,1],[1,0,0,2],[1,0,0,3],[1,0,1,0],[1,0,1,1],[1,0,1,2],[1,0,1,3],[1,0,2,0],[1,0,2,1],[1,0,2,2],[1,0,2,3],[1,0,3,0],[1,0,3,1],[1,0,3,2],[1,0,3,3],[1,1,0,0],[1,1,0,1],[1,1,0,2],[1,1,0,3],[1,1,1,0],[1,1,1,1],[1,1,1,2],[1,1,1,3],[1,1,2,0],[1,1,2,1],[1,1,2,2],[1,1,2,3],[1,1,3,0],[1,1,3,1],[1,1,3,2],[1,1,3,3],[1,2,0,0],[1,2,0,1],[1,2,0,2],[1,2,0,3],[1,2,1,0],[1,2,1,1],[1,2,1,2],[1,2,1,3],[1,2,2,0],[1,2,2,1],[1,2,2,2],[1,2,2,3],[1,2,3,0],[1,2,3,1],[1,2,3,2],[1,2,3,3],[1,3,0,0],[1,3,0,1],[1,3,0,2],[1,3,0,3],[1,3,1,0],[1,3,1,1],[1,3,1,2],[1,3,1,3],[1,3,2,0],[1,3,2,1],[1,3,2,2],[1,3,2,3],[1,3,3,0],[1,3,3,1],[1,3,3,2],[1,3,3,3],[2,0,0,0],[2,0,0,1],[2,0,0,2],[2,0,0,3],[2,0,1,0],[2,0,1,1],[2,0,1,2],[2,0,1,3],[2,0,2,0],[2,0,2,1],[2,0,2,2],[2,0,2,3],[2,0,3,0],[2,0,3,1],[2,0,3,2],[2,0,3,3],[2,1,0,0],[2,1,0,1],[2,1,0,2],[2,1,0,3],[2,1,1,0],[2,1,1,1],[2,1,1,2],[2,1,1,3],[2,1,2,0],[2,1,2,1],[2,1,2,2],[2,1,2,3],[2,1,3,0],[2,1,3,1],[2,1,3,2],[2,1,3,3],[2,2,0,0],[2,2,0,1],[2,2,0,2],[2,2,0,3],[2,2,1,0],[2,2,1,1],[2,2,1,2],[2,2,1,3],[2,2,2,0],[2,2,2,1],[2,2,2,2],[2,2,2,3],[2,2,3,0],[2,2,3,1],[2,2,3,2],[2,2,3,3],[2,3,0,0],[2,3,0,1],[2,3,0,2],[2,3,0,3],[2,3,1,0],[2,3,1,1],[2,3,1,2],[2,3,1,3],[2,3,2,0],[2,3,2,1],[2,3,2,2],[2,3,2,3],[2,3,3,0],[2,3,3,1],[2,3,3,2],[2,3,3,3],[3,0,0,0],[3,0,0,1],[3,0,0,2],[3,0,0,3],[3,0,1,0],[3,0,1,1],[3,0,1,2],[3,0,1,3],[3,0,2,0],[3,0,2,1],[3,0,2,2],[3,0,2,3],[3,0,3,0],[3,0,3,1],[3,0,3,2],[3,0,3,3],[3,1,0,0],[3,1,0,1],[3,1,0,2],[3,1,0,3],[3,1,1,0],[3,1,1,1],[3,1,1,2],[3,1,1,3],[3,1,2,0],[3,1,2,1],[3,1,2,2],[3,1,2,3],[3,1,3,0],[3,1,3,1],[3,1,3,2],[3,1,3,3],[3,2,0,0],[3,2,0,1],[3,2,0,2],[3,2,0,3],[3,2,1,0],[3,2,1,1],[3,2,1,2],[3,2,1,3],[3,2,2,0],[3,2,2,1],[3,2,2,2],[3,2,2,3],[3,2,3,0],[3,2,3,1],[3,2,3,2],[3,2,3,3],[3,3,0,0],[3,3,0,1],[3,3,0,2],[3,3,0,3],[3,3,1,0],[3,3,1,1],[3,3,1,2],[3,3,1,3],[3,3,2,0],[3,3,2,1],[3,3,2,2],[3,3,2,3],[3,3,3,0],[3,3,3,1],[3,3,3,2],[3,3,3,3]]


leofun01 написав:

Мета: розвертати багатовимірні масиви за мілісекунди, не залежно від їхніх розмірів.
...
для користувача це виглядає наче масив реально розвернувся, бо в елементів масиву тепер нові індекси. Але на рівні віртуальної памяті (і на фізичному рівні) масив не змінився і його елементи сидять в тих самих місцях, змінилося тільки значення трансформації, яке впливає на обробку індексів, які передає користувач.
Захотів розвернути масив 500Мб => 100мсек => готово.
...

це звучить, деякою частиною, наче ліниві обчислення в хаскелі

а все решта я просто не догнав... ех

Подякували: leofun011

29

Re: Абстрактна алгебра, теорія груп, скінченні групи.

221VOLT написав:
ghci> combinations1 2 [0,1,2,3]
[[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]

подібне до цього?

Скоріше до такого :

> permutationslist [[1,0,2,3],[0,1,3,2]]
[[0,1,2,3],[1,0,2,3],[0,1,3,2],[1,0,3,2]]

> permutationslist [[1,0,2,3],[0,2,1,3]]
[[0,1,2,3],[1,0,2,3],[0,2,1,3],[1,2,0,3],[2,0,1,3],[2,1,0,3]]

221VOLT написав:

складно...

З часом ми це виправимо.

Подякували: 221VOLT1

30

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:

Скоріше до такого :

> permutationslist [[1,0,2,3],[0,1,3,2]]
[[0,1,2,3],[1,0,2,3],[0,1,3,2],[1,0,3,2]]

> permutationslist [[1,0,2,3],[0,2,1,3]]
[[0,1,2,3],[1,0,2,3],[0,2,1,3],[1,2,0,3],[2,0,1,3],[2,1,0,3]]

отже:
1 -- в списках-елементах списків значення унікальні (відсутні [0,0,0,0], [1,1,1,1], ...)
2 -- списки-елементи є унікальні, з урахуванням індексів значень ( [1,0,2,3] > [0,1,2,3], бо 1 > 0 -- перший елемент )
при цьому повторів таких же списків-елементів немає
3 -- на вході список з двох елементів -- списків з 4х чисел,
на виході -- список з таких же елементів списків

виникає лише одне запитання -- чому у другому випадку результатів 6, а в першому -- 4 ?

я там вище апнув те, що я раніше тицяв (додав приклад того, що на виході)
у мене там такого не виходило, отже, цей алгоритм трішечки інший ))

Подякували: leofun011

31

Re: Абстрактна алгебра, теорія груп, скінченні групи.

221VOLT написав:

отже:
1 -- в списках-елементах списків значення унікальні (відсутні [0,0,0,0], [1,1,1,1], ...)
2 -- списки-елементи є унікальні, з урахуванням індексів значень ( [1,0,2,3] > [0,1,2,3], бо 1 > 0 -- перший

Так, тут все правильно.

221VOLT написав:

3 -- на вході список з двох елементів -- списків з 4х чисел,
на виході -- список з таких же елементів списків

Поправка :
3 -- на вході список з довільної кількості елементів -- списків з Nх чисел,
на виході -- список з таких же елементів списків

221VOLT написав:

при цьому повторів таких же списків-елементів немає

На виході так.
А на вхід користувач може подати списки з повторами. Наприклад :

> permutationslist [[1,0,3,2],[1,0,3,2],[1,0,3,2]]
[[0,1,2,3],[1,0,3,2]]

221VOLT написав:
leofun01 написав:
> permutationslist [[1,0,2,3],[0,1,3,2]]
[[0,1,2,3],[1,0,2,3],[0,1,3,2],[1,0,3,2]]

> permutationslist [[1,0,2,3],[0,2,1,3]]
[[0,1,2,3],[1,0,2,3],[0,2,1,3],[1,2,0,3],[2,0,1,3],[2,1,0,3]]

виникає лише одне запитання -- чому у другому випадку результатів 6, а в першому -- 4 ?

Тут використовуються операції додавання перестановок.
Хотів дати посилання на приклади, але нормальних прикладів я не знайшов :o :(
Приклад додавання двох перестановок :

       0,1,2,3,4,5
  a = [2,0,1,3,5,4] = (0,2,1)(3)(4,5) = (0,2,1)(4,5)

       0,1,2,3,4,5
  b = [5,3,4,2,1,0] = (0,5)(1,3,2,4)

       0,1,2,3,4,5
a+b = [4,3,5,1,0,2] = (0,4)(1,3)(2,5)

       0,1,2,3,4,5
b+a = [4,5,3,2,0,1] = (0,4)(1,5)(2,3)

Розглянемо перший приклад [[1,0,2,3],[0,1,3,2]], є 2 перестановки, позначимо їх

  a = [1,0,2,3]
  b = [0,1,3,2]

a+a = [0,1,2,3]
a+b = [1,0,3,2]
b+a = [1,0,3,2]
b+b = [0,1,2,3]

Маємо 4 унікальні перестановки. Всі інші

a+b+a
b+a+b
a+b+a+b
...

спроби отримати з них нові перестановки будуть марними, бо результати будуть повторюватися.

Розглянемо другий приклад [[1,0,2,3],[0,2,1,3]],

    a = [1,0,2,3]
    b = [0,2,1,3]

  a+a = [0,1,2,3]
  a+b = [1,2,0,3]
  b+a = [2,0,1,3]
  b+b = [0,1,2,3]

a+b+a = [2,1,0,3]
b+a+b = [2,1,0,3]

Маємо 6 унікальних значень.
Так як останній елемент (3) не був переміщений, то можна було записати і так :

    a = [1,0,2]
    b = [0,2,1]

  a+a = [0,1,2]
  a+b = [1,2,0]
  b+a = [2,0,1]
  b+b = [0,1,2]

a+b+a = [2,1,0]
b+a+b = [2,1,0]
Подякували: 221VOLT1

32

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Знайшов я кілька програм/сайтів, які обчислюють розміри груп використовуючи генеруючі множини за мілісекунди. В той час як моя програма рахує то хвилинами і годинами. А це означає, що я тупий і не бачу чогось очевидного. *TIRED*

Наприклад Magma (система компютерної алгебри), в них там є приклади як її використовувати, працює моментально.

Продовжу через кілька годин...

Подякували: 221VOLT1

33 Востаннє редагувалося leofun01 (22.11.2019 21:46:08)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Ось реліз, гляньте, в кого є трохи вільного часу. Там звичайна exe'шка. На вхід приймає одне число (від 0 до 16), але більше ніж 10 не вводьте, бо інакше буде виконуватись надто довго. Мені потрібна допомога в оптимізації програми.

... більше ніж 8 не вводьте.

А ще хочу запросити всіх бажаючих на "code review".

Подякували: 221VOLT1

34

Re: Абстрактна алгебра, теорія груп, скінченні групи.

.zip-файл з сирцями на GitHub.
Цікаво, пане, як ви їсте - прямо з обгортками, навіть не відкриваючи?

Подякували: leofun011

35

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Якщо ви про архіви в релізі, то я їх туди не пхав, GitHub сам їх створив.
От попробуйте на GitHub'і створити реліз так, щоб там не було тих архівів.

А в сурсах архівів нема.

Подякували: 221VOLT, koala2

36 Востаннє редагувалося ReAl (22.11.2019 22:58:27)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:

Мені потрібна допомога в оптимізації програми.

Та я ж не знаю, що там у вас в cs-ах…
От у нас в c-ях отаке

    digit = 0;
    while(((byte)(1 << digit) & digitFlag) != 0)
        ++digit;

пишуть як

    digit = __builtin_ctz(~digitFlag); // а потім перевірити на <=7 замість наступної перевірки знову зсувом і маскою

що вироджується в одну-дві асемблерних команди.

Бачу, совання туди-сюди і бітової роботи багато, але після цього тижня тяжко зконцентруватися, щоб витягти алгоритми, а не peephole-оптимізаціями займатися.
Тут були Bit Twiddling Hacks? (Хоча дещо з того вже застаріло, бо з'явилися процесорні команди для цього і __builtin-ами в С воно швидше).

Подякували: leofun01, 221VOLT, /KIT\3

37

Re: Абстрактна алгебра, теорія груп, скінченні групи.

ReAl написав:

От у нас в c-ях отаке пишуть як

    digit = __builtin_ctz(~digitFlag); // а потім перевірити на <=7 замість наступної перевірки знову зсувом і маскою

що вироджується в одну-дві асемблерних команди.

C# дуже бідний в цьому плані. Коли буду переписувати проект на C, попробую використати такі оптимізації.

ReAl написав:

Тут були Bit Twiddling Hacks? (Хоча дещо з того вже застаріло, бо з'явилися процесорні команди для цього і __builtin-ами в С воно швидше).

Ох жеш ніфіга собі. *DANCE* Я й сам не знаю чи можна їх якось використати, але почитати дуже цікаво, дякую.

Подякували: 221VOLT1

38

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Мда... З пул реквестом я затупив, треба було потримати його відкритим, щоб інші змогли підняти собі статистику по "code review". Ладно, їх буде ще багато.

Подякували: 221VOLT, ostap34PHP2

39

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Після підказок ReAl бачу деякі недоліки в перестановках :

if(((short)((1 << digit) - 1 ^ -1) & digitFlag) != 0)

можна замінити на

if(((short)(-1 << digit) & digitFlag) != 0)
Подякували: 221VOLT1

40 Востаннє редагувалося ReAl (23.11.2019 23:07:28)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:

Після підказок ReAl бачу деякі недоліки в перестановках :

if(((short)((1 << digit) - 1 ^ -1) & digitFlag) != 0)

можна замінити на

if(((short)(-1 << digit) & digitFlag) != 0)

Але digitFlag має бути беззнаковим (або гарантовано додатнім у знаковому типі, тобто не використовувати старший біт):

if(digitFlag >> digit != 0)

Втім, думаю, основні втрати часу виконання не тут (а от часу розуміння коду можуть бути і тут).

Що цікаво, https://godbolt.org/z/JYRRq2
• arm32 на перші дві функції згенерував однаковий код
• в них дві зайві команди через те, що short — виправте на (unsigned short) у третій і ці дві зайві команди з'являться
• gcc x86-64 на першу функцію дав код, наче було написано if(-(1 << digit) & digitFlag) != 0) і він правий, чорт забирай, бо саме це і було написане з самого початку — (~(1 << digit) + 1)  іншим способом.
Але, повторю, думаю, що основні втрати часу не на варіаціях цих операцій.

Подякували: leofun01, 221VOLT2