dak ブログ

python、rubyなどのプログラミング、MySQL、サーバーの設定などの備忘録。レゴの写真も。

ruby でのシンプルな連結リストの実装

2021-06-18 20:45:18 | ruby
ruby でシンプルな連結リストを実装し、配列との性能比較を行ったメモ。

データを読み込んで集計処理を行う場合に、配列にデータを格納しますが、
配列が最大サイズに達すると、サイズを拡大して再度データを格納するため、
実行時間が大幅に長くなる場合があります。

そこで、1から1千万の整数を生成して、以下の方法で処理時間を比較してみました。
・方法1: 配列に値を全て格納してから出力
・方法2: 連結リストに値を全て格納し、配列に変換してから出力
 ※連結リストの実装例は最後に記します。

実行結果では、方法2は方法1の約1/2の実行時間でした。
以下、各方法のプログラムと、実行時間です。

■方法1: 配列に値を全て格納してから出力
  num = 10000000

  # データ登録
  arr = Array.new
  1.upto(num) do |i|
    arr.push(i)
  end

  # 表示
  arr.each do |elem|
    printf("%s\n", elem)
  end
実行時間
real    0m36.069s
user    0m35.909s
sys     0m0.156s


■方法2: 連結リストに値を全て格納し、配列に変換してから出力
  num = 10000000

  # データ登録
  require 'list'
  list = List.new
  1.upto(num) do |i|
    list.push(i)
  end

  # リストを配列に変換
  arr = list.to_a()

  # 出力
  arr.each do |elem|
    printf("%s\n", elem)
  end
実行時間
real    0m18.227s
user    0m17.907s
sys     0m0.316s


■連結リストの実装例
データを逐次追加するのが主要な使い方のため、連結リストの末尾に値を追加する push と、
連結リストを配列に変換する to_a のみを実装。
class List
  class Cell
    attr_accessor :val
    attr_accessor :next

    def initialize(val = nil)
      @val = val
      @next = nil
    end
  end

  def initialize()
    @num = 0
    @head = nil
    @tail = @head
  end

  def push(val)
    if @head.nil?
      @tail = @head = Cell.new(val)
    else
      @tail.next = Cell.new(val)
      @tail = @tail.next
    end

    @num += 1
  end

  def to_a()
    arr = Array.new(@num)

    i = 0
    cell = @head
    while cell
      arr[i] = cell.val
      cell = cell.next
      i += 1
    end

    return arr
  end
end


PDF.js でテキストをハイライトする方法

2021-06-12 14:47:51 | javascript
PDF.js で特定の文字列を含むPDF要素をハイライトする方法のメモ。

ここでは、PDF.js と PDF描画用の html ファイルは以下のようなディレクトリに配置しています。
www
├── pdfjs  # pdf.js
│     ├── build
│     ├── LICENSE
│     └── web
│           └── compressed.tracemonkey-pldi-09.pdf  # このPDFを描画
└── test
     └── test_viewer.html  # PDF描画用の html ファイル

PDF から getTextContent() で PDF のテキスト要素を取得して、
テキストが特定の条件を満たす場合(ここでは JavaScript を含む場合)に
ハイライトするようにします。
page.getTextContent().then(function (textContent) {
  ...
  textContent.items.forEach(function (item) {
    if (item['str'].match(/JavaScript/)) {
      ...
    }
  });
);

ハイライトは、PDFのテキスト要素と同じ位置・サイズに半透明の div タグを描画します。
位置、サイズは以下のように設定します。
        var item_left = item['transform'][4];
        var item_top = item['transform'][5];

        var rect = [item_left, item_top,
                    item_left + item['width'], item_top + item['height']];

        var view_rect = viewport.convertToViewportRectangle(rect);
        var abs_width = Math.abs(view_rect[0] - view_rect[2]);
        var abs_height = Math.abs(view_rect[1] - view_rect[3]);
        var abs_left = canvas_left + Math.min(view_rect[0], view_rect[2]);
        var abs_top = canvas_top + Math.min(view_rect[1], view_rect[3]);

また、ハイライト用の div タグを hl_parent に追加しておき、ページ遷移した際には前のページの div タグが残らないように、
hl_parent 内の div タグを削除します。
  while (hl_parent.firstChild) {
    hl_parent.removeChild(hl_parent.firstChild);
  }

全ソースは以下の通り。

<html>
<head>

<title>highlight</title>
</head>
<body>

highlight



<canvas id="the-canvas" style="border: solid;1px;"></canvas>



<button id="prev">Previous</button>
<button id="next">Next</button>
   


Page: /



<script src="/www/pdfjs/build/pdf.js"></script>
<script type="text/javascript">
var url = '/www/pdfjs/web/compressed.tracemonkey-pldi-09.pdf';

var pdfjsLib = window['pdfjs-dist/build/pdf'];

pdfjsLib.GlobalWorkerOptions.workerSrc = '/www/pdfjs/build/pdf.worker.js';

var pdfDoc = null,
pageNum = 1,
pageRendering = false,
pageNumPending = null,
scale = 1.2,
canvas = document.getElementById('the-canvas'),
ctx = canvas.getContext('2d');

// ハイライト表示用のタグ
var hl_parent = document.getElementById('highlight_parent');

// canvas の位置
var canvas_rect = canvas.getBoundingClientRect();

// ページ内の特定テキストをハイライト
function highlightTexts(page) { while (hl_parent.firstChild) { hl_parent.removeChild(hl_parent.firstChild); }
page.getTextContent().then(function (textContent) {
var pageElement = canvas.parentElement;

var viewport = page.getViewport({'scale': scale});

// highlight
textContent.items.forEach(function (item) {
if (item['str'].match(/JavaScript/)) { var item_left = item['transform'][4]; var item_top = item['transform'][5]; var rect = [item_left, item_top, item_left + item['width'], item_top + item['height']]; var view_rect = viewport.convertToViewportRectangle(rect); var abs_width = Math.abs(view_rect[0] - view_rect[2]); var abs_height = Math.abs(view_rect[1] - view_rect[3]); var abs_left = canvas_left + Math.min(view_rect[0], view_rect[2]); var abs_top = canvas_top + Math.min(view_rect[1], view_rect[3]);
var style = 'position: absolute;'
+ ' opacity: 0.50;'
+ ' background-color: yellow;'
+ ' left:' + String(abs_left) + 'px;'
+ ' top:' + String(abs_top) + 'px;'
+ ' width:' + String(abs_width) + 'px;'
+ ' height: ' + String(abs_height) + 'px;';

var e = document.createElement('div');
e.setAttribute('style', style);
hl_parent.appendChild(e);
}
});
});
}

function renderPage(num) {
pageRendering = true;
// Using promise to fetch the page
pdfDoc.getPage(num).then(function(page) {
var viewport = page.getViewport({scale: scale});
canvas.height = viewport.height;
canvas.width = viewport.width;

// Render PDF page into canvas context
var renderContext = {
canvasContext: ctx,
viewport: viewport
};
var renderTask = page.render(renderContext);

// Wait for rendering to finish
renderTask.promise.then(function() {
// highlight
highlightTexts(page);

pageRendering = false;
if (pageNumPending !== null) {
// New page rendering is pending
renderPage(pageNumPending);
pageNumPending = null;
}
});
});

document.getElementById('page_num').textContent = num;
}

function queueRenderPage(num) {
if (pageRendering) {
pageNumPending = num;
} else {
renderPage(num);
}
}

function onPrevPage() {
if (pageNum <= 1) {
return;
}
pageNum--;
queueRenderPage(pageNum);
}
document.getElementById('prev').addEventListener('click', onPrevPage);


function onNextPage() {
if (pageNum >= pdfDoc.numPages) {
return;
}
pageNum++;
queueRenderPage(pageNum);
}
document.getElementById('next').addEventListener('click', onNextPage);

pdfjsLib.getDocument(url).promise.then(function(pdfDoc_) {
pdfDoc = pdfDoc_;
document.getElementById('page_count').textContent = pdfDoc.numPages;

// Initial/first page rendering
renderPage(pageNum);
});
</script>
</body>
</html>