Hitung permanen secepat mungkin

27

Tantangannya adalah untuk menulis kode tercepat yang mungkin untuk menghitung permanen dari sebuah matriks .

Permanen dari n-by- nmatrix A= ( ai,j) didefinisikan sebagai

masukkan deskripsi gambar di sini

Di sini S_nmewakili set semua permutasi dari [1, n].

Sebagai contoh (dari wiki):

masukkan deskripsi gambar di sini

Dalam pertanyaan ini semua matriks berbentuk bujur sangkar dan hanya akan memiliki nilai -1dan 1di dalamnya.

Contohnya

Memasukkan:

[[ 1 -1 -1  1]
 [-1 -1 -1  1]
 [-1  1 -1  1]
 [ 1 -1 -1  1]]

Permanen:

-4

Memasukkan:

[[-1 -1 -1 -1]
 [-1  1 -1 -1]
 [ 1 -1 -1 -1]
 [ 1 -1  1 -1]]

Permanen:

0

Memasukkan:

[[ 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  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  1  1]]

Permanen:

192

Memasukkan:

[[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, 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, -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, 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, -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, 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, 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, -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, 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, 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, -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, 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, -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]]

Permanen:

1021509632

Tugas

Anda harus menulis kode yang, diberikan noleh nmatriks, menghasilkan permanen.

Karena saya perlu menguji kode Anda, akan sangat membantu jika Anda dapat memberikan cara sederhana bagi saya untuk memberikan matriks sebagai input ke kode Anda, misalnya dengan membaca dari standar di.

Berhati-hatilah karena permanen bisa besar (semua matriks 1s adalah kasus ekstrim).

Skor dan dasi

Saya akan menguji kode Anda secara acak + -1 matriks ukuran yang meningkat dan menghentikan pertama kali kode Anda membutuhkan lebih dari 1 menit di komputer saya. Matriks penilaian akan konsisten untuk semua pengiriman untuk memastikan keadilan.

