ReSQL.ru
     
powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / когда вектор на 100 и в каждой ячейке несколько цифр
24 сообщений из 24, страница 1 из 1
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873489
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
Код: plaintext
1.
vector<int> v(100);


вот в таком векторе надо хранить неск.цифр в произвольных ячейках, а потом добавлять/убирать из них цифры и искать совпадения
я пока нашёл выход через битмап (каждая цифра влезает в 10 бит)
(битфилд походу не сможет все поставленные задачи решить)
но есть затык с определением, когда осталась 1 цифра (это в цикле надо чекать постоянно)
а как это в битмапе сделать наиболее эффективно?
второй вектор держать с кол-вом цифр в каждой ячейке не хочется
...
Рейтинг: 0 / 0
08.10.2019, 16:32
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873496
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
полудух,

чтоб точно ответить - нужна оригинальная постановка задачи.
имхо = 100 в размерности ответ на вопрос как :)

(круглый)
...
Рейтинг: 0 / 0
08.10.2019, 16:42
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873542
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
да это я решатель sudoku пишу
в ячейки складываются цифры, которые могут быть в ячейке (их 81 штука)

ответ = 100 не понял
...
Рейтинг: 0 / 0
08.10.2019, 18:01
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873577
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
Почему вектор, а не двумерная матрица 9x9 в виде классического "статического" массива?
...
Рейтинг: 0 / 0
08.10.2019, 19:06
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873587
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
Если хочется сэкономить на хранении списка возможных чисел в ячейке, то в качестве элемента такой структуры хватит Uint16. Так как кол-во возможных значений не больше 9-ти, то используешь 9 младших (старших) бит этого числа - по одному на каждое число: если n-ый бит выставлен, значит число допустимое, если не выставлен, значит уже недопустимо. Судоку считается решенным, когда в каждой ячейке остается по одному выставленному биту, уникальному среди элементов текущей строки и текущего столбца. Подобные подходы, например, используются в моих приложениях по ссылке в профиле.
...
Рейтинг: 0 / 0
08.10.2019, 19:32
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873588
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
есть 3 многомерных вектора 9x9: строки/колонки/блоки
а для хранения исходного судоку/tmp достаточно простых векторов
...
Рейтинг: 0 / 0
08.10.2019, 19:32
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873589
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
AmKadЕсли хочется сэкономить на хранении списка возможных чисел в ячейке, то в качестве элемента такой структуры хватит Uint16. Так как кол-во возможных значений не больше 9-ти, то используешь 9 младших (старших) бит этого числа - по одному на каждое число: если n-ый бит выставлен, значит число допустимое, если не выставлен, значит уже недопустимо. Судоку считается решенным, когда в каждой ячейке остается по одному выставленному биту, уникальному среди элементов текущей строки и текущего столбца. Подобные подходы, например, используются в моих приложениях по ссылке в профиле.
так это и есть битмап
...
Рейтинг: 0 / 0
08.10.2019, 19:33
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873590
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
и как там определять, что всего 1 бит выставлен? перебором чтоли?
...
Рейтинг: 0 / 0
08.10.2019, 19:34
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873592
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
полудухи как там определять, что всего 1 бит выставлен? перебором чтоли?Для того, чтобы проверить, что в битмапе выставлен только один бит, надо проверить, является ли данное число степенью двойки.
...
Рейтинг: 0 / 0
08.10.2019, 19:36
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873619
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
ага, вот и макрос:
Код: plaintext
1.
#define IS_DEG_OF_2(n) ((n > 0)   ? (n & (n - 1)) == 0   : 0)
...
Рейтинг: 0 / 0
08.10.2019, 20:58
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873629
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
P.S.
1) Я бы записал чуть короче:
Код: plaintext
1.
n && (n & (n - 1)) == 0


2) Вместо макроса заюзал бы inline-function.
...
Рейтинг: 0 / 0
08.10.2019, 21:31
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873650
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
спасибо
inline ведь может и не включить
...
Рейтинг: 0 / 0
08.10.2019, 22:20
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873673
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
Страус топит за инлайн, ну ок
потестил я это дело и получилось как-то непонятно...
Код: 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.
#include <iostream>

#define IS_DEG_OF_2(n) (n && (n & (n - 1)) == 0)

//##############################################################################
template<typename T>
inline bool is_deg_of_2(const T n)    {return n && (n & (n - 1)) == 0;}
//##############################################################################
int main(int argc, char *argv[])
{
    system("clear");

    int n = 1999999999;
    while (--n > 0){
        if (
//          is_deg_of_2(n)
            IS_DEG_OF_2(n)
        )
        {std::cout << n << '\n';}
    }
}

/* РЕЗУЛЬТАТЫ is_deg_of_2():
-O3:
+inline +&      1.945
-inline         1.954
-inline -&      1.951
-&              1.950

-O2:
+inline +&      1.944
-inline         1.944
-inline -&      1.956
-&              1.952

-O1:
+inline +&      1.533
-inline         2.522
-inline -&      1.533
-&              1.533
-----------------------

    IS_DEG_OF_2():
-O3:            2.038
-O2:            2.040
-O1:            1.533
*/


