Как правильно делать множественную проверку?

@belalugoci · Регистрация: 01.06.2018

Студворк — интернет-сервис помощи студентам

Вопрос к знатокам C#. По результатам анализа того, какие данные меняются более активно я сделал множественную проверку вот таким образом:

C#
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
            if (DimBits[countN, 4] == DimBits[y, 4])
                if (DimBits[countN, 5] == DimBits[y, 5])
                    if (DimBits[countN, 6] == DimBits[y, 6])
                        if (DimBits[countN, 7] == DimBits[y, 7])
                            if (DimBits[countN, 8] == DimBits[y, 8])
                                if (DimBits[countN, 9] == DimBits[y, 9])
                                    if (DimBits[countN, 14] == DimBits[y, 14])
                                        if (DimBits[countN, 15] == DimBits[y, 15])
                                            if (DimBits[countN, 16] == DimBits[y, 16])
                                                if (DimBits[countN, 17] == DimBits[y, 17])
                                                    if (DimBits[countN, 18] == DimBits[y, 18])
                                                        if (DimBits[countN, 23] == DimBits[y, 23])
                                                            if (DimBits[countN, 24] == DimBits[y, 24])
                                                                if (DimBits[countN, 25] == DimBits[y, 25])
                                                                    if (DimBits[countN, 26] == DimBits[y, 26])
                                                                        if (DimBits[countN, 27] == DimBits[y, 27])
                                                                            if (DimBits[countN, 3] == DimBits[y, 3])
                                                                                if (DimBits[countN, 13] == DimBits[y, 13])
                                                                                    if (DimBits[countN, 22] == DimBits[y, 22])
                                                                                        if (DimBits[countN, 2] == DimBits[y, 2])
                                                                                            if (DimBits[countN, 12] == DimBits[y, 12])
                                                                                                if (DimBits[countN, 21] == DimBits[y, 21])
                                                                                                    if (DimBits[countN, 1] == DimBits[y, 1])
                                                                                                        if (DimBits[countN, 11] == DimBits[y, 11])
                                                                                                            if (DimBits[countN, 20] == DimBits[y, 20])
                                                                                                                if (DimBits[countN, 0] == DimBits[y, 0])
                                                                                                                    if (DimBits[countN, 10] == DimBits[y, 10])
                                                                                                                        if (DimBits[countN, 19] == DimBits[y, 19])

Вопрос: умеет ли сам C# в какой-то своей базовой реализации делать то же самое но компактно?

Я не стал делать всё через && потому что тогда мы неизбежно будем делать 28 проверок, хотя в среднем, из-за особенностей заполнения массива их будет не более 10-12.
Могу сделать массив последовательным, от 0 до 27, заполнив по частоте, если вдруг этого потребует какая-то компактная реализация.

Спасибо.

Someone007 · 04.12.2018, 06:48

Сообщение от belalugoci

Я не стал делать всё через && потому что тогда мы неизбежно будем делать 28 проверок

Чего?

Сообщение от belalugoci

Могу сделать массив последовательным, от 0 до 27, заполнив по частоте, если вдруг этого потребует какая-то компактная реализация.

Если по порядку, то циклом можно пройтись...

@belalugoci · 04.12.2018, 07:32 **[ТС]**

Сообщение от Someone007

Чего?

Ваше "чего" позволило на проблему посмотреть под другим углом. Для условия && число проверок не будет отличаться от той городушки, что написал я, надеюсь что такая реализация в C# и используется.

Сообщение от Someone007

Если по порядку, то циклом можно пройтись...

Видимо пока этот вариант самый простой.

Добавлено через 32 минуты
сделал так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
            bool equal = true;
            for (int n = 0; n < 28; n++)
            {
                if (DimBits[countN, n] != DimBits[y, n])
                {
                    equal = false;
                    break;
                }
            }
            if (equal)
            {
                // выполнить если все совпали
            }

@belalugoci · 05.12.2018, 13:25 **[ТС]**

анализируя частоту изменения данных в массиве удалось уменьшить время работы программы с 60 до 35 минут.

@nicolas2008 · 15.12.2018, 04:32

