Javascriptを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計
Javascriptでのアルゴリズムの書き方の覚書です。
説明に使用するデータ構造
アルゴリズムの説明のために、以下のようなオブジェクトの配列を使います。
var countries = [];
countries.push( { name: "日本", currency: "JPY", population: 127156000 } );
countries.push( { name: "フランス", currency: "EUR", population: 65073482 } );
countries.push( { name: "スペイン", currency: "EUR", population: 44904000 } );
countries.push( { name: "ロシア", currency: "RUB", population: 141903979 } );
countries.push( { name: "ベトナム", currency: "VND", population: 84238000 } );
countries.push( { name: "カンボジア", currency: "KHR", population: 14805000 } );
countries.push( { name: "コートジボワール", currency: "XOF", population: 44904000 } );
このオブジェクトの配列は、以下のようなコードでブラウザに表示できます。
document.write( "<table border='1'>" );
// テーブルヘッダを出力する。
document.write( "<tr>" );
document.write( "<th>国名</th>" );
document.write( "<th>通貨</th>" );
document.write( "<th>人口</th>" );
document.write( "</tr>" );
// 配列中のオブジェクト毎に以下を繰り返す。
for ( var i = 0; i < countries.length; ++i ) {
var country = countries[i];
// テーブルデータを出力する。
document.write( "<tr>" );
document.write( "<td>" + country["name"] + "</td>" );
document.write( "<td>" + country["currency"] + "</td>" );
document.write( "<td>" + country["population"] + "</td>" );
document.write( "</tr>" );
}
document.write( "</table>" );
このコードの実行結果は以下の通りです。
| 国名 | 通貨 | 人口 |
|---|---|---|
| 日本 | JPY | 127156000 |
| フランス | EUR | 65073482 |
| スペイン | EUR | 44904000 |
| ロシア | RUB | 141903979 |
| ベトナム | VND | 84238000 |
| カンボジア | KHR | 14805000 |
| コートジボワール | XOF | 44904000 |
■抽出
複数のデータの中から、特定の条件を満たすデータを抽出するアルゴリズムです。
例として、商品データproductsから特定の条件を満たすデータを抽出します。
var products = [];
products.push( { product_id: "1010", product_name: "えんぴつ", price: 80 } );
products.push( { product_id: "1020", product_name: "ボールペン", price: 100 } );
products.push( { product_id: "1030", product_name: "消しゴム", price: 100 } );
products.push( { product_id: "2010", product_name: "定規", price: 140 } );
products.push( { product_id: "2020", product_name: "コンパス", price: 300 } );
products.push( { product_id: "3010", product_name: "のり", price: 200 } );
商品データproductsをブラウザに表示すると、以下のようになります。
| 商品ID | 商品名 | 価格 |
|---|---|---|
| 1010 | えんぴつ | 80 |
| 1020 | ボールペン | 100 |
| 1030 | 消しゴム | 100 |
| 2010 | 定規 | 140 |
| 2020 | コンパス | 300 |
| 3010 | のり | 200 |
以下のコードは、商品データproductsから「price > 100」を満たすデータを抽出します。
// 抽出結果を格納する配列
var results = [];
// すべての商品データについて繰り返す。
for ( var i = 0; i < products.length; ++i ) {
var product = products[i];
// 商品データのpriceが100より大きいことを確認する。
if ( product.price > 100 ) {
// 商品データを抽出結果に追加する。
results.push( product );
}
}
抽出結果は、変数resultsに格納されます。抽出結果resultをブラウザに表示すると、以下のようになります。
| 商品ID | 商品名 | 価格 |
|---|---|---|
| 2010 | 定規 | 140 |
| 2020 | コンパス | 300 |
| 3010 | のり | 200 |
■ソート
複数のデータを、特定の条件でソートするアルゴリズムです。
Javascriptでの配列のソート
ソートの例の前に、Javascriptでの配列のソートについて説明します。
配列をソートするには、sort()メソッドを使用します。
var array = [13, 43, 22, 234];
array.sort( function( a, b ) {
// 引数１と引数２はそれぞれ配列中の値。
// 引き算により引数の大小を比較する。
// ・引数２の方が大きければ、戻り値は正の値: 引数２→引数１の順に並ぶ。
// ・引数同士が一致すれば、戻り値は０: 引数１と引数２は同列。
// ・引数１の方が大きければ、戻り値は負の値: 引数１→引数２の順に並ぶ。
return b - a;
} );
ソートの並び順は、sort()メソッドの引数に渡す比較関数で決めます。
比較関数には引数として配列の要素が２つずつ渡されます。引数２→引数１の順に並べたい場合は正の値を、引数１と引数２を同列にしたい場合は０を、引数１→引数２の順に並べたい場合は負の値を、比較関数の戻り値として返します。
なお、上記のコードは配列の要素を「数値の降順」にソートします。
ソートの例(五十音順)
それでは、ソートの例を挙げます。
例として、売上データsalesを特定の項目の「五十音順」にソートします。
var sales = [];
sales.push( { sales_date: "20090702", sales_no: "00001", product_id: "1020", amount: 10 } );
sales.push( { sales_date: "20090702", sales_no: "00002", product_id: "1010", amount: 5 } );
sales.push( { sales_date: "20090702", sales_no: "00003", product_id: "3010", amount: 20 } );
sales.push( { sales_date: "20090703", sales_no: "00001", product_id: "1030", amount: 10 } );
sales.push( { sales_date: "20090703", sales_no: "00002", product_id: "1020", amount: 15 } );
sales.push( { sales_date: "20090704", sales_no: "00001", product_id: "2020", amount: 30 } );
sales.push( { sales_date: "20090704", sales_no: "00002", product_id: "3010", amount: 20 } );
売上データsalesをブラウザに表示すると、以下のようになります。
| 売上日 | 売上番号 | 商品ID | 数量 |
|---|---|---|---|
| 20090702 | 00001 | 1020 | 10 |
| 20090702 | 00002 | 1010 | 5 |
| 20090702 | 00003 | 3010 | 20 |
| 20090703 | 00001 | 1030 | 10 |
| 20090703 | 00002 | 1020 | 15 |
| 20090704 | 00001 | 2020 | 30 |
| 20090704 | 00002 | 3010 | 20 |
以下のコードは、売上データsalesを「五十音順でsales_noの昇順」にソートします。。
sales.sort( function ( sale1, sale2 ) {
// 引数１と引数２はそれぞれ売上データ。
// 売上データからsales_noを取得する。
var sales_no1 = sale1["sales_no"];
var sales_no2 = sale2["sales_no"];
////////////////////////////////////////////
// sales_noを比較する。
////////////////////////////////////////////
if ( sales_no1 === sales_no2 ) {
// sales_noが一致する場合: 引数１と引数２は同列。
return 0;
}
if ( sales_no1 > sales_no2 ) {
// 引数１のsales_noの方が大きい: 引数２→引数１の順に並べる
return 1;
} else {
// 引数１のsales_noの方が小さい: 引数１→引数２の順に並べる
return -1;
}
});
ソート後の売上データsalesをブラウザに表示すると、以下のようになります。
| 売上日 | 売上番号 | 商品ID | 数量 |
|---|---|---|---|
| 20090702 | 00001 | 1020 | 10 |
| 20090703 | 00001 | 1030 | 10 |
| 20090704 | 00001 | 2020 | 30 |
| 20090702 | 00002 | 1010 | 5 |
| 20090703 | 00002 | 1020 | 15 |
| 20090704 | 00002 | 3010 | 20 |
| 20090702 | 00003 | 3010 | 20 |
ソートの例(数値順)
例をもう一つ挙げます。商品データproductsを特定の項目の「数値順」にソートします。
var products = [];
products.push( { product_id: "2010", product_name: "定規", price: 140 } );
products.push( { product_id: "2020", product_name: "コンパス", price: 300 } );
products.push( { product_id: "3010", product_name: "のり", price: 200 } );
products.push( { product_id: "1030", product_name: "消しゴム", price: 100 } );
products.push( { product_id: "1020", product_name: "ボールペン", price: 100 } );
products.push( { product_id: "1010", product_name: "えんぴつ", price: 80 } );
商品データproductsをブラウザに表示すると、以下のようになります。
| 商品ID | 商品名 | 価格 |
|---|---|---|
| 2010 | 定規 | 140 |
| 2020 | コンパス | 300 |
| 3010 | のり | 200 |
| 1030 | 消しゴム | 100 |
| 1020 | ボールペン | 100 |
| 1010 | えんぴつ | 80 |
以下のコードは、商品データproductsを「数値順でproduct_idの降順」にソートします。
products.sort( function ( product1, product2 ) {
// 引数１と引数２はそれぞれ商品データ。
// 商品データのproduct_idを取得する。
var product_id1 = product1["product_id"];
var product_id2 = product2["product_id"];
////////////////////////////////////////////
// product_idを比較する。
////////////////////////////////////////////
// 引き算によりproduct_idの大小を比較する。
// ・引数２のproduct_idの方が大きければ、戻り値は正の値: 引数２→引数１の順に並ぶ。
// ・product_idが一致すれば、戻り値は０: 引数１と引数２の同列。
// ・引数１のproduct_idの方が大きければ、戻り値は負の値: 引数１→引数２の順に並ぶ。
return product_id2 - product_id1;
});
ソート後の商品データproductsをブラウザに表示すると、以下のようになります。
| 商品ID | 商品名 | 価格 |
|---|---|---|
| 3010 | のり | 200 |
| 2020 | コンパス | 300 |
| 2010 | 定規 | 140 |
| 1030 | 消しゴム | 100 |
| 1020 | ボールペン | 100 |
| 1010 | えんぴつ | 80 |
■結合
２種類のデータを、特定の条件で結合するアルゴリズムです。
例として、商品データproductsと売上データsalesを結合します。
var products = ; products.push( { product_id: "1010", product_name: "えんぴつ", price: 80 } ); products.push( { product_id: "1020", product_name: "ボールペン", price: 100 } ); products.push( { product_id: "1030", product_name: "消しゴム", price: 100 } ); products.push( { product_id: "2010", product_name: "定規", price: 140 } ); products.push( { product_id: "2020", product_name: "コンパス", price: 300 } ); products.push( { product_id: "3010", product_name: "のり", price: 200 } ); var sales = ; sales.push( { sales_date: "20090702", sales_no: "00001", product_id: "1020", amount: 10 } ); sales.push( { sales_date: "20090702", sales_no: "00002", product_id: "1010", amount: 5 } ); sales.push( { sales_date: "20090702", sales_no: "00003", product_id: "3010", amount: 20 } ); sales.push( { sales_date: "20090703", sales_no: "00001", product_id: "1030", amount: 10 } ); sales.push( { sales_date: "20090703", sales_no: "00002", product_id: "1020", amount: 15 } ); sales.push( { sales_date: "20090704", sales_no: "00001", product_id: "2020", amount: 30 } ); sales.push( { sales_date: "20090704", sales_no: "00002", product_id: "3010", amount: 20 } );
商品データproductsをブラウザに表示すると以下のようになります。
| 商品ID | 商品名 | 価格 |
|---|---|---|
| 1010 | えんぴつ | 80 |
| 1020 | ボールペン | 100 |
| 1030 | 消しゴム | 100 |
| 2010 | 定規 | 140 |
| 2020 | コンパス | 300 |
| 3010 | のり | 200 |
| 売上日 | 売上番号 | 商品ID | 数量 |
|---|---|---|---|
| 20090702 | 00001 | 1020 | 10 |
| 20090702 | 00002 | 1010 | 5 |
| 20090702 | 00003 | 3010 | 20 |
| 20090703 | 00001 | 1030 | 10 |
| 20090703 | 00002 | 1020 | 15 |
| 20090704 | 00001 | 2020 | 30 |
| 20090704 | 00002 | 3010 | 20 |
以下のコードは、商品データと売上データをproduct_idをキーとして結合します。
/////////////////////////////////////////////////////////////////////////////////
// ハッシュテーブルを作成し、 product_idをキーとして商品データを取得できるようにする。
/////////////////////////////////////////////////////////////////////////////////
// ハッシュテーブル
var hash_table = {};
// すべての商品データについて繰り返す。
for ( var i = 0; i < products.length; ++i ) {
var product = products[i];
// 商品データのproduct_idを取得する。
var key = product["product_id"];
// product_idをキーとして、商品データをハッシュテーブルに格納する。
hash_table[key] = product;
}
/////////////////////////////////////////////////////////////////////////////////
// 売上データと商品データを結合する。
/////////////////////////////////////////////////////////////////////////////////
// すべての売上データについて繰り返す。
for ( var i = 0; i < sales.length; ++i ) {
var sale = sales[i];
// 売上データのproduct_idを取得する。
var product_id = sale["product_id"];
// product_idをキーとして、商品データをハッシュテーブルから取得する。
var product = hash_table[product_id];
if ( product !== undefined ) {
// 商品データを取得できた場合:
// 商品データの値を売上データに格納する。
sale["product_name"] = product["product_name"];
sale["price"] = product["price"];
}
}
結合後の売上データsalsesをブラウザに表示すると、以下のようになります。
| 売上日 | 売上番号 | 商品ID | 商品名 | 数量 | 価格 |
|---|---|---|---|---|---|
| 20090702 | 00001 | 1020 | ボールペン | 10 | 100 |
| 20090702 | 00002 | 1010 | えんぴつ | 5 | 80 |
| 20090702 | 00003 | 3010 | のり | 20 | 200 |
| 20090703 | 00001 | 1030 | 消しゴム | 10 | 100 |
| 20090703 | 00002 | 1020 | ボールペン | 15 | 100 |
| 20090704 | 00001 | 2020 | コンパス | 30 | 300 |
| 20090704 | 00002 | 3010 | のり | 20 | 200 |
■集計
複数のデータを特定の条件で集計するアルゴリズムです。
例として、売上データsalesを集計します。
var sales = [];
sales.push( { sales_date: "20090702", sales_no: "00001", product_name: "ボールペン", price: 100, amount: 10 } );
sales.push( { sales_date: "20090702", sales_no: "00002", product_name: "えんぴつ", price: 80, amount: 5 } );
sales.push( { sales_date: "20090702", sales_no: "00003", product_name: "のり", price: 200, amount: 20 } );
sales.push( { sales_date: "20090703", sales_no: "00001", product_name: "消しゴム", price: 100, amount: 10 } );
sales.push( { sales_date: "20090703", sales_no: "00002", product_name: "ボールペン", price: 100, amount: 15 } );
sales.push( { sales_date: "20090704", sales_no: "00001", product_name: "コンパス", price: 300, amount: 30 } );
sales.push( { sales_date: "20090704", sales_no: "00002", product_name: "のり", price: 200, amount: 20 } );
売上データsalesをブラウザに表示すると以下のようになります。
| 売上日 | 売上番号 | 商品名 | 数量 | 価格 |
|---|---|---|---|---|
| 20090702 | 00001 | ボールペン | 10 | 100 |
| 20090702 | 00002 | えんぴつ | 5 | 80 |
| 20090702 | 00003 | のり | 20 | 200 |
| 20090703 | 00001 | 消しゴム | 10 | 100 |
| 20090703 | 00002 | ボールペン | 15 | 100 |
| 20090704 | 00001 | コンパス | 30 | 300 |
| 20090704 | 00002 | のり | 20 | 200 |
以下のコードは、salesを集計してsales_date毎の合計数量と合計売上高を求めます。
///////////////////////////////////////////////////////
// 集計結果の初期化
///////////////////////////////////////////////////////
// 集計結果を一時的に格納するオブジェクト
var resultsObj = {};
// すべての売上データについて繰り返す。
for ( var i = 0; i < sales.length; ++i ) {
var sale = sales[i];
// 売上データのsales_dateを取得する。
var sales_date = sale["sales_date"];
if ( resultsObj[sales_date] === undefined ) {
// オブジェクトにキーsales_dateが含まれていない:
// 集計結果の初期値を生成する。
var result = { "sales_date": sales_date, "amount": 0, "total": 0 };
// 生成した初期値をキーsales_dateに関連付けてオブジェクトに格納する。
resultsObj[sales_date] = result;
}
}
///////////////////////////////////////////////////////
// salesを集計
///////////////////////////////////////////////////////
// すべての売上データについて繰り返す。
for ( var i = 0; i < sales.length; ++i ) {
var sale = sales[i];
// 売上データのsales_dateを取得する。
var sales_date = sale["sales_date"];
// キーsales_dateに関連付く集計結果をオブジェクトから取得する。
var result = resultsObj[sales_date];
// 売上データのamountを集計結果に足し合わせる。
result["amount"] += sale["amount"];
// 売上データのpriceとamountとを掛けた値を集計結果に足し合わせる。
result["total"] += sale["price"] * sale["amount"];
}
///////////////////////////////////////////////////////
// 集計結果を配列に移し替え
///////////////////////////////////////////////////////
var results = [];
// 一時オブジェクトの全てのキーとデータについて繰り返す。
for ( var sales_date in resultsObj ) {
var result = resultsObj[sales_date];
// データを配列に追加する
results.push( result );
}
集計結果は変数resultsに格納されます。集計結果resultsをブラウザに表示すると以下のようになります。
| 売上日 | 合計数量 | 合計売上高 |
|---|---|---|
| 20090702 | 35 | 5400 |
| 20090703 | 25 | 2500 |
| 20090704 | 50 | 13000 |
データ構造
アルゴリズム
- Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆マップ編)
- Javaを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計 (リスト＆ビーン編)
- PHPを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計
- VBAを使うなら理解しておきたいアルゴリズム - 抽出・結合・集計
- Javascriptを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計
- SQLを使うなら理解しておきたいアルゴリズム？(というか、select文の書き方) - where・order by・join・group by
- Bashを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計