очевидно, что -O3/-O2 автоматом инлайнят и даже ссылку ставят (или убирают? ах, если бы только asm не обосрали злые мальчишки...)
-O1 автоматом не инлайнит, но если убрать ссылку, то опять 1.533...
И он быстрее, чем оптимизированный код.

макрос с -O3/-O2 медленнее, чем -O1
...
Рейтинг: 0 / 0
08.10.2019, 23:51
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873730
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
полудух,

Я отдал предпочтение функции из более общих соображений, таких как side effect, прозрачности и прочих.
...
Рейтинг: 0 / 0
09.10.2019, 08:34
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873873
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
да к функции вопросов нет
вопрос - почему такое странное поведение у ссылки и почему O1 быстрее O2/O3
...
Рейтинг: 0 / 0
09.10.2019, 12:02
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873875
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
макрос то получается медленнее ф-и, так что ф-я ок
...
Рейтинг: 0 / 0
09.10.2019, 12:03
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873896
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AmKad
Участник
Не уловил, причем тут ссылка? Само по себе указание const еще не делает параметр ссылкой. Или ты проводил тесты с функцией, меняя ее сигнатуру? Если не предполагается изменение параметров в вызываемой функции, то примитивные типы (по крайней мере те, чья размерность не превышает разрядность адреса) рекомендуется передавать по значению, а не по адресу/ссылке, дабы исключить операцию разыменования (получения значения по адресу) в вызываемой функции.
...
Рейтинг: 0 / 0
09.10.2019, 12:25
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39873936
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
я тестировал все варианты:
inline bool is_deg_of_2(const T &n)
inline bool is_deg_of_2(const T n)
bool is_deg_of_2(const T n)
bool is_deg_of_2(const T &n)
...
Рейтинг: 0 / 0
09.10.2019, 13:07
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39874137
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
В замечательном цикле делается пара простых операций с числом и 2 обращения к методам ofstream. Каких-либо выводов на тему макрос vs функция в таких условиях тут сделать не получится.
...
Рейтинг: 0 / 0
09.10.2019, 15:32
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39874179
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
так макросы априори простенькие все
...
Рейтинг: 0 / 0
09.10.2019, 16:21
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39877389
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
не, не все..
блин, 2018 год, люди живут на макросах чуть менее, чем полностью
boost::hana вообще вся в макросах
вообще весь boost в макросах
причём они туда даже классы пихают

в целом код такой дикий, что хочется выбежать в окно

не потому ли буст в тестах часто многократно сливает нормальным либам (иногда и в десятки раз)...
YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
17.10.2019, 06:01
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39877603
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Насколько я понял макросы используются в сборке текстовых литералов через ##.

Это тот юзкейс когда шаблоны и инлайнинг нелетают.

Вот надо разобраться с какого буя им нужна сборка новых литералов и тогда проблема будет пофикшена.

P.S. Согласен. Макросы - каменный век.
...
Рейтинг: 0 / 0
17.10.2019, 12:18
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39878873
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну вот что это за фигня такая. Кодогенерация мать ее так.

Код: plaintext
1.
#define CALL_DEF(cal, class_name) int call_#class_name() .....
...
Рейтинг: 0 / 0
20.10.2019, 16:34
| Ответить | Цитировать | Написать  
когда вектор на 100 и в каждой ячейке несколько цифр
    #39879031
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
пфф... в std-либе есть и такое:
 
