Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Речь идёт о двоичном представлении числа. Классические реализации известны Код: plaintext 1. 2. 3. 4. 5. 6. или реализации основанные на принципе "разделяй и властвуй" описанные, например, в книге Генри Уоррена "Алгоритмические трюки для программиста" Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. и т.д. Прочитал что существуют методы в Си и С++ аналогичного назначения. И если объект bitset и метод count() я нашёл в стандарте С++, то функции __builtin_popcount в стандарте языка Си нет. Хотя может быть не в той документации искал. Пользовались ли вы такими функциями и правильно ли я понимаю, их вызов требует меньшего времени по сравнению с классическими реализациями показанными выше ? Интересно, существовали ли раньше методы шифрования использующие данную характеристику ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.06.2015, 07:03 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Возможно таблицами быстрее будет Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.06.2015, 09:10 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
__builtin_popcount - это "встроенная функция" для GCC только под х86, генерирует соответствующую машинную команду popcnt . Непереносимо на другие архитектуры/компиляторы, есть аналог для msvc ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.06.2015, 09:20 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Из набора SSE4 есть такая штука. Тут можно найти описание POPCNT. https://software.intel.com/sites/default/files/c8/ab/17971-intel_20sse4_20programming_20reference.pdf ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.06.2015, 13:44 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Спасибо! Скоро протестирую. Прошу прощение, уже 10 минут не могу понять почему строка выделенная желтым не работает корректно(отправляет на поток 0 к значению веса Хемминга). Подскажите пожалуйста в чём ошибка. Хотя скорее всего это не ошибка, а нормальная работа, и я что-то забыл Код: plaintext 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. Если поменять местами get_HW(x) и x то всё ок ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 03:37 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
а, long long x затирает память под get_HW(). Прошу прощение ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 03:39 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Кстати. Почему данную характеристику иначе называют "population count" ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 07:45 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
SashaMercury, Видимо, сколько битиков живут в слове. Что за формат такой %i ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 08:18 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
MasterZiv, Для x формат должен быть %ll ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 08:23 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
MasterZivSashaMercury, Видимо, сколько битиков живут в слове. Что за формат такой %i ? ну может быть :) с форматом разобрался, спасибо :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 08:41 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
MasterZivЧто за формат такой %i ? Отвечу сам себе, посмотрев в документации: %i - полный аналог %d. Я этого не знал, всю жизнь использовал %d и не жужжал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 13:08 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
MasterZivMasterZivЧто за формат такой %i ? Отвечу сам себе, посмотрев в документации: %i - полный аналог %d. Я этого не знал, всю жизнь использовал %d и не жужжал. я подумал что это был риторический вопрос в контексте "что за i если должно быть lli" :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.06.2015, 13:50 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. На прошлой неделе стал решать такую задачу . Вообще говоря, требуется найти m элемент такой последовательности . Приводится слабая оценка . Например при m= это приближение даёт 5120, а должно быть 5981. В целом, я представляю как решить эту задачу. Но данное решение требует предварительные вычисления(объём которых больше, чем мне хочется) и не кажется мне хорошим/красивым/правильным(с точки зрения как реализации, так и алгоритма). Может быть у кого-нибудь есть идеи как лучше подступиться к решению данной задачи? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.06.2015, 08:04 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
вычисление 100000000 значений у меня занимает 0,7сек весь диапазон 2*10^9 делим на 20 частей и заранее вычисляем 20 значений ключа не очень красиво, но тест пройдет ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.06.2015, 08:49 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
m_Slaвычисление 100000000 значений у меня занимает 0,7сек весь диапазон 2*10^9 делим на 20 частей и заранее вычисляем 20 значений ключа не очень красиво, но тест пройдет Если делить по 100 000 000 то потребуется порядка 300 участков. Собственно это и пришло в голову. Кроме того, возникнут нюансу связанные с тем, что первое число не всегда 1. Они конечно решаются, но слишком много предварительных вычислений в итоге. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.06.2015, 08:57 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
не подойдет вариант первое число может быть 4, его вообще в последовательности нет ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.06.2015, 09:05 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
m_Slaне подойдет вариант первое число может быть 4, его вообще в последовательности нет это все решается. Хранятся промежуточные массивы которые принадлежат всем возможным последовательностям, т.е. каждый слой шириной 10^8 элементов хранится массив из 30 элементов с некоторыми характеристиками. Например так. Остальной ерунда, и дело техники. Но это очень некрасивый способ, и мне очень не хочется его использовать. Наверняка должно быть хорошее решение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.06.2015, 09:10 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Кстати, __popcnt64 не работает в MVS Express 2013. Возможно из-за версии express, т.к.__popcnt и popcnt16 работают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 04:47 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
SashaMercury, __popcnt64 не работает на 32х битной платформе, только в х64. Не знаю как 2013, но раньше Express действительно не поддерживал компиляцию под 64 бита. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 07:18 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
вычислить значение ключа через 2 000 000 000 минут на С (mingw) считает за 20,2 сек на asm считает 4,2 сек Код: plaintext 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 07:19 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Barlone, IDE такой функции не знает. У меня 64 битная платформа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 07:55 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
m_Sla, а нужно за секунду :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 07:57 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
SSm_Sla, а нужно за секунду :) хотя наверняка можно быстрее ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 07:59 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
popcount2() из первого поста быстро работает Код: plaintext 1. 2. 3. 4. 5. результатx=2000000010 time: 620 ms ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 08:06 |
|
||
|
Вес Хэмминга: реализация и некоторые вопросы.
|
|||
|---|---|---|---|
|
#18+
Вариант m_Sla с таблицей 17785880 немного быстрее тест popcount3()x=2000000010 time: 460 ms popcount3() Код: plaintext 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. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.06.2015, 08:21 |
|
||
|
|

start [/forum/topic.php?fid=57&msg=38987431&tid=2018938]: |
0ms |
get settings: |
10ms |
get forum list: |
11ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
95ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
50ms |
get tp. blocked users: |
1ms |
| others: | 12ms |
| total: | 198ms |

| 0 / 0 |
