D vs C++ - Священные войны - Страница 6

@korvin_ · 07.02.2015, 00:11

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

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

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

А символ ^ что означает? xor? Тогда либо я не правильно понял твою формулу, либо она неправильная, т.к. выдаёт неправильные результаты. Например, вот тут правильный результат: http://ideone.com/D55Q6X , твоя формула (если там xor), выдаёт другое число.

@castorsky · 07.02.2015, 00:15

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

А символ ^ что означает? xor?

конъюнкция. В данном случае битовое И (если учесть что элементы матрицы - числа множества {0,1}).

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

твоя формула (если там xor), выдаёт другое число.

Конечно другое.

@korvin_ · 07.02.2015, 00:22

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

В данном случае битовое И (если учесть что элементы матрицы - числа множества {0,1}).
Конечно другое.

Так значит твоя формула неправильная.

Добавлено через 2 минуты
Либо постановка задачи неточная.

Добавлено через 1 минуту
Не, походу я затупил.

@castorsky · 07.02.2015, 00:29

Да, тупнул малость. В смысле я тупнул.

@korvin_ · 07.02.2015, 00:36

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

Да, тупнул малость. В смысле я тупнул.

Но у меня, похоже тоже не совсем верно: только сейчас заметил, что там «Возвести ее в квадрат по модулю 2».

@castorsky · 07.02.2015, 02:14

Короче смыл такой. Элемент результирующей матрицы a[i][j] получается произведением rew[i] * column[j], значит нас интересуют такие произведения, которые равны 1 и умножение матрицы на себя таки проделывать придетеся в полном объеме, но результат никуджа записывать не надо, а просто добавлять его сравнение с единицей к сумме.

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

только сейчас заметил

Я тоже не видел, тогда интересуют произведения, & 1, это быстрее на проверку.

Ну вот тестовый пример, который точно вычисляет правильно и то что надо. Модуль генерации файла, чтения его в память оставляю на желающих. Для данной матрицы правильный ответ 12.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(define A
  (let ((mx '((1 0 0 1 0)
              (1 1 0 0 1)
              (1 0 1 0 0)
              (1 1 1 1 0)
              (1 0 1 0 0))))
    (apply vector (map list->vector mx))))
 
 
(define (vector-mul-mod-2 mx row column length)
  (let ((res (for/fold ((s 0))
                       ((i (in-range length)))
               (+ s (bitwise-and
                     (vector-ref (vector-ref mx row) i)
                     (vector-ref (vector-ref mx i) column))))))
    (bitwise-and 1 res)))
 
 
(define (task mx)
  (let* ((len (vector-length (vector-ref mx 0)))
         (seq (in-range len)))
    (for*/fold ((s 0))
               ((i seq) (j seq))
      (+ s (vector-mul-mod-2 mx i j len)))))

@korvin_ · 07.02.2015, 10:12

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

Ну вот тестовый пример, который точно вычисляет правильно и то что надо.

И уложится в ограничения 2сек для матрицы 4000x4000? Не смеши. =)

Добавлено через 1 час 13 минут
В общем как-то так: http://ideone.com/aYbmOb

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

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
#include <iostream>
#include <cstring>
 
#define NMAX 4000
#define NUMS 63
 
typedef unsigned long long unum;
 
const int nbits = sizeof(unum)*8;
 
unum
scalar_product_mod2(unum *row, unum *col, int n)
{
    unum res, bit, sum;
    sum = 0U;
    for(int i = 0; i < n; i++)
        sum ^= row[i] & col[i];
    res = 0U;
    for(; sum != 0; sum >>= 1)
        res ^= sum & 1;
    return res;
}
 
