Dart - 探索とソート(Listの線形探索と二分探索、最良ソート(merge sort))

Dart: Up and Running
(O'Reilly Media)
Kathy Walrath Seth Ladd (著)
[Kindle版]
このブログでの感想

開発環境

• OS X Mavericks - Apple (OS)
• Dart Editor (開発環境)
• Dartium | Dart/ Structured web apps (ブラウザ, Dart VM 用 (Chromium with the Dart VM))
• Safari (ブラウザ, JavaScript 用)
• Dart (プログラミング言語)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の11章(探索とソート)、11.7(練習問題)、11-1.をDartで解いてみる。

その他参考書籍

• What is Dart? [Kindle版] (O'Reilly Media) Kathy Walrath Seth Ladd (著) このブログでの感想

11.7(練習問題)、11-1.

コード

sample.dart

import 'dart:html';
import 'dart:math' as math;

void main() {
  InputElement input1 = querySelector('#t0');
  InputElement input2 = querySelector('#t1');
  InputElement run = querySelector('#run_dart');
  InputElement clear = querySelector('#clear');
  Element pre = querySelector('#pre0');
  math.Random random = new math.Random();
  run.onClick.listen((MouseEvent event){
    String result = '${window.navigator.userAgent}\n';
    int n = int.parse(input1.value);
    int m = int.parse(input2.value);
    List<int> sequence = new List.generate(n, (int index) => random.nextInt(n));
    result += '線形探索、二分探索、比率(線形探索/二分探索)\n';
    List temp = new List.generate(m, (int index) => index);
    int start = new DateTime.now().millisecondsSinceEpoch;
    for(var x in temp){
      linearSearch(x, sequence);
    }
    int t1 = new DateTime.now().millisecondsSinceEpoch - start;
    start = new DateTime.now().millisecondsSinceEpoch;
    List<int> sequence1 = mergeSort(sequence);
    for(var x in temp){
      binSearch(x, sequence1);
    }
    int t2 = new DateTime.now().millisecondsSinceEpoch - start;
    result += '$t1, $t2, ${t1 / t2}\n';
    pre.text = result;
  });
  clear.onClick.listen((MouseEvent event) => pre.text = '');
}

int linearSearch(var x, List l){
  int i;
  int max = l.length;
  for (i = 0; i < max; i += 1){
    if (l[i] == x){
      return i;
    }
  }
  return -1;
}

int binSearch(var x, List l){
  int i = 0;
  int j = l.length - 1;
  while (i != j + 1){
    int m = (i + j) ~/ 2;
    if(l[m] < x){
      i = m + 1;
    } else {
      j = m - 1;
    }
  }
  if (0 <= i && i < l.length && l[i] == x){
    return i;
  } else {
    return -1;
  }
}

List mergeSort(List<int> sequence){
  List workspace = [];
  for(int i in new List.generate(sequence.length, (int index) => index)){
    workspace.add([sequence[i]]);
  }
  int i = 0;
  while(i < workspace.length - 1){
    List l1 = workspace[i];
    List l2 = workspace[i + 1];
    List new_l = merge(l1, l2);
    workspace.add(new_l);
    i += 2;
  }
  return workspace.last;
}

List merge(List l1, List l2){
  List new_l = [];
  int i1 = 0;
  int i2 = 0;
  while (i1 != l1.length && i2 != l2.length){
    if(l1[i1] <= l2[i2]){
      new_l.add(l1[i1]);
      i1 += 1;
    } else {
      new_l.add(l2[i2]);
      i2 += 1;
    }
  }
  new_l.addAll(l1.sublist(i1));
  new_l.addAll(l2.sublist(i2));
  return new_l;
}

配列の長さ: 繰り返し回数: