複数の部分からなる文字列の作成

Roberto Ierusalimiが、変更不可能な文字列を効果的に組み合わせる方法について説明します。

コードはLuaで記述されているという事実にもかかわらず、このアルゴリズムは文字列を変更できない他の言語に適しています。

プロローグ

Luaでは、結果文字列の「累積」（つまり、s = s..xという形式の本体を持つループ）は、非常にリソースを消費します。 このメモでは、Luaのパーツに文字列を作成する効率的な方法について説明します。

問題

たとえば、ファイルから1行ずつ読み取るなど、行を部分的に構成するとします。 典型的なコードは次のようになります。

-- WARNING: bad code ahead!! local buff = "" while 1 do local line = read() if line == nil then break end buff = buff..line.."\n" end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

無邪気な見た目にもかかわらず、このようなLuaコードは大きなファイルのパフォーマンスを大幅に低下させる可能性があります。たとえば、350 KBのファイルを読み取るのに1分近くかかります。



多くの場合、これは問題ではありません。 細い線の場合、このようなループは正常です。 ファイル全体を読み取るには、「* all」オプションを使用して、ファイル全体を読み取ることができます。 しかし、そのような単純な解決策がない場合もあります。 この場合、唯一の解決策はこの問題に対するより効率的なアルゴリズムです。 ここにそれを示します（アルゴリズム、問題ではありません）。

解決策

アルゴリズムの中心は、大きな行を一番下に格納し、小さな行を一番上に格納するスタックです。 このようなスタックの主な不変条件は、（プログラマーの間で）人気のある「ハノイの塔」に似ています。つまり、スタック内の行を短い行の上に置くことはできません。 新しい行が短い行の上に配置されると、アルゴリズムはそれらを結合します（そしてその場合のみ）。 線の組み合わせにより大きな線が作成され、下の階の隣の線よりも大きくなる場合があります。 これが発生した場合、結果の行と下からの近隣も結合されます。 これらの結合は、ループがより大きな行またはスタックの一番下に達するまでスタックを下っていきます。

 function newBuffer () return {n=0} -- 'n' counts number of elements in the stack end function addString (stack, s) tinsert(stack, s) -- push 's' into the top of the stack for i=stack.n-1, 1, -1 do if strlen(stack[i]) > strlen(stack[i+1]) then break end stack[i] = stack[i]..tremove(stack) end end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最終結果を得るには、すべての行を上から下に結合するだけです。

 function toString (stack) for i=stack.n-1, 1, -1 do stack[i] = stack[i]..tremove(stack) end return stack[1] end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

新しいデータ構造を使用して、プログラムを次のように書き換えることができます。

 local s = newBuffer() while 1 do local line = read() if line == nil then break end addString(s, line.."\n") end s = toString(s)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このプログラムは、350Kbファイルの読み取り時間を40秒から0.5秒に短縮しました。 read "* all"を呼び出すと、0.02秒で同じように高速になります。

説明

素朴なアプローチをとると何が起こるかを理解するために、読書プロセスの最中にいると仮定します。 buffにはすでに50 KBの行が含まれており、各行のサイズは20バイトです。 連結操作後

 buff = buff..line.."\n"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

buff変数にはすでに50,020バイトが含まれており、古い行はゴミになっています。 ループを2回繰り返した後、buffにはすでに50,040バイトが含まれており、すでに2行で100Kbを超えるガベージが形成されています。 したがって、Luaはガベージコレクターを起動する時間であると非常に正しく判断し、これらの100 KBを解放します。 問題は、これが2回の反復ごとに発生し、Luaがループが終了する前にガベージコレクターを2000回実行することです。 これらすべてのアクションを使用しても、メモリ消費量はファイルサイズの3倍になります。 さらに悪いことに、各連結では、行全体（50KB以上）の内容を新しい行にコピーする必要があります。



この問題はLuaだけではありません。実際のガベージコレクターを備えた他の言語で、文字列が変更不可能なオブジェクトである場合も同様に動作します（最も有名なのはJavaです）。



最初のサイクルでは、問題に対して「線形」アプローチを使用し、小さな線を次々に組み合わせてバッテリー変数にしました。 新しいアルゴリズムは、バイナリアプローチを使用してこれを回避します。 多くの小さな線を互いに結合し、結果の大きな線を他の大きな線と結合することもあります。

PS

例はかなり古いバージョンのLuaで提供されていますが、アルゴリズムの意味が十分に明確であるため、I（Xitsa）はそれらを変更しませんでした。