int
main(int argc, char *argv[])
{
    int  nums, n;
    unum bit, count;
    unum rows[NMAX][NUMS];
    unum cols[NMAX][NUMS];
    char buf[NMAX+2];
 
    std::memset(rows, 0, NMAX*NUMS*sizeof(unum));
    std::memset(cols, 0, NMAX*NUMS*sizeof(unum));
    std::memset(buf, 0, NMAX+2);
    std::cin.sync_with_stdio(false);
    std::cin >> n;
    std::cin.getline(buf, 0);
 
    for(int i = 0; i < n; i++) {
        std::cin.getline(buf, n+1);
        for(int j = 0; j < n; j++) {
            bit = buf[j] - '0';
            rows[i][j/nbits] |= bit << j%nbits;
            cols[j][i/nbits] |= bit << i%nbits;
        }
    }
 
    count = 0;
    nums = n/nbits + 1;
    if(nums > NUMS)
        nums = NUMS;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            count += scalar_product_mod2(rows[i], cols[j], nums);
 
    std::cout << count << std::endl;
 
    return 0;
}

@Voivoid · 07.02.2015, 10:36

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

В общем как-то так: http://ideone.com/aYbmOb

И как, проходит? Все равно ж по сути тоже O(N^3) получается

@korvin_ · 07.02.2015, 11:15

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

И как, проходит?

Проходит.

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

Все равно ж по сути тоже O(N^3) получается

Нет, небольшая оптимизация — представление строк основной матрицы и столбцов транспонированной битовыми массивами и обработка сразу по одной паре ullong чисел, представляющих сразу по 64 элемента матрицы, вместо по одному uchar на каждый элемент — даёт довольно ощутимый прирост. Скажем программа, генерирующая тестовый файл с матрицей и подсчитывающая элементы «в лоб» (uchar — http://ideone.com/FRlXRa) выполняется почти 5 минут для n = 4000, а вышеуказанная программа обрабатывает полученную 4k-матрицу за пару секунд.

Сложность алгоритма, думаю, получается O((n^3) / 64).

Есть еще алгоритм умножения матриц со сложностью O(n^2.3...) (не помню точное значение показателя степени), но я его пока не понял и не уверен, что его удастся адаптировать под такое представление матрицы. А может его и не придётся адаптировать и он даже для нормального представления (uchar на один элемент) будет быстрее моего.

Добавлено через 17 минут
Гм... Ideone не знает std::stoi.

Вот, чуть переделал генератор: http://ideone.com/5Q52AR (там вконце stdout'а количество единиц, которое должно получиться)
А вот, эта же матрица, скормленная программе подсчета: http://ideone.com/rH373Z результат сходится.

Скрипт для генерации тестов:

Bash
1
2
3
4
5
6
7
#!/bin/sh
 
dir="umatrix_test"
 
for n in "$@"; do
    ./umatrix_gentest $n > "$dir/$n.txt"
done

и для запуска:

Bash
1
2
3
4
5
6
7
#!/bin/sh
 
dir="umatrix_test"
 
for file in `ls $dir`; do
    echo "$file:" `./umatrix < "$dir/$file"` `tail -1 "$dir/$file"`
done

Единственная проблема: программа неправильно считывает данные из stdin, если туда перенаправлен файл с виндовыми окончаниями строк CRLF. Мне лень с этим разбираться, проще dos2unix в скрипте заюзать. =)

@Curry · 07.02.2015, 13:11

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

C++
1
2
3
    res = 0U;
    for(; sum != 0; sum >>= 1)
        res ^= sum & 1;

это может помочь отцу русской демократии (немного)

@castorsky · 07.02.2015, 14:21

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

И уложится в ограничения 2сек для матрицы 4000x4000? Не смеши. =)

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

@korvin_ · 07.02.2015, 14:35

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

это может помочь отцу русской демократии (немного)

Да вполне неплохо помогло, спс. Сделал так: http://ideone.com/WbALXQ Теперь 1.37 сек вместо 2.1.

@Dennis Ritchie · 07.02.2015, 14:48 **[ТС]**

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

Да вполне неплохо помогло, спс. Сделал так: http://ideone.com/WbALXQ Теперь 1.37 сек вместо 2.1.

