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

@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 лет продают по сути одно и тоже каждый год под новым названием немного увеличивая частоту/число ядер...

Новые блоги и статьи Все статьи Все блоги /
Грибы - это женщины, деревья - это мужчины. Анти инь янь для союза мужчины и женщины. anaschu 18.07.2026 ГЛАВНЫЙ НАУЧНО-ФИЛОСОФСКИЙ ВЫВОД: Сексуально-Репродуктивный Капитализм против Государства Моногамии Коллеги, мы вышли на финишную прямую 20-мерного ОДУ-моделирования вековой сукцессии (ветка. . .	Текстовый слайдер с нумерацией страниц и кроссбраузерность. russiannick 18.07.2026 Один мой друг написал текстовый слайдер с нумерацией страниц. Сегодня я расскажу как он умудрился подружить его с кроссбраузерностью. Очевидно сложно угодить с шириной каждому браузеру. Один крадет. . .	Грибы - это мемы, дерево - это человек. Применение микоризной модели к теории меметики Докинза. anaschu 18.07.2026 Меметический изоморфизм теории «всего»: Грибная сукцессия как модель эволюции идей Докинза Базовый код системы ОДУ микоризной сукцессии описывает не просто биологию, а универсальную. . .	Грибы - это корпорации, деревья - это государства. Механизм массонского захвата власти anaschu 18.07.2026 Макроэкономический изоморфизм теории «всего»: Грибная сукцессия как модель транснационального капитализма Базовый код системы ОДУ микоризной сукцессии описывает не просто биологию, а. . .
Расчёт периметра прямоугольника по координатам вершин Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Вычислить периметр прямоугольника, заданного координатами своих вершин на плоскости. Решение: Создан документ со следующими. . .	Подсчёт частоты трёхбуквенных слов в тексте Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Выясните, сколько раз в предложенном тексте встречается каждое трехбуквенное слово. Решение: Создан документ с единственным. . .	Сумма и количество положительных элементов в чётных строках массива Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Вычислить сумму и количество положительных элементов массива, расположенных в четных строках. Решение: Создан документ с. . .	Поиск произведения положительных чётных чисел в последовательности Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Дана произвольная последовательность целых чисел. Найти произведение положительных четных чисел данной последовательности. . . .

@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