Jika dua orang mendapatkan skor yang sama maka pemenangnya adalah yang tercepat untuk nilai tersebut n. Jika mereka berada dalam 1 detik satu sama lain maka itu adalah yang diposting terlebih dahulu.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa dan pustaka yang tersedia yang Anda suka tetapi tidak ada fungsi yang sudah ada sebelumnya untuk menghitung permanen. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda, jadi silakan sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di Linux jika memungkinkan. `

Implementasi referensi

Sudah ada pertanyaan pertanyaan codegolf dengan banyak kode dalam berbagai bahasa untuk menghitung permanen untuk matriks kecil. Mathematica dan Maple juga memiliki implementasi permanen jika Anda dapat mengaksesnya.

Mesin Saya Pengaturan waktu akan dijalankan pada mesin 64-bit saya. Ini adalah instalasi ubuntu standar dengan RAM 8GB, Prosesor Delapan-Core AMD FX-8350 dan Radeon HD 4250. Ini juga berarti saya harus dapat menjalankan kode Anda.

Informasi tingkat rendah tentang mesin saya

cat /proc/cpuinfo/|grep flags memberi

Flags flag: fpu vme de pse tc tl msr pae mce cx8 apic mc mcr pge mca f16c lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs xop skinit wdt lwp fma4 tce nodeid_msr tbm topoext perfctr_nb cpb hw_memilikibataspermukaantidakmemilikibubuhmemutuskanmemutuskanmemutakhirkansampai3dakmemutakhirkandenganmemutakhirkankekdot

Saya akan mengajukan pertanyaan multi-bahasa lanjutan yang tidak terkait dengan masalah Int besar sehingga pecinta Scala , Nim , Julia , Rust , Bash dapat memamerkan bahasa mereka juga.

Papan pemimpin

  • n = 33 (45 detik. 64 detik untuk n = 34). Ton Hospel dalam C ++ dengan g ++ 5.4.0.
  • n = 32 (32 detik). Dennis dalam C dengan gcc 5.4.0 menggunakan bendera gcc Ton Hospel.
  • n = 31 (54 detik). Christian Sievers di Haskell
  • n = 31 (60 detik). primo dengan rpython
  • n = 30 (26 detik). ezrast di Rust
  • n = 28 (49 detik). xnor dengan Python + pypy 5.4.1
  • n = 22 (25 detik). Shebang dengan Python + pypy 5.4.1

Catatan . Dalam praktiknya penentuan waktu untuk Dennis dan Ton Hospel sangat bervariasi karena alasan misterius. Misalnya mereka tampaknya lebih cepat setelah saya memuat peramban web! Pengaturan waktu yang dikutip adalah yang tercepat dalam semua tes yang telah saya lakukan.

sergiol
sumber
5
Saya membaca kalimat pertama, pikir 'Lembik', bergulir ke bawah, ya - Lembik.
orlp
@ orlp :) Sudah lama.
1
@Lembik saya menambahkan test case besar. Saya akan menunggu seseorang untuk memastikannya.
xnor
2
Salah satu jawaban mencetak hasil perkiraan, karena menggunakan pelampung presisi ganda untuk menyimpan yang permanen. Apakah itu diizinkan?
Dennis
1
@ChristianSievers Saya pikir saya mungkin bisa melakukan sihir dengan tanda-tanda, tetapi itu tidak berjalan ...
Socratic Phoenix

Jawaban:

14

gcc C ++ n ≈ 36 (57 detik di sistem saya)

Menggunakan rumus Glynn dengan kode Grey untuk pembaruan jika semua jumlah kolom genap, jika tidak menggunakan metode Ryser. Berurutan dan vektor. Dioptimalkan untuk AVX, jadi jangan berharap banyak pada prosesor yang lebih lama. Jangan repot-repot dengan n>=35untuk matriks dengan hanya +1 bahkan jika sistem Anda cukup cepat karena akumulator 128 bit yang ditandatangani akan melimpah. Untuk matriks acak Anda mungkin tidak akan mencapai overflow. Untuk n>=37pengganda internal akan mulai meluap untuk semua 1/-1matriks. Jadi hanya gunakan program ini untuk n<=36.

Berikan saja elemen matriks pada STDIN yang dipisahkan oleh segala jenis spasi

permanent
1 2
3 4
^D

permanent.cpp:

/*
  Compile using something like:
    g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -pthread -s permanent.cpp -o permanent
*/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdint>
#include <climits>
#include <array>
#include <vector>
#include <thread>
#include <future>
#include <ctgmath>
#include <immintrin.h>

using namespace std;

bool const DEBUG = false;
int const CACHE = 64;

using Index  = int_fast32_t;
Index glynn;
// Number of elements in our vectors
Index const POW   = 3;
Index const ELEMS = 1 << POW;
// Over how many floats we distribute each row
Index const WIDTH = 9;
// Number of bits in the fraction part of a floating point number
int const FLOAT_MANTISSA = 23;
// Type to use for the first add/multiply phase
using Sum  = float;
using SumN = __restrict__ Sum __attribute__((vector_size(ELEMS*sizeof(Sum))));
// Type to convert to between the first and second phase
using ProdN = __restrict__ int32_t __attribute__((vector_size(ELEMS*sizeof(int32_t))));
// Type to use for the third and last multiply phase.
// Also used for the final accumulator
using Value = __int128;
using UValue = unsigned __int128;

// Wrap Value so C++ doesn't really see it and we can put it in vectors etc.
// Needed since C++ doesn't fully support __int128
struct Number {
    Number& operator+=(Number const& right) {
        value += right.value;
        return *this;
    }
    // Output the value
    void print(ostream& os, bool dbl = false) const;
    friend ostream& operator<<(ostream& os, Number const& number) {
        number.print(os);
        return os;
    }

    Value value;
};

using ms = chrono::milliseconds;

auto nr_threads = thread::hardware_concurrency();
vector<Sum> input;

// Allocate cache aligned datastructures
template<typename T>
T* alloc(size_t n) {
    T* mem = static_cast<T*>(aligned_alloc(CACHE, sizeof(T) * n));
    if (mem == nullptr) throw(bad_alloc());
    return mem;
}

// Work assigned to thread k of nr_threads threads
Number permanent_part(Index n, Index k, SumN** more) {
    uint64_t loops = (UINT64_C(1) << n) / nr_threads;
    if (glynn) loops /= 2;
    Index l = loops < ELEMS ? loops : ELEMS;
    loops /= l;
    auto from = loops * k;
    auto to   = loops * (k+1);

    if (DEBUG) cout << "From=" << from << "\n";
    uint64_t old_gray = from ^ from/2;
    uint64_t bit = 1;
    bool bits = (to-from) & 1;

    Index nn = (n+WIDTH-1)/WIDTH;
    Index ww = nn * WIDTH;
    auto column = alloc<SumN>(ww);
    for (Index i=0; i<n; ++i)
        for (Index j=0; j<ELEMS; ++j) column[i][j] = 0;
    for (Index i=n; i<ww; ++i)
        for (Index j=0; j<ELEMS; ++j) column[i][j] = 1;
    Index b;
    if (glynn) {
        b = n > POW+1 ? n - POW - 1: 0;
        auto c = n-1-b;
        for (Index k=0; k<l; k++) {
            Index gray = k ^ k/2;
            for (Index j=0; j< c; ++j)
                if (gray & 1 << j)
                    for (Index i=0; i<n; ++i)
                        column[i][k] -= input[(b+j)*n+i];
                else
                    for (Index i=0; i<n; ++i)
                        column[i][k] += input[(b+j)*n+i];
        }
        for (Index i=0; i<n; ++i)
            for (Index k=0; k<l; k++)
                column[i][k] += input[n*(n-1)+i];

        for (Index k=1; k<l; k+=2)
            column[0][k] = -column[0][k];

        for (Index i=0; i<b; ++i, bit <<= 1) {
            if (old_gray & bit) {
                bits = bits ^ 1;
                for (Index j=0; j<ww; ++j)
                    column[j] -= more[i][j];
            } else {
                for (Index j=0; j<ww; ++j)
                    column[j] += more[i][j];
            }
        }

        for (Index i=0; i<n; ++i)
            for (Index k=0; k<l; k++)
                column[i][k] /= 2;
    } else {
        b = n > POW ? n - POW : 0;
        auto c = n-b;
        for (Index k=0; k<l; k++) {
            Index gray = k ^ k/2;
            for (Index j=0; j<c; ++j)
                if (gray & 1 << j)
                    for (Index i=0; i<n; ++i)
                        column[i][k] -= input[(b+j)*n+i];
        }

        for (Index k=1; k<l; k+=2)
            column[0][k] = -column[0][k];

        for (Index i=0; i<b; ++i, bit <<= 1) {
            if (old_gray & bit) {
                bits = bits ^ 1;
                for (Index j=0; j<ww; ++j)
                    column[j] -= more[i][j];
            }
        }
    }

    if (DEBUG) {
        for (Index i=0; i<ww; ++i) {
            cout << "Column[" << i << "]=";
            for (Index j=0; j<ELEMS; ++j) cout << " " << column[i][j];
            cout << "\n";
        }
    }

    --more;
    old_gray = (from ^ from/2) | UINT64_C(1) << b;
    Value total = 0;
    SumN accu[WIDTH];
    for (auto p=from; p<to; ++p) {
        uint64_t new_gray = p ^ p/2;
        uint64_t bit = old_gray ^ new_gray;
        Index i = __builtin_ffsl(bit);
        auto diff = more[i];
        auto c = column;
        if (new_gray > old_gray) {
            // Phase 1 add/multiply.
            // Uses floats until just before loss of precision
            for (Index i=0; i<WIDTH; ++i) accu[i] = *c++ -= *diff++;

            for (Index j=1; j < nn; ++j)
                for (Index i=0; i<WIDTH; ++i) accu[i] *= *c++ -= *diff++;
        } else {
            // Phase 1 add/multiply.
            // Uses floats until just before loss of precision
            for (Index i=0; i<WIDTH; ++i) accu[i] = *c++ += *diff++;

            for (Index j=1; j < nn; ++j)
                for (Index i=0; i<WIDTH; ++i) accu[i] *= *c++ += *diff++;
        }

        if (DEBUG) {
            cout << "p=" << p << "\n";
            for (Index i=0; i<ww; ++i) {
                cout << "Column[" << i << "]=";
                for (Index j=0; j<ELEMS; ++j) cout << " " << column[i][j];
                cout << "\n";
            }
        }

        // Convert floats to int32_t
        ProdN prod32[WIDTH] __attribute__((aligned (32)));
        for (Index i=0; i<WIDTH; ++i)
            // Unfortunately gcc doesn't recognize the static_cast<int32_t>
            // as a vector pattern, so force it with an intrinsic
#ifdef __AVX__
            //prod32[i] = static_cast<ProdN>(accu[i]);
            reinterpret_cast<__m256i&>(prod32[i]) = _mm256_cvttps_epi32(accu[i]);
#else   // __AVX__
            for (Index j=0; j<ELEMS; ++j)
                prod32[i][j] = static_cast<int32_t>(accu[i][j]);
#endif  // __AVX__

        // Phase 2 multiply. Uses int64_t until just before overflow
        int64_t prod64[3][ELEMS];
        for (Index i=0; i<3; ++i) {
            for (Index j=0; j<ELEMS; ++j)
                prod64[i][j] = static_cast<int64_t>(prod32[i][j]) * prod32[i+3][j] * prod32[i+6][j];
        }
        // Phase 3 multiply. Collect into __int128. For large matrices this will
        // actually overflow but that's ok as long as all 128 low bits are
        // correct. Terms will cancel and the final sum can fit into 128 bits
        // (This will start to fail at n=35 for the all 1 matrix)
        // Strictly speaking this needs the -fwrapv gcc option
        for (Index j=0; j<ELEMS; ++j) {
            auto value = static_cast<Value>(prod64[0][j]) * prod64[1][j] * prod64[2][j];
            if (DEBUG) cout << "value[" << j << "]=" << static_cast<double>(value) << "\n";
            total += value;
        }
        total = -total;

        old_gray = new_gray;
    }

    return bits ? Number{-total} : Number{total};
}

// Prepare datastructures, Assign work to threads
Number permanent(Index n) {
    Index nn = (n+WIDTH-1)/WIDTH;
    Index ww = nn*WIDTH;

    Index rows  = n > (POW+glynn) ? n-POW-glynn : 0;
    auto data = alloc<SumN>(ww*(rows+1));
    auto pointers = alloc<SumN *>(rows+1);
    auto more = &pointers[0];
    for (Index i=0; i<rows; ++i)
        more[i] = &data[ww*i];
    more[rows] = &data[ww*rows];
    for (Index j=0; j<ww; ++j)
        for (Index i=0; i<ELEMS; ++i)
            more[rows][j][i] = 0;

    Index loops = n >= POW+glynn ? ELEMS : 1 << (n-glynn);
    auto a = &input[0];
    for (Index r=0; r<rows; ++r) {
        for (Index j=0; j<n; ++j) {
            for (Index i=0; i<loops; ++i)
                more[r][j][i] = j == 0 && i %2 ? -*a : *a;
            for (Index i=loops; i<ELEMS; ++i)
                more[r][j][i] = 0;
            ++a;
        }
        for (Index j=n; j<ww; ++j)
            for (Index i=0; i<ELEMS; ++i)
                more[r][j][i] = 0;
    }

    if (DEBUG)
        for (Index r=0; r<=rows; ++r)
            for (Index j=0; j<ww; ++j) {
                cout << "more[" << r << "][" << j << "]=";
                for (Index i=0; i<ELEMS; ++i)
                    cout << " " << more[r][j][i];
                cout << "\n";
            }

    // Send work to threads...
    vector<future<Number>> results;
    for (auto i=1U; i < nr_threads; ++i)
        results.emplace_back(async(DEBUG ? launch::deferred: launch::async, permanent_part, n, i, more));
    // And collect results
    auto r = permanent_part(n, 0, more);
    for (auto& result: results)
        r += result.get();

    free(data);
    free(pointers);

    // For glynn we should double the result, but we will only do this during
    // the final print. This allows n=34 for an all 1 matrix to work
    // if (glynn) r *= 2;
    return r;
}

// Print 128 bit number
void Number::print(ostream& os, bool dbl) const {
    const UValue BILLION = 1000000000;

    UValue val;
    if (value < 0) {
        os << "-";
        val = -value;
    } else
        val = value;
    if (dbl) val *= 2;

    uint32_t output[5];
    for (int i=0; i<5; ++i) {
        output[i] = val % BILLION;
        val /= BILLION;
    }
    bool print = false;
    for (int i=4; i>=0; --i) {
        if (print) {
            os << setfill('0') << setw(9) << output[i];
        } else if (output[i] || i == 0) {
            print = true;
            os << output[i];
        }
    }
}

// Read matrix, check for sanity
void my_main() {
    Sum a;
    while (cin >> a)
        input.push_back(a);

    size_t n = sqrt(input.size());
    if (input.size() != n*n)
        throw(logic_error("Read " + to_string(input.size()) +
                          " elements which does not make a square matrix"));

    vector<double> columns_pos(n, 0);
    vector<double> columns_neg(n, 0);
    Sum *p = &input[0];
    for (size_t i=0; i<n; ++i)
        for (size_t j=0; j<n; ++j, ++p) {
            if (*p >= 0) columns_pos[j] += *p;
            else         columns_neg[j] -= *p;
        }
    std::array<double,WIDTH> prod;
    prod.fill(1);

    int32_t odd = 0;
    for (size_t j=0; j<n; ++j) {
        prod[j%WIDTH] *= max(columns_pos[j], columns_neg[j]);
        auto sum = static_cast<int32_t>(columns_pos[j] - columns_neg[j]);
        odd |= sum;
    }
    glynn = (odd & 1) ^ 1;
    for (Index i=0; i<WIDTH; ++i)
        // A float has an implicit 1. in front of the fraction so it can
        // represent 1 bit more than the mantissa size. And 1 << (mantissa+1)
        // itself is in fact representable
        if (prod[i] && log2(prod[i]) > FLOAT_MANTISSA+1)
            throw(range_error("Values in matrix are too large. A subproduct reaches " + to_string(prod[i]) + " which doesn't fit in a float without loss of precision"));

    for (Index i=0; i<3; ++i) {
        auto prod3 = prod[i] * prod[i+3] * prod[i+6];
        if (log2(prod3) >= CHAR_BIT*sizeof(int64_t)-1)
            throw(range_error("Values in matrix are too large. A subproduct reaches " + to_string(prod3) + " which doesn't fit in an int64"));
    }

    nr_threads = pow(2, ceil(log2(static_cast<float>(nr_threads))));
    uint64_t loops = UINT64_C(1) << n;
    if (glynn) loops /= 2;
    if (nr_threads * ELEMS > loops)
        nr_threads = max(loops / ELEMS, UINT64_C(1));
    // if (DEBUG) nr_threads = 1;

    cout << n << " x " << n << " matrix, method " << (glynn ? "Glynn" : "Ryser") << ", " << nr_threads << " threads" << endl;

    // Go for the actual calculation
    auto start = chrono::steady_clock::now();
    auto perm = permanent(n);
    auto end = chrono::steady_clock::now();
    auto elapsed = chrono::duration_cast<ms>(end-start).count();

    cout << "Permanent=";
    perm.print(cout, glynn);
    cout << " (" << elapsed / 1000. << " s)" << endl;
}

// Wrapper to print any exceptions
int main() {
    try {
        my_main();
    } catch(exception& e) {
        cerr << "Error: " << e.what() << endl;
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}
Ton Hospel
sumber
Flags flag: fpu vme de pse tc tl msr pae mce cx8 apic mc mcr pge mca f16c lahf_lm cmp_legacy svm extapic cr8_legacy ABM SSE4a misalignsse 3dnowprefetch osvw IBS XOP skinit wdt lwp fma4 tce nodeid_msr tbm topoext perfctr_core perfctr_nb CPB hw_pstate vmmcall bmi1 arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold
Saya masih men-debug harness pengujian saya untuk menjalankan kode Anda tetapi terlihat sangat cepat, terima kasih! Saya bertanya-tanya apakah ukuran int yang lebih besar mungkin menyebabkan masalah kecepatan (seperti yang Anda sarankan). Saya melihat accu.org/index.php/articles/1849 kalau-kalau ada yang menarik.
Saya harus memodifikasi kode Anda untuk menghapus quick_exit karena itu membuatnya sangat sulit untuk digunakan dalam test harness. Karena ketertarikan, mengapa Anda menggunakan rumus Ryser ketika wiki tampaknya mengklaim yang lain harus dua kali lebih cepat?
@Lembik Saya beralih ke formula Ryser karena dengan yang lain saya perlu mengurangi 2 << (n-1) pada akhirnya yang berarti akumulator int128 saya meluap jauh sebelum titik itu.
Ton Hospel
1
@Lembik Ya :-)
Ton Hospel
7

C99, n ≈ 33 (35 detik)

#include <stdint.h>
#include <stdio.h>

#define CHUNK_SIZE 12
#define NUM_THREADS 8

#define popcnt __builtin_popcountll
#define BILLION (1000 * 1000 * 1000)
#define UPDATE_ROW_PPROD() \
    update_row_pprod(row_pprod, row, rows, row_sums, mask, mask_popcnt)

typedef __int128 int128_t;

static inline int64_t update_row_pprod
(
    int64_t* row_pprod, int64_t row, int64_t* rows,
    int64_t* row_sums, int64_t mask, int64_t mask_popcnt
)
{
    int64_t temp = 2 * popcnt(rows[row] & mask) - mask_popcnt;

    row_pprod[0] *= temp;
    temp -= 1;
    row_pprod[1] *= temp;
    temp -= row_sums[row];
    row_pprod[2] *= temp;
    temp += 1;
    row_pprod[3] *= temp;

    return row + 1;
}

int main(int argc, char* argv[])
{
    int64_t size = argc - 1, rows[argc - 1];
    int64_t row_sums[argc - 1];
    int128_t permanent = 0, sign = size & 1 ? -1 : 1;

    if (argc == 2)
    {
        printf("%d\n", argv[1][0] == '-' ? -1 : 1);
        return 0;
    }

    for (int64_t row = 0; row < size; row++)
    {
        char positive = argv[row + 1][0] == '+' ? '-' : '+';

        sign *= ',' - positive;
        rows[row] = row_sums[row] = 0;

        for (char* p = &argv[row + 1][1]; *p; p++)
        {
            rows[row] <<= 1;
            rows[row] |= *p == positive;
            row_sums[row] += *p == positive;
        }

        row_sums[row] = 2 * row_sums[row] - size;
    }

    #pragma omp parallel for reduction(+:permanent) num_threads(NUM_THREADS)
    for (int64_t mask = 1; mask < 1LL << (size - 1); mask += 2)
    {
        int64_t mask_popcnt = popcnt(mask);
        int64_t row = 0;
        int128_t row_prod = 1 - 2 * (mask_popcnt & 1);
        int128_t row_prod_high = -row_prod;
        int128_t row_prod_inv = row_prod;
        int128_t row_prod_inv_high = -row_prod;

        for (int64_t chunk = 0; chunk < size / CHUNK_SIZE; chunk++)
        {
            int64_t row_pprod[4] = {1, 1, 1, 1};

            for (int64_t i = 0; i < CHUNK_SIZE; i++)
                row = UPDATE_ROW_PPROD();

            row_prod *= row_pprod[0], row_prod_high *= row_pprod[1];
            row_prod_inv *= row_pprod[3], row_prod_inv_high *= row_pprod[2];
        }

        int64_t row_pprod[4] = {1, 1, 1, 1};

        while (row < size)
            row = UPDATE_ROW_PPROD();

        row_prod *= row_pprod[0], row_prod_high *= row_pprod[1];
        row_prod_inv *= row_pprod[3], row_prod_inv_high *= row_pprod[2];
        permanent += row_prod + row_prod_high + row_prod_inv + row_prod_inv_high;
    }

    permanent *= sign;

    if (permanent < 0)
        printf("-"), permanent *= -1;

    int32_t output[5], print = 0;

    output[0] = permanent % BILLION, permanent /= BILLION;
    output[1] = permanent % BILLION, permanent /= BILLION;
    output[2] = permanent % BILLION, permanent /= BILLION;
    output[3] = permanent % BILLION, permanent /= BILLION;
    output[4] = permanent % BILLION;

    if (output[4])
        printf("%u", output[4]), print = 1;
    if (print)
        printf("%09u", output[3]);
    else if (output[3])
        printf("%u", output[3]), print = 1;
    if (print)
        printf("%09u", output[2]);
    else if (output[2])
        printf("%u", output[2]), print = 1;
    if (print)
        printf("%09u", output[1]);
    else if (output[1])
        printf("%u", output[1]), print = 1;
    if (print)
        printf("%09u\n", output[0]);
    else
        printf("%u\n", output[0]);
}

Input saat ini agak rumit; itu diambil dengan baris sebagai argumen baris perintah, di mana setiap entri diwakili oleh tanda, yaitu, + menunjukkan 1 dan - menunjukkan -1 .

Uji coba

$ gcc -Wall -std=c99 -march=native -Ofast -fopenmp -fwrapv -o permanent permanent.c
$ ./permanent +--+ ---+ -+-+ +--+
-4
$ ./permanent ---- -+-- +--- +-+-
0
$ ./permanent +-+----- --++-++- +----+++ ---+-+++ +--++++- -+-+-++- +-+-+-+- --+-++++
192
$ ./permanent +-+--+++----++++-++- +-+++++-+--+++--+++- --+++----+-+++---+-- ---++-++++++------+- -+++-+++---+-+-+++++ +-++--+-++++-++-+--- +--+---+-++++---+++- +--+-++-+++-+-+++-++ +-----+++-----++-++- --+-+-++-+-++++++-++ -------+----++++---- ++---++--+-++-++++++ -++-----++++-----+-+ ++---+-+----+-++-+-+ +++++---+++-+-+++-++ +--+----+--++-+----- -+++-++--+++--++--++ ++--++-++-+++-++-+-+ +++---+--++---+----+ -+++-------++-++-+--
1021509632
$ time ./permanent +++++++++++++++++++++++++++++++{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}     # 31
8222838654177922817725562880000000

real    0m8.365s
user    1m6.504s
sys     0m0.000s
$ time ./permanent ++++++++++++++++++++++++++++++++{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}   # 32
263130836933693530167218012160000000

real    0m17.013s
user    2m15.226s
sys     0m0.001s
$ time ./permanent +++++++++++++++++++++++++++++++++{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,} # 33
8683317618811886495518194401280000000

real    0m34.592s
user    4m35.354s
sys     0m0.001s
Dennis
sumber
Apakah Anda punya ide untuk perbaikan?
xnor
@xnatau Beberapa. Saya ingin mencoba mengemas multiplikasi dengan SSE dan membuka sebagian loop besar (untuk melihat apakah saya dapat mempercepat paralelisasi dan menghitung lebih dari 4 nilai sekaligus tanpa menelepon popcnt). Jika itu menghemat waktu, rintangan besar berikutnya adalah tipe integer. Untuk matriks yang dihasilkan secara acak, permanen relatif kecil. Jika saya dapat menemukan cara mudah untuk menghitung batasan sebelum melakukan perhitungan yang sebenarnya, saya mungkin membungkus semuanya dalam kondisi besar.
Dennis
@ Dennis Tentang membuka gulungan lingkaran, optimisasi kecil yang mungkin adalah membuat baris paling atas menjadi +1.
xnor
@ xnor Ya, saya mencoba itu di beberapa titik, tetapi kemudian mengembalikan perubahan untuk mencoba sesuatu yang lain (yang tidak berhasil sama sekali ). Kemacetan tampaknya menjadi perkalian integer (yang lambat untuk 64 bit dan benar - benar lambat untuk 128), itulah sebabnya saya berharap SSE akan membantu sedikit.
Dennis
1
@ Dennisu begitu. Tentang batas, satu batasan yang tidak jelas adalah dalam hal norma operator | Per (M) | <= | M | ^ n. Lihat arxiv.org/pdf/1606.07474v1.pdf
xnor
5

Python 2, n ≈ 28

from operator import mul

def fast_glynn_perm(M):
    row_comb = [sum(c) for c in zip(*M)]
    n=len(M)

    total = 0
    old_grey = 0 
    sign = +1

    binary_power_dict = {2**i:i for i in range(n)}
    num_loops = 2**(n-1)

    for bin_index in xrange(1, num_loops + 1):  
        total += sign * reduce(mul, row_comb)

        new_grey = bin_index^(bin_index/2)
        grey_diff = old_grey ^ new_grey
        grey_diff_index = binary_power_dict[grey_diff]

        new_vector = M[grey_diff_index]
        direction = 2 * cmp(old_grey,new_grey)      

        for i in range(n):
            row_comb[i] += new_vector[i] * direction

        sign = -sign
        old_grey = new_grey

    return total/num_loops

Menggunakan rumus Glynn dengan a kode Grey untuk pembaruan. Berjalan n=23dalam semenit di mesin saya. Seseorang pasti dapat melakukan implementasi yang lebih baik dalam bahasa yang lebih cepat dan dengan struktur data yang lebih baik. Ini tidak menggunakan bahwa matriks bernilai ± 1.

Implementasi rumus Ryser sangat mirip, menjumlahkan semua 0/1 vektor koefisien daripada ± 1-vektor. Dibutuhkan sekitar dua kali lebih panjang dari rumus Glynn karena menambahkan lebih dari semua vektor seperti itu, sedangkan Glynn membagi dua yang menggunakan simetri hanya dengan yang dimulai dengan +1.

from operator import mul

def fast_ryser_perm(M):
    n=len(M)
    row_comb = [0] * n

    total = 0
    old_grey = 0 
    sign = +1

    binary_power_dict = {2**i:i for i in range(n)}
    num_loops = 2**n

    for bin_index in range(1, num_loops) + [0]: 
        total += sign * reduce(mul, row_comb)

        new_grey = bin_index^(bin_index/2)
        grey_diff = old_grey ^ new_grey
        grey_diff_index = binary_power_dict[grey_diff]

        new_vector = M[grey_diff_index]
        direction = cmp(old_grey, new_grey)

        for i in range(n):
            row_comb[i] += new_vector[i] * direction

        sign = -sign
        old_grey = new_grey

    return total * (-1)**n
Tidak
sumber
Luar biasa. Apakah Anda punya pypy untuk diuji juga?
@ Lembik Tidak, saya belum menginstal banyak.
xnor
Saya akan menggunakan pypy ketika saya mengujinya juga. Bisakah Anda melihat bagaimana menerapkan formula cepat lainnya? Saya merasa ini membingungkan.
@Lembik Apa formula cepat lainnya?
xnor
1
Sebagai referensi, pada komputer saya dengan pypyini dapat dengan mudah menghitung n=28dalam 44,6 detik. Sistem Lembik tampaknya cukup sebanding dengan tambang dalam kecepatan jika tidak sedikit lebih cepat.
Kade
5

Haskell, n = 31 (54d)

Dengan banyak kontribusi yang tak ternilai oleh @Angs: gunakan Vector, gunakan produk hubungan pendek, lihat ganjil n.

import Control.Parallel.Strategies
import qualified Data.Vector.Unboxed as V
import Data.Int

type Row = V.Vector Int8

x :: Row -> [Row] -> Integer -> Int -> Integer
x p (v:vs) m c = let c' = c - 1
                     r = if c>0 then parTuple2 rseq rseq else r0
                     (a,b) = ( x p                  vs m    c' ,
                               x (V.zipWith(-) p v) vs (-m) c' )
                             `using` r
                 in a+b
x p _      m _ = prod m p

prod :: Integer -> Row -> Integer
prod m p = if 0 `V.elem` p then 0 
                           else V.foldl' (\a b->a*fromIntegral b) m p

p, pt :: [Row] -> Integer
p (v:vs) = x (foldl (V.zipWith (+)) v vs) (map (V.map (2*)) vs) 1 11
           `div` 2^(length vs)
p [] = 1 -- handle 0x0 matrices too  :-)

pt (v:vs) | even (length vs) = p ((V.map (2*) v) : vs ) `div` 2
pt mat                       = p mat

main = getContents >>= print . pt . map V.fromList . read

Upaya pertama saya pada paralelisme di Haskell. Anda dapat melihat banyak langkah pengoptimalan melalui riwayat revisi. Hebatnya, sebagian besar perubahannya sangat kecil. Kode ini didasarkan pada rumus di bagian "rumus Balasubramanian-Bax / Franklin-Glynn" dalam artikel Wikipedia tentang menghitung permanen .

pmenghitung permanen. Ini disebut viapt yang mentransformasikan matriks dengan cara yang selalu valid, tetapi sangat berguna untuk matriks yang kita dapatkan di sini.

Kompilasi dengan ghc -O2 -threaded -fllvm -feager-blackholing -o <name> <name>.hs. Untuk menjalankan dengan parallelisation, memberikan runtime parameter seperti ini: ./<name> +RTS -N. Masukan dari stdin dengan daftar yang dipisahkan koma bersarang dalam tanda kurung seperti [[1,2],[3,4]]pada contoh terakhir (baris baru diizinkan di mana-mana).

Sievers Kristen
sumber
1
Saya bisa mendapatkan peningkatan kecepatan 20-25% dengan menghubungkannya Data.Vector. Perubahan diluar yang berubah jenis fungsi: import qualified Data.Vector as V, x (V.zipWith(-) p v) vs (-m) c' ), p (v:vs) = x (foldl (V.zipWith (+)) v vs) (map (V.map (2*)) vs) 1 11,main = getContents >>= print . p . map V.fromList . read
Angs
1
@ Terima kasih banyak! Saya tidak benar-benar merasa ingin melihat tipe data yang lebih cocok. Sungguh menakjubkan betapa hal-hal kecil harus berubah (juga harus digunakan V.product). Itu hanya memberi saya ~ 10%. Mengubah kode sehingga vektor hanya berisi Ints. Tidak apa-apa karena hanya ditambahkan, angka besar datang dari perkalian. Lalu ~ 20%. Saya telah mencoba perubahan yang sama dengan kode lama, tetapi pada saat itu memperlambatnya. Saya mencoba lagi karena memungkinkan untuk menggunakan vektor tanpa kotak , yang banyak membantu!
Christian Sievers
1
@ christian-sievers glab aku bisa membantu. Berikut ini optimasi lain berdasarkan keberuntungan yang saya temukan: x p _ m _ = m * (sum $ V.foldM' (\a b -> if b==0 then Nothing else Just $ a*fromIntegral b) 1 p)- produk sebagai lipatan monadik di mana 0 adalah kasus khusus. Tampaknya bermanfaat lebih sering daripada tidak.
Angs
1
@Angs Hebat! Saya mengubahnya menjadi bentuk yang tidak perlu Transversable(saya melihat Anda tidak mengubah makan productsebelumnya bukan kesalahan ...) untuk ghc dari misalnya Debian stable. Itu menggunakan bentuk input, tapi itu tampaknya baik-baik saja: kami tidak mengandalkan itu, hanya mengoptimalkan untuk itu. Membuat pengaturan waktu jauh lebih menarik: matriks acak 30x30 saya sedikit lebih cepat dari 29x29, tetapi 31x31 membutuhkan waktu 4x. - INLINE itu sepertinya tidak berhasil untuk saya. AFAIK diabaikan untuk fungsi rekursif.
Christian Sievers
1
@ christian-sievers Ya, saya baru saja akan mengatakan sesuatu tentang itu product tetapi lupa. Tampaknya hanya panjang yang memiliki nol p, jadi untuk panjang ganjil kita harus menggunakan produk reguler alih-alih korsleting untuk mendapatkan yang terbaik dari kedua dunia.
Angs
4

Karat + extprim

Ryser langsung dengan implementasi kode Gray ini membutuhkan waktu sekitar 65 90 detik untuk menjalankan n = 31 pada laptop saya. Saya membayangkan mesin Anda akan sampai di sana di bawah 60-an. Saya menggunakan extprim 1.1.1 untuk i128.

Saya tidak pernah menggunakan Rust dan tidak tahu apa yang saya lakukan. Tidak ada opsi kompiler selain apa pun yang cargo build --releasedilakukan. Komentar / saran / optimisasi dihargai.

Doa identik dengan program Dennis.

use std::env;
use std::thread;
use std::sync::Arc;
use std::sync::mpsc;

extern crate extprim;
use extprim::i128::i128;

static THREADS : i64 = 8; // keep this a power of 2.

fn main() {
  // Read command line args for the matrix, specified like
  // "++- --- -+-" for [[1, 1, -1], [-1, -1, -1], [-1, 1, -1]].
  let mut args = env::args();
  args.next();

  let mat : Arc<Vec<Vec<i64>>> = Arc::new(args.map( |ss|
    ss.trim().bytes().map( |cc| if cc == b'+' {1} else {-1}).collect()
  ).collect());

  // Figure how many iterations each thread has to do.
  let size = 2i64.pow(mat.len() as u32);
  let slice_size = size / THREADS; // Assumes divisibility.

  let mut accumulator : i128;
  if slice_size >= 4 { // permanent() requires 4 divides slice_size
    let (tx, rx) = mpsc::channel();

    // Launch threads.
    for ii in 0..THREADS {
      let mat = mat.clone();
      let tx = tx.clone();
      thread::spawn(move ||
        tx.send(permanent(&mat, ii * slice_size, (ii+1) * slice_size))
      );
    }

    // Accumulate results.
    accumulator = extprim::i128::ZERO;
    for _ in 0..THREADS {
      accumulator += rx.recv().unwrap();
    }
  }
  else { // Small matrix, don't bother threading.
    accumulator = permanent(&mat, 0, size);
  }
  println!("{}", accumulator);
}

fn permanent(mat: &Vec<Vec<i64>>, start: i64, end: i64) -> i128 {
  let size = mat.len();
  let sentinel = std::i64::MAX / size as i64;

  let mut bits : Vec<bool> = Vec::with_capacity(size);
  let mut sums : Vec<i64> = Vec::with_capacity(size);

  // Initialize gray code bits.
  let gray_number = start ^ (start / 2);

  for row in 0..size {
    bits.push((gray_number >> row) % 2 == 1);
    sums.push(0);
  }

  // Initialize column sums
  for row in 0..size {
    if bits[row] {
      for column in 0..size {
        sums[column] += mat[row][column];
      }
    }
  }

  // Do first two iterations with initial sums
  let mut total = product(&sums, sentinel);
  for column in 0..size {
    sums[column] += mat[0][column];
  }
  bits[0] = true;

  total -= product(&sums, sentinel);

  // Do rest of iterations updating gray code bits incrementally
  let mut gray_bit : usize;
  let mut idx = start + 2;
  while idx < end {
    gray_bit = idx.trailing_zeros() as usize;

    if bits[gray_bit] {
      for column in 0..size {
        sums[column] -= mat[gray_bit][column];
      }
      bits[gray_bit] = false;
    }
    else {
      for column in 0..size {
        sums[column] += mat[gray_bit][column];
      }
      bits[gray_bit] = true;
    }

    total += product(&sums, sentinel);

    if bits[0] {
      for column in 0..size {
        sums[column] -= mat[0][column];
      }
      bits[0] = false;
    }
    else {
      for column in 0..size {
        sums[column] += mat[0][column];
      }
      bits[0] = true;
    }

    total -= product(&sums, sentinel);
    idx += 2;
  }
  return if size % 2 == 0 {total} else {-total};
}

#[inline]
fn product(sums : &Vec<i64>, sentinel : i64) -> i128 {
  let mut ret : Option<i128> = None;
  let mut tally = sums[0];
  for ii in 1..sums.len() {
    if tally.abs() >= sentinel {
      ret = Some(ret.map_or(i128::new(tally), |n| n * i128::new(tally)));
      tally = sums[ii];
    }
    else {
      tally *= sums[ii];
    }
  }
  if ret.is_none() {
    return i128::new(tally);
  }
  return ret.unwrap() * i128::new(tally);
}
ezrast
sumber
Bisakah Anda memberikan copy dan paste baris perintah untuk menginstal extprim dan mengkompilasi kode.
Outputnya terlihat seperti "i128! (- 2)" di mana -2 adalah jawaban yang benar. Apakah ini diharapkan dan dapatkah Anda mengubahnya hanya untuk menghasilkan permanen?
1
@Lembik: Output harus diperbaiki sekarang. Sepertinya Anda sudah tahu kompilasi, tapi saya melemparkannya di Git sehingga Anda bisa melakukannya git clone https://gitlab.com/ezrast/permanent.git; cd permanent; cargo build --releasejika Anda ingin memastikan memiliki setup yang sama dengan saya. Cargo akan menangani ketergantungan. Biner masuk target/release.
ezrast
Sayangnya ini memberikan jawaban yang salah untuk n = 29. bpaste.net/show/99d6e826d968
1
@Lembik gah, maaf, nilai menengah meluap lebih awal dari yang saya kira. Sudah diperbaiki, meskipun programnya jauh lebih lambat sekarang.
ezrast
3

Mathematica, n ≈ 20

p[m_] := Last[Fold[Take[ListConvolve[##, {1, -1}, 0], 2^Length[m]]&,
  Table[If[IntegerQ[Log2[k]], m[[j, Log2[k] + 1]], 0], {j, n}, {k, 0, 2^Length[m] - 1}]]]

Menggunakan Timingperintah, 20x20 matriks membutuhkan sekitar 48 detik di sistem saya. Ini tidak seefisien yang lain karena bergantung pada fakta bahwa permanen dapat ditemukan sebagai koefisien produk polimomial dari setiap baris matriks. Penggandaan polinomial yang efisien dilakukan dengan membuat daftar koefisien dan melakukan konvolusi menggunakan ListConvolve. Ini membutuhkan waktu O (2 n n 2 ) dengan asumsi konvolusi dilakukan menggunakan Fast Fourier transform atau sejenisnya yang membutuhkan waktu O ( n log n ).

mil
sumber
3

Python 2, n = 22 [Referensi]

Ini adalah implementasi 'referensi' yang saya bagikan dengan Lembik kemarin, ia gagal membuatnya n=23beberapa detik di mesinnya, di komputer saya itu melakukannya dalam waktu sekitar 52 detik. Untuk mencapai kecepatan ini, Anda perlu menjalankan ini melalui PyPy.

Fungsi pertama menghitung permanen yang mirip dengan bagaimana determinan dapat dihitung, dengan memeriksa setiap submatrix sampai Anda dibiarkan dengan 2x2 yang Anda dapat menerapkan aturan dasar. Ini sangat lambat .

Fungsi kedua adalah yang mengimplementasikan fungsi Ryser (persamaan kedua yang tercantum di Wikipedia). Set Spada dasarnya adalah powerset angka {1,...,n}(variabel s_listdalam kode).

from random import *
from time import time
from itertools import*

def perm(a): # naive method, recurses over submatrices, slow 
    if len(a) == 1:
        return a[0][0]
    elif len(a) == 2:
        return a[0][0]*a[1][1]+a[1][0]*a[0][1]
    else:
        tsum = 0
        for i in xrange(len(a)):
            transposed = [zip(*a)[j] for j in xrange(len(a)) if j != i]
            tsum += a[0][i] * perm(zip(*transposed)[1:])
        return tsum

def perm_ryser(a): # Ryser's formula, using matrix entries
    maxn = len(a)
    n_list = range(1,maxn+1)
    s_list = chain.from_iterable(combinations(n_list,i) for i in range(maxn+1))
    total = 0
    for st in s_list:
        stotal = (-1)**len(st)
        for i in xrange(maxn):
            stotal *= sum(a[i][j-1] for j in st)
        total += stotal
    return total*((-1)**maxn)


def genmatrix(d):
    mat = []
    for x in xrange(d):
        row = []
        for y in xrange(d):
            row.append([-1,1][randrange(0,2)])
        mat.append(row)
    return mat

def main():
    for i in xrange(1,24):
        k = genmatrix(i)
        print 'Matrix: (%dx%d)'%(i,i)
        print '\n'.join('['+', '.join(`j`.rjust(2) for j in a)+']' for a in k)
        print 'Permanent:',
        t = time()
        p = perm_ryser(k)
        print p,'(took',time()-t,'seconds)'

if __name__ == '__main__':
    main()
Kade
sumber
Saya pikir Anda harus mengulangi deskripsi "mirip dengan bagaimana penentu akan dihitung". Ini tidak seperti yang metode untuk penentu lambat untuk permanents, tapi satu metode lambat untuk determinan bekerja sama (dan sebagai perlahan) untuk permanents.
Christian Sievers
1
@ChristianSievers Poin bagus, saya sudah mengubahnya.
Kade
2

RPython 5.4.1, n ≈ 32 (37 detik)

from rpython.rlib.rtime import time
from rpython.rlib.rarithmetic import r_int, r_uint
from rpython.rlib.rrandom import Random
from rpython.rlib.rposix import pipe, close, read, write, fork, waitpid
from rpython.rlib.rbigint import rbigint

from math import log, ceil
from struct import pack

bitsize = len(pack('l', 1)) * 8 - 1

bitcounts = bytearray([0])
for i in range(16):
  b = bytearray([j+1 for j in bitcounts])
  bitcounts += b


def bitcount(n):
  bits = 0
  while n:
    bits += bitcounts[n & 65535]
    n >>= 16
  return bits


def main(argv):
  if len(argv) < 2:
    write(2, 'Usage: %s NUM_THREADS [N]'%argv[0])
    return 1
  threads = int(argv[1])

  if len(argv) > 2:
    n = int(argv[2])
    rnd = Random(r_uint(time()*1000))
    m = []
    for i in range(n):
      row = []
      for j in range(n):
        row.append(1 - r_int(rnd.genrand32() & 2))
      m.append(row)
  else:
    m = []
    strm = ""
    while True:
      buf = read(0, 4096)
      if len(buf) == 0:
        break
      strm += buf
    rows = strm.split("\n")
    for row in rows:
      r = []
      for val in row.split(' '):
        r.append(int(val))
      m.append(r)
    n = len(m)

  a = []
  for row in m:
    val = 0
    for v in row:
      val = (val << 1) | -(v >> 1)
    a.append(val)

  batches = int(ceil(n * log(n) / (bitsize * log(2))))

  pids = []
  handles = []
  total = rbigint.fromint(0)
  for i in range(threads):
    r, w = pipe()
    pid = fork()
    if pid:
      close(w)
      pids.append(pid)
      handles.append(r)
    else:
      close(r)
      total = run(n, a, i, threads, batches)
      write(w, total.str())
      close(w)
      return 0

  for pid in pids:
    waitpid(pid, 0)

  for handle in handles:
    strval = read(handle, 256)
    total = total.add(rbigint.fromdecimalstr(strval))
    close(handle)

  print total.rshift(n-1).str()

  return 0


def run(n, a, mynum, threads, batches):
  start = (1 << n-1) * mynum / threads
  end = (1 << n-1) * (mynum+1) / threads

  dtotal = rbigint.fromint(0)
  for delta in range(start, end):
    pdelta = rbigint.fromint(1 - ((bitcount(delta) & 1) << 1))
    for i in range(batches):
      pbatch = 1
      for j in range(i, n, batches):
        pbatch *= n - (bitcount(delta ^ a[j]) << 1)
      pdelta = pdelta.int_mul(pbatch)
    dtotal = dtotal.add(pdelta)

  return dtotal


def target(*args):
  return main

Untuk mengkompilasi, unduh sumber PyPy terbaru, dan jalankan yang berikut:

pypy /path/to/pypy-src/rpython/bin/rpython matrix-permanent.py

Eksekusi yang dihasilkan akan diberi nama matrix-permanent-catau serupa di direktori kerja saat ini.

Pada PyPy 5.0, primitif threading RPython jauh lebih primitif daripada dulu. Utas yang baru lahir membutuhkan GIL, yang lebih atau kurang berguna untuk komputasi paralel. Saya telah menggunakan forksebagai gantinya, jadi mungkin tidak berfungsi seperti yang diharapkan pada Windows, meskipun saya belum diuji gagal untuk mengkompilasi ( unresolved external symbol _fork).

Yang dapat dieksekusi menerima hingga dua parameter baris perintah. Yang pertama adalah jumlah utas, parameter opsional kedua adalah n. Jika disediakan, matriks acak akan dihasilkan, jika tidak maka akan dibaca dari stdin. Setiap baris harus dipisahkan baris baru (tanpa baris baru jejak), dan setiap ruang nilai dipisahkan. Input contoh ketiga akan diberikan sebagai:

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 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 -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 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 -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 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 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 -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 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 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 -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 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 -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

Contoh Penggunaan

$ time ./matrix-permanent-c 8 30
8395059644858368

real    0m8.582s
user    1m8.656s
sys     0m0.000s

metode

Saya telah menggunakan rumus Balasubramanian-Bax / Franklin-Glynn , dengan kompleksitas runtime O (2 n n) . Namun, alih-alih mengulangi δ dalam urutan kode abu-abu, saya malah mengganti multiplikasi vektor-baris dengan operasi xor tunggal (pemetaan (1, -1) → (0, 1)). Jumlah vektor juga dapat ditemukan dalam satu operasi, dengan mengambil n minus dua kali jumlah pop.

primo
sumber
Sayangnya kode ini memberikan jawaban yang salah untuk bpaste.net/show/8690251167e7
@Lembik diperbarui. Karena penasaran, dapatkah Anda memberi tahu saya hasil kode berikut? bpaste.net/show/76ec65e1b533
primo
Ini memberi "True 18446744073709551615" Saya menambahkan hasil untuk kode Anda yang sangat bagus sekarang juga.
@Lembik terima kasih. Saya sudah membagi perkalian agar tidak meluap 63-bit. Apakah hasil yang terdaftar diambil dengan 8 utas? Apakah 2 atau 4 membuat perbedaan? Jika 30 selesai dalam 25, sepertinya 31 harus di bawah satu menit.
Primo
-1

Racket 84 byte

Fungsi sederhana berikut berfungsi untuk matriks yang lebih kecil tetapi tergantung pada mesin saya untuk matriks yang lebih besar:

(for/sum((p(permutations(range(length l)))))(for/product((k l)(c p))(list-ref k c)))

Tidak Disatukan:

(define (f ll) 
  (for/sum ((p (permutations (range (length ll))))) 
    (for/product ((l ll)(c p)) 
      (list-ref l c))))

Kode dapat dengan mudah dimodifikasi untuk jumlah baris dan kolom yang tidak sama.

Pengujian:

(f '[[ 1 -1 -1  1]
     [-1 -1 -1  1]
     [-1  1 -1  1]
     [ 1 -1 -1  1]])

(f '[[ 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  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  1  1]])

Keluaran:

-4
192

Seperti yang saya sebutkan di atas, itu tergantung pada pengujian berikut:

(f '[[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 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 -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 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 -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 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 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 -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 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 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 -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 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 -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]])
juga
sumber
5
Apakah jawaban ini lebih baik dalam versi codegolf daripada versi kecepatan pertanyaan ini?