Лог

Добавлено через 8 минут
korvin_, класс. Наконец-то, хоть кто-то смог пропихнуть эту задачу.
Но алгоритм не очень, судя по времени.

Статистика МюМатрицы

@korvin_ · 07.02.2015, 15:07

Сообщение от Dennis Ritchie

Но алгоритм не очень, судя по времени

Ага, я видел. 0.67 сек надо бы получить.

@Dennis Ritchie · 07.02.2015, 15:09 **[ТС]**

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

Ага, я видел. 0.67 сек надо бы получить.

Надо разбивать матрицу на части и ксорить в трёхмерном массиве.

@Curry · 07.02.2015, 15:31

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

Теперь 1.37 сек вместо 2.1.

Для конкретной задачи неважно, но этот алгоритм подсчёта бит работает с любой разрядностью

C++
1
2
3
4
5
6
7
bool isOdd(unum x)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    return ((x + (x >> 8) + (x >> 16) + (x >> 32)) & 1) != 0;
}

@korvin_ · 07.02.2015, 15:45

Не по теме:

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

Для конкретной задачи неважно, но этот алгоритм подсчёта бит работает с любой разрядностью

Мне лень было разбираться, я с подобными вещами на ~~«;%:№;%?шозанах?»~~«Вы».

@Dennis Ritchie · 07.02.2015, 15:46 **[ТС]**

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

Для конкретной задачи неважно, но этот алгоритм подсчёта бит работает с любой разрядностью

Можно ещё так делать: 1LL в C++, 1L в D - единица типа long long.

Кстати, а не кто не хочет сегодня сыграть в чемпионат по программированию Rockethon 2015?

Три лучших участника получат следующие призы:

1) IPhone 6 (16 Gb)

2) Участник может выбрать Apple Watch или Samsung Gear S

3) Участник может выбрать Apple Watch или Samsung Gear S

Лучшие 150 участников получат футбоолки Rockethon с оригинальным дизайном соревнования.

Для участия нужно всего лишь зарегистрироваться на сайте и войти в соревнование.

Поддерживаемые языки программирования

GNU C GCC 4.9.2
GNU C++ 4.9.2
GNU C++11 4.9.2
Microsoft Visual C++ 2010
C# Mono 2.10
MS C# .NET 4
D DMD32 Compiler v2
Go 1.2
Haskell GHC 7.6
Java 6
Java 7
Java 8
OCaml 4
Delphi 7
Free Pascal 2
Perl 5.12
PHP 5.3
Python 2.7
Python 3.4
Ruby 2
Scala 2.11
JavaScript V8 3

P.S. Конечно, никто из вас не сможет занять первых три места. Может быть, получите футболку, если умеете олимпиадно кодить.

@Curry · 07.02.2015, 15:57

Сообщение от Dennis Ritchie

Можно ещё так делать: 1LL в C++, 1L в D - единица типа long long.

а надо unsigned long long (1ULL), хотя и без них хорошо.

Сообщение от Dennis Ritchie

Может быть, получите футболку, если умеете олимпиадно кодить.

Не, не умеем. Мы матрицы через GPGPU перемножаем, а там наверняка нельзя.

@Dennis Ritchie · 07.02.2015, 16:08 **[ТС]**

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

Не, не умеем. Мы матрицы через GPGPU перемножаем, а там наверняка нельзя.

Там нет таких жёстких ограничений по времени, так что можете спокойно попробовать.

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

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

надо unsigned long long (1ULL), хотя и без них хорошо.

Нет разницы. Типы long long и unsigned long long одинаково занимают по 64 бита. Следовательно, максимум сдвига 1ULL << 63 и 1LL << 63.

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

@castorsky 1978 / 1082 / 87 Регистрация: 29.11.2013 Сообщений: 3,353
	07.02.2015, 00:29
	Да, тупнул малость. В смысле я тупнул. 0