Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / когда вектор на 100 и в каждой ячейке несколько цифр / 24 сообщений из 24, страница 1 из 1
08.10.2019, 16:32
    #39873489
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
когда вектор на 100 и в каждой ячейке несколько цифр
Код: plaintext
1.
vector<int> v(100);


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

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

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

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


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

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

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

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

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

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

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

Код: plaintext
1.
#define CALL_DEF(cal, class_name) int call_#class_name() .....
...
Рейтинг: 0 / 0
21.10.2019, 04:58
    #39879031
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
когда вектор на 100 и в каждой ячейке несколько цифр
пфф... в 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
Форумы / C++ [игнор отключен] [закрыт для гостей] / когда вектор на 100 и в каждой ячейке несколько цифр / 24 сообщений из 24, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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