Unsafe сравнение будет быстрее.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
        static unsafe bool RowsEqual(byte[,] arr1, int arr1RowIndex, byte[,] arr2, int arr2RowIndex)
        {
            int length1 = arr1.GetLength(1);
            int length2 = arr2.GetLength(1);
 
            if (length1 != length2)
            {
                return false;
            }
 
            fixed (byte* offset1 = &arr1[arr1RowIndex, 0])
            fixed (byte* offset2 = &arr2[arr2RowIndex, 0])
            {
                for (int i = 0; i < length1; i++)
                {
                    if (offset1[i] != offset2[i])
                    {
                        return false;
                    }
                }
            }
 
            return true;
        }

@belalugoci · 17.12.2018, 05:13 **[ТС]**

Сообщение от nicolas2008

Unsafe сравнение будет быстрее.

проверяли?
просто по логике компилятор всё равно так или иначе будет оперировать с указателями, почему тогда явное обращение через указатели окажется быстрее?

Someone007 · 17.12.2018, 05:31

Сообщение от belalugoci

почему тогда явное обращение через указатели окажется быстрее?

Как минимум потому что не будет проверки на выход за границы массива, хотя это в некоторых случаях может быть автоматически оптимизировано компилятором без применения unsafe автоматически.

@belalugoci · 17.12.2018, 05:47 **[ТС]**

Сообщение от nicolas2008

Unsafe сравнение будет быстрее.

создал два массива на 100 млн байт каждый и две функции, одна ваша с unsafe, другая обычный for+if, по итогу прогнал 10 раз, интервал времени устанавливал через Stopwatch. В итоге получилось усредненное время в секундах:

3.40 - для unsafe
3.30 - для for+if

Ни разу вариант с unsafe не был быстрее.

@Nalik · 17.12.2018, 10:29

Сообщение от belalugoci

Я не стал делать всё через && потому что тогда мы неизбежно будем делать 28 проверок

Разве?

C#
1
2
3
4
5
6
7
int a = 5;
int b = 6;
if(a == 4 &&
   b == 6) //До этого места компилятор не дойдет, т.к. предыдущее сравнение не совпадает
{
 
}

Проверял так. Заведомо создал ошибку, но исключение не высветилось т.к. код до туда просто не дошел.

C#
1
2
3
4
5
6
7
int a = 5;
string b = "6c";
if (a == 4 &&
    Convert.ToInt16(b) == 6) //До этого места компилятор не дойдет
{
 
}

В таком случае будет ошибка

C#
1
2
3
4
5
6
7
int a = 5;
string b = "6c";
if (a == 5 &&
    Convert.ToInt16(b) == 6) //До этого места компилятор не дойдет
{
 
}

Могу конечно ошибаться, чисто из личных наблюдений.

А вообще я бы делал через циклы, как вы и сделали

@belalugoci · 17.12.2018, 11:45 **[ТС]**

Сообщение от Nalik

Разве?

Ну если вы прочитали один кусок, то не мешало бы дочитать и до конца где я написал:

... хотя в среднем, из-за особенностей заполнения массива их будет не более 10-12.

Связано это как раз с тем, что может условие не выполниться на первом &&, а может и на последнем, то есть если число проверок и число изменений переменных является константой, то общее среднее число проверок будет ровно в 2 раза меньше количества условий.
В моём случае я не написал 14, а указал 10-12, так как некоторые переменные меняются чаще других, в итоге я проверки сделал исходя из этой информации, но чтобы цикл был красивым от 0 до 27, я заполняю массив так, что в 0 пишется самое частое к изменению значение, а в 27 пишется то что меняется редко. В итоге такой способ позволил мне очень сильно сэкономить, в 2 раза примерно ускорить проверку.

@Nalik · 17.12.2018, 11:58

Сообщение от belalugoci

Ну если вы прочитали один кусок, то не мешало бы дочитать и до конца где я написал:

Не поверите, дочитал. И это ничего не меняет. Я лишь сказал, что конструкция

C#
1
2
if (DimBits[countN, 4] == DimBits[y, 4])
                if (DimBits[countN, 5] == DimBits[y, 5])

