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

@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, заполнив по частоте, если вдруг этого потребует какая-то компактная реализация.

Спасибо.

@maximka777 · 18.12.2018, 14:24

belalugoci, еще как вариант можно ускорить (до 8х) используя SIMD .Net. (поставить пакет System.Numerics.Vectors от microsoft) .

C#
1
2
3
var v1 = new Vector<int>(new int[] { 1, 2, 3, 4 });
var v2 = new Vector<int>(new int[] { 1, 2, 3, 4 });
if (v1 == v2) { }

Или если процессор многоядерный использовать потоки.

@nicolas2008 · 18.12.2018, 15:37

belalugoci, какой у вас тип данных в массиве?

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

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

Почему 2 часа а не 50 минут?

@belalugoci · 19.12.2018, 05:22 **[ТС]**

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

Почему 2 часа а не 50 минут?

Получилось 01:21:33.9768244, так что с unsafe как-то не складывается.
Потому что число проверок с каждой итерацией вырастает на 1, поэтому до 10% добегает за 20 секунд, а с 90 до 100 идёт минут 15.

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

Или если процессор многоядерный использовать потоки.

потоки уже используются - For(), все 4 ядра заняты в процессе работы.

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

какой у вас тип данных в массиве?

C#
1
byte[,]

@nicolas2008 · 19.12.2018, 11:39

belalugoci, Подозреваю, что код UnsafeFast тоже был "улучшен" с вашей стороны.
Вчера у вас был ulong[] сегодня опять byte[,]...

@belalugoci · 19.12.2018, 12:06 **[ТС]**

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

Подозреваю, что код UnsafeFast тоже был "улучшен" с вашей стороны.

нет, тупо скопировал отсюда.

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

Вчера у вас был ulong[] сегодня опять byte[,]...

так как до этого переделывал на ulong и были отрицательные результаты, то сейчас данные представил через byte, а unsafe код оставил такой как мне сюда дали.

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

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

Подозреваю, что код UnsafeFast тоже был "улучшен" с вашей стороны.

нет, тупо скопировал отсюда.

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

Вчера у вас был ulong[] сегодня опять byte[,]...

так как до этого переделывал на ulong и были отрицательные результаты, то сейчас данные представил через byte, а 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
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
public byte[,] DimBits = new byte[3355443, 28];
 
private void button1_Click(object sender, EventArgs e)
{
    ulong countN = 0; // число итераций
    for (x1 = 0; x1 < 3355443; x1++)
    // тут цикл упрощён сильно,
    // так как на самом деле здесь 5 вложенных циклов,
    // поэтому мне проще использовать индекс countN
    // нежели считать его из пяти значений x1..x5
   {
        /*
            тут считаем DimBits;
        */
        if ((countN > 0)) For(0, countN, Compare);
        countN++;
    }
}
 
public void Compare(int y)
{
    if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y))
    {
        //тут реагируем на совпадение, например пишем в txt совпавшие пары
    }
}
 
        public 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;
            }
        }

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

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

еще как вариант можно ускорить (до 8х) используя SIMD .Net. (поставить пакет System.Numerics.Vectors от microsoft)

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

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

@maximka777 · 19.12.2018, 12:40

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

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

Есть такая инструкция процессора с поддержкой SSE4 для подсчета бит. На с# можно вызвать через dll с++.
Для х64 пректа.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "pch.h"
#include <iostream>
#include <sstream>      // std::stringstream
#include <Windows.h>      // std::stringstream
#include <intrin.h>
 
int main()
{
    unsigned __int64 a = 0b111;
 
    int res = _mm_popcnt_u64(a);
 
    printf_s("Result %d\n", res);
 
    system("pause");
 
    return 0;
}

@belalugoci · 19.12.2018, 12:50 **[ТС]**

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

На с# можно вызвать через dll с++.
Для х64 пректа.

Вот в этом месте я и не понимаю о чем речь и как этим пользоваться.

@maximka777 · 19.12.2018, 13:23

Пример библиотеки на c++. (popcnt\x64\Release\popcnt.dll) закинуть в папку приложения с#.
Проект обязательно собирать как х64.
Запускать так

C#
1
2
[DllImport("popcnt.dll")]
static extern ulong popcnt(ulong v);

@belalugoci · 20.12.2018, 11:40 **[ТС]**

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

Подозреваю

А вот так выглядит то, что исполняется у меня за 35 минут, против 80 в unsafe:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void Compare(int y)
{
    bool equal = true;
    for (int n = 0; n < 28; n++) // этот цикл в варианте unsafe исчезает и остается только if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y))
        if (DimBits[countN, n] != DimBits[y, n])
        {
            equal = false;
            break;
        }
    if (equal)
    // это как раз то что используется в варианте unsafe : if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y))
    {
        // регистрация совпадения пары
        countX++;
    }
}

