2007-11-28

PythonでHarwell-Boeing matrix

C++のような本気言語ではなく、"バッテリー内蔵言語"であるPythonでHarwell-Boeing matrixのようなシビアな世界のデータ構造を書いたらどのぐらいになるかと試した。

このぐらいになる。


#!/usr/bin/python
# _*_ coding: euc_jp _*_
# Copyright (C) 2007 Ayukawa Hiroshi
from array import array
from itertools import izip, islice
from collections import defaultdict

class Hwmatrix(object):
def __init__(self, rownum_type="I", colnum_type="I", val_type="I"):
self.rowindex = array(rownum_type)
self.colindex = array(colnum_type)
self.val = array(val_type)
self.rowindex.append(0)

if val_type in ("f", "d"):
self.val_type = float
else:
self.val_type = int

def addrow(self, row):
row = dict(row)
cols = row.keys()
cols.sort()
vals = [row[k] for k in cols]
self.colindex.extend(cols)
self.val.extend(vals)
self.rowindex.append(self.rowindex[-1] + len(cols))

def getrow_as_pair(self, n):
rownum = self.rowindex[n]
rowlen = self.rowindex[n+1] - rownum
return islice(izip(self.colindex[rownum:], self.val[rownum:]), rowlen)

def __rmul__(self, vector):
if isinstance(vector, dict):
answer = defaultdict(self.val_type)
for k in vector.keys():
weight = vector[k]
for i, v in self.getrow_as_pair(k):
answer[i] += weight * v
return answer

def test():
"""
1 1 0 0 0
0 1 1 0 0
(0 2 3 0 1) * 0 0 1 1 0 = (0 2 5 3 1)
0 0 0 1 1
0 0 0 0 1
"""
mat = Hwmatrix()
mat.addrow({0:1, 1:1})
mat.addrow({1:1, 2:1})
mat.addrow({2:1, 3:1})
mat.addrow({3:1, 4:1})
mat.addrow({4:1})

print {1:2, 2:3, 4:1} * mat

test()


これはひょっとして実用的に使えたりしないだろうか。
会社ではC++で書いたものを使っていますが、自宅の趣味にはこういうのでもいいかも。

追記---
でも、よく考えると、ベクトルとの積__rmul__での処理なんかで、いちいち内部でPyObjectを作って参照カウンタをごにょごにょやっているんだと想像すると、一気に使う気が失せました。
やはりこういうのはC++じゃないといやだな。