circular doubly linked listを使って0/1配列を省メモリ実装
もちろんPythonを使っているので定数倍くらいのディスアドバンテージはありますが。
要素のほとんどが0で、少しだけ1であるようなサイズNの配列を、
素直に普通の配列として実装するとNのオーダーのメモリを消費します。
そこで1の入っている部分だけを双方向リストで実装してメモリが節約しよう、というアルゴリズム。
西尾泰和のブログ: Pythonでcircular doubly linked listの続編。
# -*- coding: cp932 -*-
from circularDoublyLinkedList import DList
# DListを使って巨大な0/1配列をエミュレートする
class Array(DList):
def __init__(self, size):
self.size = size
DList.__init__(self)
def get(self, index):
"index番目の要素の値を返す"
for x in self:
if x.value == index:
return 1
if x.value > index:
return 0
def set(self, index, value):
"index番目の要素の値を設定する"
if value:
self.turnOn(index)
else:
self.turnOff(index)
def turnOn(self, index):
"index番目の要素の値を1にする"
for x in self:
if x.value == index:
# すでに1になっている
return
if x.value > index:
# indexより大きい最小の数の手前に要素を追加
self.addBefore(index, x)
return
# indexより大きい数はない→末尾に追加
self.addTail(index)
def turnOff(self, index):
"index番目の要素の値を0にする"
e = self.find(index)
if e:
self.delete(e)
else:
# そんな要素はない→すでに0だった
pass
def __str__(self):
result = ["0"] * self.size
for x in self:
result[x.value] = "1"
return "[%s]" % "".join(result)
xs = Array(10)
print xs #=> [0000000000]
xs.set(5, 1)
xs.set(3, 1)
xs.set(7, 1)
print xs #=> [0001010100]
xs.set(3, 1)
print DList.__str__(xs) #=> [3, 5, 7]
xs.set(5, 0)
print xs #=> [0001000100]