делает ровно тоже самое в вашем случае, что и конструкция

C#
1
if (DimBits[countN, 4] == DimBits[y, 4] && DimBits[countN, 5] == DimBits[y, 5])

@maximka777 · 17.12.2018, 12:51

belalugoci, Я так понимаю здесь просто проверяется равенство строк массива. Если хотите оптимизировать то можно просто считать хэши строк на лету, а потом их сравнивать.
Как то так.

C#
1
2
3
4
5
6
7
8
9
10
11
12
int[,] DimBits = new int[20, 20];
int[] rowHash = new int[20];
void set(int d1, int d2, int value)
{
    rowHash[d1] = rowHash[d1] ^ DimBits[d1, d2] ^ value;
    DimBits[d1, d2] = value;
}
//проверка равенства строк
if (rowHash[countN]==rowHash[y])
{
 
}

@belalugoci · 17.12.2018, 13:00 **[ТС]**

Сообщение от Nalik

делает ровно тоже самое в вашем случае, что и конструкция

ок. мысль понял.

Сообщение от maximka777

Если хотите оптимизировать то можно просто считать хэши строк на лету, а потом их сравнивать.

Не вариант, считается порядка 80 млн элементов, потребление оперативки и затраты на расчеты сильно влияют на скорость. Поэтому мне кажется подсчёт хэша ничего не даст для оптимизации.

"^" - это возведение в степень?

По коду - не понял что именно там делается.

@maximka777 · 17.12.2018, 13:04

Сообщение от belalugoci

"^" - это возведение в степень?

Это оператор XOR

Сообщение от belalugoci

По коду - не понял что именно там делается.

Просто ксорит элементы, нужно еще добавить порядок элемента, а то правильно работать не будет.

@belalugoci · 17.12.2018, 13:19 **[ТС]**

Сообщение от maximka777

Просто ксорит элементы

всё равно не понял зачем делать xor для содержимого rowHash для самого себя, а потом еще в DimBits почему-то двумерный записывать значение какого-то value.

@maximka777 · 17.12.2018, 13:53

belalugoci, Если не секрет данные у вас как в массив попадаю из файла ? Сравнение производится когда весь массив заполнен или после изменения одного элемента ? И что вообще эта программа делает ?

@nicolas2008 · 18.12.2018, 02:42

Сообщение от belalugoci

создал два массива на 100 млн байт каждый и две функции, одна ваша с unsafe, другая обычный for+if, по итогу прогнал 10 раз, интервал времени устанавливал через Stopwatch. В итоге получилось усредненное время в секундах:
3.40 - для unsafe
3.30 - для for+if
Ни разу вариант с unsafe не был быстрее.

У меня получился такой результат

Конфигурация Debug (оптимизация кода отключена):

Bash
1
2
Unsafe exec time: 3207
Safe exec time: 8363

Конфигурация Release (оптимизация кода включена):

Bash
1
2
Unsafe exec time: 740
Safe exec time: 3293

Код бенчмарка:

