会社で初めてやったテクノロジーの共有
12125 ワード
林洪涛(林洪涛)11:09:06
今日の朝礼のテーマ:
n種類の経験石があって、経験値はそれぞれexp[i]、各経験石の個数はcount[i]で、今目標の経験値はvalueで、求めます:各種の経験石の個数、超えた部分の最小化を保証します.(i=0からn-1)
本題は多重リュックサックで拡張されたテーマです.参考資料『リュック九講』.
まず0-1リュックタイプを見てみましょう
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.リュックサックにどのアイテムを入れるかを解くと、価値の合計が最大になります.
プロセスZeroOnePackは、01リュックの中の物品を処理することを示し、2つのパラメータcost、weightはそれぞれこの物品の費用と価値を示している.
疑似コード:
procedureZeroOnePack(cost,weight)
forv=V..cost
f[v]=max{f[v],f[v-cost]+weight}
このプロセスの処理は、前に与えられた擬似コードとは異なることに注意してください.前の例のプログラムはv=Vと書きます..0は,プログラム内で各状態を方程式に従って解き,不要な思考の複雑さを避けるためである.ここではブラックボックスと見なす過程が抽象化されている以上,最適化を加えることができる.費用がcostのものは状態f[0.cost-1]に影響しないことは明らかである.このプロセスがあれば、01リュックの問題の偽コードはこのように書くことができます.
fori=1..N
ZeroOnePack(c[i],w[i]);
C++コード:
for(i=1;i<=v; i++) f[i] = 0;
for(i= 0; i
for(int j=v; j>=C[i]; j--)
f[j]= max( f[j], f[j – C[i]] +W[j] );
例:もし価値があるならば3元、4元、5元、6元、7元の硬貨はそれぞれ1枚、最も少ない硬貨は価値の20元の物品を払って、方案を求めて表(添付ファイル)を見ます
またテーマに戻り、
先に原題N=4種類の経験石を簡略化して、それぞれの経験石の1つCount[i→0~N-1]=1、それぞれの経験石の価値Exp=[i]=6、4、10、8、目標の経験値Value=19、求めます:各種の経験石の個数、部分を超えて経験石の組み合わせの方案を最小化することを保証します
解決策:同上(パスを記録すればOK).
原題を見てみましょう.
まず原題N=4種類の経験石を簡略化し、各経験石は1つのCount[i]=3、2、1、4、各経験石の価値Exp=[i]=6、4、10、8、目標経験値Value=19、求める:各種経験石の個数、部分を超えて経験石を求める組み合わせ案を最小化することを保証する.
テーマ転化:N=10種類の経験石、それぞれの経験石は1つのN[i]=1、それぞれの経験石の価値Exp=[i]=6、6、4、4、10、8、8、8、8、8、8、8、8、8、8、8、8、8、求めます:各種の経験石の個数、部分を超えて経験石の組み合わせ案を最小化することを保証します.
解決策:同上(パスを記録すればOK).
--------------------------------------------------------------------------------
今日はgbを紹介するだけですtreeの拡張使用は,複雑なバランスアルゴリズムの説明には関与していない.
需要、プレイヤーは公会のリストを取得して、1万以上のレベルのリストを維持して、リアルタイムの挿入とクエリーの時間が最も速いことを要求します.具体的な需要:100000回の挿入、毎回1本のデータ(K-V)を挿入して、1000回のクエリー、毎回Kより小さいあるいは大きい連続の20本のデータを検索します.最後に実現する性能Q×(LgN+M)、Nはデータ総量(100000)、Qはクエリー回数(1000)、Mは何個のデータ(20)
解析:リスト長100000、リアルタイムの通常の順序
削除操作:二分で位置を見つけて、直接削除して、順序を維持しないでください
検索操作:二分で位置を見つけ、データを読み出し、順序を維持しない
挿入操作:二分で位置を見つけて、直接挿入して、順序を維持する必要があります
更新操作:二分で位置を見つけて、直接修正して、順序を維持する必要があります
需要を得るには、操作の挿入と更新が難解であり、操作が終了すると、リストの順序をリアルタイムで維持する必要があります.サービス側が圧力に耐えられることを保証するには、クライアントが迅速に応答することができます.
Erlangのgbについてtreeの使い方紹介:
http://www.cnblogs.com/me-sa/archive/2012/06/23/erlang-gb_trees.html
控訴問題を解決するにはgbを使用することができます.treeデータ構造は、バランスアルゴリズムについて説明します.
赤黒樹バランスアルゴリズム(ネット上のほとんどのブログは「アルゴリズム導論」の翻訳を抜粋している)
http://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html
http://blog.chinaunix.net/uid-26575352-id-3061918.html
先人の肩に立って世界を見ると、下層部が複雑なアルゴリズム論理コードをカプセル化しているのがメリットです.
予備知識:
gb_treeのモデル:{Key,Value,Smaller,Bigger}
Smallerは左の木です
Biggerは右の木です
法則:LeftChildKey>FatherKey>RightChildKey
11
/ \
6 16
/ \ / \
3 8 13 18
/\ /\ /\ /\
1 4 7 9 12 14 17 19
/\/\/\/\/\/\/\/\
nil......nil......nil........nil.........nil.........nil....
質問1:任意のKeyを与え、Keyより大きい値または等しい値を最初に見つけます.
図:クエリー10
クエリーパス:11→6→8→9→nil
nilにクエリされると、遡及時に表示される最初のキーより大きい値が必要な値になります.答え:11
質問2:任意のKeyを与え、Key以下の最初の値を見つけます.
図:11.5を検索するとします.
クエリーパス:11→16→13→12→nil
nilにクエリされると、遡及時に表示される最初のKey未満の値が必要な値になります.答え:11
質問3:いずれかのキーを与え、キー(等しければキーを含む)より大きいM個の数値を求める
図:11.5より大きい5つの数をクエリーするとします.
第一歩:走り問題1見つけて12
第2歩:遡及遍歴中序を開始し、カウンタCount=5を使用して遡及境界を制御する
質問4:いずれかのキーを与え、キー(等しい場合はキーを含む)より小さいM個の数値を求める
図:11.5より小さい5つの数をクエリーするとします.
第一歩:走り問題2見つけ11
ステップ2:遡及ループ(中系列の逆系列)を開始し、カウンタCount=5を使用して遡及境界を制御します.
このとき、第2ステップの操作に問題が発生しました...?見つけなきゃ
9→8→7→6シーケンス
マイソリューション:ツリーの回転モデルを作成する
11
/\
6 16
/\/\
3 8 13 18
/\/\/\/\
1 4 7 9 12 14 17 19
/\/\/\/\/\/\/\/\
nil......nil......nil........nil.........nil.........nil....
ステップ1:11の左の子を見つけました
6
/\
3 8
//=>6の左右の子供を1回回転させる
1 4 7 9
/\/\/\/\
nil......nil......nil........
6
/\
8 3
//=>8、3くらいの子供を1回回転させる
7 9 1 4
/\/\/\/\
nil......nil......nil........
6
/\
8 3
//回転した結果、この時点で法則が出てきて、
9 7 4 1
/\/\/\/\
nil......nil......nil........
回転ツリー:
11
/\
6 16
/\/\
8 3 13 18
/\/\/\/\
9 7 4 1 12 14 17 19
/\/\/\/\/\/\/\/\
nil......nil......nil........nil.........nil.........nil....
質問に戻ります:私たちが探しているのは9→8→7→6というシーケンスです.
回転プロセスは、エッジ遡及、エッジ回転であり、水平アルゴリズム挿入操作に似ています.
栄兄の考え:
回転モデルの代わりに反復器を用いたが,性能はO(1)ではなく,同じデータを走るたびに少し時間がかかることがわかる.
iterator=[サブツリーリスト]では、サブツリー(ツリーが単一ノードである可能性があります)を1つ取り出すたびに、サブツリーを1回分解する必要がある場合があります(完全に分解するわけではありません).時間はサブツリーの高さに依存します
理論が終わったら、コードを見てみましょう...
昨日、1万以上のレベルのリストを維持するために、リアルタイムの挿入とクエリーの時間を最も速くする必要がありました.
具体的な需要:100000回の挿入、毎回1本のデータ(K-V)、1000回のクエリー、毎回Kより小さい連続20本のデータをクエリーします.
需要を得るにはまずgbを思い浮かべるtree、でもgbをひっくり返してtreeのソースコードは、直接使用できる言い訳が見つからず、自分でシミュレーションしました.
インターフェースが出ます.最後に実現した性能LgN+Q*M,Nはデータ総量(100000),Qはクエリー回数(1000),Mは何個のデータ(20)であるか
Erlangコード実装
テストコード
Result:
Start.... R3 : 5014, Result: {0, [{5545,5545}, {5544,5544}, {5543,5543}, {5542,5542}, {5541,5541}, {5540,5540}, {5539,5539}, {5538,5538}, {5537,5537}, {5536,5536}, {5535,5535}, {5534,5534}, {5533,5533}, {5532,5532}, {5531,5531}, {5530,5530}, {5529,5529}, {5528,5528}, {5527,5527}, {5526,5526}]}
今日の朝礼のテーマ:
n種類の経験石があって、経験値はそれぞれexp[i]、各経験石の個数はcount[i]で、今目標の経験値はvalueで、求めます:各種の経験石の個数、超えた部分の最小化を保証します.(i=0からn-1)
本題は多重リュックサックで拡張されたテーマです.参考資料『リュック九講』.
まず0-1リュックタイプを見てみましょう
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.リュックサックにどのアイテムを入れるかを解くと、価値の合計が最大になります.
プロセスZeroOnePackは、01リュックの中の物品を処理することを示し、2つのパラメータcost、weightはそれぞれこの物品の費用と価値を示している.
疑似コード:
procedureZeroOnePack(cost,weight)
forv=V..cost
f[v]=max{f[v],f[v-cost]+weight}
このプロセスの処理は、前に与えられた擬似コードとは異なることに注意してください.前の例のプログラムはv=Vと書きます..0は,プログラム内で各状態を方程式に従って解き,不要な思考の複雑さを避けるためである.ここではブラックボックスと見なす過程が抽象化されている以上,最適化を加えることができる.費用がcostのものは状態f[0.cost-1]に影響しないことは明らかである.このプロセスがあれば、01リュックの問題の偽コードはこのように書くことができます.
fori=1..N
ZeroOnePack(c[i],w[i]);
C++コード:
for(i=1;i<=v; i++) f[i] = 0;
for(i= 0; i
for(int j=v; j>=C[i]; j--)
f[j]= max( f[j], f[j – C[i]] +W[j] );
例:もし価値があるならば3元、4元、5元、6元、7元の硬貨はそれぞれ1枚、最も少ない硬貨は価値の20元の物品を払って、方案を求めて表(添付ファイル)を見ます
またテーマに戻り、
先に原題N=4種類の経験石を簡略化して、それぞれの経験石の1つCount[i→0~N-1]=1、それぞれの経験石の価値Exp=[i]=6、4、10、8、目標の経験値Value=19、求めます:各種の経験石の個数、部分を超えて経験石の組み合わせの方案を最小化することを保証します
解決策:同上(パスを記録すればOK).
原題を見てみましょう.
まず原題N=4種類の経験石を簡略化し、各経験石は1つのCount[i]=3、2、1、4、各経験石の価値Exp=[i]=6、4、10、8、目標経験値Value=19、求める:各種経験石の個数、部分を超えて経験石を求める組み合わせ案を最小化することを保証する.
テーマ転化:N=10種類の経験石、それぞれの経験石は1つのN[i]=1、それぞれの経験石の価値Exp=[i]=6、6、4、4、10、8、8、8、8、8、8、8、8、8、8、8、8、8、求めます:各種の経験石の個数、部分を超えて経験石の組み合わせ案を最小化することを保証します.
解決策:同上(パスを記録すればOK).
--------------------------------------------------------------------------------
今日はgbを紹介するだけですtreeの拡張使用は,複雑なバランスアルゴリズムの説明には関与していない.
需要、プレイヤーは公会のリストを取得して、1万以上のレベルのリストを維持して、リアルタイムの挿入とクエリーの時間が最も速いことを要求します.具体的な需要:100000回の挿入、毎回1本のデータ(K-V)を挿入して、1000回のクエリー、毎回Kより小さいあるいは大きい連続の20本のデータを検索します.最後に実現する性能Q×(LgN+M)、Nはデータ総量(100000)、Qはクエリー回数(1000)、Mは何個のデータ(20)
解析:リスト長100000、リアルタイムの通常の順序
削除操作:二分で位置を見つけて、直接削除して、順序を維持しないでください
検索操作:二分で位置を見つけ、データを読み出し、順序を維持しない
挿入操作:二分で位置を見つけて、直接挿入して、順序を維持する必要があります
更新操作:二分で位置を見つけて、直接修正して、順序を維持する必要があります
需要を得るには、操作の挿入と更新が難解であり、操作が終了すると、リストの順序をリアルタイムで維持する必要があります.サービス側が圧力に耐えられることを保証するには、クライアントが迅速に応答することができます.
Erlangのgbについてtreeの使い方紹介:
http://www.cnblogs.com/me-sa/archive/2012/06/23/erlang-gb_trees.html
控訴問題を解決するにはgbを使用することができます.treeデータ構造は、バランスアルゴリズムについて説明します.
赤黒樹バランスアルゴリズム(ネット上のほとんどのブログは「アルゴリズム導論」の翻訳を抜粋している)
http://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html
http://blog.chinaunix.net/uid-26575352-id-3061918.html
先人の肩に立って世界を見ると、下層部が複雑なアルゴリズム論理コードをカプセル化しているのがメリットです.
予備知識:
gb_treeのモデル:{Key,Value,Smaller,Bigger}
Smallerは左の木です
Biggerは右の木です
法則:LeftChildKey>FatherKey>RightChildKey
11
/ \
6 16
/ \ / \
3 8 13 18
/\ /\ /\ /\
1 4 7 9 12 14 17 19
/\/\/\/\/\/\/\/\
nil......nil......nil........nil.........nil.........nil....
質問1:任意のKeyを与え、Keyより大きい値または等しい値を最初に見つけます.
図:クエリー10
クエリーパス:11→6→8→9→nil
nilにクエリされると、遡及時に表示される最初のキーより大きい値が必要な値になります.答え:11
質問2:任意のKeyを与え、Key以下の最初の値を見つけます.
図:11.5を検索するとします.
クエリーパス:11→16→13→12→nil
nilにクエリされると、遡及時に表示される最初のKey未満の値が必要な値になります.答え:11
質問3:いずれかのキーを与え、キー(等しければキーを含む)より大きいM個の数値を求める
図:11.5より大きい5つの数をクエリーするとします.
第一歩:走り問題1見つけて12
第2歩:遡及遍歴中序を開始し、カウンタCount=5を使用して遡及境界を制御する
質問4:いずれかのキーを与え、キー(等しい場合はキーを含む)より小さいM個の数値を求める
図:11.5より小さい5つの数をクエリーするとします.
第一歩:走り問題2見つけ11
ステップ2:遡及ループ(中系列の逆系列)を開始し、カウンタCount=5を使用して遡及境界を制御します.
このとき、第2ステップの操作に問題が発生しました...?見つけなきゃ
9→8→7→6シーケンス
マイソリューション:ツリーの回転モデルを作成する
11
/\
6 16
/\/\
3 8 13 18
/\/\/\/\
1 4 7 9 12 14 17 19
/\/\/\/\/\/\/\/\
nil......nil......nil........nil.........nil.........nil....
ステップ1:11の左の子を見つけました
6
/\
3 8
//=>6の左右の子供を1回回転させる
1 4 7 9
/\/\/\/\
nil......nil......nil........
6
/\
8 3
//=>8、3くらいの子供を1回回転させる
7 9 1 4
/\/\/\/\
nil......nil......nil........
6
/\
8 3
//回転した結果、この時点で法則が出てきて、
9 7 4 1
/\/\/\/\
nil......nil......nil........
回転ツリー:
11
/\
6 16
/\/\
8 3 13 18
/\/\/\/\
9 7 4 1 12 14 17 19
/\/\/\/\/\/\/\/\
nil......nil......nil........nil.........nil.........nil....
質問に戻ります:私たちが探しているのは9→8→7→6というシーケンスです.
回転プロセスは、エッジ遡及、エッジ回転であり、水平アルゴリズム挿入操作に似ています.
栄兄の考え:
回転モデルの代わりに反復器を用いたが,性能はO(1)ではなく,同じデータを走るたびに少し時間がかかることがわかる.
iterator=[サブツリーリスト]では、サブツリー(ツリーが単一ノードである可能性があります)を1つ取り出すたびに、サブツリーを1回分解する必要がある場合があります(完全に分解するわけではありません).時間はサブツリーの高さに依存します
理論が終わったら、コードを見てみましょう...
昨日、1万以上のレベルのリストを維持するために、リアルタイムの挿入とクエリーの時間を最も速くする必要がありました.
具体的な需要:100000回の挿入、毎回1本のデータ(K-V)、1000回のクエリー、毎回Kより小さい連続20本のデータをクエリーします.
需要を得るにはまずgbを思い浮かべるtree、でもgbをひっくり返してtreeのソースコードは、直接使用できる言い訳が見つからず、自分でシミュレーションしました.
インターフェースが出ます.最後に実現した性能LgN+Q*M,Nはデータ総量(100000),Qはクエリー回数(1000),Mは何個のデータ(20)であるか
Erlangコード実装
-module(tree_misc).
-export([
make_empty_tree/0,
insert/2,
delete/2,
lookup/2,
update/3,
lookup_smaller_key/2,
lookup_bigger_key/2,
lookup_smaller_n/3,
lookup_bigger_n/3
%iterator_find_multi_with_key/3
]).
make_empty_tree() ->
gb_trees:from_orddict([]).
insert({Key, Value}, Tree) ->
gb_trees:insert(Key, Value, Tree);
insert([{Key, Value} | List], Tree) ->
NTree = gb_trees:insert(Key, Value, Tree),
insert(List, NTree);
insert([], Tree) ->
Tree.
delete(Key, Tree) ->
gb_trees:delete(Key, Tree).
lookup(Key, Tree) ->
gb_trees:lookup(Key, Tree).
update(Key, Value, Tree) ->
gb_trees:update(Key, Value, Tree).
%--------------------------------------------
%% > =:= Key Key
lookup_bigger_key(Key, {_, T} = _Tree) ->
lookup_bigger_key1(Key, T).
lookup_bigger_key1(Key, {Key1, _Value1, Smaller, _Bigger}) when Key < Key1 ->
case lookup_bigger_key1(Key, Smaller) of
none ->
Key1;
Other ->
Other
end;
lookup_bigger_key1(Key, {Key1, _Value1, _Smaller, _Bigger}) when Key =:= Key1 ->
Key;
lookup_bigger_key1(Key, {Key1, _Value1, _Smaller, Bigger}) when Key > Key1 ->
lookup_bigger_key1(Key, Bigger);
lookup_bigger_key1(_, nil) ->
none.
%% Key Num ， [{K1, V1}, {K2, V2} ...Num ...]
lookup_bigger_n(Num, Key, {_, T} = _Tree) ->
lookup_bigger_n1(Num, Key, T).
lookup_bigger_n1(Num, Key, {Key1, Value1, Smaller, Bigger}) when Key < Key1 ->
case lookup_bigger_n1(Num, Key, Smaller) of
none ->
%% ，
traverse_tree_right(Num-1, Bigger, [{Key1, Value1}]);
{NNum, List} ->
if
NNum > 0 ->
traverse_tree_right(NNum-1, Bigger, [{Key1, Value1} | List]);
true ->
{0, List}
end
end;
lookup_bigger_n1(Num, Key, {Key1, Value1, _Smaller, Bigger}) when Key =:= Key1 ->
%%
traverse_tree_right(Num-1, Bigger, [{Key1, Value1}]);
lookup_bigger_n1(Num, Key, {Key1, _Value1, _Smaller, Bigger}) when Key > Key1 ->
lookup_bigger_n1(Num, Key, Bigger);
lookup_bigger_n1(_, _, nil) ->
none.
%%
traverse_tree_right(Num, {Key, Value, Smaller, Bigger}, List) ->
if
Num =< 0 ->
{0, List};
true ->
{NNum, NList} = traverse_tree_right(Num, Smaller, List),
if
NNum =< 0 ->
{0, NList};
true ->
traverse_tree_right(NNum-1, Bigger, [{Key, Value}|NList])
end
end;
traverse_tree_right(0, _, List) ->
{0, List};
traverse_tree_right(Num, nil, List) ->
{Num, List}.
% -----------------------------------------------------------------------------------
%% < =:= Key Key
lookup_smaller_key(Key, {_, T} = _Tree) ->
lookup_smaller_key1(Key, T).
lookup_smaller_key1(Key, {Key1, _Value1, Smaller, _Bigger}) when Key < Key1 ->
lookup_smaller_key1(Key, Smaller);
lookup_smaller_key1(Key, {Key1, _Value1, _Smaller, _Bigger}) when Key =:= Key1 ->
Key;
lookup_smaller_key1(Key, {Key1, Value1, Smaller, Bigger}) when Key > Key1 ->
case lookup_smaller_key1(Key, Bigger) of
none ->
{{Key1, Value1}, Smaller};
Other ->
Other
end;
lookup_smaller_key1(_, nil) ->
none.
% Key Num ， [{K1, V1}, {K2, V2} ...Num ...]
lookup_smaller_n(Num, Key, {_, T}) ->
{_, ResultList} = lookup_smaller_n1(Num, Key, T),
ResultList.
lookup_smaller_n1(Num, Key, {Key1, _Value1, Smaller, _Bigger}) when Key < Key1 ->
lookup_smaller_n1(Num, Key, Smaller);
lookup_smaller_n1(Num, Key, {Key1, Value1, Smaller, _Bigger}) when Key =:= Key1 ->
%%
traverse_tree_left(Num-1, Smaller, [{Key1, Value1}]);
lookup_smaller_n1(Num, Key, {Key1, Value1, Smaller, Bigger}) when Key > Key1 ->
case lookup_smaller_n1(Num, Key, Bigger) of
none ->
%%
%% {{Key1, Value1}, Smaller};
traverse_tree_left(Num-1, Smaller, [{Key1, Value1}]);
{NNum, List} -> %% ，
if
NNum > 0 ->
traverse_tree_left(NNum-1, Smaller, [{Key1, Value1} | List]);
true ->
{0, List}
end
end;
lookup_smaller_n1(_, _, nil) ->
none.
%%
traverse_tree_left(Num, {Key, Value, Smaller, Bigger}, List) ->
if
Num =< 0 ->
{0, List};
true ->
{NNum, NList} = traverse_tree_left(Num, Bigger, List),
if
NNum =< 0 ->
{0, NList};
true ->
traverse_tree_left(NNum-1, Smaller, [{Key, Value}|NList])
end
end;
traverse_tree_left(0, _, List) ->
{0, List};
traverse_tree_left(Num, nil, List) ->
{Num, List}.テストコード
test() ->
Tree = tree_misc:make_empty_tree(),
F1 = fun() ->
lists:foldl(fun(X, Acc) ->
[{X, X} | Acc]
end, [], lists:seq(1, 10000))
end,
{R1, List} = timer:tc(F1),
io:format("R1 : ~p ~n", [R1]),
F2 = fun() ->
lists:foldl(fun({K, V}, OldTree)->
gb_trees:insert(K, V, OldTree)
end, Tree, List)
end,
{R2, NTree} = timer:tc(F2),
io:format("R2 : ~p ~n", [R2]),
RandNumList = hmisc:rand_n(1000, List),
%% io:format("NTree: ~p~n", [NTree]),
io:format("Start....~n"),
F3 = fun() ->
lists:map(fun({Key, _Value}) ->
tree_misc:lookup_bigger_n(20, Key + 0.5, NTree)
%tree_misc:iterator_find_multi_with_key(Key + 0.5, 20, NTree)
end, RandNumList)
end,
{R3, [Result|_]} = timer:tc(F3),
io:format("R3 : ~p, Result: ~p ~n", [R3, Result]).
Result:
Start.... R3 : 5014, Result: {0, [{5545,5545}, {5544,5544}, {5543,5543}, {5542,5542}, {5541,5541}, {5540,5540}, {5539,5539}, {5538,5538}, {5537,5537}, {5536,5536}, {5535,5535}, {5534,5534}, {5533,5533}, {5532,5532}, {5531,5531}, {5530,5530}, {5529,5529}, {5528,5528}, {5527,5527}, {5526,5526}]}