17

次のことを行う簡単なコードがあります。

F+-1 のエントリを持つすべての可能な長さ n リストを反復処理します。2nそれぞれについて、+-1 エントリを使用してすべての可能な長さリストを繰り返し処理しSます。ここで、$S$ の前半は単に後半のコピーです。このコードは、 lengthFの各サブリストを使用しての内積を計算します。F、S ごとに、最初の非ゼロ内積まで、ゼロである内積をカウントします。Sn

これがコードです。

#!/usr/bin/python

from __future__ import division
import itertools
import operator
import math

n=14
m=n+1
def innerproduct(A, B):
    assert (len(A) == len(B))
    s = 0 
    for k in xrange(0,n):
        s+=A[k]*B[k]
    return s

leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n):
    S1 = S + S
    for F in itertools.product([-1,1], repeat = n):
        i = 0
        while (i<m):
            ip = innerproduct(F, S1[i:i+n])
            if (ip == 0):
                leadingzerocounts[i] +=1
                i+=1
            else:
                break

print leadingzerocounts

の正しい出力n=14は

[56229888, 23557248, 9903104, 4160640, 1758240, 755392, 344800, 172320, 101312, 75776, 65696, 61216, 59200, 59200, 59200]

pypy を使用すると、n = 14 で 1 分 18 秒かかります。残念ながら、16,18,20,22,24,26 で実行したいと思います。numba や cython を使用してもかまいませんが、可能であれば python に近づきたいです。

これをスピードアップするための助けは大歓迎です。

ここで最速のソリューションを記録します。（更新された回答を見逃した場合はお知らせください。）

  • n = 22 at 9m35.081s by Eisenstat (C)
  • n = 18 at 1m16.344s by Eisenstat (pypy)
  • n = 18 at 2m54.998s by Tupteq (pypy)
  • n = 14 at 26s by Neil (numpy)
  • n - kslote1 (pypy) による 11m59.192s の 14
4

5 に答える 5

22

この新しいコードは、問題の周期対称性を利用することで、さらに桁違いに高速化されます。この Python バージョンは、Duval のアルゴリズムを使用してネックレスを列挙します。C バージョンはブルート フォースを使用します。両方とも、以下に説明する高速化が組み込まれています。私のマシンでは、C バージョンは 100 秒で n = 20 を解きます! エンベロープの計算では、単一のコアで 1 週間実行した場合、n = 26 になる可能性があり、以下に示すように、並列処理に適していることが示唆されています。

import itertools


def necklaces_with_multiplicity(n):
    assert isinstance(n, int)
    assert n > 0
    w = [1] * n
    i = 1
    while True:
        if n % i == 0:
            s = sum(w)
            if s > 0:
                yield (tuple(w), i * 2)
            elif s == 0:
                yield (tuple(w), i)
        i = n - 1
        while w[i] == -1:
            if i == 0:
                return
            i -= 1
        w[i] = -1
        i += 1
        for j in range(n - i):
            w[i + j] = w[j]