C#
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
        static unsafe bool RowsEqualUnsafe(byte[,] arr1, int arr1RowIndex, byte[,] arr2, int arr2RowIndex)
        {
            int length1 = arr1.GetLength(1);
            int length2 = arr2.GetLength(1);
 
            if (length1 != length2)
            {
                return false;
            }
 
            fixed (byte* offset1 = &arr1[arr1RowIndex, 0])
            fixed (byte* offset2 = &arr2[arr2RowIndex, 0])
            {
                for (int i = 0; i < length2; i++)
                {
                    if (offset1[i] != offset2[i])
                    {
                        return false;
                    }
                }
            }
 
            return true;
        }
 
        static bool RowsEqualSafe(byte[,] arr1, int arr1RowIndex, byte[,] arr2, int arr2RowIndex)
        {
            int length1 = arr1.GetLength(1);
            int length2 = arr2.GetLength(1);
 
            if (length1 != length2)
            {
                return false;
            }
 
            for (int i = 0; i < length1; i++)
            {
                if (arr1[arr1RowIndex, i] != arr2[arr2RowIndex, i])
                {
                    return false;
                }
            }
 
            return true;
        }
 
        static void Main(string[] args)
        {
            byte[,] arr1 = new byte[2, 100_000_000];
            byte[,] arr2 = new byte[2, 100_000_000];
 
            for (int i = 0; i < 100_000_000; i++)
            {
                arr1[0, i] = (byte) (i % 255);
                arr2[1, i] = (byte) (i % 255);
            }
 
            #region JIT precomplime methods before benchmark code
            bool equals = RowsEqualSafe(arr1, 0, arr2, 1) | RowsEqualUnsafe(arr1, 0, arr2, 1);
            #endregion
 
            int testCount = 10;
 
            Stopwatch sw;
            sw = Stopwatch.StartNew();
            for (int i = 0; i < testCount; i++)
            {
                equals = RowsEqualUnsafe(arr1, 0, arr2, 1);
            }
            sw.Stop();
            Console.WriteLine("Unsafe exec time: " + sw.ElapsedMilliseconds);
 
            sw = Stopwatch.StartNew();
            for (int i = 0; i < testCount; i++)
            {
                equals = RowsEqualSafe(arr1, 0, arr2, 1);
            }
            sw.Stop();
            Console.WriteLine("Safe exec time: " + sw.ElapsedMilliseconds);
        }
    }

Добавлено через 11 минут
Можно еще так:

C#
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
        // Copyright (c) 2008-2013 Hafthor Stefansson
        // Distributed under the MIT/X11 software license
        // Ref: http://www.opensource.org/licenses/mit-license.php.
        static unsafe bool RowsEqualUnsafeFast(byte[,] arr1, int arr1RowIndex, byte[,] arr2, int arr2RowIndex) 
        {
            int length1 = arr1.GetLength(1);
            int length2 = arr2.GetLength(1);
 
            if (length1 != length2)
            {
                return false;
            }
 
            fixed (byte* p1=&arr1[arr1RowIndex, 0], p2=&arr2[arr2RowIndex, 0]) 
            {
                byte* x1=p1, x2=p2;
                int l = length1;
                for (int i=0; i < l/8; i++, x1+=8, x2+=8)
                    if (*((long*)x1) != *((long*)x2)) return false;
                if ((l & 4)!=0) { if (*((int*)x1)!=*((int*)x2)) return false; x1+=4; x2+=4; }
                if ((l & 2)!=0) { if (*((short*)x1)!=*((short*)x2)) return false; x1+=2; x2+=2; }
                if ((l & 1)!=0) if (*((byte*)x1) != *((byte*)x2)) return false;
                return true;
            }
        }

Результаты:

Конфигурация Debug (оптимизация кода отключена):

Bash
1
2
3
Unsafe exec time: 3245
UnsafeFast exec time: 641
Safe exec time: 8389

Конфигурация Release (оптимизация кода включена):

Bash
1
2
3
Unsafe exec time: 750
UnsafeFast exec time: 162
Safe exec time: 3179

@belalugoci · 18.12.2018, 04:49 **[ТС]**

Сообщение от maximka777

Если не секрет данные у вас как в массив попадаю из файла ?

нет

Сообщение от maximka777

Сравнение производится когда весь массив заполнен

нет, для массива размерностью X делается сравнение с предыдущими X-1 элементами. Каждый элемент вычисляется как манипуляция с битами, все исходные данные уникальны, а вот вычисляемые проверяются на уникальность. Чтобы исключить большое потребление памяти при переходе от 5х5 бит матрицы я пока придумал только постоянно считать значения для любого Dim[x-1] элемента при сравнении его с Dim[x] - вычислительная нагрузка вырастет, но память не будет расти в геометрической прогрессии.

Сообщение от maximka777

И что вообще эта программа делает ?

Более подробно чем я написал выше сказать не могу, это алгоритмические изыскания.

Сообщение от nicolas2008

У меня получился такой результат

приму к сведению. Но я так и не понял что там с чем сравнивается и как я могу это использовать, в функции фигурирует два массива байт двумерных, у меня два одномерных массива, я переделывал так что было

