コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2014年1月6日 >>> 2014年1月6日
link もっと後

2014年1月6日

Scalaでバイナリ解析

ScalaにてBooleanのリストをビット列に見立てて、任意のビット数を上位ビット〜下位ビットにOR演算し、Intのリストとして返すという処理をやりたいのです。

ビット列 (0, 1, 0, 0, 1, 1, 0, 0, 0) に対して、(1ビット取る, 3ビット取る, 5ビット取る) という処理を行って、結果として (0, 4, 24) が返る、そんなイメージです。

いきなり作るとコケたときショックがデカいので、まずは単純化して必ず8ビットずつ取る処理で考えてみます。入力、出力は下記の通りです。

やりたいこと

(入力)
List(
  true, false, false, true, true, false, true, false,
  true, true, true, false, true, false, true, true
)

(出力)
List(154, 235)

やりたいことはシンプルなのですが、あまりスマートな書き方が思いつきません。

foreachで書く

まず思いついたのがforeachです。

foreachの場合

val a = List(
  true, false, false, true, true, false, true, false,
  true, true, true, false, true, false, true, true
)
var acc = 0
var p = 0
var b: List[Int] = List()

a.foreach { it =>
  acc <<= 1
  if (it) acc |= 1
  p += 1

  if (p >= 8) {
    b = b :+ acc
    acc = 0
    p = 0
  }
}

println(b)

動くには動きますが、8ビット読むごとにリストのコピー処理が走るという、富豪プログラミングの限界に挑戦しているようなプログラムです。

map関数で書く

次に思い浮かぶのはmap関数ですが、基本的にforeachと変わらないように思います。変換前と変換後が1:1対応するなら簡単に書けますが、n:1対応させると一時変数の隠蔽が必要になり面倒です。

mapの場合

object BooleanToByte {
  def apply(): (Boolean => Option[Int]) = {
    val o = new BooleanToByte()
    o.mapper
  }
}

class BooleanToByte() {
  private var v = 0
  private var p = 0

  def mapper(b: Boolean): Option[Int] = {
    v <<= 1
    if (b) v |= 1
    p += 1

    if (p >= 8) {
      val result = Some(v)
      v = 0
      p = 0
      result
    } else {
      None
    }
  }
}


val a = List(
  true, false, false, true, true, false, true, false,
  true, true, true, false, true, false, true, true
)

val b = a.map(BooleanToByte()).flatten

println(b)

ひとまず見た目をa.map(f) の形に近づけるためだけに頑張りました。コードがダサいというか、Scala初心者感が丸出しというか。もっとスマートに書けるはずですが、今の私のレベルではなんとも…。

ちなみに最後のflattenはSomeオブジェクトを展開して中身の値を取り出すために使っています。ついでにNoneも消してくれるナイスな奴です。

iteratorはどうか?

最後にリストの要素を列挙するもう一つの手段、イテレータが思いつきました。foreachと異なりn:1対応に融通が利きます。いや…融通が利くというより、自由に記述できてしまうが故にn:1だろうとn:mだろうと、もはや何でもアリと言った方が正しいですね。

iteratorの場合

val a = List(
  true, false, false, true, true, false, true, false,
  true, true, true, false, true, false, true, true
)
val it = a.iterator
var b: List[Int] = List()

while (it.hasNext) {
  var acc = 0
  var p = 0

  while (p < 8) {
    acc <<= 1
    if (it.next()) acc |= 1

    p += 1
  }
  b = b :+ acc
}

println(b)

先ほどのforeachやmapのような、無理やり頑張った感はなくなったように思いますが、今度は変換元に8未満の要素数が残っているとき、例外がスローされてしまうという欠点もあります。

これがforeachを差し置いてベストか?と言われると、何とも言い難い、難しいですね。

編集者:すずき(2014/01/07 08:56)

コメント一覧

  • よしださん(2014/01/08 01:48)
    ふむふむ。。
    私はRubyで考えてみます!
  • すずきさん(2014/01/11 14:05)
    (いけじからの Facebook コメント転記)
    val b = List(false, true, false, false, true, true, false, false, false)
    val c = List(1,3,5)
    に対して、case ((i,o),n)=>(i.drop(n),i.take(n)::o)._2.reverse.map{bs=>bs.map{b=>if(b) 1 else 0}.fold(0){(i,b)=>i*2+b}}.toList\nとかやりたいんですが、色々汚ないですね。
  • すずきさん(2014/01/11 14:06)
    (Facebook コメント転記)
    やりたいことはなんとなくわかりますが、かなりゴチャゴチャしますね。
    やはりイテレータでがんばるか。
  • すずきさん(2014/01/11 14:06)
    (いけじからの Facebook コメント転記)
    整理してこんな感じです。
    https://gist.github.com/anonymous/9d3cf430f76293b8b36c
  • すずきさん(2014/01/11 14:07)
    (Facebook コメント転記)
    print入れまくってやっと意味がわかりました。
    foldLeftってタプル返せるんですね。応用が利きそうです。
  • すずきさん(2014/01/11 14:31)
    >よしださん
    どの言語でも、速くて読みやすい、を目指すと難しそうですね。
  • IKeJIさん(2014/01/11 17:11)
    Rubyで、int,short,longしか出てこないなら、
    pack、unpackだけでできないかな。
open/close この記事にコメントする



link もっと前
2014年1月6日 >>> 2014年1月6日
link もっと後

管理用メニュー

link 記事を新規作成

<2014>
<<<01>>>
---1234
567891011
12131415161718
19202122232425
262728293031-

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事3件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 03/26 03:20