def leading_zero_counts(n):
    assert isinstance(n, int)
    assert n > 0
    assert n % 2 == 0
    counts = [0] * n
    necklaces = list(necklaces_with_multiplicity(n))
    for combo in itertools.combinations(range(n - 1), n // 2):
        for v, multiplicity in necklaces:
            w = list(v)
            for j in combo:
                w[j] *= -1
            for i in range(n):
                counts[i] += multiplicity * 2
                product = 0
                for j in range(n):
                    product += v[j - (i + 1)] * w[j]
                if product != 0:
                    break
    return counts


if __name__ == '__main__':
    print(leading_zero_counts(12))

C バージョン:

#include <stdio.h>

enum {
  N = 14
};

struct Necklace {
  unsigned int v;
  int multiplicity;
};

static struct Necklace g_necklace[1 << (N - 1)];
static int g_necklace_count;

static void initialize_necklace(void) {
  g_necklace_count = 0;
  for (unsigned int v = 0; v < (1U << (N - 1)); v++) {
    int multiplicity;
    unsigned int w = v;
    for (multiplicity = 2; multiplicity < 2 * N; multiplicity += 2) {
      w = ((w & 1) << (N - 1)) | (w >> 1);
      unsigned int x = w ^ ((1U << N) - 1);
      if (w < v || x < v) goto nope;
      if (w == v || x == v) break;
    }
    g_necklace[g_necklace_count].v = v;
    g_necklace[g_necklace_count].multiplicity = multiplicity;
    g_necklace_count++;
   nope:
    ;
  }
}

int main(void) {
  initialize_necklace();
  long long leading_zero_count[N + 1];
  for (int i = 0; i < N + 1; i++) leading_zero_count[i] = 0;
  for (unsigned int v_xor_w = 0; v_xor_w < (1U << (N - 1)); v_xor_w++) {
    if (__builtin_popcount(v_xor_w) != N / 2) continue;
    for (int k = 0; k < g_necklace_count; k++) {
      unsigned int v = g_necklace[k].v;
      unsigned int w = v ^ v_xor_w;
      for (int i = 0; i < N + 1; i++) {
        leading_zero_count[i] += g_necklace[k].multiplicity;
        w = ((w & 1) << (N - 1)) | (w >> 1);
        if (__builtin_popcount(v ^ w) != N / 2) break;
      }
    }
  }
  for (int i = 0; i < N + 1; i++) {
    printf(" %lld", 2 * leading_zero_count[i]);
  }
  putchar('\n');
  return 0;
}

符号対称性 (4x) を活用し、最初の内積テスト (漸近的に O(sqrt(n))x) に合格したベクトルのみを反復処理することで、少し高速化できます。

import itertools


n = 10
m = n + 1


def innerproduct(A, B):
    s = 0
    for k in range(n):
        s += A[k] * B[k]
    return s


leadingzerocounts = [0] * m
for S in itertools.product([-1, 1], repeat=n - 1):
    S1 = S + (1,)
    S1S1 = S1 * 2
    for C in itertools.combinations(range(n - 1), n // 2):
        F = list(S1)
        for i in C:
            F[i] *= -1
        leadingzerocounts[0] += 4
        for i in range(1, m):
            if innerproduct(F, S1S1[i:i + n]):
                break
            leadingzerocounts[i] += 4
print(leadingzerocounts)

C バージョン。PyPy に比べてどれだけのパフォーマンスが失われているかを感じてください (PyPy の 16 は、C の 18 にほぼ相当します)。

#include <stdio.h>

enum {
  HALFN = 9,
  N = 2 * HALFN
};

int main(void) {
  long long lzc[N + 1];
  for (int i = 0; i < N + 1; i++) lzc[i] = 0;
  unsigned int xor = 1 << (N - 1);
  while (xor-- > 0) {
    if (__builtin_popcount(xor) != HALFN) continue;
    unsigned int s = 1 << (N - 1);
    while (s-- > 0) {
      lzc[0]++;
      unsigned int f = xor ^ s;
      for (int i = 1; i < N + 1; i++) {
        f = ((f & 1) << (N - 1)) | (f >> 1);
        if (__builtin_popcount(f ^ s) != HALFN) break;
        lzc[i]++;
      }
    }
  }
  for (int i = 0; i < N + 1; i++) printf(" %lld", 4 * lzc[i]);
  putchar('\n');
  return 0;
}

このアルゴリズムは、 のすべての値を累積しているだけなので、恥ずかしいほど並列ですxor。C バージョンでは、封筒の裏に計算すると、計算には数千時間の CPU 時間で十分であることが示唆されていますn = 26。これは、EC2 の現在のレートで数百ドルになります。間違いなくいくつかの最適化 (ベクトル化など) を行う必要がありますが、このような 1 回限りの場合、プログラマーの努力がどれだけ価値があるかわかりません。

于 2014-11-19T19:24:32.103 に答える
2

私はこれをスピードアップしようとしましたが、ひどく失敗しました:(しかし、コードを送信しています。何とか高速ですが、のような値には十分ではありませんn=24.

私の仮定

リストは値で構成されているため、リストの代わりに数値を使用することにしました。各ビットは可能な値の 1 つを表します。ビットが設定されている場合、これは を意味1し、ゼロになっている場合は を意味し-1ます。乗算の唯一の可能な結果{-1, 1}は1orであるため、乗算の代わりに-1ビット単位を使用しました。XORまた、対称性があることにも気付きました。そのため、可能なリストのサブセット (4 分の 1) をチェックし、結果を 4 倍するだけで済みます (David は彼の回答でこれを説明しました)。

最後に、計算の必要をなくすために、考えられる操作の結果を表にまとめました。大量のメモリを必要としますが、気にする必要はありません (n=24約 150MB だったからです)。

そして、@David Eisenstat が質問に答えました :) それで、私は彼のコードを取得し、ビットベースに変更しました。約2〜3倍高速です（n=16Davidのソリューションの〜90秒と比較して、〜30秒かかりました）が、結果を得るにはまだ十分ではないと思いますn=26。

import itertools

n = 16
m = n + 1
mask = (2 ** n) - 1

# Create table of sum results (replaces innerproduct())
tab = []
for a in range(2 ** n):
    s = 0
    for k in range(n):
        s += -1 if a & 1 else 1
        a >>= 1
    tab.append(s)

# Create combination bit masks for combinations
comb = []
for C in itertools.combinations(range(n - 1), n // 2):
    xor = 0
    for i in C:
       xor |= (1 << i)
    comb.append(xor)

leadingzerocounts = [0] * m
for S in xrange(2 ** (n-1)):
    S1 = S + (1 << (n-1))
    S1S1 = S1 + (S1 << n)

    for xor in comb:
        F = S1 ^ xor

        leadingzerocounts[0] += 4
        for i in range(1, m):
            if tab[F ^ ((S1S1 >> i) & mask)]:
                break
            leadingzerocounts[i] += 4

print(leadingzerocounts)

結論

私は何か素晴らしいものを発明したと思っており、ビットのこのすべての混乱が大きなスピードアップをもたらすことを望んでいましたが、ブーストは残念ながら小さかったです:(

その理由は、Python が演算子を使用する方法にあると思います。単一のアセンブラ コマンドで実行できる場合でも、算術 (または論理) 演算ごとに関数を呼び出します (pypy演算をそのレベルまで単純化できることを望んでいましたが、そうではありませんでした。 t)。したがって、おそらくこのビット操作ソリューションで C (または ASM) を使用した場合、優れたパフォーマンスが得られるでしょう (おそらく に到達する可能性がありますn=24)。

于 2014-11-20T13:27:23.583 に答える
2

これを NumPy 配列に転送して、この質問から借りてきました: itertools product speed up

これは私が得たものです（ここでさらにスピードアップがあるかもしれません）：

def find_leading_zeros(n):
    if n % 2:
        return numpy.zeros(n)
    m = n+1
    leading_zero_counts = numpy.zeros(m)
    product_list = [-1, 1]
    repeat = n
    s = (numpy.array(product_list)[numpy.rollaxis(numpy.indices((len(product_list),) * repeat),
                                                  0, repeat + 1).reshape(-1, repeat)]).astype('int8')
    i = 0
    size = s.shape[0] / 2
    products = numpy.zeros((size, size), dtype=bool)
    while i < m:
        products += (numpy.tensordot(s[0:size, 0:size],
                                     numpy.roll(s, i, axis=1)[0:size, 0:size],
                                     axes=(-1,-1))).astype('bool')
        leading_zero_counts[i] = (products.size - numpy.sum(products)) * 4
        i += 1

    return leading_zero_counts

n=14 で実行すると、次のようになります。

>>> find_leading_zeros(14)
array([ 56229888.,  23557248.,   9903104.,   4160640.,   1758240.,
        755392.,    344800.,    172320.,    101312.,     75776.,
        65696.,     61216.,     59200.,     59200.,     59200.])

だから、すべてがよさそうだ。速度に関して：

>>> timeit.timeit("find_leading_zeros_old(10)", number=10)
28.775046825408936
>>> timeit.timeit("find_leading_zeros(10)", number=10)
2.236745834350586

あなたの考えを見てください。

編集：

元のバージョンでは N=14 で 2074MB のメモリを使用していたので、連結配列を削除してnumpy.roll代わりに使用しました。また、ブール配列を使用するようにデータ型を変更すると、n=14 の場合、メモリが 277MB に減少します。

時間的には、編集は再び少し速くなります:

>>> timeit.timeit("find_leading_zeros(10)", number=10)
1.3816070556640625

EDIT2：

わかりましたので、デビッドが指摘したように対称性を追加して、これを再度減らします。現在、213MBを使用しています。以前の編集と比較した比較タイミング:

>>> timeit.timeit("find_leading_zeros(10)", number=10)
0.35357093811035156

「純粋なpython」にとって悪くない私のMacブックで14秒でn = 14のケースを実行できるようになりました。

于 2014-11-19T18:47:14.897 に答える
0

私の意見では、パフォーマンスを向上させる良い方法は、python ビルトインを使用することです。

最初に map を使用してエントリの積を計算します。

>>> a =[1,2,3]
>>> b = [4,5,6]
>>>map(lambda x,y : x*y, a , b)
[4, 10, 18]

次にreduceを使用して合計を計算します。

>>> reduce(lambda v,w: v+w, map(lambda x,y :x*y, a, b))
32

したがって、関数は次のようになります

def innerproduct(A, B):
    assert (len(A) == len(B))
    return reduce(lambda v,w: v+w, map(lambda x,y :x*y, A, B))

次に、これらの「for ループ」をすべて取り除き、ジェネレーターに置き換えて、StopIteration をキャッチします。

#!/usr/bin/python

from __future__ import division
import itertools
import operator
import math

n=14
m=n+1
def innerproduct(A, B):
    assert (len(A) == len(B))
    return reduce(lambda v,w: v+w, map(lambda x,y :x*y, A, B))


leadingzerocounts = [0]*m

S_gen = itertools.product([-1,1], repeat = n)

try:
    while(True):
       S = S_gen.next()
       S1 = S + S
       F_gen = itertools.product([-1,1], repeat = n)
       try:
           while(True):
               F = F_gen.next()
               for i in xrange(m):
                   ip = innerproduct(F, S1[i:i+n])
                   if (ip == 0):
                       leadingzerocounts[i] +=1
                       i+=1
                   else:
                      break
       except StopIteration:
           pass

except StopIteration as e:
    print e

print leadingzerocounts

n を小さくすると速度が向上することを確認しましたが、私のジャロピーには、バージョンや n=14 の元のコードを計算するための馬力がありませんでした。これをさらに高速化する方法は、次の行をメモ化することです。

    F_gen = itertools.product([-1,1], repeat = n)
于 2014-11-20T16:49:17.397 に答える