upd: кажется я понял почему работает медленно, в моем варианте идет сравнение одного со многими, а в варианте if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y)) идет сравнение многих со многими. Сейчас покумекаю как переделать.

Добавлено через 3 часа 15 минут

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

upd: кажется я понял почему работает медленно, в моем варианте идет сравнение одного со многими, а в варианте if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y)) идет сравнение многих со многими. Сейчас покумекаю как переделать.

нет, я ошибаюсь как мне кажется. Массив размерностью byte[countN, 28], каждую итерацию цикла нужно бегать и проверять 28 ячеек, что делается циклом

C#
1
for (int n = 0; n < 28; n++)

в процедуре Compare, а пробегание по всем элементам массива byte[countN-1, 28] я делаю через

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

То есть для того чтобы заменить

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void Compare(int y)
{
    if (RowsEqualUnsafeFast(DimBits, countN, DimBits, y))
    {
        // регистрация совпадения пары
        countX++;
    }
}
 
public static unsafe bool RowsEqualUnsafeFast(byte[,] arr1, int arr1RowIndex, byte[,] arr2, int arr2RowIndex)
{
    int length1 = 28;// arr1.GetLength(1);
    int length2 = 28;// arr2.GetLength(1);
 
    fixed (byte* p1 = &arr1[arr1RowIndex, 0], p2 = &arr2[arr2RowIndex, 0])
    {
        byte* x1 = p1, x2 = p2;
        for (int i = 0; i < length1 / 8; i++, x1 += 8, x2 += 8)
            if (*((long*)x1) != *((long*)x2)) return false;
        if ((length1 & 4) != 0) { if (*((int*)x1) != *((int*)x2)) return false; x1 += 4; x2 += 4; }
        if ((length1 & 2) != 0) { if (*((short*)x1) != *((short*)x2)) return false; x1 += 2; x2 += 2; }
        if ((length1 & 1) != 0) if (*((byte*)x1) != *((byte*)x2)) return false;
        return true;
    }
}

Добавлено через 3 часа 35 минут
В общем сейчас добился что оба варианта работают 34,5-35,5 минут, но эффекта он unsafe fast нет. Возможно нужен большой массив чтобы эффект наблюдался.

@nicolas2008 · 20.12.2018, 17:37

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

В общем сейчас добился что оба варианта работают 34,5-35,5 минут, но эффекта он unsafe fast нет. Возможно нужен большой массив чтобы эффект наблюдался.

Похоже что да. Думаю на таком маленьком массиве доп. проверки if ((length1 & 4) != 0), if ((length1 & 2) != 0), if ((length1 & 1) != 0) содержат больше операций чем обычная проверка всех байтов по очереди.
А обычный RowsEqualUnsafe пробовали?

@belalugoci · 21.12.2018, 06:56 **[ТС]**

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

А обычный RowsEqualUnsafe пробовали?

Сейчас проверил - нет эффекта.
Кстати и нет эффекта от popcnt.
upd: вернул цикл и кое что косметически подправил с вариантом простого цикла, стабильно 33 минуты вместо 34-37.

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
byte x1, x2, x3, x4, x5; // исходные значение с которыми мы и работаем
 
// подсчёт количества бит делается разными способами, но по скорости я не заметил разницы никакой
// так как биты берутся из разных чисел, то мы не можем сделать popcnt явно
// поэтому сначала должны получить или число, которое отдадим в popcnt
// или считать как-то иначе
 
// первый вариант - узнать наличие определенного бита логическим И
// и используя его как индекс массива получить 1 или 0
// вполне заслуживает премию тупости, но работает
// участвует массив byte[] BitsValue и переменные x1_1 и т.п.
public static readonly byte[] BitsValue = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
x1_1 = BitsValue[x1 & 1];
 
// второй вариант - оперирование массивом бит, возможно есть более простой вариант перевода bool в byte
BitArray ba_x2 = new BitArray(new byte[] { x2 });
x2_1 = (byte)(ba_x2.Get(0) ? 1 : 0);
 
// третий вариант - комбинация первого и второго
x3_1 = (byte)((x3 & 1) > 0 ? 1 : 0);
 
// это переменные считаем первым способом, не суть
x4_1 = BitsValue[x4 & 1];
x5_1 = BitsValue[x5 & 1];
 
