สร้างซีรีส์พจนานุกรมอย่างมีประสิทธิภาพใน Python

อัลกอริทึมที่มีประสิทธิภาพมากดัดแปลงมาจากหนังสือของ Jorg Arndt "Matters Computational"
(บทที่ 7.2 Co-lexicographic order for compositions into exactly k parts)

n = 4
k = 3

x = [0] * n
x[0] = k

while True:
    print(x)
    v = x[-1]
    if (k==v ):
        break
    x[-1] = 0
    j = -2
    while (0==x[j]):
        j -= 1
    x[j] -= 1
    x[j+1] = 1 + v

[3, 0, 0, 0]
[2, 1, 0, 0]
[2, 0, 1, 0]
[2, 0, 0, 1]
[1, 2, 0, 0]
[1, 1, 1, 0]
[1, 1, 0, 1]
[1, 0, 2, 0]
[1, 0, 1, 1]
[1, 0, 0, 2]
[0, 3, 0, 0]
[0, 2, 1, 0]
[0, 2, 0, 1]
[0, 1, 2, 0]
[0, 1, 1, 1]
[0, 1, 0, 2]
[0, 0, 3, 0]
[0, 0, 2, 1]
[0, 0, 1, 2]
[0, 0, 0, 3]

จำนวนการเรียบเรียงและเวลาเป็นวินาทีสำหรับ Python ธรรมดา (บางทีอาร์เรย์ numpy อาจเร็วกว่า) สำหรับ n=100 และ k = 2,3,4,5 (2.8 ghz Cel-1840)

2  5050 0.040000200271606445
3  171700 0.9900014400482178
4  4421275 20.02204465866089
5  91962520 372.03577995300293
I expect time  2 hours for 100/6 generation

เช่นเดียวกับอาร์เรย์ numpy (x = np.zeros((n,), dtype=int)) ให้ผลลัพธ์ แย่ลง - แต่อาจเป็นเพราะฉันไม่รู้วิธีใช้อย่างถูกต้อง

2  5050 0.07999992370605469
3  171700 2.390003204345703
4  4421275 54.74532389640808

โค้ดเนทิฟ (นี่คือ Delphi คอมไพเลอร์ C/C++ อาจเพิ่มประสิทธิภาพได้ดีกว่า) สร้าง 100/6 ใน 21 วินาที

3  171700  0.012
4  4421275  0.125
5  91962520  1.544
6  1609344100 20.748

นอนไม่หลับจนกว่าจะวัดไม่เสร็จ :)

MSVS VC++: 18 วินาที! (การเพิ่มประสิทธิภาพ O2)

5  91962520 1.466
6  1609344100 18.283

100 ล้านตัวแปรต่อวินาที เสียเวลามากในการตรวจสอบเซลล์ว่าง (เนื่องจากอัตราการเติมมีน้อย) ความเร็วที่ Arndt อธิบายนั้นบรรลุถึงอัตราส่วน k/n ที่สูงกว่า และมีค่าประมาณ 300-500 ล้านตัวแปรต่อวินาที:

n=25, k=15 25140840660 60.981  400 millions per second

คำแนะนำของฉัน:

1. เขียนใหม่เป็นตัวสร้างโดยใช้ yield แทนที่จะเป็นลูปที่เชื่อมตัวแปรโกลบอลเข้าด้วยกันในการวนซ้ำแต่ละครั้ง
2. เก็บผลรวมต่อเนื่องแทนการคำนวณผลรวมของชุดย่อยบางส่วนของการแสดงตัวเลขในอาร์เรย์
3. ดำเนินการกับอินสแตนซ์เดียวของการแสดงหมายเลขการทำงานของคุณ แทนที่จะเชื่อมต่อสำเนาของอินสแตนซ์ดังกล่าวกับตัวแปรชั่วคราวในการวนซ้ำแต่ละครั้ง

หมายเหตุ ไม่มีคำสั่งใดที่มีความหมายโดยนัย

ฉันมีทางออกที่ดีกว่าโดยใช้ itertools ดังนี้

from itertools import product
n = 4 #number of elements
s = 3 #sum of elements
r = []
for x in range(n):
    r.append(x)
result = [p for p in product(r, repeat=n) if sum(p) == s]
print(len(result))
print(result)

ฉันกำลังบอกว่าวิธีนี้ดีกว่าเพราะระบบของฉันใช้เวลา 0.1 วินาที ในขณะที่โค้ดที่มี numpy ของคุณใช้เวลา 0.2 วินาที

แต่เท่าที่ n=100 และ s=6 โค้ดนี้ต้องใช้เวลาในการพิจารณาชุดค่าผสมทั้งหมด ฉันคิดว่าจะใช้เวลาหลายวันในการคำนวณผลลัพธ์

ฉันพบวิธีแก้ปัญหาโดยใช้ itertools เช่นกัน (ที่มา: https://bugs.python.org/msg144273 ). รหัสดังต่อไปนี้:

import itertools
import operator

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

int_part = lambda n, k: (tuple(map(c.count, range(k))) for c in combinations_with_replacement(range(k), n))
for item in int_part(3,4): print(item)