私のコメントで、解析はかなり簡単だと言いました。これがどのように行われるかです。質問にはファイル形式の適切な仕様が欠けているため、次のように仮定します。
ファイルはプロパティで構成され、値は次のとおりです。
document ::= property*
property ::= word "(" value ("," value)* ")"
値は、コンマで区切られた数字を含む二重引用符で囲まれた文字列、または単一の単語です。
value ::= '"' ( word | number ("," number)* ) '"'
スペース、バックスラッシュ、およびコメントは無関係です。
これが可能な実装です。簡単なパーサーの書き方については詳しく説明しません。
package Parser;
use strict; use warnings;
sub parse {
my ($data) = @_;
# perform tokenization
pos($data) = 0;
my $length = length $data;
my @tokens;
while(pos($data) < $length) {
next if $data =~ m{\G\s+}gc
or $data =~ m{\G\\}gc
or $data =~ m{\G/[*].*?[*]/}gc;
if ($data =~ m/\G([",()])/gc) {
push @tokens, [symbol => $1];
} elsif ($data =~ m/\G([0-9]+[.][0-9]+)/gc) {
push @tokens, [number => 0+$1];
} elsif ($data =~ m/\G(\w+)/gc) {
push @tokens, [word => $1];
} else {
die "unreckognized token at:\n", substr $data, pos($data), 10;
}
}
return parse_document(\@tokens);
}
sub token_error {
my ($token, $expected) = @_;
return "Wrong token [@$token] when expecting [@$expected]";
}
sub parse_document {
my ($tokens) = @_;
my @properties;
push @properties, parse_property($tokens) while @$tokens;
return @properties;
}
sub parse_property {
my ($tokens) = @_;
$tokens->[0][0] eq "word"
or die token_error $tokens->[0], ["word"];
my $name = (shift @$tokens)->[1];
$tokens->[0][0] eq "symbol" and $tokens->[0][1] eq '('
or die token_error $tokens->[0], [symbol => '('];
shift @$tokens;
my @vals;
VAL: {
push @vals, parse_value($tokens);
if ($tokens->[0][0] eq 'symbol' and $tokens->[0][1] eq ',') {
shift @$tokens;
redo VAL;
}
}
$tokens->[0][0] eq "symbol" and $tokens->[0][1] eq ')'
or die token_error $tokens->[0], [symbol => ')'];
shift @$tokens;
return [ $name => @vals ];
}
sub parse_value {
my ($tokens) = @_;
$tokens->[0][0] eq "symbol" and $tokens->[0][1] eq '"'
or die token_error $tokens->[0], [symbol => '"'];
shift @$tokens;
my $value;
if ($tokens->[0][0] eq "word") {
$value = (shift @$tokens)->[1];
} else {
my @nums;
NUM: {
$tokens->[0][0] eq 'number'
or die token_error $tokens->[0], ['number'];
push @nums, (shift @$tokens)->[1];
if ($tokens->[0][0] eq 'symbol' and $tokens->[0][1] eq ',') {
shift @$tokens;
redo NUM;
}
}
$value = \@nums;
}
$tokens->[0][0] eq "symbol" and $tokens->[0][1] eq '"'
or die token_error $tokens->[0], [symbol => '"'];
shift @$tokens;
return $value;
}
ここで、 からの出力として次のデータ構造を取得しますParser::parse。
(
["Student_name", "Eric"],
["scoreA", [10, 20, 30, 40]],
["scoreB", [15, 30, 45, 50, 55]],
[
"final",
[12.23, 19, 37.88, 45.98, 60],
[7, 20.11, 24.56, 45.66, 57.88],
[5, 15.78, 22.88, 40.9, 57.99],
[10, 16.87, 26.99, 38.99, 40.66],
],
["Student_name", "Liy"],
["scoreA", [5, 10, 20, 60]],
["scoreB", [25, 30, 40, 55, 60]],
[
"final",
[2.23, 15, 37.88, 45.98, 70],
[10, 28.11, 34.56, 45.66, 57.88],
[8, 19.78, 32.88, 40.9, 57.66],
[10, 27.87, 39.99, 59.99, 78.66],
],
...,
)
次のステップとして、それをネストされたハッシュに変換して、構造を持つようにします。
{
Eric => {
scoreA => [...],
scoreB => [...],
final => [[...], ...],
},
Liy => {...},
...,
}
したがって、この小さなサブルーチンを実行するだけです。
sub properties_to_hash {
my %hash;
while(my $name_prop = shift @_) {
$name_prop->[0] eq 'Student_name' or die "Expected Student_name property";
my $name = $name_prop->[1];
while( @_ and $_[0][0] ne 'Student_name') {
my ($prop, @vals) = @{ shift @_ };
if (@vals > 1) {
$hash{$name}{$prop} = \@vals;
} else {
$hash{$name}{$prop} = $vals[0];
}
}
}
return \%hash;
}
これでメインコードができました
my $data = properties_to_hash(Parser::parse( $file_contents ));
これで、問題のパート 2 であるスコアの計算に進むことができます。つまり、何をする必要があるかを明確にしたら。
編集：双一次補間
fを特定の座標の値を返す関数とします。それらの座標に値がある場合は、それを返すことができます。それ以外の場合は、次の既知の値で双一次補間を実行します。
双一次内挿[ 1 ]の式は次のとおりです。
f(x, y) = 1/( (x_2 - x_1) · (y_2 - y_1) ) · (
f(x_1, y_1) · (x_2 - x) · (y_2 - y)
+ f(x_2, y_1) · (x - x_1) · (y_2 - y)
+ f(x_1, y_2) · (x_2 - x) · (y - y_1)
+ f(x_2, y_2) · (x - x_1) · (y - y_1)
)
ここで、テーブルscoreA内のデータ ポイントの位置を最初の軸に、位置を 2 番目の軸に示します。次のことを行う必要があります。finalscoreA
- 要求された値
x, yが範囲内にあることをアサートする
- 次に小さいポジションと次に大きいポジションをフェッチする
- 補間を実行する
.
sub f {
my ($data, $x, $y) = @_;
# do bounds check:
my ($x_min, $x_max, $y_min, $y_max) = (@{$data->{scoreA}}[0, -1], @{$data->{scoreB}}[0, -1]);
die "indices ($x, $y) out of range ([$x_min, $x_max], [$y_min, $y_max])"
unless $x_min <= $x && $x <= $x_max
&& $y_min <= $y && $y <= $y_max;
ボクシング インデックスを取得するには、x_1, x_2, y_1, y_2考えられるすべてのスコアを反復処理する必要があります。x_i1, x_i2, y_i1, y_i2基になる配列の物理インデックスも覚えておきます。
my ($x_i1, $x_i2, $y_i1, $y_i2);
for ([$data->{scoreA}, \$x_i1, \$x_i2], [$data->{scoreB}, \$y_i1, \$y_i2]) {
my ($scores, $a_i1, $a_i2) = @$_;
for my $i (0 .. $#$scores) {
if ($scores->[$i] <= $x) {
($$a_i1, $$a_i2) = $i == $#$scores ? ($i, $i+1) : ($i-1, $i);
last;
}
}
}
my ($x_1, $x_2) = @{$data->{scoreA}}[$x_i1, $x_i2];
my ($y_1, $y_2) = @{$data->{scoreB}}[$y_i1, $y_i2];
ここで、上記の式による補間を実行できますが、既知のインデックスでの各アクセスは、物理インデックスを介したアクセスに変更できるため、次のようf(x_1, y_2)になります。
$final->[$x_i1][$y_i2]
詳細説明sub f
sub f { ... }fおそらく悪い名前ですが、name でサブを宣言します。bilinear_interpolationより良い名前かもしれません。
my ($data, $x, $y) = @_sub は 3 つの引数を取ると述べています。
$datascoreA、配列参照であるフィールド、scoreBおよびを含むハッシュfinal参照。$xscoreA、補間が必要な軸に沿った位置。$yscoreB、補間が必要な軸に沿った位置。
$x次に、との位置$yが境界内で有効であることをアサートします。の最初の値$data->{scoreA}は最小値です。最大値は最後の位置 (index -1) にあります。両方を一度に取得するには、配列 sliceを使用します。スライスは一度に複数の値にアクセスし、 のようなリストを返します@array[1, 2]。参照を使用する複雑なデータ構造を使用しているため、 で配列を逆参照する必要があり$data->{scoreA}ます。これにより、スライスは のようになります@{$data->{scoreA}}[0, 1]。
$x_minandの値が得られたので、要求された値が最小値/最大値で定義された範囲内に$x_maxない限り、and エラーをスローします。$xこれは、次の場合に当てはまります。
$x_min <= $x && $x <= $x_max
または範囲外の$x場合$yは、実際の範囲を示すエラーをスローします。だからコード
die "indices ($x, $y) out of range ([$x_min, $x_max], [$y_min, $y_max])"
たとえば、次のようなエラーをスローできます
indices (10, 500) out of range ([20, 30], [25, 57]) at script.pl line 42
$xここで、 の値が小さすぎて大きすぎることがわかります$y。
次の問題は、隣接する値を見つけることです。とがscoreA成り立つと仮定すると[1, 2, 3, 4, 5]、 との値を選択したいと思います。しかし、少し後でいくつかの気の利いたトリックを引き出すことができるので、値自体ではなく、隣接する値の位置を覚えておく必要があります。したがって、これは上記の例でandを示します (矢印はゼロベースであることを思い出してください)。$x3.73423
これを行うには、配列のすべてのインデックスをループします。≤ である値を見つけると$x、インデックスを覚えています。たとえば3、 は ≤$xである最初の値なので、インデックス を覚えています2。次に高い値については、少し慎重になる必要があります。明らかに、次のインデックスを取得するだけでよいので、2 + 1 = 3. しかし今、それが であると仮定し$xます5。これは境界チェックに合格します。≤ である最初の値は$xvalue5になるため、 position を覚えることができます4。ただし、 position にはエントリがない5ため、現在のインデックス自体を使用できます。これは後でゼロ除算につながるため、位置3と4(値4と5) を覚えておいたほうがよいでしょう。
コードで表現、つまり
my ($x_i1, $x_i2);
my @scoreA = @{ $data->{scoreA} }; # shortcut to the scoreA entry
for my $i (0 .. $#scores) { # iterate over all indices: `$#arr` is the last idx of @arr
if ($scores[$i] <= $x) { # do this if the current value is ≤ $x
if ($i != $#scores) { # if this isn't the last index
($x_i1, $x_i2) = ($i, $i+1);
} else { # so this is the last index
($x_i1, $x_i2) = ($i-1, $i);
}
last; # break out of the loop
}
}
私の元のコードでは、より複雑なソリューションを選択して、 の隣人を見つけるために同じコードをコピーして貼り付けないようにしています$y。
値も必要なので、インデックスを持つスライスを介して取得します。
my ($x_1, $x_2) = @{$data->{scoreA}}[$x_i1, $x_i2];
$x1, $x_2, $y_1, $y_2これで、双一次補間を実行する四角形を定義するすべての周囲の値が得られました。数式は簡単に Perl に変換できます。正しい演算子 ( *、乗算ではなく·) を選択するだけで、変数の前にドル記号が必要になります。
私が使用した式は再帰的です。 fの定義はそれ自体を参照します。これは、考えて再帰を中断しない限り、無限ループを意味します。fは、特定の位置での値を表します。ほとんどの場合、これは補間を意味します。ただし、$xとがそれぞれ と の値と$y等しい場合、双一次補間は必要なく、エントリを直接返すことができます。scoreAscoreBfinal
これは、$xとの両方$yが配列のメンバーであるかどうかを確認し、早期復帰を行うことで実行できます。$x_1, ..., $y_2または、すべてが配列のメンバーであるという事実を利用できます。補間する必要がないことがわかっている値で再帰する代わりに、配列アクセスを行うだけです。これがインデックスを保存したもの$x_i1, ..., $y_i2です。したがって、元の式が言うところf(x_1, y_1)や類似するところはどこでも、同等のものを書き$data->{final}[$x_i1][$y_i2]ます。