Код: 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.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
#define _DEFINE_ARRAY_FUNCTION(_Op, _Name)                              \
  template<typename _Tp>                                                \
    inline void                                                         \
    _Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, const _Tp& __t) \
    {                                                                   \
      for (_Tp* __p = __a._M_data; __p < __a._M_data + __n; ++__p)      \
        *__p _Op##= __t;                                                \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    inline void                                                         \
    _Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, _Array<_Tp> __b) \
    {                                                                   \
      _Tp* __p = __a._M_data;                                           \
      for (_Tp* __q = __b._M_data; __q < __b._M_data + __n; ++__p, ++__q) \
        *__p _Op##= *__q;                                               \
    }                                                                   \
                                                                        \
  template<typename _Tp, class _Dom>                                    \
    void                                                                \
    _Array_augmented_##_Name(_Array<_Tp> __a,                           \
                             const _Expr<_Dom, _Tp>& __e, size_t __n)   \
    {                                                                   \
      _Tp* __p(__a._M_data);                                            \
      for (size_t __i = 0; __i < __n; ++__i, ++__p)                     \
        *__p _Op##= __e[__i];                                           \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    inline void                                                         \
    _Array_augmented_##_Name(_Array<_Tp> __a, size_t __n, size_t __s,   \
                             _Array<_Tp> __b)                           \
    {                                                                   \
      _Tp* __q(__b._M_data);                                            \
      for (_Tp* __p = __a._M_data; __p < __a._M_data + __s * __n;       \
           __p += __s, ++__q)                                           \
        *__p _Op##= *__q;                                               \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    inline void                                                         \
    _Array_augmented_##_Name(_Array<_Tp> __a, _Array<_Tp> __b,          \
                             size_t __n, size_t __s)                    \
    {                                                                   \
      _Tp* __q(__b._M_data);                                            \
      for (_Tp* __p = __a._M_data; __p < __a._M_data + __n;             \
           ++__p, __q += __s)                                           \
        *__p _Op##= *__q;                                               \
    }                                                                   \
                                                                        \
  template<typename _Tp, class _Dom>                                    \
    void                                                                \
    _Array_augmented_##_Name(_Array<_Tp> __a, size_t __s,               \
                             const _Expr<_Dom, _Tp>& __e, size_t __n)   \
    {                                                                   \
      _Tp* __p(__a._M_data);                                            \
      for (size_t __i = 0; __i < __n; ++__i, __p += __s)                \
        *__p _Op##= __e[__i];                                           \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    inline void                                                         \
    _Array_augmented_##_Name(_Array<_Tp> __a, _Array<size_t> __i,       \
                             _Array<_Tp> __b, size_t __n)               \
    {                                                                   \
      _Tp* __q(__b._M_data);                                            \
      for (size_t* __j = __i._M_data; __j < __i._M_data + __n;          \
           ++__j, ++__q)                                                \
        __a._M_data[*__j] _Op##= *__q;                                  \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    inline void                                                         \
    _Array_augmented_##_Name(_Array<_Tp> __a, size_t __n,               \
                             _Array<_Tp> __b, _Array<size_t> __i)       \
    {                                                                   \
      _Tp* __p(__a._M_data);                                            \
      for (size_t* __j = __i._M_data; __j<__i._M_data + __n;            \
           ++__j, ++__p)                                                \
        *__p _Op##= __b._M_data[*__j];                                  \
    }                                                                   \
                                                                        \
  template<typename _Tp, class _Dom>                                    \
    void                                                                \
    _Array_augmented_##_Name(_Array<_Tp> __a, _Array<size_t> __i,       \
                             const _Expr<_Dom, _Tp>& __e, size_t __n)   \
    {                                                                   \
      size_t* __j(__i._M_data);                                         \
      for (size_t __k = 0; __k<__n; ++__k, ++__j)                       \
        __a._M_data[*__j] _Op##= __e[__k];                              \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    void                                                                \
    _Array_augmented_##_Name(_Array<_Tp> __a, _Array<bool> __m,         \
                             _Array<_Tp> __b, size_t __n)               \
    {                                                                   \
      bool* __ok(__m._M_data);                                          \
      _Tp* __p(__a._M_data);                                            \
      for (_Tp* __q = __b._M_data; __q < __b._M_data + __n;             \
           ++__q, ++__ok, ++__p)                                        \
        {                                                               \
          while (! *__ok)                                               \
            {                                                           \
              ++__ok;                                                   \
              ++__p;                                                    \
            }                                                           \
          *__p _Op##= *__q;                                             \
        }                                                               \
    }                                                                   \
                                                                        \
  template<typename _Tp>                                                \
    void                                                                \
    _Array_augmented_##_Name(_Array<_Tp> __a, size_t __n,               \
                             _Array<_Tp> __b, _Array<bool> __m)         \
    {                                                                   \
      bool* __ok(__m._M_data);                                          \
      _Tp* __q(__b._M_data);                                            \
      for (_Tp* __p = __a._M_data; __p < __a._M_data + __n;             \
           ++__p, ++__ok, ++__q)                                        \
        {                                                               \
          while (! *__ok)                                               \
            {                                                           \
              ++__ok;                                                   \
              ++__q;                                                    \
            }                                                           \
          *__p _Op##= *__q;                                             \
        }                                                               \
    }                                                                   \
                                                                        \
  template<typename _Tp, class _Dom>                                    \
    void                                                                \
    _Array_augmented_##_Name(_Array<_Tp> __a, _Array<bool> __m,         \
                             const _Expr<_Dom, _Tp>& __e, size_t __n)   \
    {                                                                   \
      bool* __ok(__m._M_data);                                          \
      _Tp* __p(__a._M_data);                                            \
      for (size_t __i = 0; __i < __n; ++__i, ++__ok, ++__p)             \
        {                                                               \
          while (! *__ok)                                               \
            {                                                           \
              ++__ok;                                                   \
              ++__p;                                                    \
            }                                                           \
          *__p _Op##= __e[__i];                                         \
        }                                                               \
    }


/usr/include/c++/6/bits/valarray_array.h
...
Рейтинг: 0 / 0
21.10.2019, 04:58
| Ответить | Цитировать | Написать  
24 сообщений из 24, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / когда вектор на 100 и в каждой ячейке несколько цифр
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&msg=39873873&tid=2017548]:
 0ms
get settings:
 11ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 37ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 264ms
total:  401ms
созд. / загр.: 401ms
x
x
Закрыть


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