C#
1
static unsafe bool RowsEqualUnsafeFast(ulong[] arr1, int arr1RowIndex, ulong[] arr2, int arr2RowIndex)

возможно причина в этом. Я в любом случае не понимаю как сравнение

C#
1
a == b

будет медленнее, чем точно такое же сравнение, но с предварительным расчетом хэша. Тут вероятно выигрыш должен появляться при сравнении строк, хотя опять же по сравнению строк много примеров и все сводятся к уменьшению числа проходов, а для вычисления хэша мы пойдем читать опять все символы. В общем мне не хватает теоретической базы и понимания области применения.

@nicolas2008 · 18.12.2018, 12:20

belalugoci, В вашем первом примере был двухмерный массив, поэтому я тоже сделал пример для двухмерного.
В общем случае, unsafe должен быть быстрее за счет отсутствия проверок выхода за границы массива при доступе по индексу.
Если размер элемента меньше чем размер регистра процессора, то выиграш еще и за счет пакетных операций (как в примере unsafe fast, byte - 1 байт, long -8 байт).
Никакого хеширования тут нет.

@belalugoci · 18.12.2018, 13:56 **[ТС]**

Сообщение от nicolas2008

В вашем первом примере был двухмерный массив, поэтому я тоже сделал пример для двухмерного.

C#
1
DimBits[countN, 6] == DimBits[y, 6]

эквивалентно

C#
1
a[6] == b[6]

Сообщение от nicolas2008

В общем случае, unsafe должен быть быстрее за счет отсутствия проверок выхода за границы массива при доступе по индексу.

ок, буду знать.

Сообщение от nicolas2008

Если размер элемента меньше чем размер регистра процессора, то выиграш еще и за счет пакетных операций

ага, разглядел.

Сообщение от nicolas2008

Никакого хеширования тут нет.

увидел, невнимательно посмотрел ваш вариант.

переделал свой проект под unsafe fast, запустил, обычно исполняется 35 минут, посмотрим что это даст.

Добавлено через 28 минут

Сообщение от nicolas2008

В вашем первом примере был двухмерный массив, поэтому я тоже сделал пример для двухмерного.

Что-то не так. Переделал вот такой код:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
        public void Compare(int y)
        {
            bool equal = true;
            for (int n = 0; n < 28; n++)
                if (DimBits[countN, n] != DimBits[y, n])
                {
                    equal = false;
                    break;
                }
            if (equal)
            {
                countX++; // не суть
            }
        }

на

C#
1
2
3
4
5
6
7
        public void Compare(int y)
        {
            if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y))
            {
                countX++;
            }
        }

за 25 минут выполнилось только 54%, так что общее время выполнения будет >2 часов. А было 35 минут.
Код собран в варианте Release для x64.
Сам Compare вызывается так

C#
1
if ((countN > 0)) For(0, countN, Compare);

где countN текущая позиция в статичном массиве, а выше используемый y - это набор индексов в том же массиве DimBits но в диапазоне 0>=y<countN

Новые блоги и статьи Все статьи Все блоги /
Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	05.12.2018, 13:25 [ТС]
	анализируя частоту изменения данных в массиве удалось уменьшить время работы программы с 60 до 35 минут. 0

@maximka777 95 / 74 / 27 Регистрация: 13.08.2018 Сообщений: 203
	17.12.2018, 13:53
	belalugoci, Если не секрет данные у вас как в массив попадаю из файла ? Сравнение производится когда весь массив заполнен или после изменения одного элемента ? И что вообще эта программа делает ? 0

@nicolas2008 1152 / 860 / 263 Регистрация: 30.04.2009 Сообщений: 3,603
	18.12.2018, 12:20
	belalugoci, В вашем первом примере был двухмерный массив, поэтому я тоже сделал пример для двухмерного. В общем случае, unsafe должен быть быстрее за счет отсутствия проверок выхода за границы массива при доступе по индексу. Если размер элемента меньше чем размер регистра процессора, то выиграш еще и за счет пакетных операций (как в примере unsafe fast, byte - 1 байт, long -8 байт). Никакого хеширования тут нет. 0