// взятая из интернета функция по подсчету числа бит
public byte BitCount(ulong value)
{
    ulong result = value - ((value >> 1) & 0x5555555555555555UL);
    result = (result & 0x3333333333333333UL) + ((result >> 2) & 0x3333333333333333UL);
    return (byte)(unchecked(((result + (result >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56);
}
 
// любезно предоставленный здесь на форуме вариант с использованием аппаратного подсчета popcnt
[DllImport("popcnt.dll")]
static extern ulong popcnt(ulong v);
 
// итак, после всех манипуляций выше мы должны считать биты
 
// 1. оперируем битами непосредственно из исходных чисел
// а потом считаем всё через popcnt
DimBits[countN, 1] = (byte)popcnt((ulong)((x1 & 1) | ((x2 & 1) << 1) | ((x3 & 1) << 2) | ((x4 & 1) << 3) | ((x5 & 1) << 4)));
 
// 2. тоже используем исходные числа
// но считаем биты другой функцией
DimBits[countN, 1] = (byte)BitCount((ulong)((x1 & 1) | ((x2 & 1) << 1) | ((x3 & 1) << 2) | ((x4 & 1) << 3) | ((x5 & 1) << 4)));
 
// 3. тупо суммируем посчитанные ранее 1 и 0
DimBits[countN, 1] = (byte)(x1_1 + x2_1 + x3_1 + x4_1 + x5_1);

Рассмотрю другие варианты, будет интересно что еще можно придумать.

Добавлено через 8 минут
Я правильно думаю что вариант

C#
1
x5_16 = BitsValue[x5 & 16];

должен быть немного медленнее чем

C#
1
x5_16 = (x5 & 16) >> 4;

?

@maximka777 · 21.12.2018, 09:44

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

Кстати и нет эффекта от popcnt.

Его нет потому что с# для вызова метода с одной инструкцией, городит ещё +100500 , поэтому все преимущество сводится на нет. Здесь поможет только чистый с++. Кстати для проверки битов тоже есть инструкция (BT) называется.

@belalugoci · 24.12.2018, 10:09 **[ТС]**

Как ни странно, но вариант с цепочкой

C#
1
2
3
if (DimBits[countN, 0] == DimBits[y, 0])
   ...
      if (DimBits[countN, 27] == DimBits[y, 27])

немного медленнее чем

C#
1
2
3
4
5
6
7
8
bool equal = true;
for (int n = 0; n < 28; n++)
    if (DimBits[countN, n] != DimBits[y, n])
    {
        equal = false;
        break;
    }
if (equal) {...}

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

Добавлено через 5 часов 3 минуты
интересно,
добавил одну строку

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ulong[] freq = new ulong[28];
 
public void Compare(int y)
{
    bool equal = true;
    for (int n = 0; n < 28; n++)
        if (DimBits[countN, n] != DimBits[y, n])
        {
            equal = false;
            freq[n]++; // это добавлено
            break;
        }
    if (equal) {...}
}

а программа стала исполняться 2,5 часа, если строку закомментировать, то исполняется 35 минут. Что в данном случае так тормозит? Доступ к памяти?

@belalugoci · 25.12.2018, 04:59 **[ТС]**

сравнил работу проекта на Core i5-2400 и Core 2 Quad Q9300, разница по производительности 35 минут и 75 минут, но разница в частоте 3,1 ГГц и 2,5ГГц, если свести к 3,1 старичка Q9300 то он будет считать 60 минут. Смотрим на cpuboss.com и видим, что разница в производительности практически в 2 раза - печалька, я, если честно, думал разрыв будет куда серьезнее.
i5 сделан в 1 квартал 11 года, а Q9300 - 1 квартал 8 года. И тут уже не всё так печально, за 3 года производительность CPU увеличилась в 2 раза, а когда сравниваешь i5 2400 и i5 6600 произведенный еще через 3 года, то разница всего 20%.

Someone007 · 25.12.2018, 05:20

Не по теме:

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

а когда сравниваешь i5 2400 и i5 6600 произведенный еще через 3 года, то разница всего 20%

Так у них по моему архитектура одинаковая, вот и разница такая маленькая. Intel сделали большой скачек в плане производительности как раз с выходом Sandy Bridge и после этого вот уже 7 лет продают по сути одно и тоже каждый год под новым названием немного увеличивая частоту/число ядер...

Новые блоги и статьи Все статьи Все блоги /
Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))

@nicolas2008 1152 / 860 / 263 Регистрация: 30.04.2009 Сообщений: 3,603
	19.12.2018, 11:39
	belalugoci, Подозреваю, что код UnsafeFast тоже был "улучшен" с вашей стороны. Вчера у вас был ulong[] сегодня опять byte[,]... 0

@belalugoci 475 / 294 / 29 Регистрация: 01.06.2018 Сообщений: 3,676
	25.12.2018, 04:59 [ТС]
	сравнил работу проекта на Core i5-2400 и Core 2 Quad Q9300, разница по производительности 35 минут и 75 минут, но разница в частоте 3,1 ГГц и 2,5ГГц, если свести к 3,1 старичка Q9300 то он будет считать 60 минут. Смотрим на cpuboss.com и видим, что разница в производительности практически в 2 раза - печалька, я, если честно, думал разрыв будет куда серьезнее. i5 сделан в 1 квартал 11 года, а Q9300 - 1 квартал 8 года. И тут уже не всё так печально, за 3 года производительность CPU увеличилась в 2 раза, а когда сравниваешь i5 2400 и i5 6600 произведенный еще через 3 года, то разница всего 20%. 0